This application generates very random 9x9 Intoku 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'.
- Intoku Generator - generates Intoku puzzles and solutions.
- Solution - represents the Intoku grid as either a fully solved or partially solved grid. Contains the logic for validating a Intoku and the internal state for converging towards a completed Intoku solution.
- Position - represents the state of a cell in the Intoku puzzle. It holds possible value states for the constraint propagation logic.
- Puzzle - contains a fully solved Intoku Solution and a partially solved Intoku 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 Intoku generator uses a constraint propagration technique to generate the Intoku puzzles quickly and efficiently. When the algorithm reaches a dead end in the current decision tree path within the Intoku 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 Intoku rules.
A puzzle is generated by first solving a completely blank Intoku 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 Intokus per second on a 2012 MacBook Pro.
For further details on the algorithms to generate the Intoku puzzles, read the Solution.m file and IntokuGenerator.m.
Uniqueness of a partial Intoku 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.