題目

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,
There exist two distinct solutions to the 4-queens puzzle:

[
[".Q..", // Solution 1
"...Q",
"Q...",
"..Q."],
["..Q.", // Solution 2
"Q...",
"...Q",
".Q.."]
]

分析

尋找N*N矩陣中放置N個(gè)皇后使其不會(huì)相互攻擊的方案。使用回溯，一行一行的尋找可能的點(diǎn)，找到的話，繼續(xù)找下一行，否則就退出。當(dāng)找到一個(gè)可行的方案時(shí)候，需要將此時(shí)的二維數(shù)組的數(shù)據(jù)保存到最后的指針中。
C代碼如下已通過：

int a[1000][1000];
//judge if(x,y)could be 1 in a[][]
bool place(int x,int y,int n)
{
    int i=0,j=0;
    for(i=0;i<x;i++)
        if(a[i][y]==1)  return false;
//search in left and top
    i=x-1;j=y-1;
    while(i>=0&&j>=0)
    {
        if(a[i][j]==1)return false;
        i--;j--;
    }
//search in right and top
    i=x-1;j=y+1;
    while(i>=0&&j<n)
    {
        if(a[i][j]==1)return false;
        i--;j++;
    }
//if ok return true
    return true;
}
void huisu(int no,int n,int *returnSize,char ***answer)
{
    if(no==n-1)
    {
        for(int i=0;i<n;i++)
        {
            if(place(n-1,i,n)==true)
            {
                a[n-1][i]=1;
                answer[*returnSize]=(char**)malloc(sizeof(char*)*n);
                for(int j=0;j<n;j++)
                {
                    answer[*returnSize][j]=(char*)malloc(sizeof(char)*(n+1));
                    for(int k=0;k<n;k++)
                    {
                        if(a[j][k]==0)
                            answer[*returnSize][j][k]='.';
                        else
                            answer[*returnSize][j][k]='Q';
                    }
                    answer[*returnSize][j][n]='\0';
                }
                *returnSize=*returnSize+1;
                a[n-1][i]=0;
            }
        }
    }
    else
    {
        for(int i=0;i<n;i++)
        {
            if(place(no,i,n)==true)
            {
                a[no][i]=1;
                huisu(no+1,n,returnSize,answer);
                a[no][i]=0;
            }
        }
    }
}

/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
char*** solveNQueens(int n, int* returnSize) {
    char ***ans=(char ***)malloc(sizeof(char **)*100000);
    *returnSize=0;
    for(int i=0;i<n;i++)
    {
        for(int j=0;j<n;j++)
            a[i][j]=0;
    }
    huisu(0,n,returnSize,ans);
    return ans;
}