Rubyで富豪的プログラミングで８クイーンに挑戦そして玉砕

８クイーンというパズル問題があるよ。

簡単に説明すると、8x8のチェス盤があってここに飛車角の動きをする8つのクイーンを、互いが取り合わない位置に配置する問題だよ。

８クイーンの組合せは全部で92通りあるそうだよ。それでループとか再帰とか、バックトラックとか動的計画とかのアルゴリズムの手法を駆使して、その解法をプログラミングするというのがプログラマーたちの頭の体操になっているんだ。ちょっと検索すれば大量の模範解答が得られるよ。

で、僕もRubyを使ってこの問題を解いてみようと思うんだけど、どうもこの手のアルゴリズムが僕は嫌いというか苦手みたいで、解法を試行錯誤したり他の人の書いた模範解答を解読する気が、どうしても起きないんだよ。まあ僕の能力不足としか言いようがないんだけど..

それでも暫くその理由を考えてみたら、なんとなく原因が分かったんだよ。それはこの手の問題では問と実装コードとの間に大きな隔たりがあるってことなんだ。つまり問と実装コードとの間には「実装者の工夫の大きな塊」が存在していて、それが問と実装コードとの隔たりを大きくしてる、そう僕は感じるんだ。

で、この「工夫の大きな塊」はその実装者毎にまちまちで、結果実装コードはその実装者固有のものになっている。これは言い換えれば、８クイーン問題をうまく抽象化できていない、とも言えると思うんだけど。

できれば僕は自分の働きをできるだけ小さくして、Rubyにもっともっと働いて欲しいと願ってるんだけど..

そんなわけで..

問と実装コードとの間の隔たりをできるだけ小さくした抽象度の高い富豪的プログラミングで、エイトクイーンに挑戦してみたよ:) まあ最初から玉砕するのは分かってるんだけどね..

ここではチェス盤のサイズとクイーンの数を８に限定しない実装を試みるよ。クラス名をQueenSolverとして初期化時に盤サイズとクイーン数を指定できるようにしよう。そしてsolveメソッドで解答の組合せを出力するよ。

# queen_solver.rb
class QueenSolver
  def initialize(nth=8, queens=8)
    @nth = nth
    @queens = queens
  end
  
  def solve
  end
end
QueenSolver.new.solve # =>

さてsolveの中身なんだけど、ここでは富豪的アプローチでいくからすべての可能な配置の組み合わせを用意して、そこから条件を満たさないつまり、一対でも衝突のあるクイーンのある組を取り除くことで、有効な組み合わせを見つけ出すよ。

だからsolveメソッドの中身はこんな感じになるよ。

class QueenSolver
  def solve
    all_combinations.reject do |pattern|
      pattern.combination(2).any? { |a, b| conflict?(a, b) }
    end
  end
end

all_combinationsですべての組合せを作ってそこからrejectで不適合なパターンの組を除くんだ。rejectのブロックではそのパターン中のクイーン相互の衝突を見て、その一つでも衝突があったらそのパターンを除外するよ。そのためにcombinationしてるよ。

で、あとはsolveの補助関数としてのall_combinationsとconflict?を定義すればいいよ。まずはall_combinationsから。

ここでちょっと盤サイズ3x3　クイーン数2の簡単な例を考えてみるよ。盤の座標は次の9つになるよね。

[[0,0],[0,1],[0,2],
  [1,0],[1,1],[1,2],
  [2,0],[2,1],[2,2]]

この盤における2つのクイーンの配置の組合せは、9C2となって36通りあるよ。

9C2 = 9! / 2(9-2)! = 36

この考えに従ってall_combinationsをRubyで表現すると、次のようになるんだ。

class QueenSolver
  def all_combinations
    board_coordinates.combination(@queens)
  end
end

で盤の座標board_coordinatesは、repeated_permutationを使って次のように書けるよ。

class QueenSolver
  def all_combinations
    board_coordinates.combination(@queens)
  end
  def board_coordinates
    [*0..@nth-1].repeated_permutation(2).to_a
  end
end
qs = QueenSolver.new(3,2)
qs.board_coordinates # => [[0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2], [2, 0], [2, 1], [2, 2]]
qs.all_combinations.to_a # => [[[0, 0], [0, 1]], [[0, 0], [0, 2]], [[0, 0], [1, 0]], [[0, 0], [1, 1]], [[0, 0], [1, 2]], [[0, 0], [2, 0]], [[0, 0], [2, 1]], [[0, 0], [2, 2]], [[0, 1], [0, 2]], [[0, 1], [1, 0]], [[0, 1], [1, 1]], [[0, 1], [1, 2]], [[0, 1], [2, 0]], [[0, 1], [2, 1]], [[0, 1], [2, 2]], [[0, 2], [1, 0]], [[0, 2], [1, 1]], [[0, 2], [1, 2]], [[0, 2], [2, 0]], [[0, 2], [2, 1]], [[0, 2], [2, 2]], [[1, 0], [1, 1]], [[1, 0], [1, 2]], [[1, 0], [2, 0]], [[1, 0], [2, 1]], [[1, 0], [2, 2]], [[1, 1], [1, 2]], [[1, 1], [2, 0]], [[1, 1], [2, 1]], [[1, 1], [2, 2]], [[1, 2], [2, 0]], [[1, 2], [2, 1]], [[1, 2], [2, 2]], [[2, 0], [2, 1]], [[2, 0], [2, 2]], [[2, 1], [2, 2]]]

次にconflict?を定義しよう。クイーンは飛車角の動きをするから、縦、横、斜めの何れかでの衝突をもって、適合の判定をするよ。

class QueenSolver
  def conflict?(a, b)
    conflict_x?(a, b) || conflict_y?(a, b) || conflict_cross?(a, b)
  end
end

conflict_x?とconflict_y?はクイーンのxまたはy座標を比較すればいいから簡単だね。conflict_cross?の判定にはちょっと工夫がいるけど、それはx-y座標の和と差を比較することで判定できるんだよ。だからこれらのコードは次のようになるよ。

class QueenSolver
  def conflict_x?(a, b)
    a[0] == b[0]
  end
  def conflict_y?(a, b)
    a[1] == b[1]
  end
  def conflict_cross?(a, b)
    a.inject(:-) == b.inject(:-) || a.inject(:+) == b.inject(:+)
  end
end

さあこれでQueenSolverの完成だよ。コードを再掲するよ。

class QueenSolver def initialize(nth=8, queens=8) @nth = nth @queens = queens end def solve all_combinations.reject do |pattern| pattern.combination(2).any? { |a, b| conflict?(a, b) } end end def all_combinations board_coordinates.combination(@queens) end def board_coordinates [*0..@nth-1].repeated_permutation(2).to_a end def conflict?(a, b) conflict_x?(a, b) || conflict_y?(a, b) || conflict_cross?(a, b) end def conflict_x?(a, b) a[0] == b[0] end def conflict_y?(a, b) a[1] == b[1] end def conflict_cross?(a, b) a.inject(:-) == b.inject(:-) || a.inject(:+) == b.inject(:+) end end

さてちゃんと動作するかテストするよ。Wikipediaによれば2クイーンと3クイーンには解がなくて、4には2つ、5には10、6には4つの解があるそうだよ。

require "rspec" require_relative "queen_solver" describe QueenSolver do context "solve 2x2 to 4x4" do it "solve 2x2" do QueenSolver.new(2,2).solve.should be_empty end it "solve 3x2" do answers = [ [[0,0],[2,1]],[[0,0],[1,2]],[[0,2],[1,0]],[[1,0],[2,2]], [[0,1],[2,0]],[[1,2],[2,0]],[[0,1],[2,2]],[[0,2],[2,1]] ] QueenSolver.new(3,2).solve.sort.should == answers.sort end it "solve 3x3" do QueenSolver.new(3,3).solve.should be_empty end it "solve 4x4" do answer = [ [[0, 1], [1, 3], [2, 0], [3, 2]], [[0, 2], [1, 0], [2, 3], [3, 1]] ] QueenSolver.new(4,4).solve.sort.should == answer.sort end end it "solve 5x5" do QueenSolver.new(5,5).solve.size.should == 10 end it "solve 6x6" do QueenSolver.new(6,6).solve.size.should == 4 end it "solve 8x8" do QueenSolver.new(8,8).solve.size.should == 92 end end

まずは2x2から4x4のテスト。

% rspec queen_solver_spec.rb -c -fd -l5
Run filtered including {:line_number=>5}
QueenSolver
  solve 2x2 to 4x4
    solve 2x2
    solve 3x2
    solve 3x3
    solve 4x4
Finished in 0.02028 seconds
4 examples, 0 failures

うまくいってるね!

次は5x5。

% rspec queen_solver_spec.rb -c -fd -l31
Run filtered including {:line_number=>31}
QueenSolver  solve 5x5
Finished in 0.37836 seconds
1 example, 0 failures

これもパスした。

次は6x6。

% rspec queen_solver_spec.rb -c -fd -l35
Run filtered including {:line_number=>35}
QueenSolver  solve 6x6
Finished in 15.05 seconds
1 example, 0 failures

これもOKだよ。ただ実行時間が15秒と結構掛かってるね..

さあ、いよいよエイトクイーン8x8をテストするよ。

% rspec queen_solver_spec.rb -c -fd -l39
Run filtered including {:line_number=>39}
QueenSolver
.....

やっぱり帰ってこない!

8x8におけるall_combinationsの数は、64C8だから..

64C8 = 64! / 8!(64-8)! = 4426165368

44億パターン!

あと3年くらい経ったらこれくらいの計算はRubyでもさっと解けるようになるのかな..

blog comments powered by Disqus

100円〜で好評発売中！
M'ELBORNE BOOKS