cellularmitosis/README.md

## README.md

      
    Raw
  

              README.md
            
          
    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:


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.

  
## sudoku-mut.py
#!/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

## sudoku.py
#!/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

## wikipedia-board.txt
530070000
600195000
098000060
800060003
400803001
700020006
060000280
000419005
000080079
	#!/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