leetcode 面試題 08.12. 八皇後

設計一種算法，列印 N 皇後在 N × N 棋盤上的各種擺法，其中每個皇後都不同行、不同列，也不在對角線上。這裡的“對角線”指的是所有的對角線，不隻是平分整個棋盤的那兩條對角線。

注意：本題相對原題做了擴充

示例:

 輸入：4

 輸出：[[".Q..","...Q","Q...","..Q."],["..Q.","Q...","...Q",".Q.."]]

 解釋: 4 皇後問題存在如下兩個不同的解法。

[

 [".Q..",  // 解法 1

  "...Q",

  "Q...",

  "..Q."],

 ["..Q.",  // 解法 2

  "Q...",

  "...Q",

  ".Q.."]

]

來源：力扣（LeetCode）

連結：https://leetcode-cn.com/problems/eight-queens-lcci

#include "stdafx.h"
#include "stdio.h"
#include "stdlib.h"

#define SIZE 1000

bool PlaceQueen(int posi, int posj, int n, int *queenPositionRow, int *queenPositionCol)
{
    if (queenPositionRow[posi] != -1) {
        return false;
    }
    
    if (queenPositionCol[posj] != -1) {
        return false;
    }
    
    int j = 1;
    for (int i = posi - 1; i >= 0; i--, j++) {
        if (posj - j >= 0 && queenPositionRow[i] == posj - j) {
            return false;
        }
        if (posj + j < n && queenPositionRow[i] == posj + j) {
            return false;
        }
    }
    
    j = 1;
    for (int i = posi + 1; i < n; i++, j++) {
        if (posj - j >= 0 && queenPositionRow[i] == posj - j) {
            return false;
        }
        if (posj + j < n && queenPositionRow[i] == posj + j) {
            return false;
        }
    }
    
    return true;
}

char ** GenerateQueenMap(int n, int *queenPositionRow, int *queenPositionCol)
{
    char **map = (char **)malloc(n * sizeof(char *));
    for (int i = 0; i < n; i++) {
        map[i] = (char *)malloc((n + 1) * sizeof(char));
        for (int j = 0; j < n; j++) {
            map[i][j] = '.';
        }
        map[i][queenPositionRow[i]] = 'Q';
        map[i][n] = 0;
    }
    return map;
}

void BackTrack(char*** ret, int i, int n, int* returnSize, int** returnColumnSizes, 
               int *queenPositionRow, int *queenPositionCol)
{
    if (i == n) {
        ret[*returnSize] = GenerateQueenMap(n, queenPositionRow, queenPositionCol);
        (*returnColumnSizes)[*returnSize] = n;
        (*returnSize)++;
        return;
    }
    
    int j;
    for (int j = 0; j < n; j++) {
        bool canPlace = PlaceQueen(i, j, n, queenPositionRow, queenPositionCol);
        if (canPlace == true) {
            queenPositionRow[i] = j;
            queenPositionCol[j] = i;
            BackTrack(ret, i + 1, n, returnSize, returnColumnSizes,
                      queenPositionRow, queenPositionCol);
            queenPositionRow[i] = -1;
            queenPositionCol[j] = -1;
        }
        
    }
}

/**
 * Return an array of arrays of size *returnSize.
 * The sizes of the arrays are returned as *returnColumnSizes array.
 * Note: Both returned array and *columnSizes array must be malloced, assume caller calls free().
 */
char*** solveNQueens(int n, int* returnSize, int** returnColumnSizes)
{
    if (returnSize == NULL || returnColumnSizes == NULL) {
        return NULL;
    }
    
    if (n < 1) {
        *returnSize = 0;
        return NULL;
    }
    
    *returnSize = 0;
    char ***ret = (char ***)malloc(SIZE * sizeof(char **));
    *returnColumnSizes = (int *)malloc(SIZE * sizeof(int));
    int* queenPositionRow = (int*)malloc(n * sizeof(int));
    int* queenPositionCol = (int*)malloc(n * sizeof(int));
    for (int i = 0; i < n; i++) {
        queenPositionRow[i] = -1;
        queenPositionCol[i] = -1;
    }
    
    BackTrack(ret, 0, n, returnSize, returnColumnSizes, queenPositionRow, queenPositionCol);
    
    free(queenPositionRow);
    free(queenPositionCol);

	return ret;
}

void testcase1(void)
{
    int n = 8;
    int returnSize;
    int* returnColumnSizes;
    char ***ret = solveNQueens(n, &returnSize, &returnColumnSizes);
    if (ret != NULL && returnSize > 0) {
        printf("*****************************************\n");
        for(int m = 0; m < returnSize; m++) {
            printf("[\n");
            for (int i = 0; i < n; i++) {
                printf("  [");
                for (int j = 0; j < n; j++) {
                    printf("%c", ret[m][i][j]);
                }
                printf("]\n");
            }
            printf("]\n");
        }
    }
}

int main()
{
    testcase1();
    return 0;
}