Next Sec.: バックトラッキングによる問題解決の一般形 Upper Sec.: バックトラッキング Prev. Sec.: 問題解決とバックトラッキング


nクィーン問題

n*nのチェス盤にn個のクィーンを互いに利きがないように配置せよ.」


n=4の場合 解は図を見て下さい。バックトラッキングを利用しています。

下のプログラムの関数の説明

i
探索の深さのレベル(チェス盤のi行)
x[i]
i レベル(i 行)でクイーンを置いた列
check(i,j)
レベル(i 行)でクィーンを置けるときtrue, それ以外のときfalseを与えるprocedure
search(i)
i-1レベルまでの探索の成功を前提として, iレベル以降の探索をすべて行うprocedure


メインプログラム


#include <stdio.h>

#define N 4

typedef enum {FALSE, TRUE} bool;

int a[N];

bool check(int x, int y);
void search(int i);

void main(void)
{
/*      int i;

        for (i = 0; i < N; i++)
                a[i] = 0;       */

        search(0);
}


探索プロシージャ


bool check(int x, int y)
{
        int i;

        for (i = 0; i < y; i++)
                if (x == a[i] || x - y + i == a[i] || x + y - i == a[i])
                        return FALSE;
        return TRUE;
}

void search(int i)
{
        int j, k;

        for (j = 0; j < N; j++)
                if (check(j, i)) {
                        a[i] = j;
                        if (i == N - 1) {
                                for (k = 0; k < N; k++)
                                        printf("%d ", a[k] + 1); /* {0 - N-1} から {1 - N}に変換するために a[k] に 1 を加えて出力 */
                                putchar('\n');
                        } else
                                search(i + 1);
                        /* a[i] = 0; */
                }
}



Next Sec.: バックトラッキングによる問題解決の一般形 Upper Sec.: バックトラッキング Prev. Sec.: 問題解決とバックトラッキング