|
［ 簡単な説明 ］
チェスのクイーンは、縦、横、斜めの８方向に直進できる駒ですが、これをチェス盤（８×８）の上に８個おけるだろうか？ というのが「８クイーン」という問題です。（明らかに８個を超えては置けません。） 「Ｎクイーン」はこれを拡張し、Ｎ×Ｎの盤の上にＮ個のクイーンを置こう という問題となります。 Ｎ＝２、３の場合は解はありません。Ｎ＝４以上で解が存在します。 Ｎ＝４以上のケースにおける解の個数は、下記となります。 |
| Ｎ | 解の個数 | |
| 全パターン数 | 鏡像解を除く パターン数 |
|
| ４ | １ | １ |
| ５ | １０ | ２ |
| ６ | ４ | １ |
| ７ | ４０ | ６ |
| ８ | ９２ | １２ |
| ９ | ３５２ | ４６ |
| １０ | ７２４ | ９２ |
| １１ | ２６８０ | ３４１ |
| １２ | １４２００ | − (*1) |
|
出力例は、最もポピュラーな８クイーン問題（Ｎ＝８）を、鏡像解排除オプションにて解いた例です。 nqueen 8 -a -d 鏡像解（回転・反転及びその組合せで同じパターンとなる解）の排除は、解が１つ求まるたびに、他の７つの鏡像解を求めて、リストに登録しておき、解の候補ができた際にそのリストでチェックするというオーソドックスなものです。 ８クイーンの解は、全部で９２パターンで、鏡像解を除くと１２パターンとなります。 |
（トップに戻る）
/* nqueen.c */
/*
original : C MAGAZINE 1991年8月号「アルゴリズムとデータ構造入門」
８クイーン求解プログラム。
history : 鏡像解排除ルーチン追加。
*/
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define SUCCESS 1 /* 成功。 */
#define FAIL 0 /* 失敗。 */
#define FREE 1 /* この場所は利き筋でない。(置ける) */
#define NOT_FREE 0 /* この場所は利き筋。 (置けない) */
typedef struct qlist
{
char **qpos;
struct qlist *next;
} QLIST;
QLIST *getqlist(int n);
void set_solution(int pos[], int n);
int check_solution(int pos[], int n);
void usage(char *prog);
void init_board(int n, int no_mirror);
void print_queens(int n);
void try_all(int a, int n, int no_mirror);
int try(int a, int n);
void nqueen(int n, int do_all, int no_mirror);
QLIST *start; /* 見つかった解とその鏡像解 */
int *pos; /* 各行に置かれたクイーンの位置。 */
int *col; /* クイーンが垂直方向に利いているかを示す配列。 */
int *down; /* クイーンが右斜め下向きに利いているかを示す配列。 */
int *up; /* クイーンが右斜め上向きに利いているかを示す配列。 */
QLIST *getqlist(int n)
{
QLIST *p;
int i;
p = (QLIST *)malloc(sizeof(QLIST));
if(p == NULL)
{
fprintf(stderr, "Error : out of memory in getqlist()\n");
exit(-1);
}
p->qpos = (char **)malloc(8 * sizeof(char *));
if(p->qpos == NULL)
{
fprintf(stderr, "Error : out of memory in getqlist()\n");
exit(-1);
}
p->qpos[0] = (char *)calloc(8 * n, sizeof(char));
if(p->qpos[0] == NULL)
{
fprintf(stderr, "Error : out of memory in getqlist()\n");
exit(-1);
}
for(i = 1; i < 8; i++) p->qpos[i] = p->qpos[i - 1] + n;
p->next = NULL;
return p;
}
void set_solution(int pos[], int n)
{
QLIST *p, *q;
int i, j, j4, n1;
for(p = start; p->next != NULL; p = p->next) ;
n1 = n - 1;
for(i = 0; i < n; i++) p->qpos[0][i] = pos[i];
for(i = 0; i < n; i++) p->qpos[1][pos[i]] = n1 - i;
for(i = 0; i < n; i++) p->qpos[2][n1 - i] = n1 - pos[i];
for(i = 0; i < n; i++) p->qpos[3][n1 - pos[i]] = i;
for(j = 0, j4 = 4; j < 4; j++, j4++)
for(i = 0; i < n; i++) p->qpos[j4][i] = n1 - p->qpos[j][i];
q = getqlist(n);
p->next = q;
}
int check_solution(int pos[], int n)
{
QLIST *p;
int i, j;
p = start;
do
{
for(i = 1; i < 8; i++)
{
for(j = 0; j < n; j++) if(pos[j] != p->qpos[i][j]) break;
if(j == n) return 0;
}
p = p->next;
} while(p->next != NULL);
return 1;
}
void usage(char *prog)
{
fprintf(stderr, "使用法 : %s N [ -a [ -d ]]\n", prog);
fprintf(stderr, " N : クイーンの数（省略付加）\n");
fprintf(stderr, " -a : すべての解を表示するオプション\n");
fprintf(stderr, " -d : 鏡像解を排除するオプション（-a オプション指定時のみ有効）\n");
fprintf(stderr, " （デフォルトでは最初の解のみ表示）\n");
exit(0);
}
void init_board(int n, int no_mirror) /* クイーンの位置。利き筋を初期化する。 */
{
int i;
for (i = 0; i < n; i++) pos[i] = -1;
for (i = 0; i < n; i++) col[i] = FREE;
for (i = 0; i < 2 * n - 1; i++) down[i] = FREE;
for (i = 0; i < 2 * n - 1; i++) up[i] = FREE;
if(no_mirror) start = getqlist(n);
}
void print_queens(int n) /* クイーンの位置を出力する。 */
{
static long count = 0;
int i, j;
printf("*** solution %ld ***\n", ++count);
for(i = 0; i < n; i++)
{
for(j = 0; j < n; j++) printf((pos[i] == j)? "Q ": ". ");
printf("\n");
}
printf("\n");
}
void try_all(int a, int n, int no_mirror)
/* a行目以降すべての行にクイーンを置いてみる。
(すべてのパターンを表示する) */
{
static int flag = 1;
int b; /* 左から右に向かって順番にクイーンが
置けるかどうかを調べる。 */
for(b = 0; b < n; b++)
{
/* a行目のb番目に置けるかどうか調べる。 */
if(col[b] == FREE && up[a + b] == FREE && down[a - b + (n-1)] == FREE)
{
/* 置くことができた。 */
pos[a] = b; /* 場所を記録して、利き筋をセットする。 */
col[b] = NOT_FREE;
up[a + b] = NOT_FREE;
down[a - b + (n-1)] = NOT_FREE;
/* N個のクイーンをすべて置くことができれば成功である。 */
if (a + 1 >= n)
{
if(no_mirror == 0) print_queens(n);
else
{
if(flag || check_solution(pos, n))
{
set_solution(pos, n);
print_queens(n);
}
flag = 0;
}
}
else try_all(a + 1, n, no_mirror);
pos[a] = -1; /* クイーンを取り除く。 */
col[b] = FREE;
up[a + b] = FREE;
down[a - b + (n-1)] = FREE;
}
}
}
int try(int a, int n) /* a行目以降すべての行にクイーンを置いてみる。 */
{
int b;
/* 左から右に向かって順番にクイーンが
置けるかどうかを調べる。 */
for(b = 0; b < n; b++)
{
/* a行目のb番目に置けるかどうか調べる。 */
if(col[b] == FREE && up[a + b] == FREE && down[a - b + (n-1)] == FREE)
{
/* 置くことができた。*/
pos[a] = b; /* 場所を記録して、利き筋をセットする。 */
col[b] = NOT_FREE;
up[a + b] = NOT_FREE;
down[a - b + (n-1)] = NOT_FREE;
/* N個のクイーンをすべて置くことができれば成功である。 */
if(a + 1 >= n) return SUCCESS;
/* a+1行目以降のすべての行に置けたら成功である。 */
if(try(a + 1, n) == SUCCESS) return SUCCESS;
/* 失敗した。クイーンを取り除く。 */
pos[a] = -1;
col[b] = FREE;
up[a + b] = FREE;
down[a - b + (n-1)] = FREE;
}
}
return FAIL; /* 結局この行には置ける場所がなかった。 */
}
void nqueen(int n, int do_all, int no_mirror)
{
pos = (int *)calloc(n, sizeof(int));
col = (int *)calloc(n, sizeof(int));
down = (int *)calloc(2 * n - 1, sizeof(int));
up = (int *)calloc(2 * n - 1, sizeof(int));
if(pos == NULL || col == NULL || down == NULL || up == NULL)
{
fprintf(stderr, "Error : out of memory in nqueen()\n");
exit(-1);
}
init_board(n, no_mirror);
if(do_all) try_all(0, n, no_mirror);
else
{
if(try(0, n) == SUCCESS) print_queens(n);
else printf("Sorry, but there is no solution.\n");
}
free((char *)pos);
free((char *)col);
free((char *)down);
free((char *)up);
}
int main(int argc, char *argv[])
{
int do_all = 0, no_mirror = 0, n;
if(argc < 2) usage(argv[0]);
n = atoi(argv[1]);
if(n < 4)
{
fprintf(stderr, "Error : illegal parameter input.\n");
exit(-1);
}
if(argc >= 3)
{
if(strcmp(argv[2], "-a") == 0 || strcmp(argv[2], "-A") == 0)
do_all = 1;
if(argc >= 4 && strcmp(argv[3], "-d") == 0 || strcmp(argv[2], "-D") == 0)
no_mirror = 1;
}
nqueen(n, do_all, no_mirror);
return 1;
}
|
（トップに戻る）
*** solution 1 *** *** solution 2 *** *** solution 3 *** Q . . . . . . . Q . . . . . . . . Q . . . . . . . . . . Q . . . . . . . . Q . . . . . Q . . . . . . . . . . . Q . . . . . . . Q . . . . . Q . . . . . . . Q . . . . Q . . . . . . . . . . . . Q . . Q . . . . . . . . . . . Q . . . Q . . . . . . . . . . . Q . . . . Q . . . . Q . . . . . . . . Q . . . . . . . Q . . . . . . . . . . . . Q . . . . Q . . . . . . . . Q . . . . . . . Q . . . *** solution 4 *** *** solution 5 *** *** solution 6 *** . Q . . . . . . . Q . . . . . . . Q . . . . . . . . . . Q . . . . . . . Q . . . . . . . . Q . . . . . . . . Q . . . . . . . Q . Q . . . . . . . Q . . . . . . . . . . Q . . . . . . . . . . Q . . . Q . . . . . Q . . . . . . . . . . Q . . . . . . . . . . . Q . . . . . . . Q . . . . . . . Q . . . . . Q . . . . . . . Q . . . . Q . . . . . . . . Q . . . . . . Q . . . . . . . . . Q . . . *** solution 7 *** *** solution 8 *** *** solution 9 *** . Q . . . . . . . Q . . . . . . . Q . . . . . . . . . . . Q . . . . . . . . Q . . . . . . . Q . . . . . . . . Q . . Q . . . . . . . . . Q . . . . . Q . . . . . . . . . . Q . . . . . . . . . Q Q . . . . . . . . . . . . . . Q Q . . . . . . . . . . Q . . . . . . . . Q . . . . . . Q . . . . . . . . . . Q . Q . . . . . . . . . . . . Q . . . . . . Q . . . . . . Q . . . . . . Q . . . . . *** solution 10 *** *** solution 11 *** *** solution 12 *** . . Q . . . . . . . Q . . . . . . . Q . . . . . . . . . Q . . . . . . . Q . . . . . . . . Q . . . Q . . . . . . . . . . . . . Q . Q . . . . . . . . . . . . . Q . . . Q . . . . . . . . Q . . . Q . . . . . . . Q . . . . . . . . . . . . . . Q . . . . . . Q . . . . . . . Q . Q . . . . . . . . . . Q . . . . . Q . . . . . . . . . . . . Q . . . . . . Q . . . . . . . Q . . . . . Q . . . . |
戻る（メインメニュー）
戻る（その他メニュー）
注意事項