Sudoku puzzle convert string of values into a dictionary of key/value pairs. Udacity Artificial Intelligence nanodegree project 1, quiz 1: Encoding the Board.

1-sudoku-box.py

from utils import *

# `grid` is defined in the test code scope as the following:
# (note: changing the value here will _not_ change the test code)
# grid = '..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..'

def grid_values(grid):
    """Convert grid string into {<box>: <value>} dict with '.' value for empties.

    Args:
        grid: Sudoku grid in string form, 81 characters long
    Returns:
        Sudoku grid in dictionary form:
        - keys: Box labels, e.g. 'A1'
        - values: Value in corresponding box, e.g. '8', or '.' if it is empty.
    """
    assert len(grid) == 81, "Input must be 81 characters"
    
    result = {}
    rowNum = 0

    for i in range(0, len(grid)):
        if i > 0 and i % len(cols) == 0:
            rowNum = rowNum + 1

        rowName = rows[rowNum]
        colName = cols[i % len(cols)]
        
        key = rowName + colName

        result[key] = grid[i]

    return result

2-sudoki-box.py

from utils import *
from math import *

def grid_values(grid):
    """Convert grid string into {<box>: <value>} dict with '123456789' value for empties.

    Args:
        grid: Sudoku grid in string form, 81 characters long
    Returns:
        Sudoku grid in dictionary form:
        - keys: Box labels, e.g. 'A1'
        - values: Value in corresponding box, e.g. '8', or '123456789' if it is empty.
    """
    assert len(grid) == 81, "Input must be 81 characters"
    
    result = {}
    rowNum = 0

    for i in range(0, len(grid)):
        if i > 0 and i % len(cols) == 0:
            rowNum = rowNum + 1

        rowName = rows[rowNum]
        colName = cols[i % len(cols)]
        
        key = rowName + colName

        result[key] = grid[i] if grid[i] != '.' else cols

    return result

3-eliminate.py

from utils import *
from math import *

def eliminate(values):
    """Eliminate values from peers of each box with a single value.

    Go through all the boxes, and whenever there is a box with a single value,
    eliminate this value from the set of values of all its peers.

    Args:
        values: Sudoku in dictionary form.
    Returns:
        Resulting Sudoku in dictionary form after eliminating values.
    """
    # Get a list of all cells with a single value in them.
    readKeys = {}
    for row in range(0, len(rows)):
        for col in range(0, len(cols)):
            key = rows[row] + cols[col]
            value = values[key]

            if len(value) == 1:
                readKeys[key] = value

    # Now go through the list of target keys and remove their value from all peers.
    for key in readKeys.keys():
        row = key[0]
        col = key[1]
        value = readKeys[key]
        
        #print('Working on ' + row + col)
        
        # Remove this value from all cells in the row.
        #print('Row')
        for colIndex in range(0, len(cols)):
            indexKey = row + cols[colIndex]
            if not indexKey in readKeys.keys():
                values[indexKey] = values[indexKey].replace(value, '')
                #print('Replaced ' + value + ' in cell ' + indexKey + ': ' + values[indexKey])
        
        #print('Column')
        # Remove this value from all cells in the column.
        for rowIndex in range(0, len(rows)):
            indexKey = rows[rowIndex] + col
            if not indexKey in readKeys.keys():
                values[indexKey] = values[indexKey].replace(value, '')
                #print('Replaced ' + value + ' in cell ' + indexKey + ': ' + values[indexKey])

        #print('Box')
        # Remove this value from all cells in the 3x3 box.
        boxX = floor(cols.index(col) / 3) * 3
        boxY = floor(rows.index(row) / 3) * 3
        
        for y in range(boxY, boxY + 3):
            for x in range(boxX, boxX + 3):
                indexKey = rows[y] + cols[x]
                if not indexKey in readKeys.keys():
                    values[indexKey] = values[indexKey].replace(value, '')
                    #print('Replaced ' + value + ' in cell ' + indexKey + ': ' + values[indexKey])

    return values

4-only-choice.py

from utils import *
from math import *

def only_choice(values):
    """Finalize all values that are the only choice for a unit.

    Go through all the units, and whenever there is a unit with a value
    that only fits in one box, assign the value to this box.

    Input: Sudoku in dictionary form.
    Output: Resulting Sudoku in dictionary form after filling in only choices.
    """
    
    # Go through all cells in the grid.
    for row in range(0, len(rows)):
        for col in range(0, len(cols)):
            key = rows[row] + cols[col]
            value = values[key]

            # If this value has multiple digits, check for an only-choice.
            if len(value) > 1:
                # Check against all other cells in the row.
#                print('Row')
                hash1 = {}
                # Go through each digit in the cell.
                for value1 in [char for char in value]:
                    # Check this digit against each value in the row.
                    for colIndex in range(0, len(cols)):
                        indexKey = rows[row] + cols[colIndex]
#                        print('Checking cell ' + indexKey + ' with value ' + values[indexKey] + ' against ' + key + ' with value ' + value + ' for ' + value1)
                        if values[indexKey].find(value1) != -1:
                            hashKey = str(value1)
                            hash1[hashKey] = { 'key': key, 'count': (hash1[hashKey]['count'] + 1 if hashKey in hash1 else 1) }

#                print(hash1)

                # Check against all other cells in the column.
#                print('Column')
                hash2 = {}
                # Go through each digit in the cell.
                for value1 in [char for char in value]:
                    # Check this digit against each value in the row.
                    for rowIndex in range(0, len(rows)):
                        indexKey = rows[rowIndex] + cols[col]
#                        print('Checking cell ' + indexKey + ' with value ' + values[indexKey] + ' against ' + key + ' with value ' + value + ' for ' + value1)
                        if values[indexKey].find(value1) != -1:
                            hashKey = str(value1)
                            hash2[hashKey] = { 'key': key, 'count': (hash2[hashKey]['count'] + 1 if hashKey in hash2 else 1) }

#                print(hash2)

                # Check against all other cells in the box.
#                print('Box')
                hash3 = {}
                # Remove this value from all cells in the 3x3 box.
                boxX = floor(cols.index(key[1]) / 3) * 3
                boxY = floor(rows.index(key[0]) / 3) * 3

                # Go through each digit in the cell.
                for value1 in [char for char in value]:
                    # Check this digit against each value in the row.
                    for y in range(boxY, boxY + 3):
                        for x in range(boxX, boxX + 3):
                            indexKey = rows[y] + cols[x]
#                            print('Checking cell ' + indexKey + ' with value ' + values[indexKey] + ' against ' + key + ' with value ' + value + ' for ' + value1)
                            if values[indexKey].find(value1) != -1:
                                hashKey = str(value1)
                                hash3[hashKey] = { 'key': key, 'count': (hash3[hashKey]['count'] + 1 if hashKey in hash3 else 1) }

                # Find any hash counts with a score of 1 and set their value in the cell key.
                for hashKey in hash1.keys():
                    if hash1[hashKey]['count'] == 1:
                        setKey = hash1[hashKey]['key']
#                        print('Only choice for ' + key + ' is ' + hashKey)
                        values[key] = hashKey
    
                # Find any hash counts with a score of 1 and set their value in the cell key.
                for hashKey in hash2.keys():
                    if hash2[hashKey]['count'] == 1:
                        setKey = hash2[hashKey]['key']
#                        print('Only choice for ' + key + ' is ' + hashKey)
                        values[key] = hashKey
    
                # Find any hash counts with a score of 1 and set their value in the cell key.
                for hashKey in hash3.keys():
                    if hash3[hashKey]['count'] == 1:
                        setKey = hash3[hashKey]['key']
#                        print('Only choice for ' + key + ' is ' + hashKey)
                        values[key] = hashKey

    return values

5-constraint-propagation.py

from utils import *

def reduce_puzzle(values):
    stalled = False
    count = 1
    
    while not stalled:
        # Check how many boxes have a determined value
        solved_values_before = len([box for box in values.keys() if len(values[box]) == 1])

        # Your code here: Use the Eliminate Strategy
        values = eliminate(values)
        
        # Your code here: Use the Only Choice Strategy
        values = only_choice(values)
        
        # Check how many boxes have a determined value, to compare
        solved_values_after = len([box for box in values.keys() if len(values[box]) == 1])
        
        # If no new values were added, stop the loop.
        stalled = solved_values_before == solved_values_after
        
        # Stop looping if the puzzle is solved.
        if solved_values_after == len(values):
            #print('Solution found after ' + str(count) + ' iterations.')
            stalled = True
        
        # Sanity check, return False if there is a box with zero available values:
        if len([box for box in values.keys() if len(values[box]) == 0]):
            return False
            
        count = count + 1
            
    return values

6-search.py

from utils import *

def search(values):
    "Using depth-first search and propagation, create a search tree and solve the sudoku."
    
    # First, reduce the puzzle using the previous function
    values = reduce_puzzle(values)
    if not values:
        # Failed to find a solution.
        return False
    elif all(len(values[value]) == 1 for value in boxes):
        # Solved.
        return values
    else:
        # Choose one of the unfilled squares with the fewest possibilities
        fringe = {}

        # Collect all values with multiple values. These will be candidates for branching.
        for row in range(0, len(rows)):
            for col in range(0, len(cols)):
                key = rows[row] + cols[col]
                value = values[key]
    
                if len(value) > 1:
                    fringe[key] = value
    
        # Sort the choices by length.                
        fringe_sorted = sorted(fringe.items(), key=lambda x: len(x[1]))
    
        # Select the next child to solve.
        child = fringe_sorted.pop(0)
        key = child[0]
        value = child[1]
    
        # Now use recursion to solve each one of the resulting sudokus, and if one returns a value (not False), return that answer!
        # Add a child board for each potential value.
        for digit in [char for char in value] :
            # Replace the multi-values with the selected value to try.
            #print('Trying ' + key + '=' + digit)
            new_values = values.copy()
            new_values[key] = digit
            
            result = search(new_values)
            if result:
                # Solved.
                return result

output.txt

display(grid_values('..3.2.6..9..3.5..1..18.64....81.29..7.......8..67.82....26.95..8..2.3..9..5.1.3..'))

Looks good!

. . 3 |. 2 . |6 . . 
9 . . |3 . 5 |. . 1 
. . 1 |8 . 6 |4 . . 
------+------+------
. . 8 |1 . 2 |9 . . 
7 . . |. . . |. . 8 
. . 6 |7 . 8 |2 . . 
------+------+------
. . 2 |6 . 9 |5 . . 
8 . . |2 . 3 |. . 9 
. . 5 |. 1 . |3 . . 



Eliminate

input

123456789 123456789     3     |123456789     2     123456789 |    6     123456789 123456789 
    9     123456789 123456789 |    3     123456789     5     |123456789 123456789     1     
123456789 123456789     1     |    8     123456789     6     |    4     123456789 123456789 
------------------------------+------------------------------+------------------------------
123456789 123456789     8     |    1     123456789     2     |    9     123456789 123456789 
    7     123456789 123456789 |123456789 123456789 123456789 |123456789 123456789     8     
123456789 123456789     6     |    7     123456789     8     |    2     123456789 123456789 
------------------------------+------------------------------+------------------------------
123456789 123456789     2     |    6     123456789     9     |    5     123456789 123456789 
    8     123456789 123456789 |    2     123456789     3     |123456789 123456789     9     
123456789 123456789     5     |123456789     1     123456789 |    3     123456789 123456789 

output

   45    4578    3   |   49     2     147  |   6     5789    57  
   9    24678    47  |   3      47     5   |   78    278     1   
   25    257     1   |   8      79     6   |   4    23579   2357 
---------------------+---------------------+---------------------
  345    345     8   |   1     3456    2   |   9    34567  34567 
   7    123459   49  |  459   34569    4   |   1    13456    8   
  1345  13459    6   |   7     3459    8   |   2     1345   345  
---------------------+---------------------+---------------------
  134    1347    2   |   6     478     9   |   5     1478    47  
   8     1467    47  |   2     457     3   |   17    1467    9   
   46    4679    5   |   4      1      47  |   3    24678   2467 
   
only choice

input

   45    4578    3   |   49     2     147  |   6     5789    57  
   9    24678    47  |   3      47     5   |   78    278     1   
   25    257     1   |   8      79     6   |   4    23579   2357 
---------------------+---------------------+---------------------
  345    345     8   |   1     3456    2   |   9    34567  34567 
   7    123459   49  |  459   34569    4   |   1    13456    8   
  1345  13459    6   |   7     3459    8   |   2     1345   345  
---------------------+---------------------+---------------------
  134    1347    2   |   6     478     9   |   5     1478    47  
   8     1467    47  |   2     457     3   |   17    1467    9   
   46    4679    5   |   4      1      47  |   3    24678   2467 
   
output

  4     8     3   |  9     2     1   |  6     5     7   
  9     6     7   |  3     4     5   |  8     2     1   
  2     5     1   |  8     7     6   |  4     9     3   
------------------+------------------+------------------
  5    345    8   |  1    3456   2   |  9     7     6   
  7     2     9   |  5   34569   4   |  1   13456   8   
  1   13459   6   |  7    3459   8   |  2    1345   5   
------------------+------------------+------------------
  3     7     2   |  6     8     9   |  5     1     4   
  8     1     4   |  2     5     3   |  7     6     9   
  6     9     5   |  4     1     7   |  3     8     2   
  
constraint propagation

input

  4     8     3   |  9     2     1   |  6     5     7   
  9     6     7   |  3     4     5   |  8     2     1   
  2     5     1   |  8     7     6   |  4     9     3   
------------------+------------------+------------------
  5    345    8   |  1    3456   2   |  9     7     6   
  7     2     9   |  5   34569   4   |  1   13456   8   
  1   13459   6   |  7    3459   8   |  2    1345   5   
------------------+------------------+------------------
  3     7     2   |  6     8     9   |  5     1     4   
  8     1     4   |  2     5     3   |  7     6     9   
  6     9     5   |  4     1     7   |  3     8     2   

output
  
4 8 3 |9 2 1 |6 5 7 
9 6 7 |3 4 5 |8 2 1 
2 5 1 |8 7 6 |4 9 3 
------+------+------
5 4 8 |1 3 2 |9 7 6 
7 2 9 |5 6 4 |1 3 8 
1 3 6 |7 9 8 |2 4 5 
------+------+------
3 7 2 |6 8 9 |5 1 4 
8 1 4 |2 5 3 |7 6 9 
6 9 5 |4 1 7 |3 8 2