sudoku_solver.py

import copy
import itertools
from collections import defaultdict

import numpy as np

def get_minigrid_for_coord(i, j):
    h = i / 3
    w = j / 3
    return w, h


class Grid(object):
    def __init__(self, width, height, data):
        self.width = width
        self.height = height
        self.data = data
        
        self._possibilities_grid = [[set(range(1, 10)) for _ in xrange(width)]
                                    for _ in xrange(height)]
        self._minigrid = defaultdict(lambda: set(range(1, 10)))
        self._to_solve = []
        self._solve_grids()


    def _solve_grids(self):
        _width_grid = [set(range(1, 10)) for _ in xrange(self.width)]
        _height_grid = [set(range(1, 10)) for _ in xrange(self.height)]

        for i in xrange(self.width):
            for j in xrange(self.height):
                item = self.data[i][j]
                if item:
                    _width_grid[i].remove(item)
                    _height_grid[j].remove(item)
                    self._minigrid[get_minigrid_for_coord(i, j)].remove(item)

        for i in xrange(self.width):
            for j in xrange(self.height):
                item = self.data[i][j]
                if not item:
                    self._to_solve.append((i, j))
                    self._possibilities_grid[i][j] = (
                        _width_grid[i] & _height_grid[j] & 
                        self._minigrid[get_minigrid_for_coord(i, j)]
                    )

def solve_sudoku(chain, possibilities_grid, result_grid, removed_possibilities_width, removed_possibilities_height, removed_possibilities_minigrid):
    if len(chain) == 0:
        return True
    first, last = chain[0], chain[1:]
    i, j = first
    for possibility in possibilities_grid[i][j]:
        if possibility in (removed_possibilities_width[i] & removed_possibilities_height[j] & removed_possibilities_minigrid[get_minigrid_for_coord(i, j)]):
            removed_possibilities_width_copy = copy.deepcopy(removed_possibilities_width)
            removed_possibilities_height_copy = copy.deepcopy(removed_possibilities_height)
            removed_possibilities_minigrid_copy = copy.deepcopy(removed_possibilities_minigrid)

            removed_possibilities_width_copy[i].remove(possibility)
            removed_possibilities_height_copy[j].remove(possibility)
            removed_possibilities_minigrid_copy[get_minigrid_for_coord(i, j)].remove(possibility)
            if solve_sudoku(last, possibilities_grid, result_grid, removed_possibilities_width_copy, removed_possibilities_height_copy, removed_possibilities_minigrid_copy):
                result_grid[(i,j)] = possibility
                return True
    return False

def main():
    data = []
    result = {}
    with open('./question001.txt') as f:
        for line in f.readlines():
            data.append([(None if c == '0' else int(c)) for c in list(line.strip())])

    g = Grid(9, 9, data)
    solve_sudoku(g._to_solve, g._possibilities_grid, result, defaultdict(lambda: set(range(1, 10))), defaultdict(lambda: set(range(1, 10))), defaultdict(lambda: set(range(1, 10))))

    for (i, j), el in result.iteritems():
        g.data[i][j] = el

    print np.array(g.data)

if __name__ == '__main__':
    main()