In this post, I’m going to walk through how to write a sudoku solver using logic and basic python data structures.
This puzzle-solving AI (like many artificial intelligence tasks) doesn’t need a neural network, so I won’t beat this screw with a hammer.
The code referenced in this post can be found at https://github.
com/aaronfrederick/SudokuSolver.
There are 2 nines in the first column…For the uninitiated, the basic rules of sudoku are that in the 9×9 puzzle, a single 1–9 digit is not to be repeated in any row, column, or 3×3 square that makes up the puzzle.
There are some digits already inserted in the puzzle and some blank.
Guessing should not be necessary to complete a puzzle, as incorrect guesses will render a puzzle unsolvable.
Now that we know everything we need to know, let’s get into it!To represent a puzzle in python, I will be creating a list of lists called container, where the larger list will contain 9 sublists (the rows) and the sublists have 9 entries (the entries).
Empty spaces will be represented by 0s and filled in values will be represented by their number.
In sudoku, the rules spell out how to solve the puzzle, so we can start there to make our first attempt at a solver (*foreshadowing alert: there will be more than one).
We will need to write 3 main functions to check what possible values could occupy an empty square:A function to check the row for possible valuesA function to check the column for possible valuesA function to check the square for possible valuessubtract_set = {1,2,3,4,5,6,7,8,9}def check_horizontal(i,j): return subtract_set – set(container[i])def check_vertical(i, j): ret_set = [] for x in range(9): ret_set.
append(container[x][j]) return subtract_set – set(ret_set)def check_square(i, j): first = [0,1,2] second = [3,4,5] third = [6,7,8] find_square = [first, second, third] for l in find_square: if i in l: row = l if j in l: col = l return_set = [] for x in row: for y in col: return_set.
append(container[x][y]) return subtract_set – set(return_set)The functions I just showed use set notation, the logic being that we can obtain the possible values in a row by subtracting the digits currently occupying the row from a master set of digits 1–9.
In plain English, if our row (represented by a list) contains the digits 1, 3, 5, 7, 9, subtracting that set of numbers from 1–9 gives us possible values of 2, 4, 6, and 8.
Our function returns that set, and we can move forward.
Our check_vertical function operates very similarly, but instead of examining the row, it examines the jth element of each row, effectively mimicking a column.
To continue the example, if our column contains 2, 4, and 7, then our function would return a set of 1, 3, 5, 6, 8, 9.
The check_square function is slightly more complicated than the previous two, but the basic logic is that we find which of the 9 3×3 squares our empty square resides in, create a list of the current values in that 3×3 by iterating through its indices, and return 1–9 minus that list.
Wrapping up these functions together in get_poss_values, we can obtain a list of possible values for any given square by taking the intersection of the 3 sets from our functions above:def get_poss_vals(i, j): poss_vals = list(check_square(i, j) .
intersection(check_horizontal(i, j)) .
intersection(check_vertical(i, j))) return poss_valsdef explicit_solver(container): for i in range(9): for j in range(9): if container[i][j] == 0: poss_vals = get_poss_vals(i, j) if len(poss_vals) == 1: container[i][j] = list(poss_vals)[0] print_container(container) return containerThe explicit solver function above iterates through every square and if it is empty (the value is 0), the solver tries to fill it in.
That occurs if there is only 1 possible value based off the functions we previously described.
This explicit method solves easy puzzles very nicely, but misses out on some important information that precludes us from solving more difficult puzzles.
Our explicit solver is a great naive approach, but neglects information gained from surrounding squares.
When we are examining a square that, for example, has possible values of 1, 2, and 3, if each other empty square in the row could only be 1 or 2, then we know that the square we are examining MUST be 3 through process of elimination.
The implicit solver function implements this logic by assembling the possible values of one square and comparing that to the possible values of the rest of the row, column, and 3×3 square.
Below, I have included the entire implicit solver function.
It is a handful of code, as there are three different sections to include the logic mentioned above for the rows, columns, and 3×3 squares.
def implicit_solver(i, j, container): if container[i][j] == 0: poss_vals = get_poss_vals(i, j) #check row row_poss = [] for y in range(9): if y == j: continue if container[i][y] == 0: for val in get_poss_vals(i, y): row_poss.
append(val) if len(set(poss_vals)-set(row_poss)) == 1: container[i][j] = list(set(poss_vals)-set(row_poss))[0] print_container(container) #check column col_poss = [] for x in range(9): if x == i: continue if container[x][j] == 0: for val in get_poss_vals(x, j): col_poss.
append(val) if len(set(poss_vals)-set(col_poss)) == 1: container[i][j] = list(set(poss_vals)-set(col_poss))[0] print_container(container) #check square first = [0, 1, 2] second = [3, 4, 5] third = [6, 7, 8] find_square = [first, second, third] for l in find_square: if i in l: row = l if j in l: col = l square_poss = [] for x in row: for y in col: if container[x][y] == 0: for val in get_poss_vals(x, y): square_poss.
append(val) if len(set(poss_vals)-set(square_poss)) == 1: container[i][j] = list(set(poss_vals)-set(square_poss))[0] print_container(container) return containerUsing the implicit solver in concert with the explicit solver allows us to solve medium and hard puzzles in seconds (and if the print statements are commented out, fractions of a second)!There are more ways to solve this, but sticking to the spirit of sudoku by playing by the rules still leads to a very fast solution.
I welcome any feedback to improving this code and incorporating more methods of solving, please reach out in the comments!.