[leetcode题解] 51. N-Queens

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.

Example:

Input: 4 Output: [
 [".Q..",  // Solution 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // Solution 2
  "Q...",
  "...Q",
  ".Q.."]
] Explanation: There exist two distinct solutions to the 4-queens puzzle as shown above.

题目意思就是传统的N皇后问题,输出所有解。给定一个N*N的中国象棋棋盘,在棋盘上放置N个皇后,保证N各皇后互相之间无法被吃,即N个皇后两两均不在水平,垂直或者正斜45度和负斜45度的直线上。

输出所有可能的放置方法。

整体思路是通过回溯的方式直接进行搜索,遍历每一行的每一个位置,当前位置放上皇后之后,前面放过的位置是否满足要求,如果满足要求,则在这个位置放一个皇后,接着行号加一,去下一行继续搜,N行都有满足的位置,则表示找到一种可行解。若某一行没有任何位置满足条件,则直接返回上一行,继续搜索下一个位置。

用深度优先搜索+回溯的方式解决该问题。

C语言代码要注意,返回结果是个三维数组,即指向一个二维数组的数组,这个二维数组是一个指向一维char *的数组,每个一维中保存的是一个char *,因为是char *,所以最后要加‘\0’,

否则就是越界,leetcode直接报错。

C语言代码:

#include <stdbool.h>

#define N 100
#define MAX 120000
#define ND 3
int dirs[ND][2] = { {-1, 0}, {-1, -1}, {-1, 1} };

bool used[N][N];

bool check_dir(int x, int y, int dx, int dy, int n) {
    int nx, ny;
    bool ret = true;

    for (;;) {
        nx = x + dx;
        ny = y + dy;

        if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
            break;
        }

        if (used[nx][ny]) {
            ret = false;
            break;
        }

        x = nx;
        y = ny;
    }

    return ret;
}

bool check(int x, int y, int n) {
    int i;
    bool ret = true;

    for (i = 0; i < ND; i++) {
        ret = check_dir(x, y, dirs[i][0], dirs[i][1], n);
        if (!ret) {
            return ret;
        }
    }
    return ret;
}

void dfs(int idx, int n, char ***res, int *sol_cnt) {
    int i, j;
    char **arr = NULL;

    if (idx >= n) {
        arr = (char **)malloc(n * sizeof(char *));
        for (i = 0; i < n; i++) {
            arr[i] = (char *)malloc((n + 1) * sizeof(char));
            for (j = 0; j < n; j++) {
                if (used[i][j] == 1) {
                    arr[i][j] = 'Q';
                } else {
                    arr[i][j] = '.';
                }
            }
            arr[i][j] = '\0';
        }
        res[*sol_cnt] = arr;
        (*sol_cnt) += 1;
        return;
    }

    for (i = 0; i < n; i++) {
        if (!check(idx, i, n)) {
            continue;
        }

        used[idx][i] = true;
        dfs(idx + 1, n, res, sol_cnt);
        used[idx][i] = false;
    }
}


char *** solveNQueens(int n, int* returnSize, int** returnColumnSizes){
    char ***res = NULL;
    int i, j, k;
    
    res = (char ***)malloc(MAX * sizeof(char **));
    (*returnColumnSizes) = malloc(MAX * sizeof(int));
    
    memset(used, 0, sizeof(used));
    *returnSize = 0;
    dfs(0, n, res, returnSize);

    *returnColumnSizes = malloc(*returnSize * sizeof(int));
    for (i = 0; i < *returnSize; i++) {
        (*returnColumnSizes)[i] = n;
    }

    return res;
}   


C++语言代码:

#define N 100
#define ND 3
int dirs[ND][2] = { {-1, 0}, {-1, -1}, {-1, 1} };

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        
        memset(used, 0, sizeof(used));
        dfs(0, n, res);
        return res;
    }
    
    void dfs(int idx, int n, vector<vector<string>> &res) {
        int i, j;
        
        if (idx >= n) {
            vector<string> sol;
            string line = "";
            
            for (i = 0; i < n; i++) {
                line = "";
                for (j = 0; j < n; j++) {
                    if (used[i][j] == 1) {
                        line.push_back('Q');
                    } else {
                        line.push_back('.');
                    }
                }
                sol.push_back(line);
            }
            res.push_back(sol);
            return;
        }
        
        for (i = 0; i < n; i++) {
            if (!check(idx, i, n)) {
                continue;
            }
            
            used[idx][i] = true;
            dfs(idx + 1, n, res);
            used[idx][i] = false;
        }
    }
    
    bool check_dir(int x, int y, int dx, int dy, int n) {
        int nx, ny;
        bool ret = true;
        
        for (;;) {
            nx = x + dx;
            ny = y + dy;
            
            if (nx < 0 || nx >= n || ny < 0 || ny >= n) {
                break;
            }
            
            if (used[nx][ny]) {
                ret = false;
                break;
            }
            
            x = nx;
            y = ny;
        }
        
        return ret;
    }
    
    bool check(int x, int y, int n) {
        int i;
        bool ret = true;
        
        for (i = 0; i < ND; i++) {
            ret = check_dir(x, y, dirs[i][0], dirs[i][1], n);
            if (!ret) {
                return ret;
            }
        }
        return ret;
    }
private:
    bool used[N][N];
};

本文遵从CC3.0协议转载请注明:转自凌风技术站

本文标题:[leetcode题解] 51. N-Queens

本文链接地址:https://www.iaccepted.net/algorithm/leetcode/217.html

相关文章