Ruby で数独 (その2)

  • ????????????????????

先日、数独を解くための Ruby のプログラムを書きましたが、少し書き直してみました。ソルバー部分は 25 行になって短くなったけど、可読性は下がっている気が…

まったく同じ探索木の辿り方で、もっと本質的に短くなるような方法はあるのだろうか?それにしても、この手のパズルものは解くのも面白いけど、プログラムを書くこと自体もパズルっぽくてとても面白いですねー

ほかのサイトの数独ソルバーもいくつか試してみましたが、このソルバーは解をひとつしか見つけれない代わりに、一つ目の解の発見が早い傾向がありました。まあ、探索の枝を選別しているのであたりまえといえばあたりまえなのですが。以下、コード。

# sudoku.rb
# by septuplebass (http://septuplebass.blog135.fc2.com/)
def solveSudoku sheet
  rfill,cfill,bfill = 3.times.collect {
    9.times.collect { Array.new(9,false) } }
  (0..8).to_a.repeated_permutation(2) { |i,j|
    rfill[i][sheet[i][j]] = cfill[j][sheet[i][j]] = bfill[i/3*3+j/3][sheet[i][j]] = true if sheet[i][j]!=0 }
  (1..9).each { |val| sudokuRec 0,0,val,sheet,rfill,cfill,bfill }
end
def sudokuRec i, j, val, sheet, rfill, cfill, bfill
  return true if sheet.flatten.count(0) == 0
  empty = sheet[i][j]==0
  return false if empty and (rfill[i][val] || cfill[j][val] || bfill[i/3*3+j/3][val] )
  sheet[i][j]=val if empty
  rfill[i][val]=cfill[j][val]=bfill[i/3*3+j/3][val]=true if empty
  i2, j2 = (0..8).to_a.repeated_permutation(2).collect { |i,j|
    [sheet[i][j]==0 ? (1..9).count { |v| ! (rfill[i][v] || cfill[j][v] || bfill[i/3*3+j/3][v] )
      } : 9999, i, j] }.min[1..2]
  (1..9).each { |val2|
    return true if sudokuRec i2,j2,val2,sheet,rfill,cfill,bfill }
  sheet[i][j] = 0 if empty
  rfill[i][val]=cfill[j][val]=bfill[i/3*3+j/3][val]=false if empty
  return false
end
# helper function
def printSheet(mat)
  (0..8).each { |i|
    puts "-"*31 if i % 3 == 0
    (0..8).each { |j|
      print (j%3==0 ? "|" : "") + mat[i][j].to_s.center(3)
    }
    puts "|"
  }
  puts "-"*31
end
def readProblem(filename)
  open(filename) {|file|
    chars=[]
    (0..8).collect { |row|
      (0..8).collect { |col|
        chars = file.gets.chomp.split("") if col==0
        throw "File format error : "+
          chars.join if !(chars.join =~ /^[1-9*]{9}$/)
        chars[col] == "*" ? 0 : chars[col].to_i
      }
    }
  }
end
# Main routine
sheet=readProblem ARGV[0]
puts "Problem (Input)"
printSheet sheet
puts "Solving..."
solveSudoku sheet
puts "Solution"
printSheet sheet

当然、rfill, cfill, bfill というフラグたちを使わない方法もあるのですが、2箇所で真偽判定につかうために、コードがさらにごちゃごちゃしてくるのでやめました。スピードも遅くなった(1秒→5秒)。

はてなブックマーク - Ruby で数独 (その2)
Pocket