遡及法:八皇后問題

遡及法とは何ですか.
遡及は、基本的な列挙に由来します.

void print( A,  S)

{

    if (S )  A

    else  “ ” S 

    {

        print(A , S-{v}); // 

    }           

}

ここで、テスト要素はforループによって加えられ、curの下付きスケールによって現在の位置を再帰的に示す.明らかに,これは解ツリーに対するシーケンス遍歴過程であり,リーフノードが問題の解である.
しかし,問題規模が拡大すると列挙量指数級が拡大する.問題は,解の判断をリーフノードに列挙し,探索経路における判断を無視することである.そのため遡及は運に応じて生まれた.つまり、テストノードが加入したときに合理性をテストすることである.再帰:枝を切る.異なる問題に対して,再帰的枠組みが明確であり,最も重要なのは判決条件を確定することである.
八皇后問題:皇后は同行せず、同列、同対角線である.対角線はy=x+cとy=-x+cの2組の平行線に相当する.プログラム:

#include <stdio.h>



int maze[8]; // 

int cnt = 0; // 



void dfs(int row)

{

    if (row == 8)

    { // 

        cnt++;

        for (int i = 0; i < 8; i++)

            printf("%d ", maze[i]);

        printf("
");

    }

    else

    {

        for (int i = 0; i < 8; i++)

        {// cur 

            int ok = 1;

            for (int j = 0; j < row; j++)

            {// 

                if (maze[j] == i || (j - maze[j]) == (row - i) || (j + maze[j]) == (row + i))

                {//   

                    ok = 0;

                    break;

                }

            }



            if (ok)

            {// ， 

                maze[row] = i;

                dfs(row + 1);

            }// ， 

        }

    }

}



int main()

{

    dfs(0);

    printf("cnt = %d
", cnt);

    return 0;    

}

最後に92の解がある.しかし実際には12個の独立解しかなく,どのようにさらなる最適化を行うかはより深い問題である.本文は遡及の基本的な枠組みを学ぶことを目的とする.