#!/usr/bin/env python

# Simple brute force sudoku solver.
# Written by Mike Sullivan in June 2008 and released to the public domain.

import sys, math

class BitSet:
    """A set of natural numbers represented by a bit array."""
    def __init__(self):
        self._bits = 0

    def add(self, x):
        self._bits |= (1 << x)

    def remove(self, x):
        # set it and then remove it: deals with longs where & ~ wouldn't
        n = 1 << x
        self._bits = (self._bits | n) ^ n

    def __contains__(self, x):
        return (self._bits & (1 << x)) != 0

    def union(self, s):
        t = BitSet()
        t._bits = self._bits | s._bits
        return t

class Sudoku:
    """A Sudoku board representation and solver

    The solver is a simple brute force solver. It uses a bitset per every
    row, column, and square to keep track of what values are available at any
    given location."""

    def __init__(self, f):
        """Initialize a Sudoku board from a file.

        f -- a file object to read from"""
        self.read_board(f)
        self.setup_sets()

    # this could be a one liner, but I wanted to error check :(
    def read_board(self, f):
        """Read a Sudoku board from a file.

        This will determine the initial values and and size of the board.
        BUG: While this is mostly able to deal with board sizes larger than 9,
             it can not deal with any initial values other than 1-9.
        
        f -- a file object to read from"""
        size = 0
        board = []
        for line in f:
            line = line.strip()
            if not line: continue
            if not size: size = len(line)
            if size != len(line):
                raise ValueError("expected size %d, got %d"
                                 % (size, len(line)))
            board.append([ int(c) for c in line ])
        if (len(board) != size): 
            raise ValueError("expected size %d, got %d"
                             %  (size, len(board)))
            
        n = int(math.sqrt(size))
        if (n*n != size):
            raise ValueError("size %d not a perfect square" % size)

        self.n, self.board = n, board


    def __str__(self):
        """Format the board as a string for pretty output"""
        n = self.n
        s = ""
        for i in xrange(len(self.board)):
            for j in xrange(len(self.board)):
                s += str(self.board[i][j])
                if (j+1) % n == 0:
                    s += ' '
            if (i+1) % n == 0:
                s += '\n'
            s += '\n'
        return s.strip()
        

    def setup_sets(self):
        """Create and populate the sets for keeping track of numbers used"""
        n, board = self.n, self.board

        self.row_sets = [ BitSet() for row in board ]
        self.col_sets = [ BitSet() for row in board ]
        self.sqr_sets = [ [ BitSet() for i in xrange(n) ] for j in xrange(n) ]

        for i in xrange(len(board)):
            for j in xrange(len(board)):
                x = board[i][j]
                if not x: continue
                self.set_pos(i, j, x)
        
    def next_pos(self, i, j):
        j += 1
        if j >= len(self.board):
            i += 1
            j = 0
        return i, j
    
    def set_pos(self, i, j, x):
#        print "setting %d, %d to %d" % (i, j, x)
        self.board[i][j] = x
        self.row_sets[i].add(x)
        self.col_sets[j].add(x)
        self.sqr_sets[i//self.n][j//self.n].add(x)

    def clear_pos(self, i, j, x):
        self.board[i][j] = 0
        self.row_sets[i].remove(x)
        self.col_sets[j].remove(x)
        self.sqr_sets[i//self.n][j//self.n].remove(x)
    
    def get_blocked(self, i, j):
        return self.row_sets[i].union(
            self.col_sets[j].union(
                self.sqr_sets[i//self.n][j//self.n]))

    def solve(self, i=0, j=0):
        """Attempt to find a single solution to this puzzle.

           Returns a boolean indicating whether it succeeded and
           updates the state of the board."""
        if i >= len(self.board): 
            return True
        elif self.board[i][j]:
            return self.solve(*self.next_pos(i, j))

        blocked = self.get_blocked(i, j)
        for x in xrange(1, len(self.board)+1):
            if x not in blocked:
                self.set_pos(i, j, x)
                if self.solve(*self.next_pos(i, j)):
                    return True
                self.clear_pos(i, j, x)
        
        return False


def main(args):
    game = Sudoku(sys.stdin)
    print "Puzzle:"
    print game
    print
    if game.solve():
        print "Solution:" 
        print game
    else:
        print "No solutions found"


if __name__ == '__main__':
    sys.exit(main(sys.argv))