一起刷leetcode(51):N-Queens


问题:51.N-Queens
来源:https://leetcode.com/submissions/detail/22543856/
问题描述:
The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.
1.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.

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

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

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

相关问题:https://leetcode.com/problems/n-queens-ii/
已邀请:

青原行思 - Crazy about ML!

赞同来自:


Recursive Back Tracking,经典回溯问题。
/*--------------------------
* Date:2015-03-08
* Author:qingyuanxingsi
* Title:51.N-Queens
* Link:https://leetcode.com/problems/n-queens/
* Result:AC
* Idea:Recursive Back Tracking
*/

include <iostream>

include <vector>

include <string>

include <cstdlib>

using namespace std;

class Solution {
private:
    vector<vector<string>> result;
public:
    vector<vector<string>> solveNQueens(int n){
        vector<int> temp(n);
        for(int i=0;i<n;i++){
            temp[i] = i+1;
        }
        backtrack_queen(temp,0,n);
        return result;
    }

    bool legal(vector<int> tmp,int t){
        for(int i=0;i<t;i++){
            if(abs(i-t)==abs(tmp[i]-tmp[t])){
                return false;
            }
        }
        return true;
    }

    void backtrack_queen(vector<int> temp,int t,int n){
        if(t==n){
            vector<string> pos;
            for(auto num:temp){
                string temp(n,'.');
                temp[num-1] = 'Q';
                pos.push_back(temp);
            }
            result.push_back(pos);
        }
        else{
            for(int i=t;i<n;i++){
                swap(temp[i],temp[t]);
                if(legal(temp,t)){
                    backtrack_queen(temp,t+1,n);
                }
                swap(temp[i],temp[t]);
            }
        }
    }
};

要回复问题请先登录注册

返回顶部