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

Question

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                                                            ###
### [email protected]                                                     ### 
#####################################################################################

## 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

Answer 1

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                                                            ###
    ### [email protected]                                                     ### 
    #####################################################################################

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 <[email protected]>

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 column^th 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 <[email protected]>'
__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}