RubyでN-Queensの問題を解決する

N-Queensは、 N*NボードにN個のクイーンを配置する必要がある興味深いコーディングチャレンジです。 。

次のようになります：

女王はすべての方向に移動できます：

• 垂直
• 水平
• 対角線

解決策（多くの場合があります）は、すべてのクイーンをボードに配置する必要があります。 ＆すべての女王は他のすべての女王の手の届かないところにいる必要があります。

この記事では、私がどのようにして解決策を思いついたのかを学びます。

計画

この種の課題を解決するときは、まず、計画を平易な英語で書き留めることから始めるのがよいでしょう。

これは、問題が何であるか、およびそれを解決するための手順を明確にするのに役立ちます。

計画を立てるのに問題がある場合は、問題を100％理解していることを確認してください 。

N-Queensソリューションの私の計画：

• 開始@位置0,0
• 有効な位置の場合：クイーンを配置し、列を進め（+ 1）、行を0に設定します
  • 上、下、左、右、斜めを確認
• それ以外の場合：1マス進む
  • 現在の位置==nでない限り、上に移動します（行+ 1）
  • クイーンを現在の列に配置できない場合のバックトラック
    • 最後の女王を削除
    • 行と列を行+1で最後の女王の位置に設定します

これは私が最初に書き留めたもののよりクリーンなバージョンです。

実装する前に、詳細が必要な手順をドリルダウンします。

今 ：

あなたの計画は完璧ではありませんが（私の計画は完璧ではありませんでした）、それはあなたに何に向けて取り組むべきかについての考えを与えるでしょう。

しっかりとした計画を立てられない場合は、解決策を探すことに何の問題もありません …

…ソリューションがどのように機能するかを理解してから、独自のソリューションを作成してください。

有効な動きを見つける

位置が有効かどうかを確認するには、いくつかの方向を見る必要があります。

2Dボードをいじくり回す代わりに、クイーンの配列を用意することにしました。 ボード内での位置。

次に、このクイーンの配列を検証する位置と照合します。

たとえば、行チェックの場合：

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

これにより、行が取得された場合はクイーンが返され、取得されなかった場合はnilが返されます。

クイーンを配置した後、次の列に移動するので、列が空いているかどうかを確認する必要はありません。 。

対角線については、4つあるため、追加の作業が必要です。

右上の対角線のコードは次のとおりです。

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

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

  diagonals
end

他の対角線は同じですが、唯一の違いはループと方向（行+ 1 /行-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でそれを解決する方法について学びました。また、問題解決スキルを向上させる方法も学びました。

この記事が気に入ったら、その恩恵を受けることができる人と共有してください。

読んでくれてありがとう！