n-皇后__牛客网

JacobGo！

package go.jacob.day0610.chapter8_recursion;

import java.util.ArrayList;

/**
 * 著名n皇后问题
 * 题目解析：
 * n个皇后摆放在n*n的棋盘格中，使得横、竖和两个对角线方向均不会同时出现两个皇后
 * <p>
 * 解题思路：
 * 由于需要在n*n的棋盘格中放入n个皇后，就必须每一行放一个
 * 否则就会出现一行有两个皇后的情况，会发生冲突。
 * 那么就可以递归的解决每一行问题
 * 最核心的问题是：如何能快速判断不合法的情况，即快速剪枝
 * 同行或同列的冲突可以简单用一个数组来考虑，难点是两条对角线
 * 对角线条数2*n-1
 * 左对角线：坐标x+y是一个唯一定值  x+y      范围为0到2*n-2
 * 右对角线：坐标x-y是一个唯一定值  x-y+n-1  范围为0到2*n-2
 */
public class Solution {

    private ArrayList<String[]> res;

    private boolean[] col;//列
    private boolean[] dia1;//左对角线
    private boolean[] dia2;//右对角线

    public ArrayList<String[]> solveNQueens(int n) {
        res = new ArrayList<String[]>();
        if (n == 0)
            return res;
        col = new boolean[n];
        dia1 = new boolean[2 * n - 1];
        dia2 = new boolean[2 * n - 1];

        putQueen(n, 0, new ArrayList<Integer>());
        return res;
    }

    //尝试在一个n皇后问题中，摆放第index行的皇后位置,row存放的是每一行皇后存放的下标
    private void putQueen(int n, int index, ArrayList<Integer> row) {
        if (index == n) {
            res.add(generateBoard(n, row));
            return;
        }

        for (int i = 0; i < n; i++) {
            //判断能否将第index行的皇后摆放在第i列
            if (!col[i] && !dia1[index + i] && !dia2[index - i + n - 1]) {
                col[i] = true;
                dia1[index + i] = true;
                dia2[index - i + n - 1] = true;

                row.add(i);
                putQueen(n, index + 1, row);
                row.remove(row.size() - 1);

                col[i] = false;
                dia1[index + i] = false;
                dia2[index - i + n - 1] = false;
            }
        }
    }

    private String[] generateBoard(int n, ArrayList<Integer> row) {
        String[] list = new String[n];
        for (int i = 0; i < n; i++) {
            StringBuilder s = new StringBuilder();
            for (int j = 0; j < n; j++) {
                if (j == row.get(i))
                    s.append("Q");
                else
                    s.append(".");
            }
            list[i] = s.toString();
        }
        return list;
    }
}

编辑于 2018-06-10 11:14:17 回复(1)

Java

拾贰儿

import java.util.ArrayList;
import java.util.Arrays;

public class Solution {
ArrayList<String[]> ret = new ArrayList<>();
    public ArrayList<String[]> solveNQueens(int n) {
        if(n <= 0) return ret;
        int[] array = new int[n];
        helper(array, 0);
        return ret;
    }


    //A[i] = j 表示  i 行 j 列 上放置了一个皇后

    public boolean check(int[] array,int k){

        //验证新加入的第k行是否可以

        for(int i = 0;i < k; i++){

            if(array[i] == array[k] || k - i == Math.abs(array[k] - array[i])) return false;

        }

        return true;

    }

   

    public void helper(int[] array,int k){

        if(k == array.length){

            String[] s = new String[array.length];

            for(int i = 0;i < array.length;i++){

                char[] ca = new char[array.length];

                Arrays.fill(ca, '.');

                ca[array[i]] = 'Q';

                s[i] = new String(ca);

            }

            ret.add(s);

            return;

        }

        for(int i = 0;i< array.length;i++){

            array[k] = i;

            if(check(array,k)){

                helper(array, k + 1);

            }

        }

    }

}

发表于 2017-11-13 09:41:16 回复(0)

后劲好大

import java.util.ArrayList;
public class Solution {
    static ArrayList<String[]> result;
	public ArrayList<String[]> solveNQueens(int n) {		
		result = new ArrayList<>();
		if(n <= 0)
			return result;
		// cols[i]代表第i个皇后所在的列
		int[] cols = new int[n];
		for(int i = 0; i < n; i++){
			// 将第1个queen放置好
			cols[0] = i;
			Strategy(cols, 1);
		}
		
		return result;
    }
     // 递归放置皇后
	public void Strategy(int[] cols, int row){
              // 放到了最后一列，结束
		if(row == cols.length){
                    // 这里其实最好用StringBuffer
			String[] str = new String[cols.length];
			for(int i = 0; i < str.length; i++){
				str[i] = "";
				for(int j = 0; j < str.length; j++){
					if(j == cols[i])
						str[i] += "Q";
					else
						str[i] += ".";
				}
			}
			result.add(str);
			return;
		}
              // 试凑放置皇后的位置
		for(int i = 0; i < cols.length; i++){
			if(isValid(cols, row, i)){
				cols[row] = i;
				Strategy(cols, row + 1);
			}
		}
		
	}
	// 判断在row行col列放置的皇后是否合法
	public boolean isValid(int[] cols, int row, int col){
		if(cols == null)
			return false;
		// 与之前皇后在同一列或者斜对角线，即不合法
		for(int i = 0; i < row; i++){
			if(cols[i] == col || Math.abs(cols[i] - col) == Math.abs(row - i))
				return false;
		}
		return true;
	}
}

发表于 2017-05-05 11:03:29 回复(0)

探花一笑若奈何

/*

	运行时间：151ms



	占用内存：15344k

*/
import java.util.ArrayList;
public class Solution {
    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> r = new ArrayList<String[]>();
        char[][] cur = new char[n][n];
        for(int i = 0;i < n;i++){
            for(int j = 0;j < n;j++)
                cur[i][j] = '.';
        }
        dfs(r,cur,n,0);
        return r;
    }
    private void dfs(ArrayList<String[]> r,char[][] cur,int n,int row){
        if(n == row){
            String[] s = new String[n];
            for(int i = 0;i < n;i++){
                String tmp = new String(cur[i]);
                s[i] = tmp;
            }
            r.add(s);
            return;
        }
        for(int i = 0;i < n;i++){
            if(isValid(cur,n,row,i)){
                cur[row][i] = 'Q';
                dfs(r,cur,n,row+1);
                cur[row][i] = '.';
            }
        }
    }
    private boolean isValid(char[][] cur,int n,int row,int col){
        //从第一行往下面依次放入queue，所以不用考虑下面未放入的，只考虑上面已存在的
        //排除行
        for(int i = 0;i < col;i++){
            if(cur[row][i] == 'Q') return false;
        }
       //排出列
        for(int i = 0;i < row;i++){
            if(cur[i][col] == 'Q') return false;
        }
       //排除斜线
        for(int i = row - 1,j = col - 1;i >= 0 && j >= 0;i--,j--){
            if(cur[i][j] == 'Q') return false;
        }
        // 排除反斜线
        for(int i = row - 1,j = col + 1;i >= 0 && j< n;i--,j++){
            if(cur[i][j] == 'Q') return false;
        }
        return true;
    }
}

发表于 2018-03-24 15:05:47 回复(1)

C++

勇敢牛牛，不怕困难！

class Solution {
public:
  vector<vector<string> > solveNQueens(int n) {
    vector<string> board(n, string(n, '.'));
    DFS(0, board, n);
    return sols_;
  }
  
  
private:
  vector<vector<string>> sols_;
  int cols_, diag1_, diag2_;
  
  bool available(int x, int y, int n) {
    return !(cols_ & 1 << x 
             || diag1_ & 1 << (x + y) 
             || diag2_ & 1 << (n - 1 + x - y));
  }
  
  void putBoard(vector<string>& board, int x, int y, int n, bool flag) {
    board[y][x] = flag ? 'Q' : '.';
    if (flag) {
      cols_ |= 1 << x;
      diag1_ |= 1 << (x + y);
      diag2_ |= 1 << (n - 1 + x - y);
    } else {
      cols_ -= 1 << x;
      diag1_ -= 1 << (x + y);
      diag2_ -= 1 << (n - 1 + x - y);
    }
  }
  
  void DFS(int y, vector<string>& board, int n) {
    if (y == n) {
      sols_.emplace_back(board);
      return;
    }
    
    for (int x = 0; x < n; ++x) {
      if (not available(x, y, n)) continue;
      
      putBoard(board, x, y, n, true);
      DFS(y + 1, board, n);
      putBoard(board, x, y, n, false);
    }
  }
  
};

发表于 2021-10-08 08:51:35 回复(0)

今天刷了几道题？

class Solution {
public:
    vector<vector<string> > res;
    vector<int> A;
    int n;
    vector<vector<string> > solveNQueens(int n) {
        this->n=n;
        A.resize(n);
        findNQueens(0);
        return res;
    }
    bool check(int row,int col){
        for(int i=0;i<row;i++){
            if(A[i]==col||abs(A[i]-col)==abs(i-row)){
                return false;
            }
        }
        return true;
    }
    void findNQueens(int k){
        if(k==n){
            vector<string> v(n,string(n,'.'));
            for(int i=0;i<n;i++){
                v[i][A[i]]='Q';
            }
            res.push_back(v);
            return;
        }
        for(int i=0;i<n;i++){
            if(check(k,i)){
                A[k]=i;
                findNQueens(k+1);
            }
        }
    }
};

发表于 2019-07-06 18:18:17 回复(0)

代码敲的的再六也不如手推SVM爽

深度优先DFS，维护一个vecor<vector<bool>> flag只有当bool值为true才允许放皇后；

放皇后之后将对角线和列置为false;

要注意flag是值传递。

class Solution {
public:
    vector<vector<string>> res;
    vector<vector<string>> solveNQueens(int n) {
        vector<string> curStr;
        vector<vector<bool>> flag(n, vector<bool>(n, true)); 
        nQueens(n, 0, curStr, flag);
        return res;
    } 
    void nQueens(int &n, int cur, vector<string> &curStr, vector<vector<bool>> flag){
        if(curStr.size() == n){
            res.push_back(curStr);
            return ;
        }
        for(int i = 0; i < n; i ++ ){
            if(!flag[cur][i]){
                continue;
            }
            else{
                curStr.push_back(cStr(i,n));
                
                nQueens(n, cur+1, curStr, flagTrans(flag, cur, i));
                
                curStr.pop_back();
            }
        }
    }
    
    vector<vector<bool>> flagTrans(vector<vector<bool>> flag, int i, int j){
        int len = flag.size();
        for(int k = 0; k < len; k++ )
            flag[k][j] = false;
        int token1 = i, token2 = j;
        while(max(++token1,++token2) < len){
            flag[token1][token2] = false;
        }
        token1 = i, token2 = j;
        while(min(--token1,--token2) >= 0){
            flag[token1][token2] = false;
        }
        token1 = i, token2 = j;
        while(++token1<len && --token2>=0){
            flag[token1][token2] = false;
        }
        token1 = i, token2 = j;
        while(--token1>=0 && ++token2<len){
            flag[token1][token2] = false;
        }

        return flag;
    }
    
    
    string cStr(int index,int &n){
        string s;
        for(int i= 0; i<n ;i++){
            if(i == index)
                s+='Q';
            else
                s+='.';
        }
        return s;
    }
};

发表于 2019-06-13 11:38:45 回复(1)

C/C++

hhhuu

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> board(n, string(n, '.'));
        vector<int> pos(n, 1);
        vector<int> flag1(n + n - 1, 1); // ↘️的对角线
        vector<int> flag2(n + n - 1, 1); // ↙️的对角线
        backTrack(res, board, pos, flag1, flag2, 0);
        return res;
    }

    void backTrack(vector<vector<string>> &res, vector<string> &board, vector<int> &pos, vector<int> &flag1, vector<int>& flag2, int idx) {
        if(idx == pos.size()) {
            res.push_back(board);
            return;
        }
        for(int i = 0; i < pos.size(); ++i) {
            // 不能出现同一列
            if(pos[i] == 0)
                continue;
            // 不能出现在同一条斜线上
            int n = i - idx, m = i + idx;
            n += (pos.size() - 1);
            if(flag1[n] == 0 || flag2[m] == 0)
                continue;
            pos[i] = 0;
            board[idx][i] = 'Q';
            flag1[n] = 0;
            flag2[m] = 0;
            backTrack(res, board, pos, flag1, flag2, idx + 1);
            pos[i] = 1;
            board[idx][i] = '.';
            flag1[n] = 1;
            flag2[m] = 1;
        }
    }
};

发表于 2018-08-29 11:12:16 回复(0)

llch__

    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> result = new ArrayList<String[]>();
        boolean col[] = new boolean[n+1];    //列
        boolean tip1[] = new boolean[n*2+1]; //右对角斜线 2~2n
        boolean tip2[] = new boolean[n*2+1]; //左对角斜线 2~2n
        Stack<String> stack = new Stack<String>();
        nQueens(n, 1, col, tip1, tip2, result, stack);
        return result;
    }
    public void nQueens(int n, int cou, boolean col[], boolean tip1[], boolean tip2[], ArrayList<String[]> result, Stack<String> stack){
        if(cou > n){
            String a[] = new String[n];
            stack.toArray(a);
            result.add(a);
            return;
        }
        for(int i=1; i<=n; i++){
            if(!col[i] && !tip1[cou+i] && !tip2[n-cou+1+i]){
                stack.push(genString(i, n));
                col[i] = true;
                tip1[cou+i] = true;
                tip2[n-cou+1+i] = true;
                nQueens(n, cou+1, col, tip1, tip2, result, stack);
                col[i] = false;
                tip1[cou+i] = false;
                tip2[n-cou+1+i] = false;
                stack.pop();
            }
        }
    }
    public String genString(int i, int len){
        char chs[] = new char[len];
        Arrays.fill(chs, '.');
        chs[i-1] = 'Q';
        return new String(chs);
    }

发表于 2018-07-28 15:52:01 回复(0)

丶沉梦昂志

import java.util.*;
public class Solution {
    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> res = new ArrayList<String[]>();
        helper(n, 0, new int[n], res);//利用一个数组保存Q的位置信息，数组下标表示行，数组元素表示放置Q的列
        return res;
    }

    private void helper(int n, int row, int[] columnForRow, ArrayList<String[]> res) {
        if (row == n) {//row=n表示已经找到了数组，将数组转化为结果即可。
            String[] item = new String[n];
            for (int i = 0; i < n; i++) {
                StringBuilder strRow = new StringBuilder();
                for (int j = 0; j < n; j++) {
                    if (columnForRow[i] == j)//在数组记录的位置上写入Q
                        strRow.append('Q');
                    else
                        strRow.append('.');//在其他所有位置上写入.
                }
                item[i] = strRow.toString();
            }
            res.add(item);
            return;
        }
        for (int i = 0; i < n; i++) {
            columnForRow[row] = i;
            if (check(row, columnForRow)) {
                helper(n, row + 1, columnForRow, res);
            }
        }
    }

    private boolean check(int row, int[] columnForRow) {
        for (int i = 0; i < row; i++) {
            if (columnForRow[row] == columnForRow[i] || Math.abs(columnForRow[row] - columnForRow[i]) == row - i)
                return false;
        }
        return true;
    }
}

发表于 2017-11-22 13:45:07 回复(0)

大灰兔

力求LOC最短，采用map减少判断合法棋盘的开销：

class Solution(object):
    def solve(self, n, i, m, l0, l1, l2):
        if i == n:
            return [m[:]]
        res = []
        for j in range(n):
            if j not in l0 and i + j not in l1 and j - i not in l2:
                m.append(j)
                l0[j] = 1
                l1[i + j] = 1
                l2[j - i] = 1
                res.extend(self.solve(n, i + 1, m, l0, l1, l2))
                m.pop()
                l0.pop(j)
                l1.pop(i + j)
                l2.pop(j - i)
        return res

    def solveNQueens(self, n):
        res = self.solve(n, 0, [], {}, {}, {})
        solutions = []
        for r in res:
            solution = []
            for rr in r:
                line = ""
                for i in range(n):
                    line += "." if i != rr else "Q"
                solution.append(line)
            solutions.append(solution)
        return solutions

编辑于 2017-10-07 19:11:25 回复(0)

C/C++

nbgao

class Solution {
public:
    vector<vector<string> > solveNQueens(int n) {
        string str;
        for(int i=0;i<n;i++)
    		str.push_back('.');
    	vector<string> vec;
    	int a[n];
    	for(int i=0;i<n;i++)
	    	vec.push_back(str);
	    vector<vector<string> > res;
	    Back(n,0,res,vec,a);
	    return res;
    }
    
    void Back(int n,int t,vector<vector<string> > &res,vector<string> vec,int *a)
    {
    	if(n == t)
    	{
    		res.push_back(vec);
    		return;
		}
		for(int i=0;i<n;i++)
		{
			a[t] = i;
			if(Push(t,a))
			{
				vec[t][i] = 'Q';
				Back(n,t+1,res,vec,a);
				vec[t][i] = '.';
			}
		}
	}
	
	bool Push(int m,int a[])
	{
		bool flag = true;
		for(int i=0;i<m;i++)
		{
			if(a[i] == a[m] || abs(a[m]-a[i]) == (m-i))
			{
				flag = false;
				break;
			}
		}
		return flag;
	}
};

发表于 2017-08-12 00:48:45 回复(0)

Java

Holiday_12138

import java.util.*;
public class Solution {
    ArrayList<String[]> list = new ArrayList<String[]>();
    public ArrayList<String[]> solveNQueens(int n) {
        char[][] res = new char[n][n];
        for(char[] chs : res)
            Arrays.fill(chs, '.');
        int[] cols = new int[n];
        int[] slash1 = new int[2*n-1];
        int[] slash2 = new int[2*n-1];
        DFS(res, n, 0, cols, slash1, slash2);
        return list;
        
    }
    
    public void DFS(char[][] res, int n, int cur, int cols[], int slash1[], int slash2[]) {
        if(cur == n) {
            String[] s = new String[n];
            for(int i=0; i<n; i++)
                s[i] = new String(res[i]);
            list.add(s);
        }
        for(int i=0; i<n; i++) {
            if(cols[i] != 1 && slash1[cur + i] != 1 && slash2[n-1-cur+i] != 1) {
                cols[i] = 1;
                slash1[cur + i] = 1;
                slash2[n-1-cur+i] = 1;
                res[cur][i] = 'Q';
                DFS(res, n, cur+1, cols, slash1, slash2);
                cols[i] = 0;
                slash1[cur + i] = 0;
                slash2[n-1-cur+i] = 0;
                res[cur][i] = '.';
            }
        }
    }
}

发表于 2017-06-19 13:44:09 回复(0)

whisky_

class Solution {

public:

vector<vector<string> > solveNQueens(int n) {

vector<vector<string>> ret;

vector<string> board(n, string(n, '.'));

set<int> col_used;

DFS(ret, board, col_used, 0);

return ret;

}

void DFS(vector<vector<string>> &all_boards, vector<string> &board, set<int> &col_used, int r){

int rows=board.size(), cols=board[0].size();

if(r>=rows)

all_boards.push_back(board);

else

for(int c=0; c<cols; ++c)

if(check(board, col_used, r, c)){

col_used.insert(c);

board[r][c]='Q';

DFS(all_boards, board, col_used, r+1);

board[r][c]='.';

col_used.erase(c);

}

bool check(vector<string> &board, set<int> &col_used, int r, int c){

if(col_used.count(c))

return false;

int rows=board.size(), cols=board[0].size();

int dr, dc;

for(dr=1, dc=1; r+dr<rows&&c+dc<cols; ++dr, ++dc)

if(board[r+dr][c+dc]=='Q')

return false;

for(dr=-1, dc=-1; r+dr>=0&&c+dc>=0; --dr, --dc)

if(board[r+dr][c+dc]=='Q')

return false;

for(dr=-1, dc=1; r+dr>=0&&c+dc<cols; --dr, ++dc)

if(board[r+dr][c+dc]=='Q')

return false;

for(dr=1, dc=-1; r+dr<rows&&c+dc>=0; ++dr, --dc)

if(board[r+dr][c+dc]=='Q')

return false;

return true;

}

};

发表于 2017-04-20 17:01:59 回复(0)

xyxlil

class Solution {
public:
    vector > solveNQueens(int n) {
        vector > res;
        vector solution;
        vector occupiedCol(n, -1);
        solveNQueens(0, n, solution,res, occupiedCol);
        return res;
    }
private:
    void solveNQueens(int row, int n, vector& solution, vector >& res, vector& occupiedCol) {
        if(row == n){res.push_back(solution);return;}
        for(int i=0; i < n; i++) {
            string s(n, '.');
            s[i] = 'Q';
            occupiedCol[row] = i;
            solution.push_back(s);
            if(ifValid(occupiedCol, row, i)) {
                solveNQueens(row+1, n, solution, res, occupiedCol);
            }
            solution.pop_back();
            occupiedCol[row] = -1;
        }
    }
    bool ifValid(vector& occupiedCols, int i, int j) {
        int len = occupiedCols.size();
        for(int m = 0; m < i; m++) {//检查前面的行
            int k = occupiedCols[m];
            if(j == k || abs(j-k) == abs(i-m))//若前面的行皇后所在的列与j相等或者与(i,j)在同一对角线上
                return false;
        }
        return true;
    }

};

编辑于 2017-01-26 16:46:49 回复(0)

牛客865742号

    //递归回溯
    vector<vector<string> > solveNQueens(int n) {
        string str;
        for(int i=0;i<n;i++)
            str.push_back('.');
        vector<string> vec;
        int *arr=new int[n];
        for(int i=0;i<n;i++)
            vec.push_back(str);
        vector<vector<string>> result;
        goahead(n,0,result,vec,arr);
        return result;
    }
    void goahead(int n,int t,vector<vector<string>> &res,vector<string> vec,int *arr){
        if(n==t){
            res.push_back(vec);
            return;
        }
        for(int i=0;i<n;i++){
            arr[t]=i;
            if(push(t,arr)){
                vec[t][i]='Q';
                goahead(n,t+1,res,vec,arr);
                vec[t][i]='.';
            }
        }
    }
    bool push(int m,int *arr){
        bool flag=true;
        for(int i=0;i<m;i++){
            if(arr[i]==arr[m] ||abs(arr[m]-arr[i])==(m-i)){
                flag=false;
                break;
            }
        }
        return flag;
    }

发表于 2016-09-15 16:33:12 回复(0)

codebread

class Solution {
public:
    //tmp[i]表示第i行的Q在哪一列
    void findSolution(int n,vector<vector<int> >&pos,
                     vector<int>&tmp){
        if(tmp.size()==n)
        {
            pos.push_back(tmp);
            return;
        }
        int i,j,k;
       	for( i=0;i<n;i++){
             k=tmp.size();
            for( j=0;j<k;j++){
                if(i==tmp[j]||
                   abs(k-j)==abs(i-tmp[j]))
                    break;
            }
            if(j<k)
                continue;
            tmp.push_back(i);
            findSolution(n,pos,tmp);
            int end=tmp.size()-1;
            if(k!=end)
				tmp.erase(tmp.begin()+k,
                     tmp.begin()+end);
			else
				tmp.erase(tmp.begin()+k);
        }
    }
    void drawSolution(int n,vector<vector<string> >&solve,
                     vector<vector<int> >&pos){
       
        for(int i=0;i<pos.size();i++){
            string s(n,'.');
        	vector<string>row(n,s);
            for(int j=0;j<n;j++){
                row[j][pos[i][j]]='Q';         
            }
            solve.push_back(row);
        }
    }
    vector<vector<string> > solveNQueens(int n) {
        vector<vector<string> >solve;
        if(n<1)
            return solve;
        vector<vector<int> >pos;
        vector<int>tmp;
        findSolution(n,pos,tmp);
        if(pos.empty())
            return solve;
        drawSolution(n,solve,pos);
        return solve;
    }
};

发表于 2016-06-07 10:31:01 回复(0)

C/C++

黄汉韬

class Solution {
public:
    vector<vector<string>> solveNQueens(int n) {
        vector<vector<string>> res;
        vector<string> cur(n, string(n, '.')); // 初始化棋盘，所有的位置都没有摆放皇后
        dfs(res, cur, n, 0);
        return res;
    }

    void dfs(vector<vector<string>> &res, vector<string> &cur, int &n, int row) {
        if (row == n) { // 当超出行数超出了棋盘，则把这次搜索的结果放入res中。
            res.push_back(cur);
            return;
        }

        for (int j = 0; j < n; j++) {
            if (isValid(cur, n, row, j)) { // 判断在(row, j)处是否可以放一个皇后
                cur[row][j] = 'Q'; // 如果可以，则放一个皇后
                dfs(res, cur, n, row + 1); // 继续在下一行找一个位置放皇后
                cur[row][j] = '.'; // 因为需要找到所有可能的情况，所以必然需要对每一行进行回退。去判断这一行的下一列是否可以放皇后。
            }
        }
    }

    bool isValid(vector<string> &cur, int &n, int row, int col) {
        // 检查列
        for (int i = 0; i < row; i++) {
            if (cur[i][col] == 'Q') {
                return false;
            }
        }
        // 检查反斜线
        for (int i = row - 1, j = col - 1; i >= 0 && j >= 0; i--, j--) {
            if (cur[i][j] == 'Q') {
                return false;
            }
        }
        // 检查斜线
        for (int i = row - 1, j = col + 1; i >= 0 && j < n; i--, j++) {
            if (cur[i][j] == 'Q') {
                return false;
            }
        }
        return true;
    }
};

发表于 2017-11-30 17:14:12 回复(1)

maoger

题目的意思就是：任意两个皇后都不能处于同一行、同一列或同一斜线上

发表于 2017-07-16 09:01:26 回复(0)

Java

牛客958742833号

我这个代码为什么提交不了？？？？？

import java.util.*;
public class Solution {
private ArrayList<String[]> res = new ArrayList<String[]>();
private int[] a;

public ArrayList<String[]> solveNQueens(int n) {
a = new int[n];
dnf(0, n, a);
return res;
}

private void dnf(int row, int n, int[] a) {
if (row == n) {
//打印a
res.add(int2str(a));
return;
}
for (int i = 0; i < n; i++) {
a[row] = i;
if (check(row, a)) {
a[row] = i;
dnf(row + 1, n, a);
}
}
}

private boolean check(int row, int[] a) {
for (int i = 0 ; i < row; i++) {
if (a[i] == a[row]) return false;
if (a[row] - a[i] == row - i) return false;
if (a[row] - a[i] == i - row) return false;
}
return true;
}

private String[] int2str(int[] a) {
String[] ab = new String[a.length];
//1302
for (int i = 0; i < a.length; i++) {
StringBuffer sb = new StringBuffer();
for (int j = 0; j < a.length; j++) {
if (i == a[j]) {
sb.append("Q");
} else {
sb.append(".");
}
}
ab[i] = sb.toString();
}

return ab;
}
}

发表于 2022-06-07 08:31:07 回复(1)

n-皇后

问题信息

热门推荐

通过挑战的用户

相关试题