Nクイーンパズルを解く

なんか集中力が落ちていたので。ずっとお絵描きしてました。部屋中紙だらけになってしまったので、たまにはプログラムを。

SICPの復習が出来そうなので、Karetta|Cパズルプログラミング-再帰編のNクイーンパズルを自分なりに改造してみます。

改造ポイント

対称性を考えずに解いた所まで。

x,y座標が逆。
コンパクトにまとめたつもり。
stdboolラブ。
関数名は気分で。

あんまり変わってないかも。

ソース

#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>

#define N 8

enum {EMPTY, QUEEEN};
int board[N][N];

void init_board(void)
{
    int x,y;

    for(y = 0; y < N; y++) {
        for(x = 0; x < N; x++)
            board[y][x] = EMPTY;
    }
}

void display(void)
{
    int x,y;

    for(y = 0; y < N; y++) {
        for(x = 0; x < N; x++) {
            putchar((board[y][x] == QUEEEN) ? 'Q' : '.');
        }
        putchar('\n');
    }
    putchar('\n');
}

void put_queen(int x, int y)
{
    board[y][x] = QUEEEN;
}

void remove_queen(int x, int y)
{
    board[y][x] = EMPTY;
}

bool check_queeen(int x, int y)
{
    if (x >= 0 && x < N &&
        y >= 0 && y < N) {
        return board[y][x] == QUEEEN;
    } else
        return false;
}

bool can_put(int x, int y)
{
    int u = y, d = y;

    while (--x >= 0) {
        if (check_queeen(x, y) ||
            check_queeen(x, ++u) ||
            check_queeen(x, --d))
              return false;
    }

    return true;
}

void try_node(int x, int y)
{
    static int cnt = 0;
    int i;

    if (can_put(x, y)) {
        put_queen(x, y);
        if (x == N - 1) {
            printf("ans : %d\n", ++cnt);
            display();
        } else {
            for (i = 0; i < N; i++) {
                try_node(x + 1, i);
            }
        }
        remove_queen(x, y);
    }
}

int main(void)
{
    init_board();

    int x = 0;
    for(x = 0; x < N; x++) {
        try_node(0, x);
    }

    return EXIT_SUCCESS;
}

とりあえずここまでぇ~。

% ./queen | tail
ans : 92
..Q.....
.....Q..
...Q....
.Q......
.......Q
....Q...
......Q.
Q.......

12queenだと、

ans : 14200
.....Q......
.......Q....
....Q.......
..........Q.
...Q........
.........Q..
......Q.....
..Q.........
...........Q
.Q..........
........Q...
Q...........

14200個解がある。

調べてみると、解の個数は

 1          1
 2          0
 3          0
 4          2
 5         10
 6          4
 7         40
 8         92
 9        352
10        724
11      2,680
12     14,200
13     73,712
14    365,596
15  2,279,184

こんな感じらしい。15になると爆発的に増えるみたい。危険。

まとめ

一個前の四則演算は結構楽しい。
Nクイーンパズルは超基本らしい。
Cでの破壊的な再帰には慣れが必要。
じっくり見てみると、桂馬飛びになってますね。桂馬で飛んで解を探したら面白そうだ。
- 桂馬以上か。飛ぶ前に結果がはっきりしてる所(自分の右、右上、右下)があるので置く必要は無い。
- 横列は、飛んでいない所のリストを保存しておく事で計算回数を減らすことが出来るかも。
- 実装は面倒なのでパス。