八皇后的演算法

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

void queens(int x);
void print(void);

unsigned int n, num;
char** checkerboard;
int* column;
int* right;
int* left;

假設n 為 4....

int main(void)
{
    int i, j;

    printf("請輸入 n 的大小: ");
    scanf("%d", &n);

    // 動態分配記憶體
    column = malloc(sizeof(int) * n);
    right = malloc(sizeof(int) * (2 * n - 1));
    left = malloc(sizeof(int) * (2 * n - 1));
    checkerboard = malloc(sizeof(char*) * n);

    // 變數初始化
    num = 0;
    for (i = 0; i < n; i++)
    {
        column[i] = 1;

        checkerboard[i] = malloc(sizeof(char) * n);
        for (j = 0; j < n; j++)
        {
            checkerboard[i][j] = 'x';
        }
    }

    for (i = 0; i < 2 * n - 1; i++)  //  i從  0 到 6 
    {
        right[i] = left[i] = 1;   //  先初始化為1
    }

    queens(0);   // 先排一個皇后

    printf("\n總共有 %d 種排法\n\n", num);

    // 釋放記憶體空間
    for (i = 0; i < n; i++)
    {
        free(checkerboard[i]);
    }

    free(checkerboard);
    free(column);
    free(right);
    free(left);

    system("pause");
}

void queens(int x)   // 一開始x 為 0 ,  下次進來會變成  1, 2, 3
{
    if (x < n)  //  n 為 4
    {
        int i;
        for (i = 0; i < n; i++) //  0 到 3
        {
            int j = i - x + n - 1;  // 右邊的x 座標, i為0,  x為0,  就是3
            int k = i + x;          // 左邊的x 座標, i為0,  x為0,  就是0

                                    // 右邊的x 座標, i為1,  x為0,  就是4

                                    // 左邊的x 座標, i為1,  x為0,  就是1

                                    // 右邊的x 座標, i為2,  x為0,  就是5
                                    // 左邊的x 座標, i為2,  x為0,  就是2


                                    // 右邊的x 座標, i為3,  x為0,  就是6
                                    // 左邊的x 座標, i為3,  x為0,  就是3


// 右邊的x 座標, i為0,  x為1,  就是2
                                    // 左邊的x 座標, i為0,  x為1,  就是1

                                    // 右邊的x 座標, i為1,  x為1,  就是3
                                    // 左邊的x 座標, i為1,  x為1,  就是2


                                    // 右邊的x 座標, i為2,  x為1,  就是4
                                    // 左邊的x 座標, i為2,  x為1,  就是3


                                    // 右邊的x 座標, i為3,  x為1,  就是5
                                    // 左邊的x 座標, i為3,  x為1,  就是4



 //  他使用  left 和 right array 來排除  左下角和 右下角的case

 //   假設   (col, row) -> (i,x) 

 // example 1 :  (1,2) 和 （2,1）   就是相衝突...

  //            兩個(i,x)帶進去算出來的k 都是 3  -> 所以這次的 left[k] 就已經被清成0

  //             不會成立

 // example 2 :  (1,2) 和 （2,3）   就是相衝突...

  //            兩個(i,x)帶進去算出來的j 都是 2  -> 所以這次的 right[j] 就已經被清成0

  //    

            if (column[i] && right[j] && left[k])
            {
                // 標記皇后位置, 並遞迴放置下一個
                column[i] = right[j] = left[k] = 0;
                checkerboard[x][i] = 'Q';

                queens(x + 1);

                column[i] = right[j] = left[k] = 1;
                checkerboard[x][i] = 'x';
            }
        }
    }
    else
    {
        // 輸出棋盤
        print();
        num++;
    }
}

void print(void)
{
    int i, j;

    printf("\n");
    for(i = 0; i < n; i++)
    {
        for(j = 0; j < n; j++)
        {
            printf("%c", checkerboard[i][j]);
        }

        printf("\n");
    }
}