Sudoku solver using complete search.

sudoku_solver.py

#!/usr/bin/env python3
# By Philip Arthur
# This program is intended to solve sudoku problem with a complete search.
# It simulates human's way to solve sudoku problem with following steps:
# 1. Forward Inference: Try to look at every column, row, and box; if there is only 1 possible cell for a particular number, set it.
# 2. Invalidate board: For every number that is set, we need to remove the possibility of other cells being that number in the same row, column and box.
# 3. Assign value: if there is a cell contains only 1 possible number, set it.
#
# If solution is not found, then trial and error approach is done by greedy best first search with assigning some value to the cells with less candidates.
#
# Usage: python3 sudoku.py < input.txt
# The program receives 9 lines input of 9 numbers (0-9) with 0 is an empty cell.
# Contact: philip.arthur30@gmail.com

import sys
import copy

class Cell:
    def __init__(self):
        self.possibility = set([1,2,3,4,5,6,7,8,9])
        self.value = 0

class Board:
    def __init__(self):
        self.cells  = [[Cell() for _ in range(9)] for _ in range(9)]
        self.action = []
   
    def set_cell(self, i, j, value):
        self.cells[i][j].value = value
        self.cells[i][j].possibility = set([value])
        self.action.append((i,j, value))
    
    def remove_value(self, i, j, value, verbose=False):
        if value in self.cells[i][j].possibility:
            if verbose:
                print("%d is not possible in %d, %d" % (value, i, j))
            self.cells[i][j].possibility.remove(value)

    def invalidate_board(self):
        """ For every fresh assigned value in action, make sure our board updates the other
            rows, columns, and boxes so they still follow the Sudoku's rule"""
        while len(self.action) != 0:
            i, j, value = self.action.pop()
            
            # invalidate row + column
            for k in range(9):
                self.remove_value(k,j,value)
                self.remove_value(i,k,value)
            # invalidate box
            box_i = i - (i%3)
            box_j = j - (j%3)
            for k in range(3):
                for l in range(3):
                    self.remove_value(box_i+k, box_j+l, value)
    
    
    def check_board(self):
        """Check the board and count how many unsolved cells in the board.""" 
        unsolved = 0
        for i in range(9):
            for j in range(9):
                if self.cells[i][j].value == 0:
                    unsolved += 1
        return unsolved
    

    def assign_value(self, verbose=False):
        # Setting value
        for i in range(9):
            for j in range(9):
                cell = self.cells[i][j]
                if cell.value == 0:
                    if verbose:
                        print("There are %d possible values in %d, %d" % (len(cell.possibility), i, j))
                    if len(cell.possibility) == 1:
                        certain_value = list(cell.possibility)[0]
                        self.set_cell(i, j, certain_value)

    def forward_inference(self):
        # For every row, try to assign a particular number in a particular cell
        for i in range(9):
            for num in range(9):
                possible = []
                for j in range(9):
                    if num in self.cells[i][j].possibility:
                        possible.append((i,j))
                if len(possible) == 1:
                    x, y = possible[0]
                    self.set_cell(x, y, num)
        # For every column, try to assign a particular number in a particular cell
        for j in range(9):
            for num in range(9):
                possible = []
                for i in range(9):
                    if num in self.cells[i][j].possibility:
                        possible.append((i,j))
                if len(possible) == 1:
                    x, y = possible[0]
                    self.set_cell(x, y, num)
        # For every box, try to assign a particular number into a particular cell
        for i in range(3):
            for j in range(3):
                for num in range(9):
                    possible = []
                    for x in range(3):
                        for y in range(3):
                            if num in self.cells[3*i+x][3*j+y].possibility:
                                possible.append((x,y))
                    if len(possible) == 1:
                        x, y = possible[0]
                        self.set_cell(3*i+x, 3*j+y, num)
   
    def solve(self):
        unsolved = 1
        while unsolved != 0 and len(self.action) != 0:
            # Execute all the actions
            self.forward_inference()
            self.invalidate_board()
            self.assign_value()
            unsolved = self.check_board()
        print("Unsolved = %d" % unsolved, file=sys.stderr)
        return unsolved == 0

    def set_info(self, info):
        self.info = info

    def print(self, stream=sys.stderr):
        if hasattr(self, "info"):
            print(self.info, file=stream)
        for i in range(9):
            for j in range(9):
                print(self.cells[i][j].value,end="", file=stream)
                if (j+1) % 3 == 0: print("|", end="", file=stream)
            print(file=stream)
            if (i+1) % 3 == 0: print("-----------", file=stream)
        print(file=stream)
    
    def unsolved(self):
        ret = []
        feasible = True
        for i in range(9):
            for j in range(9):
                k = len(self.cells[i][j].possibility)
                if k == 0:
                    feasible = False
                    break
                elif k != 1:
                    ret.append((i, j, list(self.cells[i][j].possibility)))
            if not feasible:
                break
        return sorted(ret, key=lambda x: len(x[2]))
 
### Start
board = Board()
for i, str_inp in enumerate(sys.stdin):
    for j, char in enumerate(str_inp.strip()):
        if char != "0":
            board.set_cell(i, j, int(char))

### Greedy Best First Search
queue = [board]
while len(queue) != 0:
    this_board = queue.pop(0)
    if not this_board.solve():
        ranked_cell = board.unsolved()
        print("Untrivial problem, trying to assign value to a cell that has lesser candidates.", file=sys.stderr)
        this_board.print()
        for i, j, possibility in ranked_cell:
            for trial in possibility:
                next_board = copy.deepcopy(this_board)
                next_board.set_cell(i, j, trial)
                next_board.set_info("This board was made by setting %d, %d, with %d" % (i, j, trial))
                queue.append(next_board)
    else:
        solution = this_board
        break

print("Solution found!")
solution.print(sys.stdout)