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; */
                }
}