Strict Standards: Declaration of Doku_Renderer_metadata::table_open() should be compatible with Doku_Renderer::table_open($maxcols = NULL, $numrows = NULL, $pos = NULL) in /home2/cp-wiki/htdocs/inc/parser/metadata.php on line 480

Strict Standards: Declaration of Doku_Renderer_metadata::table_close() should be compatible with Doku_Renderer::table_close($pos = NULL) in /home2/cp-wiki/htdocs/inc/parser/metadata.php on line 480

CS 190C LAB 8: Friday, March 6, 2009

In-Lab Problem

Today's lab involves solving Sudoku puzzles using recursion. If you are already familiar with Sudoku, you can skip the introduction section.

Download the following file: sudoku.py

Here is a GUI version on which you can watch the recursion working: sudoku_gui.py

Introduction to Sudoku

Sudoku puzzles are 9-by-9 grids that are partially filled with numbers. Grids are divided into nine 3-by-3 sub-grids. The objective of the puzzle is to fill in the rest of the grid such that that the following rules are true:

  1. Only numbers between 1 and 9 are used
  2. No number occurs twice in the same row
  3. … or column
  4. … or 3-by-3 sub-grid (only the 3-by-3 sub-grid shown by the thicker lines, not any arbitrary 3-by-3 sub-grid)

An example of a Sudoku puzzle is shown below. The original puzzle is shown by the black numbers, and the gray numbers are the solution.

Solving a Sudoku Puzzle

There are a variety of different ways to solve Sudoku puzzles manually and automatically. Since writing one from scratch would be far too complicated to finish by the end of a single lab session, all of the algorithm will be described in detail and much of it will be given to you. Before discussing the algorithm, we note that two new concepts are used in this lab.

Sets

If you know what sets are in mathematics, Python sets represent this concept, so you only need to look at the example Python code.

A set is essentially a collection of unique items. It has no particular ordering, like a list does. An example of a set is {1, 2, 3}; a counter-example is {1, 1, 2, 3}. The second collection is not a set, since it has two occurrences of the number 1. In our algorithm, we'll use sets to determine what possible numbers a particular cell can have by adding numbers to a set that are in the cell's row, column, and 3-by-3 grid (actually, these numbers are what the cell can't have). Set operations are shown in Python below:

>>> S = set()
>>> S.add(1) # Add 1 to the set S
>>> S.add(2) # and 2
>>> S.add(3) # and 3
>>> S.add(1) # and 1 again just to show that it only appears once
>>> S        # when we print it down here
set([1, 2, 3])
>>> if 1 in S:  # Use this line to test if an item is in S
	print '1 is in S'
 
1 is in S
>>> if 4 in S:  # Since 4 is not in S, this print never occurs
	print '4 is in S'
 
 
>>>

Matrices

Using numpy and Python lists, you've created pseudo-matrices by creating lists of lists. For the Sudoku solver, we use a matrix from numpy. The only noticeable difference you should see is that instead of retrieving an item at a coordinate using “matrix[row][col]”, you retrieve it using “matrix[row, col]”.

Sudoku puzzles are represented as 9-by-9 matrices. The initial puzzle has certain cells filled in with numbers and the rest are 0, to signify emptiness (since numbers are between 1 and 9, inclusive).

The Sudoku Algorithm

In the file you downloaded, there are three functions and code to load/attempt to solve puzzles. You can use the following puzzles for testing: board1.txt board2.txt

The only function that needs modification is the solve() function. The algorithm for solve() is explained below and is commented in code:

  1. Find the next coordinate starting from [row, col] that is empty (has a 0) or stop if we pass the end of the puzzle. From [row, col] we look left to right, top to bottom for the first empty cell.
  2. If we passed the end of the puzzle (if we get to row 9) in the loop, all cells in the puzzle are filled, so the puzzle is solved. Therefore, we can return true.
  3. Otherwise, we start try put all possible numbers for the cell at [row, col] are. To do this, we declare a set F, which stands for forbidden values. The three loops following the declaration add numbers to the set from the same row, column and 3-by-3 sub-grid.
  4. After getting a final set F, loop through all possible numbers for a Sudoku puzzle (which means 1 through 9, not anything related to F):
    1. If the current number of the loop is not in F, that means it's a possible candidate for the cell, so:
      1. We assume that the current number is the correct value for the cell, so we set that cell equal to that number.
      2. Next, we get the next coordinate (not necessarily empty, since step 1 finds the empty cell) from the current coordinate. This can be done using the next_coordinate() function, as it was above.
      3. Now, attempt to solve the puzzle starting at the next coordinate by making a recursive call.
      4. If the attempt was successful (it returns true), then also return true, because the puzzle has been completely solved. Otherwise, do nothing (which will continue to the next iteration of the loop trying all legal values).
  5. If we've completed all of the above steps without having returned true, that means we've exhausted all possible values for the current cell with no success, so change it back to an empty cell and return false.

Your task is to complete step 4 in its entirety. All other steps have been completed, so don't try and write them on your own.

Recursive Pattern

This section is not related to the actual lab (but it is related to the percolation project), so complete the lab before you read this.

The second part of the percolation project involves writing a recursive algorithm. There are similarities between the Sudoku algorithm and one possible percolation algorithm. Specifically, this pertains mostly to a percolation algorithm that will exit immediately after discovering that an input grid percolates. Hopefully this will help you complete project 2 part 2. The pattern is shown below (Note: this is a pattern similarity between specifically these two algorithms, not all recursive algorithms):

  1. If the current coordinate has reached the end, return indicating success. For Sudoku, this means the row after the last row; you can use the same idea for percolation too, but this is a design decision. The concept remains the same.
  2. A set of values is used to test a cell. In a Sudoku puzzle, it's somewhat complicated to determine this set, since it involves retrieving numbers from the same row, column, and 3-by-3 sub-grid as the current cell. For percolation, it's quite easy: there can either be flow or not.
  3. The algorithm recurses on (calls) itself, assuming that the value in the current cell is correct. The function call that does the recursion does so on neighboring cells that make sense. For the Sudoku puzzle, there is only one cell that makes sense, so this is trivial. However, for the percolation algorithm, it must possibly consider cells directly to the north, south, east, and west of the current cell. This means that you probably have to recurse more than once.
  4. If one of the recursive calls indicates that it has been successful, then we can propagate this indication. For both cases, this simply means returning true.
  5. If none of the possible values has resulted in success, we've exhausted our options for this cell given the assumption that all previous cells are correct, so revert state if necessary and indicate failure. In Sudoku, reverting the cell state to be empty is necessary to make future guesses at that cell. Is this a good idea for percolation?

Solution

from numpy import matrix, zeros, int16
import sys
import time
 
def next_coordinate(row, col):
    """
    Returns the next coordinate to explore in a sudoku puzzle, regardless of
    whether or not the cell is actually empty. The order is left to right,
    top to bottom.
    """
    if col == 8:
        return row + 1, 0
    else:
        return row, col + 1
 
def solve(M, row=0, col=0):
    """
    Recursively solves a Sudoku puzzle starting at the given row and column.
    Note that two assumptions are made:
 
    1. All positions to the left and above of the starting position are filled
    2. All filled in cells are valid (no duplicates as in the Sudoku rules)
 
    Note that the second assumption does NOT imply that the puzzle is solvable.
 
    M - A numpy matrix representing a Sudoku board. Initially, cells with
        value 0 are considered empty, and cells with other values are
        considered fixed.
    row - the current row
    col - the current column
    """
    # Find the first empty cell from [row, col]. Stop if we pass the end of the
    # puzzle.
    while row < 9 and M[row,col] != 0:
        row, col = next_coordinate(row, col)
 
    # If we passed the last row (row 8) then we've solved the puzzle, so just
    # return true.
    if row == 9:
        return True
 
    # Otherwise, we need to do the standard guessing logic below:
    # Find forbidden values.
    F = set()
 
    # Find all values in the same column
    for k in range(9):
        F.add(M[row,k])
 
    # Find all values in the same row
    for k in range(9):
        F.add(M[k,col])
 
    # Slightly trickier, we also need the numbers in the 3x3 grid containing
    # the number. box_row and box_col are the row and column of the top left
    # cell in the current box.
    box_row = row - row%3
    box_col = col - col%3
 
    # Now check the 3x3 box starting at box_row, box_col
    for k in range(3):
        for l in range(3):
            F.add(M[box_row+k, box_col+l])
 
    # General idea:
    # For the cell at location [row, col] consider all possible values between
    # 1 and 9 not creating a conflict with earlier values currently in M.
    # For every legal choice, check whether it leads to a solution by making a
    # recursive call.
    #
    # If a solution exists, the recursive call returns True and True is
    # returned (this means no further values need to be considered for cell
    # M[row, col].
    #
    # If no solution exists, the next possible value is tried. After all
    # possible values have been considered and none led to success, False is
    # returned.
    for val in xrange(1, 10):
        # Locate the next lowest value that is available
        if not val in F:
            M[row,col] = val
 
            # Find out whether the choice  M[row,col] = val leads to a solution
            # Set up the arguments for the recursive vall
            next_row, next_col = next_coordinate(row, col)
 
            # make the recursive call and check what it returns
            # take actions as described above
            if solve(M, next_row, next_col):
                return True
 
    # We get to this statement if no possible assignment to M[row,col] led to
    # a solution. Set the cell back to empty and return False.
    M[row,col] = 0
    return False
 
def read_board(filename):
    f = open(filename)
    M = matrix(zeros((9,9),dtype=int16))
    k = 0
    for s in f:
        l = []
        for t in s.split():
            l.append(int(t))
        M[k] = l
        k += 1
 
    return M
 
if __name__ == '__main__':
    if len(sys.argv) < 2:
        filename = raw_input('Input file? ')
    else:
        filename = sys.argv[1]
 
    M = read_board(filename)
 
    start = time.clock()
    if solve(M):
        print M
    else:
        print 'No solution.'
    end = time.clock()
 
    print 'Completed in', end - start, 'seconds.'
 
cs190c/lab8_09.txt · Last modified: 2009/03/10 20:46 by seh
 
Recent changes RSS feed Creative Commons License Donate Powered by PHP Valid XHTML 1.0 Valid CSS Driven by DokuWiki