Sudoku Solver | AI Agent
Every one of us at some point has tried solving a sudoku puzzle in their life. Today, we will discuss ways to teach our system on how to solve it. Interesting ? Let’s do it.
For those who don’t know, sudoku is one of the world’s most popular puzzles. It consists of a 9x9 grid, and the objective is to fill the grid with digits in such a way that each row, each column, and each of the 9 principal 3x3 sub-squares contains all of the digits from 1 to 9.
The problem can be formally set as a classical and well-known concepts of “constraint propagation/satisfaction” and “search” techniques. In this post we will be discussing both naive and efficient approaches. But, first let’s discuss our grid representation.
Grid Representation
Above, shown is a standard sudoku board. This can be represented easily in the form of “string” or “dictionary/map”.
# String representation - showing 45 cell representation (space issue)
board = '53..7....6..195....98....6.8...6...3.4..8.3..1-continued'# Dictionary representation
# Considering Rows to be 1-9 and Columns to be A-Z
board = {"A1":"5","A2":"3",..,"B1":"6","B2":".",..,"I9":"9"}# Helper function - creates dictionary from string representation
def create_dict_representation(board_s, rows, cols):
possible_comb = [r+c for r in rows for c in cols]
board_d = {p:b for b, p in zip(board_s, possible_comb)}
return board_drows = "ABCDEFGHI"
cols = "123456789"create_dict_representation(board, rows, cols)
Till now, we are done with encoding/representation of our playing board.
The first algorithm that we will discuss for sudoku problem solving is called “Elimination Technique”. Formally can be quoted as,
# The starting value for every empty box will thus be
# possibility = '123456789'Initialize all '.' cells with the initial state of "123456789"# sample output after the above step
#{
# 'A1': '123456789',
# 'A2': '123456789',
# 'A3': '3',
# 'A4': '123456789'
# 'A5': '2',
# ...
# 'I9': '123456789'
#}Loop till all cells have possibility of 1 number:
for every cell that has 1 element, find it's peers:
update board by removing that 1 element from it's peers
If you are lucky enough, you will be able to solve your sudoku from the above mentioned technique itself. To make our technique more full proof we will now discuss one more technique which can be applied in a row with the elimination technique and that’s called “Only Choice Technique”. Formally can be quoted as,
# unit - 3x3 grid
for every box in the grid:
if box in unit allows only a certain digit: #by checking it's peers
assign that value to the box#stopping condition
#Make sure that you check when there is no update in the grid
Focus on the highlighted box below, 1 can be put only in one position in the 3x3 unit and which is at A6. Think!
The above 2 techniques are the example of constraint propagation. With the above 2 powerful techniques, you are likely to succeed most of the sudoku challenges but does it actually guarantee a generic solution to all the sudoku in the world ? Well, I have not tested, but still to make it full proof we will try to add some search heuristics on the board that comes after Elimination and Only Choice techniques have been applied.
Although the “search” that we will discuss can be applied to the sudoku straight-away and doesn’t depend on the above 2 constraints, but the branching factor would be very high. i.e 9 — not a good idea. That’s why we first narrow down our search space heavily by constraint propagation and then apply search on top of it in order to be more efficient.
We could start with cells that have more than one possibilities and generate new sudokus considering those possibilities filled in those places and again do constraint propagation individually on those matrices. Let’s see a diagram that explains it better.
In the above figure, we chose the cell that has 2 possible value to get filled with i.e 8,9. Why did we choose this ? Well, there is no science to it. It is a greedy approach we opted for. If we were lucky we could get the solution with minimum possible node expansions. So, after begin chosen a cell, we generate 2 new sudoku with 8 and 9 filled in those positions. Bingo! We again have a matrix on which we can apply constraint propagation (discussed above) to simplify this. And again then expand the matrix with cell having fewer possibilities. Does it sound like recursion to you ? Well, Yes! We recursively traverse the tree in depth-first fashion.
The above proposed approach guarantees to solve any sudoku puzzle in the world. I have tested it with numerous ones. Go on and give it a try.
References:
