soduku_naive_backtracking.py

import time


# calculate the domain (set of possible values) of the cell at (row, col)
def get_domain(board_state, row, col):

  # initially state of the domain (cell can have any digit from 1-9)
  domain = range(1, 10)

  # eliminate illegal values from the domain based on the values in the cell's square
  square_start_row = int(row / 3)*3
  square_start_col = int(col / 3)*3
  for row_i in range(3):
    for col_i in range(3):
      cell_value = board_state[square_start_row + row_i][square_start_col + col_i]
      if cell_value in domain:
        domain.remove(cell_value)

  # eliminate illegal values from the domain based on the values in the cell's row
  for col_i in range(9):
    cell_value = board_state[row][col_i]
    if cell_value in domain:
      domain.remove(cell_value)

  # eliminate illegal values from the domain based on the values in the cell's column
  for row_i in range(9):
    cell_value = board_state[row_i][col]
    if cell_value in domain:
      domain.remove(cell_value)

  return domain


# solve the puzzle recursively
def solve_puzzle(board_state, current_row, current_column):

  # if finished iterating through, then return the board states
  if(current_row > 8 or current_column > 8):
    return board_state
  
  # the next cell to choose the value of
  next_row = current_row if (current_column < 8) else (current_row + 1)
  next_column = (current_column + 1) if (current_column < 8) else 0

  # if the current cell isn't empty, then continue on to next cell
  if(board_state[current_row][current_column] != 0):
    return solve_puzzle(board_state, next_row, next_column)

  # the current cell is empty, so try out each of the possible values from the domain
  else:
    result = False
    cell_domain = get_domain(board_state, current_row, current_column)
    
    for possible_value in cell_domain:
      new_board_state = [x[:] for x in board_state]
      new_board_state[current_row][current_column] = possible_value
      resulting_board = solve_puzzle(new_board_state, next_row, next_column)

      # if a result was found, return it, otherwise continue with the other domains 
      if resulting_board != False:
        return resulting_board

    # reach here only when the domain set was empty for the cell or all of the values 
    # in the domain yeilded incorrect solutions (causing a board configuration where 
    # an empty cell is reached who's domain was empty).
    return False


def print_board(board_state):
  board_as_string = ""
  for row_i in range(9):
    board_as_string += "\n"
    for col_i in range(9):
      board_as_string += str(board_state[row_i][col_i]) + " "
  print(board_as_string)


easy_puzzle = [
  [0, 2, 0, 1, 7, 8, 0, 3, 0], 
  [0, 4, 0, 3, 0, 2, 0, 9, 0], 
  [1, 0, 0, 0, 0, 0, 0, 0, 6], 
  [0, 0, 8, 6, 0, 3, 5, 0, 0], 
  [3, 0, 0, 0, 0, 0, 0, 0, 4], 
  [0, 0, 6, 7, 0, 9, 2, 0, 0], 
  [9, 0, 0, 0, 0, 0, 0, 0, 2], 
  [0, 8, 0, 9, 0, 1, 0, 6, 0], 
  [0, 1, 0, 4, 3, 6, 0, 5, 0]]

time_start_easy = time.clock()
print_board(solve_puzzle(easy_puzzle, 0, 0))
time_elapsed_easy = (time.clock() - time_start_easy)
print("Time elapsed: " + str(time_elapsed_easy))


hard_puzzle = [
  [0, 0, 0, 0, 0, 0, 6, 8, 0], 
  [0, 0, 0, 0, 7, 3, 0, 0, 9], 
  [3, 0, 9, 0, 0, 0, 0, 4, 5], 
  [4, 9, 0, 0, 0, 0, 0, 0, 0], 
  [8, 0, 3, 0, 5, 0, 9, 0, 2], 
  [0, 0, 0, 0, 0, 0, 0, 3, 6], 
  [9, 6, 0, 0, 0, 0, 3, 0, 8], 
  [7, 0, 0, 6, 8, 0, 0, 0, 0], 
  [0, 2, 8, 0, 0, 0, 0, 0, 0]]

time_start_hard = time.clock()
print_board(solve_puzzle(hard_puzzle, 0, 0))
time_elapsed_hard = (time.clock() - time_start_hard)
print("Time elapsed: " + str(time_elapsed_hard))