Sudoku Solver and Generator in Python

Question

I made a Sudoku Solver after following some tutorials. Then I made a Sudoku generator and everything works. I also used classes to make it look more organized.

I wanted to know what I can do better to optimize my code.

I would like to make it faster and more readable but not at the cost of performance.

One optimization I can think of is getting all the free spaces (find_empty) at once rather than running it every time.

Here is my code:

'''Sudoku Solver and Generator implemented in Python'''
__author__ = 'Random Coder 59'
__version__ = '1.0.1'
__email__ = '[email protected]'
from random import shuffle
import time
board = [
 [8, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 3, 6, 0, 0, 0, 0, 0],
 [0, 7, 0, 0, 9, 0, 2, 0, 0],
 [0, 5, 0, 0, 0, 7, 0, 0, 0],
 [0, 0, 0, 0, 4, 5, 7, 0, 0],
 [0, 0, 0, 1, 0, 0, 0, 3, 0],
 [0, 0, 1, 0, 0, 0, 0, 6, 8],
 [0, 0, 8, 5, 0, 0, 0, 1, 0],
 [0, 9, 0, 0, 0, 0, 4, 0, 0]
]
class Sudoku:
 '''Sudoku class for solving and generating boards'''
 @classmethod
 def str_board(cls, board):
 '''Returns a board in string format'''
 str_board = ''
 for y in range(len(board)):
 if y in [3, 6]:
 str_board += '- ' * 11 + '\n'
 for x in range(len(board[y])):
 if x in [3, 6]:
 str_board += '| '
 if x == 8:
 str_board += str(board[y][x]) + '\n'
 else:
 str_board += str(board[y][x]) + ' '
 return str_board
 @classmethod
 def find_empty(cls, board):
 '''Find and returns a empty cell if any, else returns None'''
 for y in range(len(board)):
 for x in range(len(board[0])):
 if board[y][x] == 0:
 return y, x
 return None
 @classmethod
 def valid(cls, board, num, pos):
 '''Returns if a number is valid on a position on the board'''
 for x in range(len(board[0])):
 if board[pos[0]][x] == num and pos[1] != x:
 return False
 for y in range(len(board)):
 if board[y][pos[1]] == num and pos[0] != y:
 return False
 box_y = (pos[0] // 3) * 3
 box_x = (pos[1] // 3) * 3
 for y in range(box_y, box_y + 3):
 for x in range(box_x, box_x + 3):
 if board[y][x] == num and (y, x) != pos:
 return False
 return True
 @classmethod
 def solve(cls, board):
 '''Solves a given board and returns the board. Returns False is the board is not solvable'''
 find_result = cls.find_empty(board)
 if not find_result:
 return board
 else:
 y, x = find_result
 for num in range(1, 10):
 if Sudoku.valid(board, num, (y, x)):
 board[y][x] = num
 if Sudoku.solve(board):
 return board
 board[y][x] = 0
 return False
 @classmethod
 def create_empty(cls, board, number):
 '''Creates empty spaces in board according to number, returns the board'''
 coors = [(y, x) for y in range(9) for x in range(9)]
 shuffle(coors)
 for idx in range(number):
 y, x = coors[idx]
 board[y][x] = 0
 return board
 @classmethod
 def generate_board(cls):
 '''Generates a random Sudoku board and returns it.'''
 numbers = list(range(1, 10))
 board = [[0 for _ in range(9)] for _ in range(9)]
 for y in range(len(board)):
 for x in range(len(board[0])):
 shuffle(numbers)
 for num in numbers:
 if Sudoku.valid(board, num, (y, x)):
 board[y][x] = num
 if Sudoku.solve(board):
 break
 board[y][x] = num
 return board
solver = Sudoku()
print('Original board')
print(solver.str_board(board))
t1 = time.time()
solver.solve(board)
t2 = time.time()
print('Solved puzzle')
print(solver.str_board(board))
print(f'Finished in {round(t2 - t1, 3)} seconds')

Answer 1

I am not touching your generate_board. I had actually done similar kinda thing a few months back. Here's the code. It's faster if you exchange speed for memory.

board = [
 [8, 0, 0, 0, 0, 0, 0, 0, 0],
 [0, 0, 3, 6, 0, 0, 0, 0, 0],
 [0, 7, 0, 0, 9, 0, 2, 0, 0],
 [0, 5, 0, 0, 0, 7, 0, 0, 0],
 [0, 0, 0, 0, 4, 5, 7, 0, 0],
 [0, 0, 0, 1, 0, 0, 0, 3, 0],
 [0, 0, 1, 0, 0, 0, 0, 6, 8],
 [0, 0, 8, 5, 0, 0, 0, 1, 0],
 [0, 9, 0, 0, 0, 0, 4, 0, 0]
]
# This function will decide the least possible value for an empty space, r stands for row index, c for column index
def decide(r, c):
 # As you can see, a and b will decide the native 3/3 square for a particular index
 a, b = r // 3 * 3, c // 3 * 3
 # If a number has index (5, 6) you will get a=3, b=6 this means the 3/3 square extends 
 # over row 3,4,5 and column 6,7,8 
 # After back tracking let's say our value is 5, this loop will check where 6, 7, 8, 9 are fit for being used.
 # If the spot is zero, it just starts from 1 and goes up to 9 until a suitable value if found 
 for i in range(board[r][c]+1, 10):
 for j in range(9):
 # board[r][j] checks whether the number i is there in the row r
 # board[j][c] checks whether the number i is there in the column c
 # board[a+j//3][b+j % 3] try to dry run the values j//3 and j%3 you'll understand. 
 # j//3 will give 0, 0, 0, 1, 1, 1, 2, 2, 2 over the 9 iterations.
 # j%3 will give 0, 1, 2, 0, 1, 2, 0, 1, 2 over the 9 iterations.
 # Let's say you have a=3 and b=6
 # a+j//3 will extend over 3, 3, 3, 4, 4, 4, 5, 5, 5
 # b+j%3 will give :6, 7, 8, 6, 7, 8, 6, 7, 8
 # Thus we cover the entire 3/3 square, also the row and the column.
 if board[r][j] == i or board[j][c] == i or board[a+j//3][b+j % 3] == i:
 # obviously if any of these is true, the number is not fit 
 break
 else:
 # if a number is found to be fit it is returned immediately
 return i
 # if no solution can be found, zero is returned. This means there has been some mistake with the previous solution, we'll back trace in the solve function and fix thaht.
 return 0
def solve():
 # mutable collects the indices of all the empty spots.
 mutable = [(i, j) for i, row in enumerate(board) for j, element in enumerate(row) if element == 0]
 i = 0
 while i < len(mutable):
 r, c = mutable[i]
 # we send the row and column no. of the empty spot to decide function
 board[r][c] = decide(r, c)
 # If a solution has been found, we just go on, if a zero is returned that means something's been wrong, we backtrace, reduce the value of i by i
 if board[r][c] == 0:
 i -= 1
 continue
 i += 1
def print_board():
 for i in range(len(board)):
 if i % 3 == 0:
 print('-' * 23)
 for j in range(len(board[i])):
 if j != 0 and j % 3 == 0:
 print(' | ', end='')
 print(board[i][j], end=' ')
 print()
 print('-' * 23)
from timeit import timeit
print_board()
time = timeit(solve, number=1)
print_board()
print(f'Finished in {time}s')

This code takes 0.4 seconds to solve the sudoko. Your code took 0.8 seconds on my device. Output:

-----------------------
8 0 0 | 0 0 0 | 0 0 0 
0 0 3 | 6 0 0 | 0 0 0 
0 7 0 | 0 9 0 | 2 0 0 
-----------------------
0 5 0 | 0 0 7 | 0 0 0 
0 0 0 | 0 4 5 | 7 0 0 
0 0 0 | 1 0 0 | 0 3 0 
-----------------------
0 0 1 | 0 0 0 | 0 6 8 
0 0 8 | 5 0 0 | 0 1 0 
0 9 0 | 0 0 0 | 4 0 0 
-----------------------
-----------------------
8 1 2 | 7 5 3 | 6 4 9 
9 4 3 | 6 8 2 | 1 7 5 
6 7 5 | 4 9 1 | 2 8 3 
-----------------------
1 5 4 | 2 3 7 | 8 9 6 
3 6 9 | 8 4 5 | 7 2 1 
2 8 7 | 1 6 9 | 5 3 4 
-----------------------
5 2 1 | 9 7 4 | 3 6 8 
4 3 8 | 5 2 6 | 9 1 7 
7 9 6 | 3 1 8 | 4 5 2 
-----------------------
Finished in 0.4711908s

• Random_Pythoneer59: Could you explain your functions? I am compartively now to python.
• Nothing special: ok wait a few minutes, I'll edit the answer. If you don't know about enumerate function, you can google it. Rest of things I'll be explaining in the answer.
• Random_Pythoneer59: I appreciate the effort you took into this and I understood the code now, but my question is what's the point in taking the smallest value possible? How does it help in optimization?
• Nothing special: It is a part of back tracking algorithm let's say you test every number from 0 to 9 and make a list of possible ones.... Secondly you go from let's say 5 to 9...so it's faster....now if none of the possibilities work then we conclude that previous empty spot was wrongly filled, we go back and try to fix the previous mistake.... This goes on & on until the board is solved...
• Random_Pythoneer59: Ok now I get it. Thanks!

Answer 2

One optimization I can think of is getting a all the free spaces(find_empty) at once rather than running it everytime.

Things like that would work. There are bigger fish to fry though. The main thing that causes a basic recursive solver like this to sometimes (but not on all inputs) be slow isn't really the implementation details. Of course, they also matter. But the main thing is algorithmic: a basic recursive solver fundamentally spends a lot of time exploring tons of partial solutions that aren't going to be completable, but the solver only detects the conflict very deep in the recursion tree, after spending lots of time on desperately trying to solve the bottom-right cells even though the problem may have been caused by a bad pick in the upper left of the board.

There are some strategies (common to Constraint Programming in general) that you can use to make a more advanced solver:

1. Propagate the consequences of a choice. In the context of Sudoku, that can mean iteratively checking for Singles (both naked and hidden), both right at the start but also after filling in a cell. There are more advanced propagation techniques, Sudoku can be viewed as three sets of 9 AllDifferent constraints and there are some algorithms related to that, but implementing only iterative Naked Single and Hidden Single detection is already such a huge step up in performance you probably don't need to get so fancy.
2. Use a better order than left-to-right and top-to-bottom. The order matters: if a cell is impossible to solve due to a bad choice that was made earlier, it's best to detect that conflict ASAP. Any exploration done while that bad choice is on the board, will just be wasted. A common technique to somewhat avoid that effect, is picking an empty cell with with the smallest domain (fewest possible values) first, rather than simple the first empty cell that is found.

Implementing one or both of them would surely help with the cases that are now slow, but not with the cases that are already fast. Unfortunately they would add code and increase the level of complexity, so you can reasonably say that they would hurt readability.

By the way, here is an input that tends to make basic recursive solvers really slow, you can use it to evaluate the effects of implementing the above techniques:

board = [
 [0,0,0,0,0,0,0,0,0],
 [0,0,0,0,0,3,0,8,5],
 [0,0,1,0,2,0,0,0,0],
 [0,0,0,5,0,7,0,0,0],
 [0,0,4,0,0,0,1,0,0],
 [0,9,0,0,0,0,0,0,0],
 [5,0,0,0,0,0,0,7,3],
 [0,0,2,0,1,0,0,0,0],
 [0,0,0,0,4,0,0,0,9]
]

Often I would add a performance comparison of a quick and dirty implementation of propagating naked/hidden singles, but I don't have Python installed right now. It is very effective though. The puzzle above may take dozens of seconds to solve with the current solver, and only several milliseconds with a solver that implements naked- and hidden-singles propagation. At least that is what I expect based on my experience with similar solvers.

• Random_Pythoneer59: You can use this online ide but it will most probably be slower. Anyway I understand your point but as I am new to python I dont have much idea of how to implement it. The time you took to type this is very much appreciated but could you post some working code?

Answer 3

In order to squeeze some performance, you could have 9 simple integer sets for different rows, 9 integer sets for different columns, and 9 integer sets for the \3ドル \times 3\$ minisquares. Then, when trying to check whether the next digit \$d\$ fits in the solution board cell, all you do is make sure that for that position all corresponding row/column/minisquare sets do not contain the digit. With this optimization I got optimistic results:

class IntSet:
 def __init__(self):
 self.array = [False for i in range(10)]
 def add(self, digit):
 self.array[digit] = True
 def remove(self, digit):
 self.array[digit] = False
 def contains(self, digit):
 return self.array[digit]
class SudokuSolver:
 def __init__(self, board):
 self.board = board
 self.row_set_array = [IntSet() for i in range(9)]
 self.col_set_array = [IntSet() for i in range(9)]
 self.minisquare_set_matrix = [[IntSet() for y in range(3)] for x in range(3)]
 self.solution = [[0 for i in range(9)] for j in range(9)]
 for y in range(9):
 for x in range(9):
 digit = self.board[y][x]
 self.row_set_array[y].add(digit)
 self.col_set_array[x].add(digit)
 self.minisquare_set_matrix[y // 3][x // 3].add(digit)
 def solve(self, x = 0, y = 0):
 if x == 9:
 x = 0
 y += 1
 if y == 9:
 return True
 if self.board[y][x] != 0:
 self.solution[y][x] = self.board[y][x]
 return self.solve(x + 1, y)
 for sign in range(1, 10):
 if not self.col_set_array[x].contains(sign) and not self.row_set_array[y].contains(sign):
 minisquare_x = x // 3
 minisquare_y = y // 3
 if not self.minisquare_set_matrix[minisquare_y][minisquare_x].contains(sign):
 self.solution[y][x] = sign
 self.row_set_array[y].add(sign)
 self.col_set_array[x].add(sign)
 self.minisquare_set_matrix[minisquare_y][minisquare_x].add(sign)
 if self.solve(x + 1, y):
 return True
 self.row_set_array[y].remove(sign)
 self.col_set_array[x].remove(sign)
 self.minisquare_set_matrix[minisquare_y][minisquare_x].remove(sign)
 return False

Typical output

-----------------------
8 0 0 | 0 0 0 | 0 0 0 
0 0 3 | 6 0 0 | 0 0 0 
0 7 0 | 0 9 0 | 2 0 0 
-----------------------
0 5 0 | 0 0 7 | 0 0 0 
0 0 0 | 0 4 5 | 7 0 0 
0 0 0 | 1 0 0 | 0 3 0 
-----------------------
0 0 1 | 0 0 0 | 0 6 8 
0 0 8 | 5 0 0 | 0 1 0 
0 9 0 | 0 0 0 | 4 0 0 
-----------------------
-----------------------
8 1 2 | 7 5 3 | 6 4 9 
9 4 3 | 6 8 2 | 1 7 5 
6 7 5 | 4 9 1 | 2 8 3 
-----------------------
1 5 4 | 2 3 7 | 8 9 6 
3 6 9 | 8 4 5 | 7 2 1 
2 8 7 | 1 6 9 | 5 3 4 
-----------------------
5 2 1 | 9 7 4 | 3 6 8 
4 3 8 | 5 2 6 | 9 1 7 
7 9 6 | 3 1 8 | 4 5 2 
-----------------------
Finished in 0.41106139999999997s
-----------------------
8 0 0 | 0 0 0 | 0 0 0 
0 0 3 | 6 0 0 | 0 0 0 
0 7 0 | 0 9 0 | 2 0 0 
-----------------------
0 5 0 | 0 0 7 | 0 0 0 
0 0 0 | 0 4 5 | 7 0 0 
0 0 0 | 1 0 0 | 0 3 0 
-----------------------
0 0 1 | 0 0 0 | 0 6 8 
0 0 8 | 5 0 0 | 0 1 0 
0 9 0 | 0 0 0 | 4 0 0 
-----------------------
coderodde's output:
-----------------------
8 1 2 | 7 5 3 | 6 4 9 
9 4 3 | 6 8 2 | 1 7 5 
6 7 5 | 4 9 1 | 2 8 3 
-----------------------
1 5 4 | 2 3 7 | 8 9 6 
3 6 9 | 8 4 5 | 7 2 1 
2 8 7 | 1 6 9 | 5 3 4 
-----------------------
5 2 1 | 9 7 4 | 3 6 8 
4 3 8 | 5 2 6 | 9 1 7 
7 9 6 | 3 1 8 | 4 5 2 
-----------------------
Duration 181 milliseconds.

(For entire demonstration code, see this gist.)