This post is an overview of the Sudoku game and Sudoku solver algorithm visualization that I implemented in Python 3.
Introduction
At my job we recently got a project handed to us that is written in Python.
This means there might be some Python programming in my future, so I decided to have a better look at the language.
And after some initial reading and trying things out, I decided to do a small project.
The project is a graphical Sudoku game, which can also visualize a backtracking algorithm that solves the Sudoku puzzle.
And in this post, I will go over most of the source code that is on GitHub.
Gameplan
To start let us define the goals that I set:
- Implement an algorithm that can solve a Sudoku puzzle
- Create a graphical playable Sudoku game
- Visualize how the Sudoku solver algorithm works
To achieve these goals, the steps I took were:
- Implemented a Sudoku solver algorithm
- Implemented a GUI that allows the user to play Sudoku
- Merged the Sudoku solver into the GUI and added the visualization
Sudoku solver algorithm
Concept
The first step was to implement an algorithm that could solve any Sudoku puzzle.
The idea for the algorithm is that we go through the board and try filling empty cells with one of the possible numbers
until we find a combination that correctly solves the board.
Put in a more structured way, we have an algorithm that:
- Finds the next empty cell
- if there is no empty cell, we are done with the puzzle
- Finds a candidate number that is valid in this cell
- if there is no valid number go back to the previous empty cell and try the next candidate number
- Sets the candidate number in the cell
- Continues again with the first step
Implementation
The logic of the algorithm is not that hard, the tricky part is to keep track of the previously visited cells. I decided to use the call stack to keep track of the previous cells. So I implemented a method that gets called recursively. My method gets called for every cell in the board, so the method is split into two logical parts based on the value:
-
The value is already there (there is a value between 1 and 9)
In this case, we simply forward the call and return the result. Or we return True if we are at the last cell -
The value is not there yet (the value is 0)
In this case, we try to find the next candidate number for this cell that is valid. If we find a candidate, we set the number and continue with the next cell. If no number is a candidate, we reset the cell and return False.
The full method to solve the Sudoku looks like:
def solveSudokuHelper(board, rowIdx, columnIdx):
lastColumnIdx = len(board[rowIdx]) - 1
lastRowIdx = len(board) - 1
if board[rowIdx][columnIdx] != 0:
if columnIdx == lastColumnIdx and rowIdx == lastRowIdx:
return True
if columnIdx == lastColumnIdx:
return solveSudokuHelper(board, rowIdx + 1, 0)
else:
return solveSudokuHelper(board, rowIdx, columnIdx + 1)
for candidateNumber in range(1, 10):
if isValid(candidateNumber, rowIdx, columnIdx, board):
board[rowIdx][columnIdx] = candidateNumber
if columnIdx == lastColumnIdx and rowIdx == lastRowIdx:
return True
if columnIdx == lastColumnIdx:
result = solveSudokuHelper(board, rowIdx + 1, 0)
else:
result = solveSudokuHelper(board, rowIdx, columnIdx + 1)
if result:
return True
board[rowIdx][columnIdx] = 0
return False
We can see that it takes three parameters:
- board - the 9x9 matrix that represents the Sudoku puzzle
- rowIdx - the 0-based row index
- columnIdx - the 0-based column index
The indexes tell us at which cell we want to look at in this call, and we are solving the puzzle from left to right and from top to bottom.
So we start the solving by calling solveSudokuHelper(board, 0, 0), which is wrapped in a convenience method.
def solveSudoku(board):
solveSudokuHelper(board, 0, 0)
The second thing that we need is the logic that checks if the candidate number is valid in the current cell.
Sudoku rules say that a number is valid if the same number does not appear in the same row, column, or 3x3 square.
So the method to check validity does exactly that:
def isValid(number, rowIdx, columnIdx, board):
for idx in range(9):
if board[idx][columnIdx] == number and idx != rowIdx:
return False
if board[rowIdx][idx] == number and idx != columnIdx:
return False
squareStartRowIdx = (rowIdx // 3) * 3
squareStartColumnIdx = (columnIdx // 3) * 3
for boardRowIdx in range(squareStartRowIdx, squareStartRowIdx + 3):
for boardColumnIdx in range(squareStartColumnIdx, squareStartColumnIdx + 3):
if boardRowIdx == rowIdx and boardColumnIdx == columnIdx:
continue
if board[boardRowIdx][boardColumnIdx] == number:
return False
return True
The rest of the pydoku.py script creates a board, triggers the solving, and then checks that the result is valid. If we run the script we see that we have a working Sudoku solver algorithm and we can continue with the GUI version.
Sudoku game with a GUI
Next up, I implemented a GUI playable Sudoku puzzle.
For the GUI version, I decided to group things into a class called PydokuGUI.
The class contains:
- the Sudoku board
- methods to handle user input
- methods to draw the Sudoku puzzle onto the screen
- some helper constants that are used (the width, the colors and the cell centers)
The class definition starts with some class constants and the constructor initializes three instance variables. The three variables are the screen on which we draw, the board, and the selected cell.
class PydokuGUI:
# colors that are used
COLOR_BLACK = (0, 0, 0)
COLOR_RED = (255, 0, 0)
COLOR_GREY = (105, 105, 105)
COLOR_WHITE = (255, 255, 255)
COLOR_GREEN = (0, 255, 0)
COLOR_BLUE = (0, 180, 255)
# Static width calculation based on 9 cells, 6 normal lines and 2 thicker lines
WIDTH = 9 * 39 + 6 * 1 + 2 * 3
# Helper array to have access to the center of the cells
cellCenters = [20, 60, 100, 142, 182, 222, 264, 304, 344]
def __init__(self):
self.screen = pygame.display.set_mode((self.WIDTH, self.WIDTH))
pygame.display.set_caption('Pydoku GUI')
self.selectedCell = None
self.board = self.getBoard()
... more methods ...
Since we want to visualize the cells, we need some extra information for each cell, not just the number. To support this I created a second class called PydokuCell:
class PydokuCell:
def __init__(self, number):
self.number = number
self.editable = number == 0
self.valid = True
self.selected = False
The variables should be pretty self-explanatory:
- number - the actual number in this cell
- editable - if the user can alter the number
- valid - if the number in this cell is valid
- selected - if the current cell is selected
This means that the instance variable board in the class SudokuGUI is a matrix of PydokuCell instances. At the moment we only have one Sudoku puzzle hardcoded, but it is abstracted behind the getBoard method, which could be changed and extended in the future.
def getBoard(self):
return [
[
PydokuCell(0), PydokuCell(0), PydokuCell(9),
PydokuCell(2), PydokuCell(1), PydokuCell(8),
PydokuCell(0), PydokuCell(0), PydokuCell(0)
],
[
PydokuCell(1), PydokuCell(7), PydokuCell(0),
PydokuCell(0), PydokuCell(9), PydokuCell(6),
PydokuCell(8), PydokuCell(0), PydokuCell(0)
],
[
PydokuCell(0), PydokuCell(4), PydokuCell(0),
PydokuCell(0), PydokuCell(5), PydokuCell(0),
PydokuCell(0), PydokuCell(0), PydokuCell(6)
],
[
PydokuCell(4), PydokuCell(5), PydokuCell(1),
PydokuCell(0), PydokuCell(6), PydokuCell(0),
PydokuCell(3), PydokuCell(7), PydokuCell(0)
],
[
PydokuCell(0), PydokuCell(0), PydokuCell(0),
PydokuCell(0), PydokuCell(0), PydokuCell(5),
PydokuCell(0), PydokuCell(0), PydokuCell(9)
],
[
PydokuCell(9), PydokuCell(0), PydokuCell(2),
PydokuCell(3), PydokuCell(7), PydokuCell(0),
PydokuCell(5), PydokuCell(0), PydokuCell(0)
],
[
PydokuCell(6), PydokuCell(0), PydokuCell(0),
PydokuCell(5), PydokuCell(0), PydokuCell(1),
PydokuCell(0), PydokuCell(0), PydokuCell(0)
],
[
PydokuCell(0), PydokuCell(0), PydokuCell(0),
PydokuCell(0), PydokuCell(4), PydokuCell(9),
PydokuCell(2), PydokuCell(5), PydokuCell(7)
],
[
PydokuCell(0), PydokuCell(9), PydokuCell(4),
PydokuCell(8), PydokuCell(0), PydokuCell(0),
PydokuCell(0), PydokuCell(1), PydokuCell(3)
]
]
Once we have the board, we need methods that visualize it to the screen. In the constructor, we initialized a screen with a hardcoded width and height and saved it into the instance variable screen. We will render everything onto this display by calling the method drawBoard, that:
- Validates the board - marks valid and invalid cells
- Draws the lines
- Draws the cells - numbers plus borders if needed
- Refreshes the display
All of the steps are just method calls to other, more specific methods.
def drawBoard(self):
self.validateBoard()
self.drawLines()
self.drawNumbers()
pygame.display.flip()
To validate the board, the method goes over every cell on the board and checks if it is valid. For this, we reused the isValid method from the text-based solver, which checks the row, the column, and the 3x3 square.
def validateBoard(self):
for rowIdx in range(9):
for columnIdx in range(9):
cell = self.board[rowIdx][columnIdx]
if cell.number == 0:
cell.valid = True
else:
cell.valid = self.isValid(cell.number, rowIdx, columnIdx)
For this first version, I took a shortcut and hardcoded the widths/heights. The general idea was to have cells with a width of 39 pixels, 1 pixel wide thin lines, and 3 pixel wide thick lines. That is what the display constant calculation at the start of the class sums up:
WIDTH = 9 * 39 + 6 * 1 + 2 * 3
The drawLines method draws horizontal and vertical lines every 40 pixels, and makes the third line and the sixth line thicker by actually drawing three lines in a row.
def drawLines(self):
self.screen.fill(self.COLOR_WHITE)
x = 40
for i in range(1, 10):
self.drawLine((x, 0), (x, self.WIDTH), self.COLOR_BLACK)
self.drawLine((0, x), (self.WIDTH, x), self.COLOR_BLACK)
if i % 3 == 0:
x += 1
self.drawLine((x, 0), (x, self.WIDTH), self.COLOR_BLACK)
self.drawLine((0, x), (self.WIDTH, x), self.COLOR_BLACK)
x += 1
self.drawLine((x, 0), (x, self.WIDTH), self.COLOR_BLACK)
self.drawLine((0, x), (self.WIDTH, x), self.COLOR_BLACK)
x += 40
The drawLine is a convenience wrapper around the pygame draw line method.
def drawLine(self, startPoint, endPoint, color):
pygame.draw.line(self.screen, color, startPoint, endPoint)
Next, we need to render the numbers.
That is done by calling drawNumbers.
This method goes over the whole board and
- Draws the number
- user inputs are grey
- starting numbers are black
- Colors the cell border
- invalid cells are red
- the selected cell is light blue
The method looks like:
def drawNumbers(self):
for rowIdx in range(len(self.board)):
for columnIdx in range(len(self.board[rowIdx])):
cell = self.board[rowIdx][columnIdx]
if cell.number != 0:
color = self.COLOR_GREY if cell.editable else self.COLOR_BLACK
self.drawNumber(cell.number, rowIdx, columnIdx, color)
if not cell.valid:
self.colorCellBorder(rowIdx, columnIdx, self.COLOR_RED)
elif cell.selected:
self.colorCellBorder(rowIdx, columnIdx, self.COLOR_BLUE)
The drawNumber and colorCellBorder methods center a text into a cell and draw lines over the border of the cell, respectively.
def drawNumber(self, number, rowIdx, columnIdx, color):
text = font.render(str(number),
True,
color,
self.COLOR_WHITE)
textRect = text.get_rect()
rowCenter = self.cellCenters[rowIdx]
columnCenter = self.cellCenters[columnIdx]
textRect.center = (columnCenter, rowCenter)
self.screen.blit(text, textRect)
def colorCellBorder(self, rowIdx, columnIdx, color):
rowCenter = self.cellCenters[rowIdx]
columnCenter = self.cellCenters[columnIdx]
self.drawLine((columnCenter - 20, rowCenter - 20),
(columnCenter + 20, rowCenter - 20),
color)
self.drawLine((columnCenter - 20, rowCenter + 20),
(columnCenter + 20, rowCenter + 20),
color)
self.drawLine((columnCenter - 20, rowCenter - 20),
(columnCenter - 20, rowCenter + 20),
color)
self.drawLine((columnCenter + 20, rowCenter - 20),
(columnCenter + 20, rowCenter + 20),
color)
Once we visualized the board, we can start adding methods to support the gameplay. The third instance variable that we have, selectedCell, is meant to keep track of the currently selected cell on the board. So our setSelectedCell method is used to handle the mouse click on the board from the user. We figure out which cell was clicked by the user by checking the coordinates of the click and finding out which cell the coordinates belong to.
def setSelectedCell(self, mouseClickPosition):
clickedColumnIdx = self.getCellFromCoord(mouseClickPosition[0])
clickedRowIdx = self.getCellFromCoord(mouseClickPosition[1])
if self.selectedCell is not None:
rowIdx, columnIdx = self.selectedCell
self.board[rowIdx][columnIdx].selected = False
self.selectedCell = (clickedRowIdx, clickedColumnIdx)
self.board[clickedRowIdx][clickedColumnIdx].selected = True
def getCellFromCoord(self, coordinate):
for idx, cellCenter in enumerate(self.cellCenters):
if cellCenter - 20 < coordinate and coordinate < cellCenter + 20:
return idx
return -1
Then we have methods that allow the user to set a number in the selected cell or delete it.
def setNumber(self, number):
if self.selectedCell is None:
return
rowIdx, columnIdx = self.selectedCell
cell = self.board[rowIdx][columnIdx]
if cell.editable:
cell.number = number
def delete(self):
if self.selectedCell is None:
return
self.setNumber(0)
I also added a method that allows the user to move the selected cell around using the arrow keys.
def moveSelectedCell(self, rowMove, columnMove):
if self.selectedCell is None:
return
oldRowIdx, oldColumnIdx = self.selectedCell
newRowIdx = oldRowIdx + rowMove
newColumnIdx = oldColumnIdx + columnMove
if -1 < newRowIdx and newRowIdx < 9 and -1 < newColumnIdx and newColumnIdx < 9:
self.selectedCell = (newRowIdx, newColumnIdx)
self.board[oldRowIdx][oldColumnIdx].selected = False
self.board[newRowIdx][newColumnIdx].selected = True
With these methods, we can play the Sudoku game. The only thing missing is the main method which starts everything up and runs the event loop.
def main():
pydoku = PydokuGUI()
pydoku.drawBoard()
ALLOWED_INPUTS = {pygame.K_1, pygame.K_2, pygame.K_3, pygame.K_4,
pygame.K_5, pygame.K_6, pygame.K_7, pygame.K_8, pygame.K_9}
running = True
while running:
for event in pygame.event.get():
if event.type == pygame.KEYDOWN:
if event.key in ALLOWED_INPUTS:
number = int(chr(event.key))
pydoku.setNumber(number)
elif event.key == pygame.K_DELETE or event.key == pygame.K_BACKSPACE:
pydoku.delete()
elif event.key == pygame.K_UP:
pydoku.moveSelectedCell(-1, 0)
elif event.key == pygame.K_DOWN:
pydoku.moveSelectedCell(1, 0)
elif event.key == pygame.K_RIGHT:
pydoku.moveSelectedCell(0, 1)
elif event.key == pygame.K_LEFT:
pydoku.moveSelectedCell(0, -1)
pydoku.drawBoard()
if event.type == pygame.MOUSEBUTTONUP:
pos = pygame.mouse.get_pos()
pydoku.setSelectedCell(pos)
pydoku.drawBoard()
if event.type == pygame.QUIT:
running = False
pygame.quit()
We can see the main method creates a new instance of the PydokuGUI class and then runs an infinite loop that checks the events and calls the appropriate method for each of them. We can start the whole app by running the pydoku_gui.py script.
Visualizing the Sudoku solver algorithm
The last step was to merge the Sudoku solver into the GUI version. What I needed to do was add another state to the PydokuCell that tells us which cell the algorithm is currently solving.
class PydokuCell:
def __init__(self, number):
self.number = number
self.editable = number == 0
self.valid = True
self.selected = False
self.underConsideration = False
I also added an extra check in the method drawNumbers to draw a green cell border if the cell is currently under consideration.
def drawNumbers(self):
for rowIdx in range(len(self.board)):
for columnIdx in range(len(self.board[rowIdx])):
cell = self.board[rowIdx][columnIdx]
if cell.number != 0:
color = self.COLOR_GREY if cell.editable else self.COLOR_BLACK
self.drawNumber(cell.number, rowIdx, columnIdx, color)
if cell.underConsideration:
self.colorCellBorder(rowIdx, columnIdx, self.COLOR_GREEN)
elif not cell.valid:
self.colorCellBorder(rowIdx, columnIdx, self.COLOR_RED)
elif cell.selected:
self.colorCellBorder(rowIdx, columnIdx, self.COLOR_BLUE)
Then I added a check in the main event loop to respond to a SPACE key press, which calls the method to start solving the board.
if event.type == pygame.KEYDOWN:
if event.key in ALLOWED_INPUTS:
number = int(chr(event.key))
pydoku.setNumber(number)
elif event.key == pygame.K_DELETE or event.key == pygame.K_BACKSPACE:
pydoku.delete()
elif event.key == pygame.K_UP:
pydoku.moveSelectedCell(-1, 0)
elif event.key == pygame.K_DOWN:
pydoku.moveSelectedCell(1, 0)
elif event.key == pygame.K_RIGHT:
pydoku.moveSelectedCell(0, 1)
elif event.key == pygame.K_LEFT:
pydoku.moveSelectedCell(0, -1)
elif event.key == pygame.K_SPACE:
pydoku.solveSudoku()
The method to solve the sudoku resets the board and solves it, starting at the first cell and then working recursively.
def solveSudoku(self):
self.board = self.getBoard()
self.solveSudokuHelper(0, 0)
Finally, we have the methods to solve the sudoku from the text-based version - solveSudokuHelper and isValid. The method isValid is the same since it is used only to check for the same number, while solveSudokuHelper has a couple of additions:
- The method changes the underConsideration property of the cell that it is currently checking
- The method sleeps a bit in between so that the visualization is better visible
- The method calls drawBoard in between to render the changes onto the screen while it is working
The full method looks like this:
def solveSudokuHelper(self, rowIdx, columnIdx):
lastColumnIdx = len(self.board[rowIdx]) - 1
lastRowIdx = len(self.board) - 1
currentCell = self.board[rowIdx][columnIdx]
cellCenterY = self.cellCenters[rowIdx]
cellCenterX = self.cellCenters[columnIdx]
if currentCell.number != 0:
if columnIdx == lastColumnIdx and rowIdx == lastRowIdx:
return True
elif columnIdx == lastColumnIdx:
return self.solveSudokuHelper(rowIdx + 1, 0)
else:
return self.solveSudokuHelper(rowIdx, columnIdx + 1)
currentCell.underConsideration = True
for candidateNumber in range(1, 10):
currentCell.number = candidateNumber
self.drawBoard()
time.sleep(0.02)
if self.isValid(candidateNumber, rowIdx, columnIdx):
if columnIdx == lastColumnIdx and rowIdx == lastRowIdx:
currentCell.underConsideration = False
return True
if columnIdx == lastColumnIdx:
currentCell.underConsideration = False
result = self.solveSudokuHelper(rowIdx + 1, 0)
else:
currentCell.underConsideration = False
result = self.solveSudokuHelper(rowIdx, columnIdx + 1)
if result:
currentCell.underConsideration = False
return True
currentCell.underConsideration = True
self.drawBoard()
time.sleep(0.02)
currentCell.number = 0
currentCell.underConsideration = False
return False
Conclusion
This was a nice little project to get to know Python better.
It was cool to end up with something playable, but there are still quite some improvements that can be done as an exercise.
Some ideas I left out because of time constraints were:
- Have the width and height as parameters in the constructor and dynamically calculate the cells/lines
- Extend the getBoard method to retrieve a random Sudoku board from some API
- Make the visualization customizable (adjust the sleep time, change cell colors, etc.)
- Add some label to the screen to output messages to the user and use it to display some messages (like ‘Congratulations you won!’ or some information that is accompanying the Sudoku solving)
Again, this post just went over some parts of the source code for this project, the full project can be found on GitHub.
This is it for the overview of Pydoku.
Thank you for reading through, I hope you found this article useful.