C++で互いに攻撃しないK個のナイトをN×Mチェス盤に配置する方法

この問題では、3つの整数値 K、N、M が与えられます。目的は、N×M のチェス盤上に、どの2つのナイトも互いに攻撃し合わないように K 個のナイトを配置することです。有効な配置方法が1通りも存在しない場合もあれば、複数の配置方法が存在する場合もあります。プログラムは、考えられるすべての有効な配置パターンを出力できなければなりません。

ナイトと「攻撃」の定義

ナイト（Knight）は、チェスの駒の一種で、ある方向に2マス進んだ後、左右いずれかに1マス移動するという特徴的な動きを持ちます。チェス盤上であれば、どの方向にも移動可能です。

攻撃（Attack）とは、ある駒が1回の有効な移動によって、他の駒と同じマスに到達できる状態を指します。つまり、2つのナイトが互いに攻撃関係にある場合、それらは同じ盤面上に共存できません。

問題例

入力： M = 3, N = 3, K = 5

出力：

K A K
A K A
K A K

A K A
K K K
A K A

解決アプローチ：バックトラッキング

この問題を解くためには、バックトラッキング（backtracking）という手法を用います。基本的な流れは以下のとおりです。

• チェス盤の左上から順に、行ごと・列ごとにナイトを1つずつ配置していく。
• 各マスにナイトを置く前に、その位置が既に他のナイトに攻撃されていないか（＝安全かどうか）を確認する。
• 安全であればナイトを配置し、残りのナイトについて再帰的に同じ処理を続ける。
• 配置できない場合は別のマスを試す。すべての組み合わせを網羅するために、ナイトを配置するたびに盤面のコピーを作成し、探索を分岐させる。

このように盤面の状態を保存しながら再帰的に探索を進めることで、条件を満たすすべての配置パターンを漏れなく取得できます。

C++による実装例

以下は、上記のアルゴリズムを実装したC++プログラムです。

#include <iostream>
using namespace std;
int m, n, k, count = 0;
void displayPositions(char** board){
    cout<<endl;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            cout<<board[i][j]<<"\t";
        }
        cout<<endl;
    }
}
void canattack(int i, int j, char a,
char** board){
    if ((i + 2) < m && (j - 1) >= 0) {
        board[i + 2][j - 1] = a;
    }
    if ((i - 2) >= 0 && (j - 1) >= 0) {
        board[i - 2][j - 1] = a;
    }
    if ((i + 2) < m && (j + 1)< n) {
        board[i + 2][j + 1] = a;
    }
    if ((i - 2) >= 0 && (j + 1) < n) {
        board[i - 2][j + 1] = a;
    }
    if ((i + 1) < m && (j + 2) <n) {
        board[i + 1][j + 2] = a;
    }
    if ((i - 1) >= 0 && (j + 2) < n) {
        board[i - 1][j + 2] = a;
    }
    if ((i + 1) < m && (j - 2) >= 0) {
        board[i + 1][j - 2] = a;
    }
    if ((i - 1) >= 0 && (j - 2) >= 0) {
        board[i - 1][j - 2] = a;
    }
}
bool canPlace(int i, int j, char** board){
    if (board[i][j] == '_')
        return true;
    else
        return false;
}
void place(int i, int j, char k, char a,
char** board, char** new_board){
    for (int y = 0; y < m; y++) {
        for (int z = 0; z < n; z++) {
            new_board[y][z] = board[y][z];
        }
    }
    new_board[i][j] = k;
    canattack(i, j, a, new_board);
}
void placeKnights(int k, int sti, int stj, char** board){
    if (k == 0) {
        displayPositions(board);
        count++;
    } else {
        for (int i = sti; i < m; i++) {
            for (int j = stj; j < n; j++) {
                if (canPlace(i, j, board)) {
                    char** new_board = new char*[m];
                    for (int x = 0; x < m; x++) {
                        new_board[x] = new char[n];
                    }
                    place(i, j, 'K', 'A', board, new_board);
                    placeKnights(k - 1, i, j, new_board);
                }
            }
            stj = 0;
        }
    }
}
int main() {
    m = 3, n = 3, k = 5;
    char** board = new char*[m];
    for (int i = 0; i < m; i++)
    board[i] = new char[n];
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++)
        board[i][j] = '_';
    }
    cout<<"The ways in which "<<k<<" knights can be placed in "<<m<<"x"<<n<<" chessboard are :\n";
    placeKnights(k, 0, 0, board);
    return 0;
}

実行結果

The ways in which 5 knights can be placed in 3x3 chessboard are :
K A K
A K A
K A K

A K A
K K K
A K A

コードのポイント

このプログラムでは、ナイトが配置されたマスを K、そのナイトに攻撃される可能性のあるマスを A として盤面上にマークしています。主な構成要素は以下のとおりです。

• canattack()：指定した位置からナイトが攻撃できる8方向のマスに「A」の印を付けます。
• canPlace()：対象のマスが空き（'_'）であれば true を返し、そこにナイトを配置できることを判定します。
• place()：現在の盤面を新しい盤面にコピーし、ナイトを配置したうえで攻撃範囲を更新します。これにより、バックトラッキング時に元の盤面が保持されます。
• placeKnights()：再帰的にナイトを配置していく本体部分です。K 個すべてを配置し終えた時点で、その盤面を表示し、解の数をカウントします。

なお、この手法はすべての組み合わせを探索するため、盤面サイズやナイトの数が大きくなると計算量が急増します。小規模な盤面での検証や学習用途に適した実装です。