バックトラッキングを使用したN-Queens問題のJava/C++での実装
チェスが好きなら、Nクイーンの問題について学ぶのも楽しいでしょう。バックトラッキングを理解するのは良い問題です。
バックトラックとは何ですか？
バックトラッキングでは、多くの利用可能な動きの中から1つの可能な動きから始めます。その後、問題を解決しようとします。
選択された手で問題を解決できる場合は、解決策を印刷します。それ以外の場合は、バックトラックして他の手を選択し、解決を試みます。
どの手も効果がない場合、問題に対する解決策は存在しないと主張します。
N-クイーンズ問題とは何ですか？
How can N queens be placed on an NxN chessboard so that no two of them attack each other?
この問題はN=4およびN=8で一般的に見られます。
N=4の場合の例を見てみましょう。
問題を解く前に、チェスにおけるクイーンの動きについて知っておく必要があります。
クイーンは任意の方向に任意の数だけ移動できます。唯一の制約は、移動中に方向を変えることができないことです。
女王の動きを見れば明らかなことの一つは、同じ行または列に二つの女王が存在することはできないということです。
それにより、各行および各列に1つのクイーンだけを配置することができます。
Nが4のとき、解は次のようになります：
しかし、私たちはこの取り決めをどうやって得るのですか？
Nクイーン問題の解決策
私たちがこれを解決しようとする方法は、位置にクイーンを置き、それが攻撃されている可能性を排除することです。各行/列に1つのクイーンを置きます。
女王がその選択した位置で攻撃されていることが分かった場合、次の位置を試します。
もしクイーンが行のすべての位置で攻撃されている場合、バックトラックして現在の位置の前に配置されたクイーンの位置を変更します。
私たちはN個のクイーンがすべて無事に配置されるまで、クイーンを配置しバックトラッキングするこのプロセスを繰り返します。
ステップバイステップのバックトラッキングは以下のように示されています:
赤い十字は、女王から攻撃されている位置を示します。女王を配置できる状態に達したとき、しかし行のすべての位置が攻撃されている場合、バックトラックします。
これは問題に対する唯一の解決策ではありません。各クイーンを時計回りに一歩進めると、別の解決策が得られます。
この例では、私たちはクイーンを行に従って配置しましたが、列に従って同じことをすることもできます。その場合、各クイーンは列に属します。
C++とJavaにおけるN-クイーン問題の実装
N-Queens問題をC++で実装する:
#define N 4
#include <stdbool.h>
#include <stdio.h>
//function to print the solution
void printSolution(int board[N][N])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
printf(" %d ", board[i][j]);
printf("\n");
}
}
// function to check whether the position is safe or not
bool isSafe(int board[N][N], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i])
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j])
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j])
return false;
return true;
}
// The function that solves the problem using backtracking
bool solveNQUtil(int board[N][N], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQUtil(board, col + 1))
return true;
//backtrack if the above condition is false
board[i][col] = 0; // BACKTRACK
}
}
return false;
}
// driver program to test above function
int main()
{
int board[N][N] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (solveNQUtil(board, 0) == false) {
printf("Solution does not exist");
return 0;
}
printSolution(board);
return true;
return 0;
}
JavaでのN-クイーンズ問題の実装:
package com.JournalDev;
public class Main {
static final int N = 4;
// print the final solution matrix
static void printSolution(int board[][])
{
for (int i = 0; i < N; i++) {
for (int j = 0; j < N; j++)
System.out.print(" " + board[i][j]
+ " ");
System.out.println();
}
}
// function to check whether the position is safe or not
static boolean isSafe(int board[][], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i] == 1)
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1)
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j] == 1)
return false;
return true;
}
// The function that solves the problem using backtracking
public static boolean solveNQueen(int board[][], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQueen(board, col + 1))
return true;
//backtrack if the above condition is false
board[i][col] = 0;
}
}
return false;
}
public static void main(String args[])
{
int board[][] = { { 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 },
{ 0, 0, 0, 0 } };
if (!solveNQueen(board, 0)) {
System.out.print("Solution does not exist");
return;
}
printSolution(board);
}
}
Output :
0 0 1 0
1 0 0 0
0 0 0 1
0 1 0 0
N=8 の出力は :
1 0 0 0 0 0 0 0
0 0 0 0 0 0 1 0
0 0 0 0 1 0 0 0
0 0 0 0 0 0 0 1
0 1 0 0 0 0 0 0
0 0 0 1 0 0 0 0
0 0 0 0 0 1 0 0
0 0 1 0 0 0 0 0
コード実装の理解
位置が攻撃されているかどうかを確認するために、isSafeという関数を作成しました。
その位置が攻撃から安全であれば、関数は真を返します。
static boolean isSafe(int board[][], int row, int col)
{
int i, j;
for (i = 0; i < col; i++)
if (board[row][i] == 1)
return false;
for (i = row, j = col; i >= 0 && j >= 0; i--, j--)
if (board[i][j] == 1)
return false;
for (i = row, j = col; j >= 0 && i < N; i++, j--)
if (board[i][j] == 1)
return false;
return true;
}
最初のforループは列をチェックし、2番目と3番目のforループは2つの対角線をチェックします。
次のコードは、女王をその位置に配置し、バックトラッキングを行う役割を担っています。女王の位置を示すために、そのセルを行列内で1に設定します。女王を置く前に、位置が安全であることを確認するためにisSafeを呼び出します。
public static boolean solveNQueen(int board[][], int col)
{
if (col >= N)
return true;
for (int i = 0; i < N; i++) {
//if it is safe to place the queen at position i,col -> place it
if (isSafe(board, i, col)) {
board[i][col] = 1;
if (solveNQueen(board, col + 1))
return true;
//backtrack if the above condition is false
board[i][col] = 0;
}
}
return false;
}
再帰呼び出しは盤面を渡し、列をcol+1に設定します。再帰呼び出しがfalseを返す場合、エントリを0にリセットすることでバックトラックします。
結論
これがバックトラッキングを使用してN-クイーン問題を解決する方法です。バックトラッキングについてもっと学ぶには、数独の問題を解いてみてください。