ナンプレを解くプログラム

numpla

,,,,,3,1,,
1,,7,,9,,,,
3,8,,1,,,,,
7,1,,,,,,4,2
,,,,2,,5,8,
8,,2,,,5,,,
,,,,,2,9,6,
,,4,,8,,,,
,,,5,,,,3,4

NumPlace.rb

def readfile( fn )
    fp = open( fn )
    str = ""
    fp.each_line.map { |ln|
        ln.split(",").map { |n| n.to_i }
    }
end

def solveNumPlace(problem, stack)
    memory = {candidate: [], row: 0, col: 0, problem: []}
    filled = true
    isCandidateEmpty = false
    while filled
        filled = false
        (0..8).each{|i|
            (0..8).each{|j|
                candidate = getCandidates(i, j, problem)
                if problem[i][j] == 0
                    if candidate.size == 1
                        problem[i][j] = candidate[0]
                        filled = true
                    elsif candidate.size > 1
                        memory[:candidate] = candidate
                        memory[:row] = i
                        memory[:col] = j
                    elsif candidate.size == 0
                        isCandidateEmpty = true
                    end
                end
            }
        }
    end

    if (0..8).all?{|i| (problem[i] - [1,2,3,4,5,6,7,8,9]).empty?}
        puts "solved"
        outputResult(problem)
    else
        new_num = 0
        new_row = 0
        new_col = 0
        if isCandidateEmpty
            removed = stack.pop
            if removed == nil
                puts "stack is nil"
                return
            end
            problem = removed[:problem]
            new_num = removed[:candidate][0]
            new_row = removed[:row]
            new_col = removed[:col]
            
            memory[:candidate] = removed[:candidate] - [new_num]
            if memory[:candidate].size > 0
                memory[:row] = new_row
                memory[:col] = new_col
                memory[:problem] = (0..8).map{|i| problem[i].dup}
                stack.push(memory)
            end
        else
            new_num = memory[:candidate][0]
            new_row = memory[:row]
            new_col = memory[:col]
            memory[:candidate] = memory[:candidate] - [new_num]
            memory[:problem] = (0..8).map{|i| problem[i].dup}
            stack.push(memory)
        end
        
        problem[new_row][new_col] = new_num

        solveNumPlace(problem, stack)
    end
    
end

def outputResult(problem)
    (0..8).each{|i|
        (0..8).each{|j|
            $stdout << problem[i][j] << " "
        }
        $stdout << "\n"
    }
end

def getCandidates(row, col, problem)
    candidate = [1,2,3,4,5,6,7,8,9]
    if problem[row][col] != 0
        candidate = []
    end
    candidate = checkRow(row, candidate, problem)
    candidate = checkCol(col, candidate, problem)
    candidate = checkBox(row, col, candidate, problem)
end

def checkRow(row, candidate, problem)
    candidate - problem[row]
end

def checkCol(col, candidate, problem)
    candidate - (0..8).map{|i| problem[i][col]}
end

def checkBox(row, col, candidate, problem)
    row_s = row - row % 3
    col_s = col - col % 3
    mat = problem[row_s,3].inject([]){|mat, x| mat + x[col_s,3]}
    candidate - mat 
end

np = readfile("./numpla")
stack = []
solveNumPlace(np, stack)