---
# System prepended metadata

title: Sudoku Design Spec

---

# Sudoku Design Spec
A Sudoku puzzle is a 9x9 grid of cells, furhter divided into 9 3x3 grids.  Numbers 1-9 are placed in empty cells such that each number:

1. Only once in every row
2. Only once in every column
3. Only once in every 3x3 squared region

Sudoku `creator` module creates a 9x9 puzzle with 40 numbers missing such that the puzzle will have a unique solution.  The `solver` module finds a solution of a given puzzle, according to the rules above.


### User Interface
Sudoku's only interface with the user is on the command-line, and there is exactly one command-line for creating and another for solving.

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


### Inputs and Outputs
*Creator*

* Input: No input
* Output: Creator prints a randomized Sudoku board with at least 40 missing numbers that has a unique solution.

*Solver*

* Input: The puzzle board is read from stdin in the form of 81 numbers (entered in lines of 9 at a time, or piped in). Blank spaces in the puzzle are indicated by 0s as placeholders
* Output: If the puzzle is solveable, solver will print the solved puzzle.


### Functional decomposition into modules
We anticipate the following modules or functions:

1. *main*, which validates arguments and calls appropriate `creator` or `solver` module
2. `solver`, which solves an incomplete board using backtracking
3. `creator` which creates a random board using `solver` then removes 40 numbers while preserving a unique solution


### Pseudo code for logic/algorithm flow
*Creator*

1. Generate solved puzzle
    2. Start with an empty board
    3. Choose a random array index from 1-81 and put in a random number from 1-9
    4. Call `solver` to fill the rest of the board
5. Remove 40 zeros preserving uniqueness of solution
    6. While zero-counter is less than 40
        7. Go to a random cell and see how many numbers from 1-9 would be valid, possible entries at that location
            8. If only one possible number
	            9. Insert a zero into that cell
                10. Increase zero-counter by 1
            10. Else, leave cell untouched



*Solver*

1. read the data from stdin and initialize the array
2. solve(list)
	3. for each index 0-80
		4. if that index is 0
			5. for numbers 1-9
				6. if that number is valid (doesn't exist in row, column or box)
					7. add it to the list at the current index
					8. if solve(list)
						9. return true
					10. else
						11. set that index back to 0
			12. return false if looped through 1-9 and no number works
	13. if you've looped through each number and have no zeros, return true
14. if the puzzle is solvable, print it out




### Dataflow through modules



### Testing plan

- unit tests for each funciton
- testing range of valid inputs
- fuzztesting