# DESIGN
Authors: Shreya Jain, Cam Dailey, Andrew Cho

In our Sudoku Project, we seek to design and implement a project that can randomly generate a Sudoku puzzle and which can solve a given Sudoku puzzle. In this document, we detail our design via a discussion of pseudocode and data structures for both parts of the project.

## Requirements
Requirements
Invoke Sudoku program from the command line with one command line argument and usage is as follows:

./sudoku create 
./sudoku solve 

*./sudoku create* to create a random Sudoku puzzle
*./sudoku solve* to solve a given Sudoku puzzle

Sudoku creator must satisfy the following requirements:
- Create a puzzle that has a unique solution
- There must be at least 40 missing numbers in the generated puzzle
- The puzzle must be randomized
- The puzzle is printed to stdout

Sudoku solver must satisfy the following requirements:
- Be able to accept puzzles that have multiple solutions
- Generate any one possible solution for the given puzzle
- Must not change any given numbers in the puzzle
- Should read the puzzle from stdin and print the solution to stdout.

## Major Data Structures & Format

### Board Representation Using 1d Array
We want to represent the sudoku puzzle as a 1d array (0~80 values).

Starting with 0 for (row 0; col 0), we will increment the index number by 1 horizontally. This will be the board associated with the index numbers:

   0  1  2  3  4  5  6  7  8
   9 10 11 12 13 14 15 16 17
  18 19 20 21 22 23 24 25 26
  27 28 29 30 31 32 33 34 35
  36 37 38 39 40 41 42 43 44
  45 46 47 48 49 50 51 52 53
  54 55 56 57 58 59 60 61 62
  63 64 65 66 67 68 69 70 71
  72 73 74 75 76 77 78 79 80

Our 9x9 sudoku board will have a total of 9 rows (numbered from 0 to 8) and 9 columns (numbered from 0 to 8)

### Tracker Representation Using 2d Array
Tracker is used to store the values (1~9) used in each row, column, and the sub 3x3 sqaures. It tracks which values has been used in each row, column, and sub 3x3 squares.

To do so, the tracker is a 2d array of integers. The first dimension contains 27 integer arrays. Each of the 27 integer arrays will contains 9 integers. The structure of the tracker is:
* for the first dimension:
* the first 9 arrays (0~8) represents 9 rows
* the second 9 arrays (9~17) represents 9 columns
* the third 9 arrays (18~26) represents 9 3x3 sub squares
* for the second dimension:
* each index of the array represents the values 1~9
* index 0 is value 1, index 1 is value 2, ..., index 8 is value 9
* each index can either be filled with 0s or 1s
* 0 represents unused
* 1 represents used
* Here is an example if the board is filled with 5 in row 0, col 8, sqr 3:
* tracker[0][5 - 1] = 1
* tracker[8 + 9][5 - 1] = 1
* tracker[3 + 9 + 9][5 - 1] = 1

*Note: Tracker is named scoreKeep in sudoku.c*

### Ranking Row Using counters_t
We want to have a priority for this to help with efficiency. To do this, we will instantiate a counters. Each key will represent a column with the item being the count of filled squares. Then we will use counters_iterate to sort the columns by number in decreasing order of number of filled cells into a separate array.

## Pseudocode

### Create
1. Instantiate both board and scoreKeep (tracker). Set everything to 0 in both board on scoreKeep
2. Select two random rows to fill and save it into an integer array
3. run sudokuCreate
4. rank the rows on the generated board
5. run sudokuSolverA
6. randomly generate a number from 40 to 64
7. while there is more values to be removed set by the random number
* randomly generate an index to remove
* remove the index from the board and scoreKeep
* test if there is only one solution by running sudokuSolverForCreator
* if not unique
* set board and scoreKeep to its original value
* if unique
* check whether the while loop is over the time limit
* if yes, run create again
* increment the amount of values removed

#### sudokuCreate
1. while the row on the current index is filled
* get the next row to fill
* if there are no more rows to fill
* return true
* update current index to the 0th column element on the new row
2. update the index to the next unfilled index
3. generate a random number ranging from 1 to 9 and assign it to val
4. while val can be added to the current index
* update row number, column number, and square number to the current index
* set val at the current index of the board and update scoreKeep
* recursively call sudokuCreate
* if sudokuCreate returns true, return true
* else, reset index on the board and scoreKeep to 0
* update val and run the next loop
* return false if no val can be added

#### sudokuSolverA
1. check if the board is completed
* if yes, return true
* if no, continue
2. while the row is filled at the current index
* get the next row to fill from rankedRow
* return true if there are no more rows to check
* update index as the 0th column element on the new row
3. if the value is filled on the current index, move on to the next index until the index is not filled
4. if the new index is larger than the total number of indexes, return false
5. for each val from 1 to 9
* check if val could be inserted into the current index
* if val could be inserted, fill the board with val and update scoreKeep with val
* run sudokuSolver recursively
* if the recursive function returns false, reset the board and scoreKeep to 0 and move to the next loop
* if the recursive function returns true, return true
* if val cannot be inserted, move on to the next loop
6. return false if every val cannot be inserted

#### sudokuSolverForCreator
sudokuSolverForCreator checks whether the board has a unique solution or not. It will return true if not unique, false otherwise. The pseudocode for this function is the same as sudokuSolverA except for one condition. Inside the *check if the board is completed* step, the function returns false when it first reaches that step. If it matches the if statement the second time, it will return true, indicating that the board has more than 1 solution.

sudokuSolverForCreator accepts another parameter that is an integer array which contains one integer. The integer is set to 0 before calling sudokuSolverForCreator. The pseudocode for the changed if-statement is as follows:
1. check if the board is completed
* if yes
* if the integer in the array is a 1, return true
* if not, increment the integer in the array
* return false
* if no, continue

### Solve

1. Instantiate both board and scoreKeep (tracker). Fill the board by reading stdin and appropiately change scoreKeep with the values filled into the board
2. Rank the rows by the number of empty values in each row in descending order. Save the row numbers into an array called rankedRow
3. Run sudokuSolver
4. print the board

#### sudokuSolver
### sudokuSolver
Parameters:
int board[] -> the game board
int rankedRow[] -> a list of the row numbers in order of which row has the most filled values
int scoreKeep[][BOARD_LENGTH] -> stores
int idx -> the index that we want to start solving from
int* numSolutions -> the total number of solutions for this board that have been calculated so far
int solutionBoard[] -> a board that stores a solution
time_t startTime -> the time at which sudokuSolver is first called externally (non-recursively)

*sudokuSolver* is a recursive method that 1. solves a board and 2. calculates the number of possible solutions there are

Because we are backtracking through multiple possible solution arrangements, and the backtracking will be tampering with board, we use solutionBoard to store a solution

pseudocode:
1. if this method has been running for over *SOLVE_TIME_LIMIT* seconds, return false
2. if the board is filled, increment the number of solutions and copy the current board to *solutionBoard*
3. while the row that *idx* is in is filled, move on to the next board. If there is no next board, copy over the current board to the solution board.
4. create a new variable called *newInd*
5. while *newInd* is less than the total number of elements in the board
6. if *newInd* equals 0, break
7. otherwise increment *newInd*
8. loop through the possible values that could be held in each slot (ranges from 1 to 9)
9. if this value is:
- not contained in the row of current index AND
- not contained in the column of current index AND
- not contained in the corresponding 3x3 square
13. then:
14. update the *idx*th index of the board to hold this value
15. update scoreKeep
16. call *sudokuSolver*
17. if *sudokuSolver* returned true, then return true
18. otherwise backtrack (update *scoreKeep* to remove the value we just added to the board and set the index of the board to 0)
19. return false

## User Interface
Usage:

./sudoku create # to create a random Sudoku puzzle
./sudoku solve  # to solve a given Sudoku puzzle

### create
When a user runs *./sudoku create*, the program will print a sudoku board to stdout. The printed grid will meet the following requirements:
- The grid is represented as 9 lines of text
- Each line contains 9 integers that range from 0 to 9, separated by a white space
- 0 represents a missing number in the grid
For example:
5 3 0 0 7 0 0 0 0
6 0 0 1 9 5 0 0 0
0 9 8 0 0 0 0 6 0
8 0 0 0 6 0 0 0 3
4 0 0 8 0 3 0 0 1
7 0 0 0 2 0 0 0 6
0 6 0 0 0 0 2 8 0
0 0 0 4 1 9 0 0 5
0 0 0 0 8 0 0 7 9

### solve
The program expects a grid from stdin. It expects 9 lines from stdin, where each row of the grid is one line from stdin. Each line contains 9 integers that range from 0 to 9 separated by whitespace. 0 represents a missing number in the grid.

If the given sudoku puzzle does not have a solution, the program will print "ERROR: Puzzle not solveable" to stdout. Otherwise, it will print the solution to stdout.

The printed grid will meet the requirements as described above in *create*. However, because this sudoku puzzle will be solved, there will not be any values of 0.

## Inputs and Outputs

### Inputs for Creating Sudoku
* no additional input is needed aside from calling `./sudoku create`

### Outputs from Creating Sudoku
* The puzzle is printed to stdout with the following format:
* The grid is represented as 9 lines of text
* Each line contains 9 integers that range from 0 to 9, separated by a white space
* 0 represents a missing number in the grid

### Inputs for Solving Sudoku
* To solve the sudoku, `./sudoku solve` must read the puzzle from stdin.
* The puzzle must be formatted in the way specified in "Outputs from Creating Sudoku"

### Outputs for Solving Sudoku
* The solved puzzle will be printed in stdout
* the format of the puzzle will follow the format specified in "Outputs from Creating Sudoku" but w/ the solved values

## Functional decomposition into modules

### createBoard
createBoard is called by create() and is used to instantiate scoreKeep (tracker) and the board. Moreover, it will choose two random rows to completely fill. From there, it will call *sudokuCreate* to fill the two randomly selected rows. When the function is finished, it should have completely filled two rows on the board and score the approporiate changes on scoreKeep. The pseudocode is:
1. set board and scoreKeep values to 0
2. randomly select two rows
3. call sudokuCreate

### sudokuCreate
sudokuCreate is called by create() and is used to fill two rows selected by createBoard. It is a recursive method. The pseudocode for this function is provided on the Pseudocode section in DESIGN.md.

### sudokuSolverA
sudokuSolverA is called by create(). sudokuSolverA() completes the board ins a recursive method. The pseudocode for this function is provided on the Pseudocode section in DESIGN.md.

### sudokuSolverForCreator
sudokuSolverForCreator checks whether the board has a unique solution or not. It will return true if not unique, false otherwise. Details on the pseudocode is on the Pseudocode section in DESIGN.md.

### readBoard
readBoard is called by solve() and is used to set the board and scoreKeep accordingly to the sudoku board provided in stdin. The pseudocode is:
1. set scoreKeep values to 0s
2. while there are more numbers to be entered
* set the board and scoreKeep according to the values entered in stdin
* return -1 (to indicate something is wrong) if there are too little or too many integers in stdin

### rowRanker
rowRanker is called by both create() and solve() but is mainly used to solve. rowRanker arranges the rows in descending order by how many filled indexes there are in each each row, meaning rows with less empty values will be prioritized. This method is needed to make the program more efficient. Because we use a back tracing method, we can backtrace less if there are less options to back trace in the beginning of the sequence. rowRanker will save the ranked rows in a integer array. The pseudocode is:

1. create a counter and set int rowSum to 0
2. while the index is less than 81
* if the board value at the index is not 0, increment rowSum by 1
* after every last box in each row, add the row sum to the counter
3. for every row
* add the row to an integer array by calling rowRankerHelper

#### rowRankerHelper
rowRankerHelper is a helper function for rowRanker(). It accepts an integer array, counter, and an integer (which is the row number). With the provided counter (which contains the row number and its rowSum value), it will insert the row number to the integer array while sorting the row numbers through their rowSum values from the counters. The pseudocode is:

1. instantiate a temporary integer, save the row number to rownum, and derive the rowSum value of the provided counter to newRowCount
2. for index 0 to the provided row number
3. if newRowCount is greater than the rowSum value at the current index
4. save the pre-existing row number to temp
5. swap the row number
6. update rownum and newRowCount accordingly
7. set the remainding rownum to the next available index in the integer array

### sudokuSolver
neeeeed~~~~~~~~

### nextRow
nextRow is called within the functions used by both create() and solve(). If provided an integer array of rows, the number of total rows, and the current row, it will return the next row in the array. The pseudocode is:

1. for row number 1 to the provided total number of rows
2. check if the row number is the same as the current row
* if yes, return the next row in the array
* if the current row is the last row in the array, return -1 to indicate the end of the rows

### isRowFilled & isBoardFilled
isRowFilled & isBoardFilled is called throughout multiple methods. isRowFilled is used to check if the row on the current index is full. isBoardFilled is used to check if the board is full.

For isRowFilled, the pseudocode is:
1. set the index at the index of the 0th column on the provided row
2. for every index from the current index to all the indexes on the row
3. check if the board contains a 0
* if yes return false
5. return true

For isBoardFilled, the pseudo code is:
1. for every row number
2. call isRowFilled
3. if any return false, return false
4. return true

### isContain
isContain is called throughout multiple methods. isContain accepts three parameters: value, scoreKeep (tracker), and index number. It checks whether the value can fit into the index using scoreKeep. The pseudocode is:

1. set row, column, and sub-square numbers according to the provided index
2. check if the scorekeep value at each row, column, and sub-square does not contain the provided value
3. if yes, it indicates that the value can be added at the provided index. return false (meaning it is not contained)
4. if no, it indicates that the provided value has already been used in at least once in the row, column, or sub-square. return true (meaning it is already contained)

### printer
printer is used to print the board in the format specified in the Inputs and Outputs section. The pseudocode is:

1. for every index from 0 to 80
* print the value at the index
* move onto the next line if its the last index on the row

### getSquareNumber
getSquareNumber is a mathematical method that returns the square number when provided the row and column numbers. Each square is a 3x3 square within the board. The representation of the board is as follows:

 0 | 1 | 2
 --------
 3 | 4 | 5
 ---------
 6 | 7 | 8

### randomlyGenerateNum
randomlyGenerateNum is a mathematical method that returns a random integer ranging from the provided min and max.

## Testing Plan
### Unit Testing
We also chose to implement unit testing for the lab. The strategy that we followed was testing the different parts of out functions where error cases could occur, such as what functions would return or if values were never instantiated correctly.

We wanted to ensure that each piece of our code was functioning properly and eliminate potential errors that we overlooked which is why we chose to implement unit testing.

### Fuzz Testing
We will use testing.sh to test both `./sudoku create` & `./sudoku solve` and the output will be saved in testing.out

* fuzzsudoku.sh will accept 1 integer parameter (n) that indicates how many tests should be completed
* We will create n sudoku puzzles using `./sudoku create` and will run `./sudoku solve` for each puzzle created
* For each successful creation & solution, we would increment the # of successful operation
* In the end, fuzzsudoku.sh will print "(# of successful operation)" at the last line
* It will also print "(# of unsuccessful operations)" at the last line

### testing.sh
* testing.sh will run a variety of test cases that should create and solve boards
* testing.sh will also run a variety of error cases such as:
* incorrect # of parameters for creating and solving
* incorrect input when running `./sudoku solve`