合計 昨日 今日

【C言語】騎士(ナイト)配置の探索問題 ~4×4盤ver.~

フォーラムルール
フォーラムルールはこちら  ※コードを貼り付ける場合は [code][/code] で囲って下さい。詳しくはこちら
Name: プログラミングおじさん
[URL]
Date: 2017年1月11日(水) 22:27
No: 1
(OFFLINE)

 【C言語】騎士(ナイト)配置の探索問題 ~4×4盤ver.~

各ナイトが移動可能な位置に他のナイトがないように8個のナイトを4×4の盤面に置き,その配置を以下のように出力するプログラムを書きたいのですが,プログラミング初心者のため何をどうしたらいいのか全く分かりません.詳しい方,どうかよろしくお願いします.(対象性を認めずに6種類,対象性を認めると3種類あることまでは分かりました.今回は6種類とも出力したいです.)

コード[C++]: 全て選択
1
#define SIZE 4



kkkk
・・・・
・・・・
kkkk

kk・k
k・・・
・・・k
k・kk



Name: みけCAT
[URL]
伝説なるハッカー(683,511 ポイント)
Date: 2017年1月11日(水) 22:59
No: 2
(OFFLINE)

 Re: 【C言語】騎士(ナイト)配置の探索問題 ~4×4盤ver.~

4×4ならそれぞれのマスについてナイトを置く/置かないを置くパターン数が2**(4*4) = 65536通りしかないので、
全パターンを生成してみて、条件
  • ナイトが8個
  • 各ナイトが移動可能な位置に他のナイトがない
をみたすかを判定し、条件を満たしていたら出力するようにするといいでしょう。
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

Name: たいちう
[URL]
ハッカー(142,090 ポイント)
Date: 2017年1月12日(木) 16:34
No: 3
(OFFLINE)

 Re: 【C言語】騎士(ナイト)配置の探索問題 ~4×4盤ver.~

こういうのは大好きなので作ってみました。
手元にCの環境がなかったのでJavaですが何となく読めますでしょうか。

コード[Java]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
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;
    }
}

Name: かずま
[URL]
Date: 2017年1月12日(木) 23:11
No: 4
(OFFLINE)

 Re: 【C言語】騎士(ナイト)配置の探索問題 ~4×4盤ver.~

C だから読めるでしょう。
分からないところがあれば、どこが分からないのかを質問してください。
コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#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;
}

Name: みけCAT
[URL]
伝説なるハッカー(683,511 ポイント)
Date: 2017年1月12日(木) 23:54
No: 5
(OFFLINE)

 Re: 【C言語】騎士(ナイト)配置の探索問題 ~4×4盤ver.~

みけCAT さんが書きました:4×4ならそれぞれのマスについてナイトを置く/置かないを置くパターン数が2**(4*4) = 65536通りしかないので、
全パターンを生成してみて、条件
  • ナイトが8個
  • 各ナイトが移動可能な位置に他のナイトがない
をみたすかを判定し、条件を満たしていたら出力するようにするといいでしょう。

実装してみました。
コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
#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;
}

実行結果
コード[Text]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
kkkk
....
....
kkkk
 
kk.k
k...
...k
k.kk
 
k.kk
...k
k...
kk.k
 
k.k.
.k.k
k.k.
.k.k
 
k..k
k..k
k..k
k..k
 
.k.k
k.k.
.k.k
k.k.

このコードはナイトが8個を超えるパターンもチェックして効率が悪いので、たいちうさんのコードの方がよさそうですね。

かずま さんが書きました:分からないところがあれば、どこが分からないのかを質問してください。

step(0, 0, 0)を呼び出すと、
n == KNIGHTS、すなわち0 == 8は偽なので、elseの方に行きます。
j < SIZE、すなわち0 < 4は真なので、||を含む条件式も真であり、次のブロックを実行します。
明示的に初期化されていないグローバル変数は0に初期化されるので、b[i][j] == 0は真であり、ブロックが実行されます。
すると、b[i+1][j-2]へのアクセスが発生しますが、これはb[1][-2]となり、範囲外です。
確保された範囲の外へのアクセスは未定義動作です。
C++で配列へのアクセスをラップする関数を作ってチェックすると、他にも大量の範囲外へのアクセスがあります。
どうしてこのような未定義動作を起こすプログラムを投稿したのですか?

チェックプログラム
※これはC++のプログラムです。C++の機能の参照を使っているため、C言語ではありません。
コード[C++]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include <stdio.h>
 
#define SIZE    4
#define KNIGHTS 8
 
int b[SIZE+2][SIZE+2], k;
 
int& b_check(int y, int x) {
    if (y < 0 || SIZE+2 <= y || x < 0 || SIZE+2 <= x) {
        printf("範囲外のb[%d][%d]にアクセスしました!\n", y, x);
    }
    return b[y][x];
}
 
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_check(i, j) < 0 ? " k" : " .");
            putchar('\n');
        }
    }
    else if (j < SIZE || (j = 0, ++i < SIZE)) {
        if (b_check(i, j) == 0) {
            b_check(i, j) = -1;
            b_check(i+1, j-2)++, b_check(i+1, j+2)++, b_check(i+2, j-1)++, b_check(i+2, j+1)++;
            step(n+1, i, j+1);
            b_check(i, j) = 0;
            b_check(i+1, j-2)--, b_check(i+1, j+2)--, b_check(i+2, j-1)--, b_check(i+2, j+1)--;
        }
        step(n, i, j+1);
    }
}
 
int main(void)
{
    step(0, 0, 0);
    return 0;
}

Q. 範囲外に見えても確保されていればいいのでは?
A. 動作上問題なくても、範囲外へのアクセスは未定義動作です。

N1570 J.2 Undefined behaviorより引用
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).
複雑な問題?マシンの性能を上げてOpenMPで殴ればいい!(死亡フラグ)

Name: かずま
[URL]
Date: 2017年1月13日(金) 15:37
No: 6
(OFFLINE)

 Re: 【C言語】騎士(ナイト)配置の探索問題 ~4×4盤ver.~

みけCAT さんが書きました:すると、b[i+1][j-2]へのアクセスが発生しますが、これはb[1][-2]となり、範囲外です。
確保された範囲の外へのアクセスは未定義動作です。
C++で配列へのアクセスをラップする関数を作ってチェックすると、他にも大量の範囲外へのアクセスがあります。
どうしてこのような未定義動作を起こすプログラムを投稿したのですか?

未定義動作とは思わなかったからです。

なぜ、そう思ったかというと、int b[6][6]; という宣言で 36個の int が
メモリー領域に連続して確保され、b[1][-2] は b[0][4] と同じになるからです。

C の添え字演算子 [] は、E1[E2] が (*((E1)+(E2))) と等価であると定義されて
います。したがって、b[1][-2] は *(*(b + 1) - 2) となります。int b[6][6];
という宣言の下では 、これは *(*(b + 0) + 6 - 2) に他なりません。
C では、ポインタが指す先のメモリー領域が確保されているかどうかの管理は、
プログラマに任されているのです。

しかし、規格書に未定義動作と明示されているのであれば仕方ありません。
次のように修正すれば問題ないでしょう。
コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
    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);
    }

しかし、if文による判定を何度も行うのは効率が悪いので、
一次元配列を使うことにしましょう。
コード[C]: 全て選択
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
#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;
}


Return to C言語何でも質問掲示板

オンラインデータ

このフォーラムを閲覧中のユーザー: なし & ゲスト[23人]