Skip to content

Instantly share code, notes, and snippets.

@cellularmitosis

cellularmitosis/README.md

Last active May 31, 2020
Embed
What would you like to do?
A trivial sudoku solver, in Python

Blog 2020/5/26

<- previous | index | next ->

A trivial sudoku solver, in Python

Update: it should be noted there are many boards which this program cannot solve, such as this one.

Two variations: one which uses mutation, and another in which which all functions return copies of modified data structures.

The example board (wikipedia-board.txt) was taken from https://en.wikipedia.org/wiki/Sudoku.

Simple invocation:

$ ./sudoku.py wikipedia-board.txt
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

Invocation with execution tracing: here, you can see the remaining possibilities of each grid position being reduced after each iteration, until the board is "solved" (i.e. until there is only one possibility for every grid position):

$ ./sudoku.py --verbose wikipedia-board.txt
Initial board state:
5         3         123456789 123456789 7         123456789 123456789 123456789 123456789
6         123456789 123456789 1         9         5         123456789 123456789 123456789
123456789 9         8         123456789 123456789 123456789 123456789 6         123456789
8         123456789 123456789 123456789 6         123456789 123456789 123456789 3
4         123456789 123456789 8         123456789 3         123456789 123456789 1
7         123456789 123456789 123456789 2         123456789 123456789 123456789 6
123456789 6         123456789 123456789 123456789 123456789 2         8         123456789
123456789 123456789 123456789 4         1         9         123456789 123456789 5
123456789 123456789 123456789 123456789 8         123456789 123456789 7         9
Possibilities count: 489

Iterating rows:
5         3         124689    124689    7         124689    124689    124689    124689
6         23478     23478     1         9         5         23478     23478     23478
123457    9         8         123457    123457    123457    123457    6         123457
8         124579    124579    124579    6         124579    124579    124579    3
4         25679     25679     8         25679     3         25679     25679     1
7         134589    134589    134589    2         134589    134589    134589    6
134579    6         134579    134579    134579    134579    2         8         134579
23678     23678     23678     4         1         9         23678     23678     5
123456    123456    123456    123456    8         123456    123456    7         9
Possibilities count: 321

Iterating columns:
5         3         12469     269       7         12468     14689     1249      248
6         2478      2347      1         9         5         3478      234       2478
123       9         8         2357      345       1247      13457     6         247
8         12457     124579    2579      6         1247      14579     12459     3
4         257       25679     8         5         3         5679      259       1
7         1458      13459     359       2         148       134589    13459     6
139       6         134579    3579      345       147       2         8         47
23        278       2367      4         1         9         3678      23        5
123       1245      123456    2356      8         1246      13456     7         9
Possibilities count: 229

Iterating rows:
5         3         124       26        7         2468      1489      1249      248
6         247       247       1         9         5         3478      234       2478
12        9         8         23        34        24        13457     6         247
8         125       1259      79        6         147       4579      2459      3
4         2         269       8         5         3         79        29        1
7         15        135       9         2         14        458       45        6
139       6         1359      35        35        7         2         8         4
2         278       27        4         1         9         6         3         5
123       1245      12345     2356      8         26        1346      7         9
Possibilities count: 168

<output elided...>

Iterating columns:
5         3         4         6         7         8         9         1         2
6         7         2         1         9         5         3         4         8
1         9         8         3         4         2         5         6         7
8         5         9         7         6         1         4         2         3
4         2         6         8         5         3         7         9         1
7         1         3         9         2         4         8         5         6
9         6         1         5         3         7         2         8         4
2         8         7         4         1         9         6         3         5
3         4         5         2         8         6         1         7         9
Possibilities count: 81

Solved in 7 iterations!
534678912
672195348
198342567
859761423
426853791
713924856
961537284
287419635
345286179

Here are some completely unscientific benchmarks:

sudoku-bench

sudoku-py2

sudoku-mut-py2

Interesting that with the higher-end processors and the mutable script, choice of operating-system dominates (the script is so short-lived that this is basically a test of starting a process).

With the lower-end processors, Python 2 vs Python 3 actually makes up to a 2x difference in performance.

#!/usr/bin/env python
# A sudoku solver.
# This version of the script mutates the board state in-place.
# Copyright (c) 2020 Jason Pepas.
# Released under the terms of the MIT License.
# See https://opensource.org/licenses/MIT
# Board file format: plain text, 9 lines of 9 numbers (zero for empty box).
# Example:
# 530070000
# 600195000
# 098000060
# 800060003
# 400803001
# 700020006
# 060000280
# 000419005
# 000080079
# Data structures:
# - A 'box' is a set of the remaining possible solutions for a spot in the grid.
# - A solved box has only one item (an integer) in its set.
# - A 'board' is a 2-dimensional array (9x9) of boxes (sets).
# - A solved board is a 9x9 grid of sets which each have only one item.
# The general approach is to iterate over the board and use logic to reduce
# the number of possible solutions in each box until the board is solved.
# Algorithm:
# - For each row, build a set of the solved numbers in that row, then
# remove those solutions from the remaining possibilities in each of the
# unsolved boxes in that row.
# - Do the same for each column.
# - Do the same for each 3x3 grid.
# - Repeat the above process until either the board is solved, or until
# deadlock is detected (i.e. the board state remaines unchanged after an
# iteration).
import sys
g_tracing = False
def new_set(members=None):
"""Returns a new set (with members)."""
if members is None:
members = []
try:
import sets
s = sets.Set(members)
return s
except:
return set(members)
def print_board(board, fd=sys.stdout):
"""Print the (compact) representation of the board state to fd."""
for row in board:
for box in row:
is_solved, solution = is_box_solved(box)
if is_solved:
fd.write("%s" % solution)
continue
else:
fd.write('0')
continue
fd.write('\n')
continue
def trace(msg):
"""Prints a message if tracing is enabled (with '-v' or '--verbose')."""
if g_tracing:
sys.stdout.write(msg)
def dump_board(board):
"""Print the possibility states of the board."""
for row in board:
for box in row:
count = 0
possibilities = list(box)
possibilities.sort()
for possibility in possibilities:
trace("%s" % possibility)
count += 1
if count < 9:
spaces = " " * (9 - count)
trace(spaces)
trace(' ')
continue
trace('\n')
continue
pc = possibilities_count(board)
trace("Possibilities count: %s\n" % pc)
def is_box_solved(box):
"""Returns (True, number) if the box is solved, (False, None) otherwise."""
if len(box) == 1:
return (True, list(box)[0])
else:
return (False, None)
def is_board_solved(board):
"""Returns True/False whether the board is solved."""
for row in board:
for box in row:
if len(box) > 1:
return False
else:
continue
continue
return True
def iterate_row(row):
"""Iterates the board row."""
# find the set of solved boxes in this row.
solved_numbers = new_set()
for box in row:
is_solved, solution = is_box_solved(box)
if is_solved:
solved_numbers.add(solution)
continue
else:
continue
# subtract the solved numbers from each unsolved box in this row.
for box in row:
is_solved, _ = is_box_solved(box)
if is_solved:
continue
else:
box -= solved_numbers
continue
def iterate_rows(board):
"""Iterates the rows in the board."""
for row in board:
iterate_row(row)
continue
trace('\nIterating rows:\n')
dump_board(board)
return board
def iterate_column(board, i):
"""Iterates column i in the board."""
# find the set of solved boxes in this column.
solved_numbers = new_set()
for row in board:
box = row[i]
is_solved, solution = is_box_solved(box)
if is_solved:
solved_numbers.add(solution)
continue
else:
continue
# subtract the solved numbers from each unsolved box in this column.
for j in range(len(board)):
row = board[j]
box = row[i]
is_solved, _ = is_box_solved(box)
if is_solved:
continue
else:
box -= solved_numbers
continue
def iterate_columns(board):
"""Iterates the columns in the board."""
first_row = board[0]
column_count = len(first_row)
for n in range(column_count):
iterate_column(board, n)
continue
trace('\nIterating columns:\n')
dump_board(board)
def iterate_grid(board, i):
"""Iterates grid i in the board."""
first_row_index = int(i / 3) * 3
first_col_index = (i % 3) * 3
# find the set of solved boxes in this grid.
solved_numbers = new_set()
for row_index in range(first_row_index, first_row_index+3):
for col_index in range(first_col_index, first_col_index+3):
box = board[row_index][col_index]
is_solved, solution = is_box_solved(box)
if is_solved:
solved_numbers.add(solution)
continue
else:
continue
# subtract the solved numbers from each box in the grid.
for row_index in range(first_row_index, first_row_index+3):
for col_index in range(first_col_index, first_col_index+3):
box = board[row_index][col_index]
is_solved, _ = is_box_solved(box)
if is_solved:
continue
else:
box -= solved_numbers
continue
continue
def iterate_grids(board):
"""Iterates the grids in the board."""
for n in range(9):
iterate_grid(board, n)
continue
trace('\nIterating grids:\n')
dump_board(board)
def iterate_board(board):
"""Iterates the board state."""
iterate_rows(board)
iterate_columns(board)
iterate_grids(board)
def possibilities_count(board):
"""Returns the total number of possibilities in the board state.
A solved board has a possibility count of 81."""
count = 0
for row in board:
for box in row:
count += len(box)
return count
def read_board_file(fpath):
"""Returns the initial board state as read from the puzzle file."""
fd = open(fpath)
lines = fd.readlines()
fd.close()
rows = []
for line in lines:
row = []
for i in range(9):
number = int(line[i])
if number == 0:
row.append(new_set([1,2,3,4,5,6,7,8,9]))
continue
else:
row.append(new_set([number]))
continue
rows.append(row)
continue
return rows
if __name__ == '__main__':
args = sys.argv[1:]
if len(args) > 1 and args[0] in ['-v', '--verbose']:
g_tracing = True
args = args[1:]
if len(args) != 1:
sys.stderr.write("Error: no board file specified.\n")
sys.exit(1)
board_fpath = args[-1]
board = read_board_file(board_fpath)
trace('Initial board state:\n')
dump_board(board)
iteration_count = 0
while True:
iteration_count += 1
pcount1 = possibilities_count(board)
iterate_board(board)
pcount2 = possibilities_count(board)
if pcount1 == pcount2:
sys.stderr.write("Error: don't know how to solve this board.\n")
sys.exit(1)
elif is_board_solved(board):
trace("\nSolved in %s iterations!\n" % iteration_count)
print_board(board)
sys.exit(0)
else:
continue
#!/usr/bin/env python
# A sudoku solver.
# This version of the script avoids mutation wherever possible.
# Copyright (c) 2020 Jason Pepas.
# Released under the terms of the MIT License.
# See https://opensource.org/licenses/MIT
# Board file format: plain text, 9 lines of 9 numbers (zero for empty box).
# Example:
# 530070000
# 600195000
# 098000060
# 800060003
# 400803001
# 700020006
# 060000280
# 000419005
# 000080079
# Data structures:
# - A 'box' is a set of the remaining possible solutions for a spot in the grid.
# - A solved box has only one item (an integer) in its set.
# - A 'board' is a 2-dimensional array (9x9) of boxes (sets).
# - A solved board is a 9x9 grid of sets which each have only one item.
# The general approach is to iterate over the board and use logic to reduce
# the number of possible solutions in each box until the board is solved.
# Algorithm:
# - For each row, build a set of the solved numbers in that row, then
# remove those solutions from the remaining possibilities in each of the
# unsolved boxes in that row.
# - Do the same for each column.
# - Do the same for each 3x3 grid.
# - Repeat the above process until either the board is solved, or until
# deadlock is detected (i.e. the board state remaines unchanged after an
# iteration).
import sys
import copy
g_tracing = False
def new_set(members=None):
"""Returns a new set (with members)."""
if members is None:
members = []
try:
import sets
s = sets.Set(members)
return s
except:
return set(members)
def print_board(board, fd=sys.stdout):
"""Print the (compact) representation of the board state to fd."""
for row in board:
for box in row:
is_solved, solution = is_box_solved(box)
if is_solved:
fd.write("%s" % solution)
continue
else:
fd.write('0')
continue
fd.write('\n')
continue
def trace(msg):
"""Prints a message if tracing is enabled (with '-v' or '--verbose')."""
if g_tracing:
sys.stdout.write(msg)
def dump_board(board):
"""Print the possibility states of the board."""
for row in board:
for box in row:
count = 0
possibilities = list(box)
possibilities.sort()
for possibility in possibilities:
trace("%s" % possibility)
count += 1
if count < 9:
spaces = " " * (9 - count)
trace(spaces)
trace(' ')
continue
trace('\n')
continue
pc = possibilities_count(board)
trace("Possibilities count: %s\n" % pc)
def copy_box(box):
"""Returns a copy of the box."""
return new_set(box)
def is_box_solved(box):
"""Returns (True, number) if the box is solved, (False, None) otherwise."""
if len(box) == 1:
return (True, list(box)[0])
else:
return (False, None)
def is_board_solved(board):
"""Returns True/False whether the board is solved."""
for row in board:
for box in row:
if len(box) > 1:
return False
else:
continue
continue
return True
def iterate_row(row):
"""Returns an iterated copy of the row."""
# find the set of solved boxes in this row.
solved_numbers = new_set()
for box in row:
is_solved, solution = is_box_solved(box)
if is_solved:
solved_numbers.add(solution)
continue
else:
continue
# subtract the solved numbers from each unsolved box in this row.
row2 = []
for box in row:
is_solved, _ = is_box_solved(box)
if is_solved:
box2 = copy_box(box)
row2.append(box2)
continue
else:
box2 = copy_box(box)
box2 -= solved_numbers
row2.append(box2)
continue
return row2
def iterate_rows(board):
"""Returns a copy of board with iterated rows."""
board2 = []
for row in board:
row2 = iterate_row(row)
board2.append(row2)
continue
trace('\nIterating rows:\n')
dump_board(board2)
return board2
def iterate_column(board, i):
"""Returns a copy of the board with column i iterated."""
# find the set of solved boxes in this column.
solved_numbers = new_set()
for row in board:
box = row[i]
is_solved, solution = is_box_solved(box)
if is_solved:
solved_numbers.add(solution)
continue
else:
continue
# subtract the solved numbers from each unsolved box in this column.
board2 = copy.deepcopy(board)
for j in range(len(board2)):
row = board2[j]
box = row[i]
is_solved, _ = is_box_solved(box)
if is_solved:
continue
else:
box -= solved_numbers
continue
return board2
def iterate_columns(board):
"""Returns a copy of the board with iterated columns."""
first_row = board[0]
column_count = len(first_row)
for n in range(column_count):
board = iterate_column(board, n)
continue
trace('\nIterating columns:\n')
dump_board(board)
return board
def iterate_grid(board, i):
"""Returns a copy of the board with grid i iterated."""
first_row_index = int(i / 3) * 3
first_col_index = (i % 3) * 3
# find the set of solved boxes in this grid.
solved_numbers = new_set()
for row_index in range(first_row_index, first_row_index+3):
for col_index in range(first_col_index, first_col_index+3):
box = board[row_index][col_index]
is_solved, solution = is_box_solved(box)
if is_solved:
solved_numbers.add(solution)
continue
else:
continue
# subtract the solved numbers from each box in the grid.
board2 = copy.deepcopy(board)
for row_index in range(first_row_index, first_row_index+3):
for col_index in range(first_col_index, first_col_index+3):
box = board2[row_index][col_index]
is_solved, _ = is_box_solved(box)
if is_solved:
continue
else:
box -= solved_numbers
continue
continue
return board2
def iterate_grids(board):
"""Returns a copy of the board with iterated grids."""
for n in range(9):
board = iterate_grid(board, n)
continue
trace('\nIterating grids:\n')
dump_board(board)
return board
def iterate_board(board):
"""Returns an iterated copy of the board."""
board = iterate_rows(board)
board = iterate_columns(board)
board = iterate_grids(board)
return board
def possibilities_count(board):
"""Returns the total number of possibilities in the board state.
A solved board has a possibility count of 81."""
count = 0
for row in board:
for box in row:
count += len(box)
return count
def read_board_file(fpath):
"""Returns the initial board state as read from the puzzle file."""
fd = open(fpath)
lines = fd.readlines()
fd.close()
rows = []
for line in lines:
row = []
for i in range(9):
number = int(line[i])
if number == 0:
row.append(new_set([1,2,3,4,5,6,7,8,9]))
continue
else:
row.append(new_set([number]))
continue
rows.append(row)
continue
return rows
if __name__ == '__main__':
args = sys.argv[1:]
if len(args) > 1 and args[0] in ['-v', '--verbose']:
g_tracing = True
args = args[1:]
if len(args) != 1:
sys.stderr.write("Error: no board file specified.\n")
sys.exit(1)
board_fpath = args[-1]
board = read_board_file(board_fpath)
trace('Initial board state:\n')
dump_board(board)
iteration_count = 0
while True:
iteration_count += 1
board2 = iterate_board(board)
if possibilities_count(board2) == possibilities_count(board):
sys.stderr.write("Error: don't know how to solve this board.\n")
sys.exit(1)
elif is_board_solved(board2):
trace("\nSolved in %s iterations!\n" % iteration_count)
print_board(board2)
sys.exit(0)
else:
board = board2
continue
530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.