Ruby で世界一難しい数独

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

解けたら天才! フィンランドの数学者が作った「世界一難しい数独」

解いてみました、というか ruby が解いてくれました。

ソースコード

# sudoku.rb

def printMatrix(mat)
  mat.each_with_index { |row, i|
    puts "-"*31 if i % 3 == 0
    row.each_with_index { |elm, j|
      print (j%3==0 ? "|" : "") + elm.to_s.center(3)
    }
    puts "|"  }
  puts "-"*31
end
class Sudoku
  def initialize()
    @nfilled=0
    @mat, @rowfill, @colfill, @boxfill = 4.times.collect { |j| 9.times.collect { |i| Array.new(9, (j==0) ? 0 : false) } }
    @boxi = 9.times.collect { |i| 9.times.collect { |j| 3*(i/3)+j/3  } }
    @matindex = 9.times.collect { |i| 9.times.collect { |j| [i,j] } }.flatten(1)
  end
  def readProblem(filename)
    open(filename) {|file|
      chars=[]
      @matindex.each { |row, col|
        chars = file.gets.chomp.split("") if col==0
        throw "File format error : "+chars.join if !(chars.join =~ /^[1-9*]{9}$/)
        setValue(row, col, chars[col].to_i ) if chars[col]!="*"
      }
    }
  end
  def printState()
    printMatrix(@mat)
  end
  def isEmpty?(i, j)
    @mat[i][j]==0
  end
  def canPut?(i, j, val)
    !(@rowfill[i][val] || @colfill[j][val] || @boxfill[@boxi[i][j]][val])
  end
  def setValue(i, j, val)
    k = (val!=0) ? val : @mat[i][j]
    @nfilled += (val!=0) ? 1 : -1
    @mat[i][j] = val
    @rowfill[i][k] = @colfill[j][k] = @boxfill[@boxi[i][j]][k] = (val!=0)
  end
  def getNextCand()   # Returns (i,j) that has minimum number of candidates
    @matindex.collect { |row,col|  # isEmpty?(i,j)*** : The number of candidates
      [isEmpty?(row,col) ? 1.upto(9).count { |v| canPut?(row,col,v) } : 9999, row, col]
    }.min[1..2]
  end
  def searchRec(i, j, val)
    return true if @nfilled == 81
    empt = isEmpty?(i, j)
    if empt
      return false if !canPut?(i, j, val)
      setValue(i, j, val)
    end
    nexti, nextj = getNextCand()
    1.upto(9){ |nextval|
      return true if searchRec(nexti, nextj, nextval)
    }
    setValue(i, j, 0) if empt
    return false
  end
  def search()
    for i in 1..9
      break if searchRec(0,0,i)
    end
  end
end
# Main routine
sudoku=Sudoku.new
sudoku.readProblem(ARGV[0])
puts "Problem (Input)"
sudoku.printState
puts "Solving..."
sudoku.search
puts "Solution"
sudoku.printState

といてみる

以下のような数独を記述したファイル(difficult.txt)を準備して

**53*****
8******2*
*7**1*5**
4****53**
*1**7***6
**32***8*
*6*5****9
**4****3*
*****97**

 > ruby sudoku.rb difficult.txt

を実行すれば OK です。

結果(見たくない人は注意!)

 > ruby sudoku.rb difficult.txt
Problem (Input)
-------------------------------
| 0  0  5 | 3  0  0 | 0  0  0 |
| 8  0  0 | 0  0  0 | 0  2  0 |
| 0  7  0 | 0  1  0 | 5  0  0 |
-------------------------------
| 4  0  0 | 0  0  5 | 3  0  0 |
| 0  1  0 | 0  7  0 | 0  0  6 |
| 0  0  3 | 2  0  0 | 0  8  0 |
-------------------------------
| 0  6  0 | 5  0  0 | 0  0  9 |
| 0  0  4 | 0  0  0 | 0  3  0 |
| 0  0  0 | 0  0  9 | 7  0  0 |
-------------------------------
Solving...
Solution
-------------------------------
| 1  4  5 | 3  2  7 | 6  9  8 |
| 8  3  9 | 6  5  4 | 1  2  7 |
| 6  7  2 | 9  1  8 | 5  4  3 |
-------------------------------
| 4  9  6 | 1  8  5 | 3  7  2 |
| 2  1  8 | 4  7  3 | 9  5  6 |
| 7  5  3 | 2  9  6 | 4  8  1 |
-------------------------------
| 3  6  7 | 5  4  2 | 8  1  9 |
| 9  8  4 | 7  6  1 | 2  3  5 |
| 5  2  1 | 8  3  9 | 7  6  4 |
-------------------------------

中身の説明

searchRec という関数を使って再帰的に解を探索します。ポイントは矛盾のない状態が与えられたとき、次にどのセルをターゲットに探索するか、という部分です(Sudoku class の getNextCand メソッド)。「世界一難しい数独」のような探索木が深くなるような問題では、ここを適当に実装してしまうと計算が終わらない。次のターゲットを不確実性が最小であるようなセルにするとかなり計算が高速になりました。ここでつまづいたせいで時間がかかってしまった…

所要時間はコーディング3時間、計算時間1秒です。自力で解く人に負けなくてよかった:-) ちょっとコードが長くなりすぎたかな…(汗

はてなブックマーク - Ruby で世界一難しい数独
Pocket

  • http://septuplebass.blog135.fc2.com/blog-entry-6.html sing a song of song

    Ruby で数独 (その2)

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