This application generates very random 9x9 Sudoku solutions and puzzles and allows the user to solve the puzzles using a very simple user interface. The UI allows a user to select a cell, enter a valid number between 1-9, and fill in all of the possible values for the grid. The user can click 'Check' to validate the current supplied values against the solution. The user can also change the difficulty level by choosing 'Easy', 'Medium', or 'Hard'. New puzzles can be generated using the 'New' button. Using the 'Solve' or 'Hide' button the user can reveal or hide the solution to a given puzzle.
To Build, load the Project into XCode and click 'Product' -> 'Run'.
XCTest is used for unit tests. To run the tests in XCode, click 'Product' -> 'Test'.
- Sudoku Generator - generates Sudoku puzzles and solutions.
- Solution - represents the Sudoku grid as either a fully solved or partially solved grid. Contains the logic for validating a Sudoku and the internal state for converging towards a completed Sudoku solution.
- Position - represents the state of a cell in the Sudoku puzzle. It holds possible value states for the constraint propagation logic.
- Puzzle - contains a fully solved Sudoku Solution and a partially solved Sudoku solution that is generated based on a difficulty parameter. The game logic compares the fully solved Solution against the player's partially solved grid when validating the grid.
- ViewController - all of the UI logic for managing the game.
- AppDelegate - the iOS application delegate.
- main - bootstrap code.
The Sudoku generator uses a constraint propagration technique to generate the Sudoku puzzles quickly and efficiently. When the algorithm reaches a dead end in the current decision tree path within the Sudoku solution space, the algorithm stores the previous states of the decision tree and uses backtracking to find another path to a full solution.
Randomization is acheived by randomly assigning number to the cells while adhering to the constraints of the Sudoku rules.
A puzzle is generated by first solving a completely blank Sudoku grid, and then randomly removing values from a number of cells in the solved grid to arrive at a partial solution. The number of values removed depends on the difficulty parameter choosen. The higher the difficulty, the more cells that are removed.
The algorithm works fairly fast, generating roughly 25-40 Sudokus per second on a 2012 MacBook Pro.
For further details on the algorithms to generate the Sudoku puzzles, read the Solution.m file and SudokuGenerator.m.
Uniqueness of a partial Sudoku puzzle is not currently checked. This would require an exhaustive search of the entire decision tree of a partial solution to analyze if there are non-unique solutions for a complete grid.