今日は簡単なものを書きます。C 言語で 8 クイーン問題を解く方法です。C 言語を学んだことがある方なら、このクラシックな問題を知っているはずです。解法はさまざまですが、現在は主にバックトラックと再帰の 2 つの方法があります。今日はバックトラック + 再帰の方法を説明します。効率はあまり高くないかもしれませんが、理解しやすいです。
問題: 8 つのクイーンを国際象棋の標準盤に配置して、互いに攻撃しないようにすることができますか。具体的には、8×8 のチェス盤にクイーンを配置します。クイーンはすべての方向に移動できますが、同じ直線上には配置できません。
具体的な解法：最初の行の最初の列からチェスの駒を配置します（列優先と仮定します）。そして、その駒が占有する行と斜めのラインの番号を記録します。次に、前のすべての駒が占有する番号を除外した状態で、次の駒を有効な位置に配置します。これを繰り返し、8 つの駒を配置するまで続けます。
以下はコードです：
/*
* 8 クイーンアルゴリズム問題
* 著者: CG
* 2008 年 12 月 22 日
*/
#include "stdio.h"
#include "stdlib.h"
#include "conio.h"
#define N 8 /* クイーンの数を 8 に設定 */
int a [N], b [2*N + 1], c [2*N +1];/* 3 つの配列はそれぞれの方向のクイーンを記録する */
int count = 0;/* カウンター */
int Queen(int row) {
int col; /* ローカル変数 */
for (col = 1 ; col < = N ; col++){
if (a[col - 1] + b[row + col - 2] + c[row - col + N - 1] == 0) {
/*
* ここが非常に重要です。クイーンの位置が条件に合致するかどうかを判断するために使用されます。
* 各方向の直線上にクイーンが存在しない場合にのみ条件に合致します。
* a [col-1] は col 列にクイーンがあるかどうかを記録します。1 はクイーンがあることを示します。
* b [row+col-2] は左上から数えて row+col-1 の傾きが 1 の直線上にクイーンがあるかどうかを記録します。
* c [row-col+N-1] は右上から数えて row-col+N-1 の傾きが - 1 の直線上にクイーンがあるかどうかを記録します。
*/
a [col - 1] = 1; /* データを変更する */
b[row + col - 2] = 1;
c[row - col + N - 1] = 1;
gotoxy(col \* 2 , row);/\* クイーンを描画する \*/
putch('Q');
if (row < N){/\* まだすべての行を探索していない場合 \*/
Queen(row + 1); /\* 続ける \*/
}
else {/\* 再帰終了 \*/
count++; /\* カウンターをインクリメントする \*/
gotoxy(1 , N + 2);
printf("解法 %d ", count);
getch();
}
a\[col - 1\] = 0; /\* データをクリアする \*/
b\[row + col - 2\] = 0;
c\[row - col + N-1\] = 0;
gotoxy(col \* 2 , row); /\* グラフィックをクリアする \*/
putch('.');
}/\*if \*/
}/*for */
return 0;
}/*Queen */
int main()
{
int i, j;
clrscr ();/* 画面をクリアする */
for (i = 1 ; i <= N ; i++){/* チェス盤を描画する */
for(j = 1 ; j <= N ; j++){
gotoxy (i * 2 , j);/* 文字の位置に注意してください。大文字の Q とドットは 2 つの文字のスペースを占めます。*/
putch('.');
}/*for*/
}/*for*/
Queen (1); /* バックトラックアルゴリズムを開始する */
gotoxy (1 , N + 3); /* 最終結果を表示する */
printf ("% d 解法 n", count);
system("pause");
}/*main*/