RubyでNクイーン問題を解く方法【バックトラッキングの実装を徹底解説】

N-Queens（Nクイーン）は、N×Nの盤面にN個のクイーンを配置する、非常に興味深いコーディングチャレンジです。

イメージは以下のようになります。

クイーンは全方向に移動できる駒です。

• 縦方向
• 横方向
• 斜め方向

この問題の解答（複数存在する場合もあります）では、すべてのクイーンを盤上に配置しつつ、どのクイーンも他のクイーンの攻撃範囲に入らないようにする必要があります。

この記事では、私がどのような思考プロセスで解答にたどり着いたのかを紹介します。

まずは計画を立てる

この種のチャレンジに取り組むときは、まず平易な言葉で計画を書き出すことから始めるのが効果的です。

そうすることで、「何が問題なのか」「それを解くための手順は何か」が明確になります。

もし計画を書くのに苦労しているなら、問題を100%理解できているかを今一度確認しましょう。

私がN-Queensの解答のために書いた計画は以下の通りです。

• 位置(0,0)からスタートする
• 有効な位置であれば：クイーンを置き、列を1つ進め（+1）、行を0に戻す
  • 上下左右と斜め方向をチェックする
• 有効でなければ：1マス進む
  • 現在位置がnに達していない限り、上へ進む（row + 1）
  • 現在の列にクイーンを置けない場合はバックトラックする
    • 最後に置いたクイーンを削除する
    • 行と列を、最後のクイーンの位置+1に設定する

これは、最初に書き出した内容を整理したバージョンです。

実装前に、より詳細な検討が必要なステップについては、さらに掘り下げて考えます。

大事なポイント：

最初の計画は完璧ではないでしょう（私の計画もそうでした）。それでも、目指すべき方向性を示してくれるのが計画の価値です。

もし確固たる計画が書けないのであれば、解答を調べることに何の問題もありません。

まず解答の仕組みを理解し、そのうえで自分自身のコードを書けばいいのです。

有効な手の判定方法

ある位置が有効かどうかを判定するには、複数の方向を調べる必要があります。

2次元の盤面を直接扱う代わりに、私は盤上のクイーンとその位置を配列として管理することにしました。

そして、検証したい位置を、このクイーンの配列と照合します。

例えば、行のチェックは以下のように書けます。

def queen_in_row(row)
  @queens_in_board.find { |r, c| r == row }
end

このメソッドは、その行が既に使用されていればクイーンを返し、空いていればnilを返します。

列が空いているかどうかのチェックは不要です。クイーンを置いた直後に次の列へ移動するため、同じ列に2つのクイーンが並ぶことはないからです。

一方、斜め方向は4つあるため、もう少し工夫が必要です。

右上方向の斜めを求めるコードは以下の通りです。

def right_upper_diagonal_for(row, column, n)
  diagonals = []

  until row == n || column == n
    diagonals << [row += 1, column += 1]
  end

  diagonals
end

他の3つの斜め方向もほぼ同じ構造で、違いはループの終了条件と進む方向（row + 1 / row - 1）だけです。

正しく動作させるまでに多少の試行錯誤がありましたが、それはごく自然なことです。

重要なのは、これらのメソッドを個別にテストして正しく動くことを確認することです。動作するメソッド群が揃えば、あとはそれらを組み合わせるだけで完全な解答になります。

すべての斜め方向をまとめ、盤上の全クイーンと照合するメソッドがこちらです。

def queen_in_diagonal(row, column, n)
  diagonals =
    right_upper_diagonal_for(row, column, n) +
    left_upper_diagonal_for(row, column, n) +
    left_lower_diagonal_for(row, column, n) +
    right_lower_diagonal_for(row, column, n)


  diagonals.any? { |r, c| r == row && c == column } ||
  diagonals.any? { |r, c| @queens_in_board.any? { |qr, qc| r == qr && c == qc } }
end

バックトラッキングの実装方法

このような自明でない課題を解くには、鍵となる洞察・テクニック・アルゴリズムの知識が欠かせません。

N-Queensの場合、その鍵となるのがバックトラッキングです。

バックトラッキングとは、以前に行った操作（盤上へのクイーン配置など）を取り消し、別の構成で再度試す手法のことです。

当初はここが最难関だと思っていましたが、実際に取り組んでみると意外と簡単でした。

仕組みを理解するために、私は簡単なシミュレーションを行いました。

盤面と、クイーンを表す箱を描いてみます。

そして、マウスで直接箱を盤面上に動かしながら、アルゴリズムの挙動をシミュレートしました。

コードは以下の通りです。

while row >= n
  row    = @queens_in_board[-1][0] + 1
  column = @queens_in_board[-1][1]

  puts "Backtracking, deleted: #{@queens_in_board.pop}"
end

行き詰まったときは、他の問題でも同じ手法が使えます。お絵かきソフトや紙に図を描いて、実際に手を動かしてみると良いでしょう。

この仕組みの要点は以下の通りです。

• 上へ進み続け、盤面の最上部に達したら、その列にはクイーンを置けなかったことを意味する
• 現在位置を最後のクイーンの位置に設定し、そのクイーンを盤から削除することでバックトラックする
• その位置からクイーンを置けない場合は、さらにバックトラックを繰り返す

行位置の「+1」こそが、最後のクイーンを前進させて再配置し、新たな盤面構成を切り開くための仕組みです。

n = 4でこのコードを実行すると、次のような出力が得られます（n = 2とn = 3には解が存在しません）。

"placing at 0 0"
"placing at 2 1"
Backtracking, deleted: [2, 1]
"placing at 3 1"
"placing at 1 2"
Backtracking, deleted: [1, 2]
Backtracking, deleted: [3, 1]
Backtracking, deleted: [0, 0]
"placing at 1 0"
"placing at 3 1"
"placing at 0 2"
"placing at 2 3"

以下のGIFは、このアルゴリズムの動きを視覚化した例です。

完全なコード

def solve_n_queens(n)
  @queens_in_board = []

  row = 0
  column = 0

  until @queens_in_board.size == n
    if queen_in_row(row) || queen_in_diagonal(row, column, n)
      row += 1

      while row >= n
        row    = @queens_in_board[-1][0] + 1
        column = @queens_in_board[-1][1]

        puts "Backtracking, deleted: #{@queens_in_board.pop}"
      end
    else
      place_queen(row, column)

      p "placing at #{row} #{column}"

      row = 0
      column += 1
    end
  end

  @queens_in_board
end

def queen_in_row(row)
  @queens_in_board.find { |r, c| r == row }
end

def queen_in_diagonal(row, column, n)
  diagonals =
    right_upper_diagonal_for(row, column, n) +
    left_upper_diagonal_for(row, column, n) +
    left_lower_diagonal_for(row, column, n) +
    right_lower_diagonal_for(row, column, n)


  diagonals.any? { |r, c| r == row && c == column } ||
  diagonals.any? { |r, c| @queens_in_board.any? { |qr, qc| r == qr && c == qc } }
end

def top_row?(row, n)
  row == n
end

def place_queen(row, column)
  @queens_in_board << [row, column]
end

def right_upper_diagonal_for(row, column, n)
  diagonals = []

  until row == n || column == n
    diagonals << [row += 1, column += 1]
  end

  diagonals
end

def left_upper_diagonal_for(row, column, n)
  diagonals = []

  until row == n || column == 0
    diagonals << [row += 1, column -= 1]
  end

  diagonals
end

def right_lower_diagonal_for(row, column, n)
  diagonals = []

  until row == 0 || column == n
    diagonals << [row -= 1, column += 1]
  end

  diagonals
end

def left_lower_diagonal_for(row, column, n)
  diagonals = []

  until row == 0 || column == 0
    diagonals << [row -= 1, column -= 1]
  end

  diagonals
end

def print_board(n)
  board = Array.new(n) { Array.new(n) { "." } }

  @queens_in_board.each { |queen| board[queen[0]][queen[1]] = "Q" }

  board.map { |n| n.join("|") }.reverse
end

p solve_n_queens(4)
p solve_n_queens(5)

puts print_board(5)

再帰による別解

こちらは、すべての可能な解を見つけられる別バージョンです。

def solve_n_queens(n, column = 0, queens_in_board = [])
  @queens_in_board = queens_in_board

  n.times do |row|
    unless queen_in_row(row) || queen_in_diagonal(row, column, n)
      place_queen(row, column)

      solve_n_queens(n, column + 1, @queens_in_board)

      remove_last_queen
    end
  end

  puts print_board(n) if @queens_in_board.size == n
end

変更が必要なのはsolve_n_queensメソッドだけです。

このバージョンでは、再帰（自分自身を呼び出すメソッド）を使って、すべての部分的な解を網羅的に探索します。

完全な解が見つかったタイミングで、print_boardメソッドを使って結果を出力します。

まとめ

この記事では、N-Queensというコーディングチャレンジの概要と、Rubyでの具体的な解き方を学びました。さらに、問題解決スキルを高めるためのアプローチ（計画を書き出す、個別にテストする、図でシミュレーションするなど）も身につけることができました。

この記事が役に立ったと感じたら、ぜひ周りの方にもシェアしてください。

最後までお読みいただきありがとうございました！