# Recursive Depth First Search for finding valid sudoku boards in Python 3

I am not an experienced programmer, and I decided to make a program that could find all possible sudoku arrangements just for fun. As far as I can see, the program is working all right, but I'd like to know how could I improve it, since there are some parts that are a little "polluted". Specially the way I deal with the blocks of the board.

#####################################################################################
### Sudoku Valid Boards Generator using recursive depth-first search approach     ###
### by Anderson Freixo                                                            ###
### anderson.freixo@gmail.com                                                     ###
#####################################################################################

## The board is represented by lists of lists from board[0][0] to board[9][9].
## There are three functions which tests the rules for choosing a valid number in sudoku.
## Then, after we call the search function for the first time, and it checks for valid numbers
## it calls itself again adding the new valid number to the board.
## (The commented prints are just for debugging)

blocks = []
solutions = []

for n in range(3):                                                                      #Initializes the 'blocks' list which contains the groups
for m in range(3):                                                                    #of positions of each of the nine blocks of the game
blocks.append(list(itertools.product((0+3*n,1+3*n,2+3*n),(0+3*m,1+3*m,2+3*m))))     #the result is a list of 9 lists with 9 tuples each
#containing the position
#(I know it's really awkward, but I couldn't think of a clear
# and fast way of doing it)

#Functions to test the selected number:

def is_in_line(num, board, line):                              # #1 - Is the number already in the line?
if num in board[line]:
#print("Number", num, "already in the line!")
return True

def is_in_column(num, board, line, column):                    # #2 - Is the number already in the column?
for line_idx in range(len(board)):
if line_idx < line:
if board[line_idx][column] == num:
#print("Number", num, "already in the column!")
return True

def is_in_block(num, board, line, column):                     # #3 - Is the number already in the block?
global blocks

for block in blocks:
if (line, column) in block:                              # First finds out to which block the current position belongs to
myblock = block
break

for l, c in myblock:                                       # Then, tests if the position is filled
if l < len(board) and c < len(board[l]):                 # and checks if the number in the position
if board[l][c] == num:                                 # is the number being tested
#print("Number", num, "in the same block!")
return True

def search(board):
if len(solutions) > 1000: return                             # Just a random limit for the program to stop
# (there are more than 6x10**21 possible solutions)

global solutions                                             # If the board is complete, than this board is a solution
if len(board) == 9 and len(board[8]) == 9:
print("A solution was found!")
solutions.append(board)
print("Solution n.", len(solutions),":")
print(board)
return

myboard = list(board)                                        #   I had to create this new board to be able to append a new line in the board
#   without interfering in the original one. This is necessary when the
#   length of the line is 9 because of the situation below.

next_line = len(board)-1                                     #   Finds out which is the next position to evaluate
if len(board[next_line]) == 9:                               #   Filling up one line at a time. If the line has been filled
next_line+=1                                               #   (length = 9) then the position to be analyzed must be
myboard.append([])                                         #   line+1 column 0.
next_column = 0                                            #   (If I didn't append the empty list, there would be problems
else:                                                        #   regarding the index range in the test functions)
next_column = len(board[next_line])

for n in range(1,10):                                        #   If any of the tests return True, skip to the next iteration
if is_in_line(n, myboard, next_line): continue
if is_in_column(n, myboard, next_line, next_column): continue
if is_in_block(n, myboard, next_line, next_column): continue

#   Otherwise...
new_board = copy.deepcopy(myboard)                         #   Create a new board with the valid number in it
new_board[next_line].append(n)                             #   (Found it necessary to generate a deep copy, otherwise all the new numbers
search(new_board)                                          #   would be added to the same list)
#   and then call the function again

return

search([[]])                                                   #   starts the search with an empty board


# Style

Your indentation is variable, some times 2 spaces, some times 4. I suggest you stick to 4 as per PEP8 conventions. continues on the same line than the ifs feels also odd.

Most of your comments can be converted into docstrings. This give more valuable information that can be accessed at runtime too (e.g. using the help builtin in a python shell).

In the same vein, some magic variable such as __author__ or __credits__ can have more meaning than a comment.

Compare the help on your module:

Help on module sudoku_depth_first_solver_original:

NAME
sudoku_depth_first_solver_original

DESCRIPTION
#####################################################################################
### Sudoku Valid Boards Generator using recursive depth-first search approach     ###
### by Anderson Freixo                                                            ###
### anderson.freixo@gmail.com                                                     ###
#####################################################################################

FUNCTIONS
is_in_block(num, board, line, column)

is_in_column(num, board, line, column)

is_in_line(num, board, line)

search(board)

DATA
blocks = [[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2,...
m = 2
n = 2
solutions = [[[1, 2, 3, 4, 5, 6, 7, 8, 9], [4, 5, 6, 7, 8, 9, 1, 2, 3]...

FILE
/home/mettinger/code_testing/codereview/sudoku_depth_first_solver_original.py


with the help on a rewrite I present latter:

Help on module sudoku_depth_first_solver:

NAME
sudoku_depth_first_solver - Sudoku Valid Boards Generator

DESCRIPTION
This module is using a recursive depth-first search approach
to generate every valid board from a starting template.

FUNCTIONS
find_block(line, column)
Retrieve the block which contain the cell at the given line and column

initialize(board)
Ensure a board has at least 9 lines and 9 columns

is_in_block(num, board, line, column)
Test if the given number lies in the given block of the given board

is_in_column(num, board, column)
Test if the given number lies in the given column of the given board

is_in_line(num, board, line)
Test if the given number lies in the given line of the given board

search(board)
Generate all valid solutions that can fit in the given board

DATA
BLOCKS = [[(0, 0), (0, 1), (0, 2), (1, 0), (1, 1), (1, 2), (2, 0), (2,...

AUTHOR
Anderson Freixo <anderson.freixo@gmail.com>

CREDITS
Contributors:
* Mathias Ettinger (https://codereview.stackexchange.com/users/84718/mathias-ettinger)

FILE
/home/mettinger/code_testing/codereview/sudoku_depth_first_solver.py


Lastly, the last line (search([[]])) should be under an if __name__ == '__main__' clause.

# Itertools

You know how to use this module so you could came up with that yourself, but your two for loops to build the block constant are essentially itertools.product(range(3), repeat=2). So you can write:

blocks = []

for n, m in itertools.product(range(3), repeat=2):
blocks.append(list(itertools.product((0+3*n,1+3*n,2+3*n),(0+3*m,1+3*m,2+3*m))))


which, in turn, can be a list-comprehension to better highlight the fact that blocks is a constant (so better name it ALL_CAPS, now we’re at it):

BLOCKS = [
list(itertools.product(
(3*n, 3*n + 1, 3*n + 2),
(3*m, 3*m + 1, 3*m + 2),
)) for n, m in itertools.product(range(3), repeat=2)
]


# Searching for numbers

• It's very redundant to return True in an if block (and return False in the associated else or implicitly return None), just return the value of the boolean you compute.
• You do not need to know the number of lines in the board beforehand to search for a number in a column. Just iterate over each line and get the columnth number.
• You can extract a function searching for the right block to simplify the function searching for a number in a block.

# Simplifications

If you consider that valid boards always have 9 rows and 9 columns, you do not need to worry about IndexErrors. As such, I would suggest writting a function that ensure that and fill the board with None in case it isn't the right size.

After that, all what's left is to use indexes in your recursion rather than computing lengths. An helper function dedicated to the recursion called by search with initial parameters could be of great use here.

I would also consider using generators instead of filling lists of results. The advantage here is that, if you want to access the result #453215, you can ask itertools.islice to do so and it won't eat up your RAM.

# Improvements

I don't see any benefit to provide the original [[]] in your current code. As it assume it is always the starting state. Instead, we could use this parameter at our advantage to turn your code into a solver of partial grids at very tiny cost. The only thing necessary (beside ensuring a 9×9 grid) is to "skip" cells that already have a number in it.

# Proposed improvements

"""Sudoku Valid Boards Generator

This module is using a recursive depth-first search approach
to generate every valid board from a starting template.
"""

__author__ = 'Anderson Freixo <anderson.freixo@gmail.com>'
__credits__ = '''Contributors:
* Mathias Ettinger (https://codereview.stackexchange.com/users/84718/mathias-ettinger)
'''

import copy
import itertools

# List of indices (line, column) for each cell in each
# 3×3 block of a sudoku grid.
BLOCKS = [
list(itertools.product(
range(3*n, 3*(n+1)),
range(3*m, 3*(m+1)),
)) for n, m in itertools.product(range(3), repeat=2)
]

def is_in_line(num, board, line):
"""Test if the given number lies in the given line of the given board"""
return num in board[line]

def is_in_column(num, board, column):
"""Test if the given number lies in the given column of the given board"""
for line in board:
if line[column] == num:
return True
return False

def is_in_block(num, board, line, column):
"""Test if the given number lies in the given block of the given board"""
for l, c in find_block(line, column):
if board[l][c] == num:
return True
return False

def find_block(line, column):
"""Retrieve the block which contain the cell at the given line and column"""
cell = (line, column)
for block in BLOCKS:
if cell in block:
return block

def initialize(board):
"""Ensure a board has at least 9 lines and 9 columns"""
# Copy the parameter in order to not update it in place
board = copy.deepcopy(board)
while len(board) < 9:
board.append([None] * 9)

for line in board:
line.extend([None] * (9 - len(line)))

return board

def search(board):
"""Generate all valid solutions that can fit in the given board"""

def _search_helper(board, line, column):
"""Recursivelly try all number for the cell at the
given line and column and generate the solution if
the grid has been filled.
"""

if (line, column) == (9, 0):
# Reached the end of the recursion so
# this board must be complete.
yield copy.deepcopy(board)
return

new_column = (column + 1) % 9
new_line = line if new_column else line + 1
if board[line][column]:
# Skip cells that already have a number before the search
yield from _search_helper(board, new_line, new_column)
return

for number in range(1, 10):
if is_in_line(number, board, line):
continue
if is_in_column(number, board, column):
continue
if is_in_block(number, board, line, column):
continue

board[line][column] = number
yield from _search_helper(board, new_line, new_column)
# Reset cell so this number doesn't interact
# with subsequent recursive searches
board[line][column] = None

yield from _search_helper(initialize(board), 0, 0)

if __name__ == '__main__':
from pprint import pprint

# print the first 1000 valid grid generated
for i, solution in enumerate(search([[]])):
print('Solution n°{}:'.format(i))
pprint(solution)
if i > 999:
break

print('-' * 80)

# Solve a given grid
grid = [
[3, 4, 0, 8, 2, 6, 0, 7, 1],
[0, 0, 8, 0, 0, 0, 9, 0, 0],
[7, 6, 0, 0, 9, 0, 0, 4, 3],
[0, 8, 0, 1, 0, 2, 0, 3, 0],
[0, 3, 0, 0, 0, 0, 0, 9, 0],
[0, 7, 0, 9, 0, 4, 0, 1, 0],
[8, 2, 0, 0, 4, 0, 0, 5, 9],
[0, 0, 7, 0, 0, 0, 3, 0, 0],
[4, 1, 0, 3, 8, 9, 0, 6, 2],
]
for i, solution in enumerate(search(grid)):
print('Solution n°{}:'.format(i))
pprint(solution)


grid to solve found here

• Thank you for your answer! It's very complete and I'm learning a lot from it . I don't understand completely the code you suggested yet, because 'm still trying to understand the functioning of "yield from". But besides that, I got curious to know why it isn't ok to implicitly return None instead of returning False in the end of is_in_column() and is_in_block(), and why a deep copy was necessary in initialize(board). Aug 31 '17 at 18:17
• @AndersonFreixo You can think of yield from iterable as pretty much for x in iterable: yield x Aug 31 '17 at 18:24
• @AndersonFreixo and for return False vs nothing, it's to convey the intent more unambiguously. But the comment was mostly for the is_in_line function. Aug 31 '17 at 18:26