首页 > 试题广场 >

n-皇后

[编程题]n-皇后

热度指数：7956 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 32M，其他语言64M
算法知识视频讲解

N皇后问题是把N个皇后放在一个N×N棋盘上，使皇后之间不会互相攻击。

给出一个整数n，返回n皇后问题的所有摆放方案

例如：

4皇后问题有两种摆放方案

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

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

算法知识视频讲解

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)

Java

Raymond🌽

参考了labuladong的回溯算法代码框架，可是他书里用的是C++写了，对字符串操作方便一些。但我只会JAVA，用JAVA写的确比较麻烦些😭，调整输出格式就花了整一个小时。哭死

import java.util.*;
public class Solution {
    
    //结果集
    ArrayList<String[]> res = new ArrayList<String[]>();
    public ArrayList<String[]> solveNQueens(int n) {
        if(n==0){
            return res;
        }
        // '.' 表示空，'Q' 表示皇后，初始化空棋盘。
        String[][] board = new String[n][n];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++)
                board[i][j]=".";
        }
        backtrack(board, 0);
        return res;
        
    }
    
    void backtrack(String[][] board, int row){
        
        //结束条件
        if(row == board.length){
            int n = board.length;
            String[] tmp = new String[n];
            for(int i=0;i<n;i++){
                tmp[i]="";
                for(int j=0;j<n;j++){
                    tmp[i] += board[i][j];
                }
            }
            res.add(tmp);
            return;
        }
        
        //循环递归
        for(int col=0; col<board[row].length; col++){
            //决策树判断，排除不合法的下棋位置
            if(!isValid(board, row, col)){
                continue;
            }
            //做选择
            board[row][col] = "Q";
            //进入下一行决策树
            backtrack(board, row+1);
            //撤销选择
            board[row][col] = ".";
        }
    }
    
    boolean isValid(String[][] board, int row, int col){
        int n = board.length;
        //检查列是否有皇后互相冲突
        for(int i=0; i<n; i++){
            if(board[i][col] == "Q")
                return false;
        }
        //检查右上方
        for(int i=row-1, j=col+1; i>=0&&j<n; i--,j++){
            if(board[i][j] == "Q")
                return false;
        }
        //检查左上方
        for(int i=row-1, j=col-1; i>=0&&j>=0; i--,j--){
            if(board[i][j] == "Q")
                return false;
        }
        return true;
    }
}

发表于 2022-03-09 17:10:54 回复(0)

Java

嘿，man

/**
使用一维数组
leetcode 通过 ：Runtime: 2 ms, faster than 97.02% of Java online */
class Solution {
    public List<List<String>> solveNQueens(int n) {
        List<List<String>> res = new ArrayList();
        int [] visit = new int[n];
        dfs(res,visit,0,n);
        return res;
    }
    
    private void dfs(List<List<String>> res,int [] visit,int row,int n){
        if(row == n){
            List<String> t = new ArrayList();
            char [] temp = new char[n];
            int count = 0;
            while(count < n){
                for(int j = 0;j<n;j++){
                    if(visit[count] == j){
                        temp[j] = 'Q';
                    }else{
                        temp[j] = '.';
                    }
                }
                t.add(new String(temp));
                count++;
            }
            res.add(t);
            return;
        }
        for(int col=0;col<n;col++){
            if(isValid(row,col,n,visit)){
                visit[row] = col;
                dfs(res,visit,row+1,n);
            }
        }
        
    }
    
    private boolean isValid(int row,int col,int n,int [] visit){
        for(int i=0;i<row;i++){
            if(visit[i] == col || Math.abs(i-row) == Math.abs(visit[i]-col)){
                return false;
            }
        }
        return true;
    }
    
}

发表于 2020-02-09 18:01:03 回复(0)

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)

Java

lsx

import java.util.ArrayList;
 
public class NQueen {
    public static void main(String[] args) {
        NQueen nQueen = new NQueen();
        ArrayList<String[]> lists = nQueen.solveNQueens(4);
    }
    public ArrayList<String[]> solveNQueens(int n) {
        ArrayList<String[]> results = new ArrayList<>();
        if (n <= 0) {
            return results;
        }
        if (n == 1) {
            String[] strings = new String[1];
            strings[0] = "Q";
            results.add(strings);
            return results;
        }
        int k = 1;  // k表示当前行
        int[] x = new int[n+1];  //x[k] 表示当前列
 
        while (k>0) {
            x[k] = x[k] + 1;
            while ((x[k] <= n) && !place(k, x)) { //跳出循环表示：当前位置k可以放或者超出
                x[k] = x[k] + 1; // 不能放在该位置，判断下一列
            }
 
 
            if (x[k] <= n) { //找到满足皇后的位置
                if (k == n){ //最后一个皇后找到位置
                    String[] strings = new String[n];
                    for (int i = 1; i < n+1; i++) {
                        StringBuffer sb = new StringBuffer();
                        for (int j = 0; j < n; j++) {
                            sb.append(".");
                        }
                        sb.setCharAt(x[i]-1, 'Q');
                        strings[i-1] = sb.toString();
                        //System.out.print(x[i] + " ");
                    }
                    results.add(strings);
                }else{
                    k = k + 1;
                    x[k] = 0;  // 列重置
                }
 
            }else//未找到满足皇后的位置
                k = k - 1; //回溯
        }
 
        return results;
    }
 
    // 约束条件，判断当前位置可不可以放
    private boolean place(int k, int[] x) {
        int i = 1;
        while (i < k) {
            if (x[i] == x[k] || Math.abs(x[i] - x[k]) == Math.abs(i-k)) {
                return false;
            }
            ++i;
        }
        return true;
    }
}
 
 
 
    

编辑于 2017-08-17 15:46:13 回复(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)

Java

城市里的养猫者

I didn't invent a wheel here. We just remember the busy columns and diagonals and recursively try to put the queen into the next row. But I think the code below is short enough to be reproduced in the interview.

Hope it helps!

public class Solution { private void helper(int r, boolean[] cols, boolean[] d1, boolean[] d2, String[] board, List<String[]> res) { if (r == board.length) res.add(board.clone()); else { for (int c = 0; c < board.length; c++) { int id1 = r - c + board.length, id2 = 2*board.length - r - c - 1; if (!cols[c] && !d1[id1] && !d2[id2]) { char[] row = new char[board.length];
                    Arrays.fill(row, '.'); row[c] = 'Q';
                    board[r] = new String(row);
                    cols[c] = true; d1[id1] = true; d2[id2] = true;
                    helper(r+1, cols, d1, d2, board, res);
                    cols[c] = false; d1[id1] = false; d2[id2] = false;
                }
            }
        }
    } public List<String[]> solveNQueens(int n) {
        List<String[]> res = new ArrayList<>();
        helper(0, new boolean[n], new boolean[2*n], new boolean[2*n], new String[n], res); return res;
    }
}