今日は N クイーンと関連する問題、ナイトの巡回問題、またはチェスの駒の巡回問題について話します。もちろん、ここでのナイトはチェスのナイトです。両者には多くの共通点がありますが、制約される経路の違いが主な違いです。N クイーンは主に条件を満たすだけで自由に配置できますが、ナイトの巡回は上下の経路に関係があります。深さ優先探索や幅優先探索などのグラフアルゴリズム、およびグラフの構築などのアルゴリズムを主に使用します。
要件：チェス盤の任意の位置にある駒のナイトを実装し、チェス盤の各マスを重複せずに通過させる。
分析：まず、ナイトがチェス盤上でどのように移動するかを知る必要があります。国際チェスのルールに基づいて、ナイトには 8 つの移動可能な位置がありますが、境界に関しては別途考慮する必要があります。ナイトの移動はこれら 8 つの可能性を考慮する必要があり、使用できない位置を除外し、使用できる位置に移動する必要があります。8 つの位置が使用できない場合は、前のステップに戻る必要があります。これは幅優先探索と同様のものであり、ナイトがすべての位置を通過し、移動するための使用可能な位置がない場合、巡回は終了します。
分析が完了しました。以下にコードを示します。質問があれば、コメントを残してください。
/* ナイトの巡回問題
* 2008 年 12 月 28 日 CG
**/
#include"stdio.h"
#include"conio.h"
#include"stdlib.h"
int f[11][11] ;
int adjm[121][121];
long fgf;
int n,m;
int es(int i1,int j1,int i2,int j2){
adjm[(i1-1)*n+j1][(i2-1)*n+j2]=1;
adjm[(i2-1)*n+j2][(i1-1)*n+j1]=1;
return;/* パスを接続する */
}/*es*/
int creatadjm (){/* 使用可能なパスを描画する */
int i,j;
for(i=1;i< =n;i++)
for(j=1;j<=n;j++)
f [i][j]=0;/* パスの初期化 */
for(i=1;i<=m;i++)
for(j=1;j<=m;j++)
adjm [i][j]=0;/* チェス盤の初期化 */
for(i=1;i<=n;i++)
for(j=1;j<=n;j++)
if (f [i][j]==0){/* 有効なパスを設定 */
f[i][j]=1;
if((i+2<=n)&&(j+1<=n)) es(i,j,i+2,j+1);
if((i+2<=n)&&(j-1>=1)) es(i,j,i+2,j-1);
if((i-2>=1)&&(j+1< =n)) es(i,j,i-2,j+1);
if((i-2>=1)&&(j-1>=1)) es(i,j,i-2,j-1);
if((j+2< =n)&&(i+1<=n)) es(i,j,i+1,j+2);
if((j+2<=n)&&(i-1>=1)) es(i,j,i-1,j+2);
if((j-2>=1)&&(i+1< =n)) es(i,j,i+1,j-2);
if((j-2>=1)&&(i-1>=1)) es(i,j,i-1,j-2);
}/*if*/
return 1;
}/*createadjm*/
int travel (int p,int r){/* ナイトの巡回 */
int i,j,q;
for(i = 1 ; i < = n ; i++)
for(j = 1 ; j <= n ;j++)
if (f [i][j] > r)/* 条件に合致する？*/
f[i][j]=0;
r = r + 1;
i=((p-1) / n) + 1;
j=((p-1) % n) + 1;
f[i][j] = r;
fgf++;/* パスの選択記録 */
for(q = 1 ; q < = m ; q++){
i=((q-1) / n) + 1;
j=((q-1) % n) + 1;
if((adjm[p][q] == 1) && (f[i][j] == 0))
travel (q , r);/* 再帰的に巡回 */
}/*for*/
return 1;
}/*travel*/
int main(){
int i,j,k,l;
clrscr();
printf ("チェス盤のサイズ n を入力してください：");scanf ("% d",&n);/* チェス盤のサイズを入力（最大 11）*/
m = n * n;
creatadjm ();/* 使用可能なパスを描画 */
/* 使用可能なパスを出力
for (i=1;i<=m;i++){/* 出力 */
for(j=1;j<=m;j++) printf("%2d",adjm[i][j]);
printf("n");
}
getchar();
*/
printf ("開始位置 i,j を入力してください：");/* 巡回を開始する位置を入力 */
scanf("%d %d",&i,&j);
l = (i - 1) * n + j;
while ((i> 0) || (j > 0)){/*0 0 が入力されるまでループ */
for(i = 1 ; i < = n ; i++)
for(j = 1 ; j <= n ; j++)
f [i][j] = 0;/* パスの初期化 */
k = 0;
travel (l , k);/* 巡回 */
printf (" 選択: % d パス n 最終パス",fgf);/* パスの選択回数を出力 */
fgf=0;/* リセット */
for (i = 1 ; i <= n ; i++){/* 巡回パスを出力 */
for(j = 1 ; j <= n ; j++)
printf("%4d",f[i][j]);
printf("n");
}
printf ("開始位置 i,j を入力してください：");scanf ("% d % d",&i,&j);/* 続けて入力 */
l = (i - 1) * n + j;
}/*while*/
return 0;
}/*main*/