《leetCode》：N-Queens（奇葩的测试平台，居然不能AC）

题目

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 -queens puzzle:

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

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

思路

以前在《剑指offer》上面做过8皇后的题，思路剑这里：

http://blog.csdn.net/u010412719/article/details/49008281

实现代码如下：

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

/**
 * Return an array of arrays of size *returnSize.
 * Note: The returned array must be malloced, assume caller calls free().
 */
char ***result; //全局变量，用来存储最后的结果 
int index_result;//结果的下标 
//用来判断代表N皇后位置的这种组合是不是满足要求的。
bool isNQueens(int *arr,int n){
    if(arr==NULL||n<){
        return false;
    }
    for(int i=;i<n;i++){
        for(int j=i+;j<n;j++){
            if(((j-i)==(arr[j]-arr[i]))||((j-i)==(arr[i]-arr[j]))){//只要发现有两个皇后可以相互攻击，就返回false； 
                return false;
            }
        }
    }
    return true;
}
void swap(int *a,int *b){
    int temp=*a;
    *a=*b;
    *b=temp;
}
void solveNQueens_1(int *arr,int n,int begin){
    if(arr==NULL||n<){
        return;
    }
    if(begin==n-){//得到一个八皇后组合的位置，看是否满足 不被攻击的情况，即n皇后都不在一条斜线上
        if(isNQueens(arr,n)){
            //如果是，则开始保存
            result[index_result]=(char **)malloc(n*sizeof(char *));
            if(result[index_result]==NULL){
                exit(EXIT_FAILURE);
            } 
            for(int k=;k<n;k++){
                result[index_result][k]=(char *)malloc(n*sizeof(char));
                if(result[index_result][k]==NULL){
                    exit(EXIT_FAILURE);
                }
                memset(result[index_result][k],'.',n*sizeof(char));//全部初始化为'.' 
                result[index_result][k][arr[k]]='Q';//将皇后的位置用字符'Q'赋值 
            }
            index_result++;

        } 

    }
    for(int i=begin;i<n;i++){
            swap(arr+begin,arr+i);
            solveNQueens_1(arr,n,begin+);
            swap(arr+begin,arr+i);
    } 
}
char*** solveNQueens(int n, int* returnSize) {
    if(n<){
        return ;
    }
    int total=n*n*n;//这里，猜测他的总共符合要求的位置，共n*n种，如果不够，则再扩充 
    result=(char ***)malloc(total*sizeof(char **));
    index_result=;
    if(result==NULL){
        exit(EXIT_FAILURE);
    } 
    int *arr=(int *)malloc(n*sizeof(int));
    if(arr==NULL){
        exit(EXIT_FAILURE);
    }
    for(int i=;i<n;i++){
        arr[i]=i;
    }

    solveNQueens_1(arr,n,);
    *returnSize=index_result;
    return result;
}
//测试代码如下：
int main(void){
    int n;
    while(scanf("%d",&n)!=EOF&&n>){
        int returnSize=;
        char ***result1=solveNQueens( n, &returnSize);
        for(int i=;i<returnSize;i++){
            printf("第%d种结果如下:\n",i);
            for(int j=;j<n;j++){
                for(int k=;k<n;k++){
                    printf("%c  ",result1[i][j][k]);
                }
                printf("\n");
            }
            printf("\n\n");
        }
    }
    return ;
}
           

代码写的没有啥问题，最后不能AC，原因见“遇到的问题2”，比较奇葩

遇到的问题

1、这种情况，是因为当n=8时，共有92种符合情况的组合，但是，在代码的实现中，我只分配了n*n=64种情况的存储空间。因此报错。

2、结果都是相同的结果，只是在顺序上面不同罢了，就不能AC。这个测试系统不是太全面，只能说，要是想要测试系统太完善，也确实为难他了。因为测试系统也只是按顺序来保存结果的，但是你至少在题目中说明要求呀：将结果按从小到大的顺序进行存储。