Sudoku like an AI
I am doing the Udacity Artificial Intelligence Nanodegree and one of the first projects is to build an Artificial Intelligence that can solve Sudoku puzzles.
The essential idea is to search the space of possible Sudoku solutions and to constrain the size of this space by propagating the constraints implied by the rules of Sudoku from solved(or close to solved) squares to unsolved squares. The main Sudoku constraints are that every row, column and sub-square has to contain all 9 digits in only one of its boxes.
Concepts
- Box: A single sudoku element, that can contain only one digit.
- Unit: A sudoku unit consists of 9 boxes. In a solved sudoku, each unit contains all the digits 1–9, one per box. A unit can be a row, a column or a sub-square(sometimes diagonals are also considered units)
- Peer: a single box can have peers, a peer being any other box that is in the same unit as the box under consideration.
- Solved block: A block with the correct value filled in.
- Unsolved block: A block for which the correct value has not been determined yet.
Strategies
- Main sequence
Start off assigning all possible values to all unsolved blocks. Apply the strategies Eliminate, Only Choice and, if necessary Naked Twins.
If at this point every block has one value assigned to it, stop as you have found a solution.
If not, and all blocks still have values assigned to them, find an unsolved block with the least amount of possible values assigned to it. For each possible value that can be assigned to this block, make a copy of the sudoku and apply the Main Sequence to it.
If you have any blocks with all possible values eliminated, you have failed to find a solution using this copy of the sudoku and one of your other copies will hold the solution.
- Strategies
- Eliminate: For each solved box, remove the value assigned to it from its peers’ list of possible values list.
- Only choice: Check each box’s possible values list. If a box A has one value X in its list that none of its peers have in their possible values list, then assign X to A which will make it into a solved box.
- Naked Twins: Look for peers that have two (or more) values that are identical. You can now remove the possible values of these Naked Twin boxes from all their peers not in the Naked Twin relationship.
You should now be able to systematically solve most sudoku puzzles out there, like a machine!