【Leetcode】51. N-Queens (搜索)

水深无声 2022-03-06 11:40 87阅读 0赞

The *n*\-queens puzzle is the problem of placing *n* queens on an *n*×*n* chessboard such that no two queens attack each other.

![8-queens.png][]

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.

题目大意：

每个Q周围的八个格子中不允许出现Q。

解题思路：

按行搜索，所以我们只需要考虑每一列是否存在或者斜线上是否存在，所以我们可以看出搜索的判断条件有两个，1）当前Q的列号是否前面出现过。2）当前Q的列号与之前Q的列号相减的绝对值如果等于行号的差，则两个位于同一条斜线上。

开始学习C++，以后Python和C++混合双打。

#include <vector>
    #include <string>
    #include <cstdio>
    #include <iostream>
    #include <stdlib.h>
    using namespace std;
    
    class Solution {
    
    private:
    	vector<string> board;
    	vector<vector<string>> ans;
    
    	void solve(vector<string>& board, vector<int>& pos, int num, int n) {
    		if (num == n) {
    			ans.push_back(board);
    			return;
    		}
    		for (int i = 0; i < n; i++) {
    			pos[num] = i;
    			if (valid(pos, num)) {
    				board[num][i] = 'Q';
    				solve(board, pos, num + 1, n);
    				board[num][i] = '.';
    			}
    		}
    
    	}
    
    	bool valid(vector<int>& pos, int num) {
    		for (int i = 0; i < num; i++) {
    			if (pos[i] == pos[num] || abs(pos[i] - pos[num]) == num - i) {
    				return false;
    			}
    		}
    		return true;
    	}
    
    public:
    	vector<vector<string>> solveNQueens(int n) {
    		string row(n, '.');
    		for (int i = 0; i < n; i++) {
    			board.push_back(row);
    		}
    		vector<int> pos = vector<int>(n);
    		// 此处不跑图，只跑N个位置，查找是否存在有横纵坐标相同的情况
    		solve(board, pos, 0, n);
    
    		return ans;
    	}
    };
    
    int main(void) {
    	Solution obj;
    	vector<vector<string>> ans;
    	ans = obj.solveNQueens(4);
    	for (int i = 0; i < ans.size(); i++) {
    		for (int j = 0; j < ans[i].size(); j++) {
    			cout << ans[i][j] << endl;
    		}
    		cout << '\n';
    	}
    	return 0;
    }

[8-queens.png]: https://assets.leetcode.com/uploads/2018/10/12/8-queens.png