***N-Queens

2024-06-18 17:48
文章标签 queens

本文主要是介绍***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.

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

[[".Q..",  // Solution 1"...Q","Q...","..Q."],["..Q.",  // Solution 2"Q...","...Q",".Q.."]
]
分析:

不会!!!

不会!!!

不会!!!

o(╯□╰)o

http://blog.csdn.net/linhuanmars/article/details/20667175

N皇后问题是非常经典的问题了,记得当时搞竞赛第一道递归的题目就是N皇后。因为这个问题是典型的NP问题,所以在时间复杂度上就不用纠结了,肯定是指数量级的。下面我们来介绍这个题的基本思路。
主要思想就是一句话:用一个循环递归处理子问题。这个问题中,在每一层递归函数中,我们用一个循环把一个皇后填入对应行的某一列中,如果当前棋盘合法,我们就递归处理先一行,找到正确的棋盘我们就存储到结果集里面。
这种题目都是使用这个套路,就是用一个循环去枚举当前所有情况,然后把元素加入,递归,再把元素移除,这道题目中不用移除的原因是我们用一个一维数组去存皇后在对应行的哪一列,因为一行只能有一个皇后,如果二维数组,那么就需要把那一行那一列在递归结束后设回没有皇后,所以道理是一样的。

这道题最后一个细节就是怎么实现检查当前棋盘合法性的问题,因为除了刚加进来的那个皇后,前面都是合法的,我们只需要检查当前行和前面行是否冲突即可。检查是否同列很简单,检查对角线就是行的差和列的差的绝对值不要相等就可以。代码如下

public class Solution {public List<List<String>> solveNQueens(int n) {List<List<String>> res = new ArrayList<List<String>>();helper(n,0,new int[n], res);return res;}private void helper(int n, int row, int[] columnForRow, List<List<String>> res){if(row == n){List<String> item = new ArrayList<String>();for(int i=0;i<n;i++){StringBuilder strRow = new StringBuilder();for(int j=0;j<n;j++){if(columnForRow[i]==j)strRow.append('Q');elsestrRow.append('.');}item.add(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;}
}



这篇关于***N-Queens的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/1072691

相关文章

Leetcode204: N-Queens II

Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. 有了上一题的解法,简单修改下即可 class Solution {private:int num=0;public: in

【LeetCode】N-Queens II 【九度】题目1254:N皇后问题

N-Queens II Total Accepted: 2737 Total Submissions: 10408 My Submissions Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions.

【PAT】【Advanced Level】1128. N Queens Puzzle (20)

1128. N Queens Puzzle (20) 时间限制 300 ms 内存限制 65536 kB

leetcode-52. N-Queens II

leetcode-52. N-Queens II 题目: > Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. 跟上一题一样,比上一题简单。51-N-Queens I public c

leetcode-51. N-Queens

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 t

159.N-Queens II

Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. 分析:与上一道题目一样,只不过这个题只需要返回solution的数量即可。 /** Step1:定义一个数组nod

[leetcode]N-Queens

64ms过大集合 class Solution {vector<vector<string>> result;public:bool canPlace(int i, int j, vector<string> &tmp, int n){if(i == 0) return true;for(int k = 0; k < i; k++){if(tmp[k][j] == 'Q') return

leetcode:N-Queens II 【Java】

一、问题描述 Follow up for N-Queens problem. Now, instead outputting board configurations, return the total number of distinct solutions. 二、问题分析 参考问题leetcode:N-Queens 【Java】 三、算法代码 public cl

leetcode:N-Queens 【Java】

一、问题描述 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-queen

let 51 N-Queens

主题思想: 这是一道搜索题, 典型的回溯算法思路。 当搜索时,通常满足条件,需要改变某种状态。一种情况处理完后,应该把改变的状态再改回来,这就是回溯的核心。 典型的深度搜索。 具体到这道题, 可以对存储空间优化,因为搜索时可以一行一行搜索,即先寻找第一行合适的位置,再寻找第二行,这样可以用一个List 记录每一行的位置,list中添加的下标就是行号,存储的值是对应的列值。 具体代码: clas