I love playing Sudoku. It’s just therapeutic to me, but I do get stuck on those harder level Sudoku puzzles that require a trial-and-error approach. I like to mark the possibilities in the corners of a cell, and I run out of space rather quickly on those harder level puzzles.
Anyway, solving the harder level puzzles is not the point of this exercise in writing a Sudoku solver. I just thought it would be fun to write a solver, and more importantly, I wanted to learn more about using Tkinter.
To begin with, here is the Github repository so you can refer to the code:
https://github.com/tanyanghan/sudoku
When you look at a Sudoku grid, the single cell is the most fundamental element. It can hold a number between 1 to 9. I start with defining a class that represents the single cell. In the first commit of sudoku_simply.py, you will see a class definition for the Sudoku_Cell:
# This class defines a single cell on a Sudoku grid
class Sudoku_Cell:
def __init__(self, value=0):
if not value:
self.possible_values = [1,2,3,4,5,6,7,8,9]
self.cells_need_updating = False
else:
self.possible_values = [value]
self.cells_need_updating = True
The class has two data members. The data member possible_values is the list of numbers that the individual cell could contain, and if only one value is left in the list, that value is the final value of the cell.
The other data member cells_need_updating is a Boolean used to indicate if other cells in the row, or column, or 3×3 grid area, needs to be updated when this cell has arrived at its final value. This is important for how the solver works.
Whenever a cell has arrived at its final value, the other cells that are on the same row, or column, or 3×3 grid area, would need to remove this cell’s final value from their list of possible_values. This is achieved by calling the class method remove_possible_value(). The code below is from the initial commit of sudoku_simply.py:
def remove_possible_value(self,value):
if len(self.possible_values) == 1:
# we have already arrived at an answer previously, do nothing
return
try:
self.possible_values.remove(value)
except ValueError:
# value not found, continue
pass
else:
# value removed, check if we have arrived at an answer
if len(self.possible_values) == 1:
# cell value has been determined, flag that we need to update
#other cells
self.cells_need_updating = True
In this method, we do nothing and return if the cell has already arrived at its final value. Otherwise, we try to remove the value that is passed into the method from the list of possible_values. If the value was not in the list of possible_values, we quietly exit the function. If we do succeed in removing the value from the list, we check if we have arrived at the final value, and if so, we set cells_need_updating to True.
The function other_cells_need_updating() is to check if cells_need_updating Boolean is set, and the function get_value() is to read the final value, or return zero if the cell has not arrived at its final value.
With the Sudoku_Cell class more or less defined, we’ll next look at the Sudoku grid as a whole in the next post.