Tl;dr: Solve some cells before proceeding with backtracking!
I always liked solving mathematical puzzles and always struggled with finding entertaining and challenging problems to practice coding. That said, when the idea of writing a script that would solve Sudoku in a more sophisticated way than just using the backtracking method came to my head, I started thinking about the solution right away.
The Idea
Backtracking, which is pretty much placing numbers in empty cells and checking if a Sudoku board is still valid seems to be an inefficient way of solving the problem. The solution will be found eventually (if there is a solution), but why not try to apply additional logic to it? The same logic that is applied by people using a pencil on the last page of the newspaper with a printed puzzle.
I implemented some rules to make backtracking easier. Every cell that is solved beforehand reduces the set of solutions dramatically and makes script run much shorter. Two rules I decided to apply are the ones that anybody who has ever solved Sudoku uses and can describe.
Find a cell that only one number can be placed into:
There is not much effort required to find cells where only one number can be put. You pick a cell and think of possibilities by eliminating the numbers that are already written in the given box, column and row. You found there is only one option? You found the solution.Find a box/column/row where a number can be put only in one cell:
Time to apply reverse logic here. Instead of looking for a cell that has only one possibility which makes it valid, you look for a box, column or row and check if one of the numbers that is missing from it can be placed only in one spot.
After determining these rules, I decided to find a way I would like my script to run. Here is the simplified algorithm flowchart that describes how the first part of my script works:
Simple as it is. Straightforward rules we have all applied to solve Sudoku. The most interesting is still to come though: backtracking.
When I first thought about implementing backtracking in my code, I did not know that recursion is not the best way of writing algorithms in Python. I fully implemented a way to solve the problem recursively, as backtracking seemed to be a perfect example of using it, and had to rewrite this part of the code, pretty much from scratch. Still, lesson for the life. Here is how I implemented backtracking after all:
The Code
With that explained, here is my code:
import time #used to check script's run time
#class representing a single cell of sudoku board
class Cell:
def __init__(self, row_number, column_number, value):
self.row = row_number #0 thru 8
self.column = column_number #0 thru 8
self.box = self.set_box_number() #0 thru 8
self.value = value #0 if empty cell
self.possibilities = self.set_initial_possibilities() #empty list or 1 thru 9
#set box number based on row and column number
def set_box_number(self):
box_number = int(self.column/3)
box_number += int(self.row/3)*3
return box_number
#set possibilities to empty list if cell not empty or 1 thru 9
def set_initial_possibilities(self):
if self.value != 0:
return []
else:
return [*range(1, 10)]
#class solving sudoku in 'human' way
class Solver:
def __init__(self, board):
self.cells = []
for row_no, row in enumerate(board):
for col_no, val in enumerate(row):
self.cells.append(Cell(row_no, col_no, val))
#get all cells from box
def get_cells_from_box(self, box_number):
return [cell for cell in self.cells if box_number == cell.box]
#get all cells from column
def get_cells_from_column(self, column_number):
return [cell for cell in self.cells if column_number == cell.column]
#get all cells from row
def get_cells_from_row(self, row_number):
return [cell for cell in self.cells if row_number == cell.row]
#get all cells within same box, column and row as given cell
def get_conflicting_cells(self, given_cell):
return {cell for cell in self.cells if given_cell.box == cell.box or given_cell.column == cell.column or given_cell.row == cell.row}
#remove not valid possibilities from all cells
def set_all_cells_possibilities(self):
for cell in self.cells:
self.remove_cell_value_from_others_possibilities(cell)
#look for a cell with single possibility and solve it
def find_and_solve_cell_with_one_possibility(self):
for cell in self.cells:
if len(cell.possibilities) == 1:
self.solve_cell(cell, cell.possibilities[0])
return True
return False
#look for unique possibilities in all boxes, column and rows
def find_and_solve_unique_possibilities(self):
for number in range (0, 8):
if self.if_unique_possibility_within_cells(self.get_cells_from_box(number)):
return True
if self.if_unique_possibility_within_cells(self.get_cells_from_column(number)):
return True
if self.if_unique_possibility_within_cells(self.get_cells_from_row(number)):
return True
return False
#look for unique possibility in group of cells
def if_unique_possibility_within_cells(self, same_group_cells):
counts = [0] * 10
for cell in same_group_cells:
for possibility in cell.possibilities:
counts[possibility] += 1
if 1 in counts:
unique_value = counts.index(1)
for cell in same_group_cells:
if unique_value in cell.possibilities:
self.solve_cell(cell, unique_value)
return True
return False
#solve cell and remove its value from other cells possibilities
def solve_cell(self, given_cell, value):
given_cell.value = value
given_cell.possibilities = []
self.remove_cell_value_from_others_possibilities(given_cell)
#remove cell value from possibilites of cells within same box, column and row
def remove_cell_value_from_others_possibilities(self, given_cell):
for conflicting_cell in self.get_conflicting_cells(given_cell):
try:
conflicting_cell.possibilities.remove(given_cell.value)
except:
continue
#main algorithm of the class
def run(self):
while(True):
if not self.find_and_solve_cell_with_one_possibility():
if not self.find_and_solve_unique_possibilities():
break
#class solving sudoku with backtracking algorithm
class Backtrack():
def __init__(self, cells):
self.cells = cells
self.unsolved_cells = [cell for cell in self.cells if cell.value == 0]
#get all cells within same box, column and row as given cell
def get_conflicting_cells_values(self, given_cell):
return {cell.value for cell in self.cells if given_cell.box == cell.box or given_cell.column == cell.column or given_cell.row == cell.row}
#check validity of sudoku if cell is set to given value
def if_solution_valid(self, given_cell, cell_value_to_check):
return not cell_value_to_check in self.get_conflicting_cells_values(given_cell)
#check current cell value and pick next of its possibilities
def get_next_possibility(self, given_cell):
if given_cell.value == 0:
return given_cell.possibilities[0]
else:
return given_cell.possibilities[given_cell.possibilities.index(given_cell.value)+1]
#main algorithm of the class
def run(self):
current_cell_number = 0
while (current_cell_number >= 0 and current_cell_number < len(self.unsolved_cells)):
current_cell = self.unsolved_cells[current_cell_number]
try:
#get next possibility for cell
next_possibility = self.get_next_possibility(current_cell)
except IndexError:
#no more possibilities for cell -> take step back and work on previous cell
current_cell.value = 0
current_cell_number -= 1
else:
#possibility valid -> change cell value and proceed to next cell
if self.if_solution_valid(current_cell, next_possibility):
current_cell.value = next_possibility
current_cell_number += 1
#possibility not valid -> change cell value and repeat process
else:
current_cell.value = next_possibility
#class responsible for printing sudoku board in readable form
class Printer():
def __init__(self, cells):
self.cells = cells
#print sudoku board
def print(self):
last_cell_row_no = 0
for cell in self.cells:
if last_cell_row_no != cell.row:
print()
print(cell.value, end = " ")
last_cell_row_no = cell.row
print("\n- - - - - - - - -")
#class responsible for checking if sudoku solution is valid
class Validator():
def __init__(self, cells):
self.cells = cells
#check if sudoku solution is valid
def if_valid(self):
for cell in self.cells:
if cell.value == 0:
return False
return True
#print sudoku validity
def print(self):
if self.if_valid():
print("Sudoku solved!")
else:
print("Sudoku is not valid!")
### main part below ###
def main():
#sudoku to solve
sudoku_to_solve = [
[0, 0, 0, 0, 0, 0, 2, 0, 0],
[0, 8, 0, 0, 0, 7, 0, 9, 0],
[6, 0, 2, 0, 0, 0, 5, 0, 0],
[0, 7, 0, 0, 6, 0, 0, 0, 0],
[0, 0, 0, 9, 0, 1, 0, 0, 0],
[0, 0, 0, 0, 2, 0, 0, 4, 0],
[0, 0, 5, 0, 0, 0, 6, 0, 3],
[0, 9, 0, 4, 0, 0, 0, 7, 0],
[0, 0, 6, 0, 0, 0, 0, 0, 0]
]
start_time = time.time() #start timer to measure run time
solver = Solver(sudoku_to_solve)
printer=Printer(solver.cells)
printer.print()
solver.set_all_cells_possibilities() #checks possibilities for all cells
solver.run() #comment this line to leave everything to backtracking
backtrack=Backtrack(solver.cells)
backtrack.run()
printer=Printer(backtrack.cells)
printer.print()
validator=Validator(backtrack.cells)
validator.print()
print("Run time: %s seconds" % (time.time() - start_time))
if __name__ == "__main__":
main()
Summary
The code follows the idea shown in the algorithm flowcharts: a way to solve Sudoku faster than just with backtracking. This can be proven: run the script twice, first with solver.run() left out as it is, and second without that line (or with # before it) to skip the part that simplifies Sudoku before backtracking kicks in. Depending on the complexity, run time may decrease significantly. In the example written in the script, my run times are approx. 6.9 vs 64 seconds.
This could be even faster if more complex Sudoku solving rules were used. I will leave it as it is for now, as I am happy with the result. These simple rules helped to find a solution much faster already.
Find my code on GitHub:
Top comments (4)