#!/usr/bin/env ruby
#
#  Created by Benny Pollak on 2006-05-29.
#  Copyright (c) 2006. All rights reserved.
# This library is free software; you can redistribute it and/or
# modify it under the terms of the GNU Lesser General Public
# License as published by the Free Software Foundation; either
# version 2.1 of the License, or (at your option) any later version.
# 
# This library is distributed in the hope that it will be useful,
# but WITHOUT ANY WARRANTY; without even the implied warranty of
# MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the GNU
# Lesser General Public License for more details.
# 
# You should have received a copy of the GNU Lesser General Public
# License along with this library; if not, write to the Free Software
# Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301  USA
# 
class Sudoku
    def initialize(p)
        @p = p
        @sqrSz = Math.sqrt(p.size).to_i
    end
        
        
    def solve()
        return solveCell(0, 0)
    end
    
    def solveCell(row, col)
        if col >= @p.size
            return true
        elsif row >= @p.size
            return solveCell(0, col+1)
        elsif @p[row][col] != 0
            return solveCell(row+1, col)
        end
        for num in 1..@p.size
            if (valid(row, col, num))
                @p[row][col] = num
                #print "",row,",",col,",",num,"\n"
                if solveCell(row+1, col)
                    return true
                end
            end
        end
        @p[row][col]=0
        return false
    end
    def validInRow?(row, num)
        for col in 0...@p.size
            #print "r ",row,",",col,",",num,"\n"
            return false if @p[row][col].abs() == num
        end
        return true
    end
    def validInCol?(col, num)
        for row in 0...@p.size
            #print "r ",row,",",col,",",num,"\n"
            return false if @p[row][col].abs() == num
        end
        return true
    end
    def validInSquare?(row, col, num)
        r1 = (row / @sqrSz) * @sqrSz
        c1 = (col / @sqrSz) * @sqrSz
        for r in r1...(r1+@sqrSz)
            for c in c1...(c1+@sqrSz)
                #print "s ",r,",",c,",",num,"\n"
                return false if @p[r][c].abs() == num
            end
        end
        return true
    end
    def valid(row, col, num)
        isValid = validInRow?(row, num) && validInCol?(col, num) && validInSquare?(row, col, num)
        #print "Not valid ",row,",",col,",",num,"\n" unless isValid
        return isValid
    end
    def put()
        @p.each {|r|
            r.each {|c| 
                if c == 0
                    print "   "
                else
                    printf "%-3d",c.abs
                    end
            }
            print "\n"
        }
    end
end

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

s = Sudoku.new(p)
puts "Unsolved:"
s.put
if s.solve
    puts "Solved:"
    s.put()
else
    puts "Puzzle has no solution"
end