【Ｃ言語】騎士（ナイト）配置の探索問題 ～４×４盤ver.～
Posted: 2017年1月11日(水) 22:27
全パターンを生成してみて、条件
- ナイトが8個
- 各ナイトが移動可能な位置に他のナイトがない
package test;
public class Main {
public static void main(String... arg) {
backTrack(0, 0);
}
private static final int SIZE = 4;
private static final int KNIGHTS = 8;
private static int[] x = new int[KNIGHTS];
private static int[] y = new int[KNIGHTS];
private static int count;
private static void show() {
char[][] buf = new char[SIZE][SIZE];
for (int i = 0; i < SIZE; i++)
for (int j = 0; j < SIZE; j++)
buf[i][j] = '.';
for (int i = 0; i < KNIGHTS; i++)
buf[x[i]][y[i]] = 'N';
count++;
System.out.println(count + ":");
for (int j = 0; j < SIZE; j++) {
System.out.print(" ");
for (int i = 0; i < SIZE; i++)
System.out.print(buf[i][j]);
System.out.println();
}
System.out.println();
}
private static void backTrack(int n, int index) {
if (n == KNIGHTS) {
show();
return;
}
for (int i = index; i < SIZE * SIZE; i++) {
x[n] = i % SIZE;
y[n] = i / SIZE;
if (checkBoard(n))
backTrack(n + 1, i + 1);
}
}
private static boolean checkBoard(int n) {
for (int i = 0; i < n; i++) {
int dx = Math.abs(x[i] - x[n]);
int dy = Math.abs(y[i] - y[n]);
if (dx == 1 && dy == 2) return false;
if (dx == 2 && dy == 1) return false;
}
return true;
}
}
#include <stdio.h>
#define SIZE 4
#define KNIGHTS 8
int b[SIZE+2][SIZE+2], k;
void step(int n, int i, int j)
{
if (n == KNIGHTS) {
printf("\n%d:\n", ++k);
for (i = 0; i < SIZE; i++) {
for (j = 0; j < SIZE; j++)
printf(b[i][j] < 0 ? " k" : " .");
putchar('\n');
}
}
else if (j < SIZE || (j = 0, ++i < SIZE)) {
if (b[i][j] == 0) {
b[i][j] = -1;
b[i+1][j-2]++, b[i+1][j+2]++, b[i+2][j-1]++, b[i+2][j+1]++;
step(n+1, i, j+1);
b[i][j] = 0;
b[i+1][j-2]--, b[i+1][j+2]--, b[i+2][j-1]--, b[i+2][j+1]--;
}
step(n, i, j+1);
}
}
int main(void)
{
step(0, 0, 0);
return 0;
}
実装してみました。みけCAT さんが書きました:4×4ならそれぞれのマスについてナイトを置く/置かないを置くパターン数が2**(4*4) = 65536通りしかないので、
全パターンを生成してみて、条件をみたすかを判定し、条件を満たしていたら出力するようにするといいでしょう。
- ナイトが8個
- 各ナイトが移動可能な位置に他のナイトがない
#include <stdio.h>
#define SIZE 4
#define NUM 8
/* ナイトが移動可能な位置 */
static const int d[8][2] = {
{1, 2}, {1, -2}, {-1, 2}, {-1, -2},
{2, 1}, {2, -1}, {-2, 1}, {-2, -1}
};
int main(void) {
int search;
int search_max = 1 << (SIZE * SIZE);
int is_first = 1;
/* 全パターン探索する */
#if 0
/* 普通に前から探索する */
for (search = 0; search < search_max; search++) {
#else
/* 逆から探索したら条件に合いそう */
for (search = search_max - 1; search >= 0; search--) {
#endif
int ok = 1;
int count = 0;
int i;
/* それぞれのマスをチェックする */
for (i = 0; ok && i < (SIZE * SIZE); i++) {
/* ナイトがいる場合 */
if ((search >> i) & 1) {
int y = i / SIZE;
int x = i % SIZE;
int j;
/* ナイトを数える */
count++;
/* 移動可能な位置に他のナイトがないかをチェックする */
for (j = 0; j < 8; j++) {
int ny = y + d[j][0];
int nx = x + d[j][1];
/* この位置が盤面内、かつナイトがいる場合、NG */
if (0 <= ny && ny < SIZE && 0 <= nx && nx < SIZE && ((search >> (ny * SIZE + nx)) & 1)) {
ok = 0;
break;
}
}
}
}
/* 条件を満たしている場合、出力する */
if (ok && count == NUM) {
int y, x;
/* 2番目以降の場合、前に出力した盤面との間に空行を入れる */
if (!is_first) putchar('\n');
/* 盤面を出力する */
for (y = 0; y < SIZE; y++) {
for (x = 0; x < SIZE; x++) {
putchar(((search >> (y * SIZE + x)) & 1) ? 'k' : '.');
}
putchar('\n');
}
/* 出力をしたことを記録する */
is_first = 0;
}
}
return 0;
}
step(0, 0, 0)を呼び出すと、かずま さんが書きました:分からないところがあれば、どこが分からないのかを質問してください。
1 The behavior is undefined in the following circumstances:
(中略)
— An array subscript is out of range, even if an object is apparently accessible with the
given subscript (as in the lvalue expression a[1][7] given the declaration int
a[4][5]) (6.5.6).
未定義動作とは思わなかったからです。みけCAT さんが書きました:すると、b[i+1][j-2]へのアクセスが発生しますが、これはb[1][-2]となり、範囲外です。
確保された範囲の外へのアクセスは未定義動作です。
C++で配列へのアクセスをラップする関数を作ってチェックすると、他にも大量の範囲外へのアクセスがあります。
どうしてこのような未定義動作を起こすプログラムを投稿したのですか？
else if (j < SIZE || (j = 0, ++i < SIZE)) {
if (b[i][j] == 0) {
b[i][j] = -1;
if (j >= 2) b[i+1][j-2]++;
b[i+1][j+2]++;
if (j >= 1) b[i+2][j-1]++;
b[i+2][j+1]++;
step(n+1, i, j+1);
b[i][j] = 0;
if (j >= 2) b[i+1][j-2]--;
b[i+1][j+2]--;
if (j >= 1) b[i+2][j-1]--;
b[i+2][j+1]--;
}
step(n, i, j+1);
}
#include <stdio.h>
#define SIZE 4
#define KNIGHTS 8
#define B(i, j) b[(i) * (SIZE+2) + (j)]
int b[(SIZE+2) * (SIZE+2)], k;
void step(int n, int i, int j)
{
if (n == KNIGHTS) {
printf("\n%d:\n", ++k);
for (i = 0; i < SIZE; i++) {
for (j = 0; j < SIZE; j++)
printf(B(i, j) < 0 ? " k" : " .");
putchar('\n');
}
}
else if (j < SIZE || (j = 0, ++i < SIZE)) {
if (B(i, j) == 0) {
B(i, j) = -1;
B(i+1, j-2)++, B(i+1, j+2)++, B(i+2, j-1)++, B(i+2, j+1)++;
step(n+1, i, j+1);
B(i, j) = 0;
B(i+1, j-2)--, B(i+1, j+2)--, B(i+2, j-1)--, B(i+2, j+1)--;
}
step(n, i, j+1);
}
}
int main(void)
{
step(0, 0, 0);
return 0;
}