#!/usr/bin/env ruby

def array_is_valid(array)
    x = array.dup
    x.delete(0)
    x.uniq == x
end

def array_is_complete(array)
    !array.include?(0) && array.uniq == array
end

def each_block(puzzle)
    0.upto(8) do |row|
        return false unless yield(puzzle[row * 9 ... (row + 1) * 9])
    end
    
    0.upto(8) do |col|
        array = []
        0.upto(8) do |row|
            array << puzzle[row * 9 + col]
        end
        return false unless yield(array)
    end
    
    0.upto(2) do |metarow|
        0.upto(2) do |metacol|
            array = []
            0.upto(2) do |row|
                0.upto(2) do |col|
                    array << puzzle[(metarow * 3 + row) * 9 + metacol * 3 + col]
                end
            end
            return false unless yield(array)
        end
    end
    
    return true
end

def puzzle_is_valid(puzzle)
    each_block(puzzle) do |array|
        array_is_valid(array)
    end
end

def puzzle_is_complete(puzzle)
    each_block(puzzle) do |array|
        array_is_complete(array)
    end
end

def traverse_puzzle(puzzle)
    $count += 1
=begin
    if $count % 100 == 0
        puts $count
    end
=end

    if puzzle_is_complete(puzzle) then
        print "solution at #{$count}: "
        p puzzle
        exit
        #return
    end
    
    if !puzzle_is_valid(puzzle) then
        return
    end
    
    zero_index = puzzle.index(0)
    1.upto(9) do |i|
        new_puzzle = puzzle.dup
        new_puzzle[zero_index] = i
        traverse_puzzle(new_puzzle)
    end
end

$puzzle_path = ARGV[0]
$puzzle = []
File.open($puzzle_path) do |puzzle_file|
    puzzle_file.each_line do |line|
        line.chomp.each_byte do |byte|
            $puzzle << ('' << byte).to_i
        end
    end
end

$count = 0
traverse_puzzle($puzzle)
puts "tried #{$count} partial solutions"