Sudoku Solver

sudoku.py

import time


#### Works #### 


start = time.time()

''' Moderate Puzzle ''' # Takes about 0.641 to solve
puzzel = '8..4.6..7......4...1....65.5.9.3.78.....7.....48.2.1.3.52....9...1......3..9.2..5'

''' Easy Puzzle ''' # Takes about 0.328 to solve
##puzzel = '1.742..9.4.......2.5.7..1.39...5..6..4.8.6.2.3.5....1.2...13..6..3.9..7.6....84.5'

''' Most Difficult Puzzle ''' # Takes 45.27 to solve
##puzzel = '8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..'


grid = [] # grid of numbers i.e. the puzzel
possible_grid = [] # grid with possibilities for each cell

# parsing puzzel and storing it in List of Lists (2-D array)
for i in range(0, 81, 9):
    col = []
    for entry in puzzel[i:9+i]:
        if entry == '.':
            col.append(0)
        else:
            col.append(int(entry))
    grid.append(col)

# Print the grid   
for col in grid:
    print col
print '------------------------------'

# Every cell can have possibility of numbers from 1-9
# Eliminating a few obvious numbers by looking at
# Row, Column, and Box
def narrow_possible(x, y, grid):
    if grid[x][y] > 0:
        return []
    row = grid[x]
    col = []
    for i in range(9):
        col.append(grid[i][y])
    center_x, center_y = 3 * (x/3) + 1, 3 * (y/3) + 1
    box = [grid[center_x - 1][center_y - 1], grid[center_x - 1][center_y], grid[center_x - 1][center_y + 1], grid[center_x][center_y - 1], grid[center_x][center_y], grid[center_x][center_y + 1],grid[center_x + 1][center_y - 1], grid[center_x + 1][center_y], grid[center_x + 1][center_y + 1]]
    possible = [i for i in range(1, 10)]
    for i in range(1, 10):
        if i in row or i in col or i in box:
            possible.remove(i)
    return possible

# This is used to narrow down the possiblities from possible_grid
# Works similar to narrow_possible()
def eliminate_possible(x, y, grid, possible_grid):
    center_x, center_y = 3 * (x/3) + 1, 3 * (y/3) + 1
    for i in range(9):
        if grid[x][y] in possible_grid[x][i]: possible_grid[x][i].remove(grid[x][y])
        if grid[x][y] in possible_grid[i][y]: possible_grid[i][y].remove(grid[x][y])
    box = [(center_x - 1, center_y - 1), (center_x - 1, center_y), (center_x - 1, center_y + 1), (center_x, center_y - 1), (center_x, center_y), (center_x, center_y + 1), (center_x + 1, center_y - 1), (center_x + 1, center_y), (center_x + 1, center_y + 1)]
    for rc in box:
        if grid[x][y] in possible_grid[rc[0]][rc[1]]: possible_grid[rc[0]][rc[1]].remove(grid[x][y])
    return possible_grid

# This part uses narrow_possilbe() to generate possiblites for
# all blank cells
for row in range(9):
    grid_row = []
    for col in range(9):
        grid_row.append(narrow_possible(row, col, grid))
    possible_grid.append(grid_row)

# Wherever there is only one possibility that is the answer for that cell
# and when u choose that answer, the number will be eliminated from its
# row, column and box
flag = True
while flag:
    n = False
    for r_index, row in enumerate(possible_grid):
        for c_index, col in enumerate(row):
            if len(col) == 1:
                grid[r_index][c_index] = col[0]
                possible_grid = eliminate_possible(r_index, c_index, grid, possible_grid)
                n = True
    if not n: flag = False


for row in grid:
    print row
print '------------------------------'

# This makes a copy of possilble_grid
def copy(a):
    b = []
    for i in range(9):
        row = []
        for j in range(9):
            row.append(list(a[i][j]))
        b.append(row)
    return b

# This makes a copy of grid
def copy_grid(a):
    b = []
    for i in a:
        b.append(list(i))
    return b

# solve() does a DFS and eliminates possibilites
def solve(grid, possible_grid):


    min_x, min_y = 1000, 1000

    
    for i in range(9):
        for j in range(9):
            if grid[i][j] == 0:
                min_x = i
                min_y = j
                break

    if min_x == 1000:
        for row in grid:
            print row
        print time.time() - start
        exit()
    for possibility in possible_grid[min_x][min_y]:
        grid[min_x][min_y] = possibility
        
        copy_possible_grid = eliminate_possible(min_x, min_y, grid, copy(possible_grid))

        solve(copy_grid(grid), copy_possible_grid)
        


solve(grid, possible_grid)

sudoku_refactored.py

import time

start = time.time()

def parse_puzzle(puzzle):
    grid = []
    for i in range(0, 81, 9):
        col = []
        for entry in puzzle[i:9+i]:
            if entry == '.': col.append(0)
            else: col.append(int(entry))
        grid.append(col)
    return grid

def print_grid(grid):
    for row in grid: print row
    print '------------------------------'

def get_center_coordinates(x, y):
    return 3*(x/3)+1, 3*(y/3)+1

def get_box(grid, x, y, ignore_cell = False):
    box = []
    cx, cy = get_center_coordinates(x, y)
    for i in range(-1, 2):
        for j in range(-1, 2):
            if cx + i == x and cy + j == y: 
                if not ignore_cell: box.append(grid[cx + i][cy + j])
            else: box.append(grid[cx + i][cy + j])
    return box

def get_row(grid, r, c, ignore_cell = False):
    index_range = range(9)
    if ignore_cell: index_range.remove(c)
    return [grid[r][i] for i in index_range]

def get_col(grid, r, c, ignore_cell = False):
    index_range = range(9)
    if ignore_cell: index_range.remove(r)
    return [grid[i][c] for i in index_range]

def narrow_possible(x, y, grid):
    if grid[x][y] > 0: return []
    row = grid[x]
    col = get_col(grid, x, y)
    box = get_box(grid, x, y)
    possible = []
    for i in range(1, 10):
        if not (i in row or i in col or i in box): 
            possible.append(i)
    return possible

def eliminate_possible(x, y, grid, possible_grid):
    center_x, center_y = get_center_coordinates(x, y)
    for i in range(9):
        if grid[x][y] in possible_grid[x][i]: possible_grid[x][i].remove(grid[x][y])
        if grid[x][y] in possible_grid[i][y]: possible_grid[i][y].remove(grid[x][y])
    box = [(center_x - 1, center_y - 1), (center_x - 1, center_y), (center_x - 1, center_y + 1), (center_x, center_y - 1), (center_x, center_y), (center_x, center_y + 1), (center_x + 1, center_y - 1), (center_x + 1, center_y), (center_x + 1, center_y + 1)]
    for rc in box:
        if grid[x][y] in possible_grid[rc[0]][rc[1]]: possible_grid[rc[0]][rc[1]].remove(grid[x][y])
    return possible_grid

def generate_possibilites_for_blank_cells(grid):
    possiblities_grid = []
    for row in range(9):
        grid_row = []
        for col in range(9): grid_row.append(narrow_possible(row, col, grid))
        possiblities_grid.append(grid_row)
    return possiblities_grid

def eliminate_possibilies_from_possibilities_grid(grid, possibilities_grid):
    more_possibilites_to_eliminate = True
    while more_possibilites_to_eliminate:
        possibilities_eliminated = False
        for r_index, row in enumerate(possibilities_grid):
            for c_index, col in enumerate(row):
                if len(col) == 1:
                    grid[r_index][c_index] = col[0]
                    possibilities_grid = eliminate_possible(r_index, c_index, grid, possibilities_grid)
                    possibilities_eliminated = True
        if not possibilities_eliminated: more_possibilites_to_eliminate = False
    return grid, possibilities_grid

def copy(a):
    b = []
    for i in range(9):
        row = []
        for j in range(9): row.append(list(a[i][j]))
        b.append(row)
    return b

def copy_grid(a):
    b = []
    for i in a: b.append(list(i))
    return b

def find_blank_cell(grid):
    min_x, min_y = None, None
    for i in range(9):
        for j in range(9): 
            if grid[i][j] == 0: return i, j
    return min_x, min_y

def check(x, row_col):
    return not (x in row_col)

def check_sudoku(grid):
    for x in range(9):
        for y in range(9):
            cell = grid[x][y]
            row, col, box = get_row(grid, x, y, True), get_col(grid, x, y, True), get_box(grid, x, y, True)
            if not (check(cell, row) and check(cell, col) and check(cell, box)):
                return False
    return True


def solve(grid, possibilities_grid):
    x, y = find_blank_cell(grid)

    if x == None and y == None:
        global start
        print_grid(grid)
        print time.time() - start

        start = time.time()
        if check_sudoku(grid): print '!! Solved !!'
        print time.time() - start
        exit()

    for possibility in possibilities_grid[x][y]:
        grid[x][y] = possibility
        copy_possibilities_grid = eliminate_possible(x, y, grid, copy(possibilities_grid))
        solve(copy_grid(grid), copy_possibilities_grid)

def main():
    # Easy
    # puzzle = '1.742..9.4.......2.5.7..1.39...5..6..4.8.6.2.3.5....1.2...13..6..3.9..7.6....84.5'
    # Medium
    # puzzle = '8..4.6..7......4...1....65.5.9.3.78.....7.....48.2.1.3.52....9...1......3..9.2..5'
    # Hard
    puzzle = '8..........36......7..9.2...5...7.......457.....1...3...1....68..85...1..9....4..'

    grid = parse_puzzle(puzzle)
    print_grid(grid)
    possibilites_grid = generate_possibilites_for_blank_cells(grid)
    grid, possibilities_grid = eliminate_possibilies_from_possibilities_grid(grid, possibilites_grid)
    print_grid(grid)
    solve(grid, possibilites_grid)

main()