Leetcode之回溯法专题-51. N皇后（N-Queens）
2024-08-29 20:07:27
Leetcode之回溯法专题-51. N皇后（N-Queens）
n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上，并且使皇后彼此之间不能相互攻击。
上图为 8 皇后问题的一种解法。
给定一个整数 n，返回所有不同的 n 皇后问题的解决方案。
每一种解法包含一个明确的 n 皇后问题的棋子放置方案，该方案中 'Q' 和 '.' 分别代表了皇后和空位。
示例:
输入: 4
输出: [
[".Q..", // 解法 1
"...Q",
"Q...",
"..Q."], ["..Q.", // 解法 2
"Q...",
"...Q",
".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。 分析：输入一个N，求在这个N*N的面板里，N皇后的解法。要求是，放置了一个皇后时，该皇后的 行 列 不能存在其他皇后，且2个对角线上也不能有皇后。
利用回溯法可以解答这一题，首先初始化一个N*N的数组，并在其值上设置成'.'。
char mp[][] = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mp[i][j] = '.';
}
}
然后我们new一个存答案的List，
List<List<String>> ans = new ArrayList<>();
在写DFS之前，我们需要写一个boolean型的ok函数，用于判断一个棋盘是否符合要求：
public boolean ok(char[][] mp, int len, int x, int y) {
// check row
for (int i = 0; i < len; i++) {
if (i == y)
continue;
if (mp[x][i] == 'Q')
return false;
}
// check col
for (int i = 0; i < len; i++) {
if (i == x)
continue;
if (mp[i][y] == 'Q')
return false;
}
// x=1 y=3
int cnt = 0;
int up = 0;
int down = 0;
for(int i=y+1;i<len;i++){
up = (++cnt)*-1+x;
down = cnt*1+x;
if(up<len && up>=0){
//System.out.println("mp[up][i]=["+up+"]["+i+"]");
if(mp[up][i]=='Q')
return false;
}
if(down>=0 && down<len){
//System.out.println("mp[down][i]=["+down+"]["+i+"]");
if(mp[down][i]=='Q'){
return false;
}
}
}
//System.out.println("other");
cnt = 0;
for(int i=y-1;i>=0;i--){
up = (++cnt)*-1+x;
down = cnt*1+x;
if(up<len && up>=0){
//System.out.println("mp[up][i]=["+up+"]["+i+"]");
if(mp[up][i]=='Q')
return false;
}
if(down>=0 && down<len){
//System.out.println("mp[down][i]=["+down+"]["+i+"]");
if(mp[down][i]=='Q'){
return false;
}
}
}
return true;
}
下一步开始写dfs函数，
第一个参数是mp数组，是这一副棋盘，
第二个参数是n，代表的是棋盘的大小，
第三个参数是i，把2维的矩阵转换为1维了，例如i=1就对应着（0，1）这个点，以此类推。
第四个参数是queen，用来存现在放的棋子的个数。
public void dfs(char[][] mp, int len, int i,int queen) {
int x = i / len;
int y = i % len;
if ((x >= len || y >= len)) {
if(queen!=len) return;
List<String> list = new ArrayList<>();
for (int a = 0; a < len; a++) {
String tmp = "";
for (int b = 0; b < len; b++) {
tmp += mp[a][b];
}
list.add(tmp);
}
ans.add(list);
return;
}
dfs(mp,len,i+1,queen);
if (ok(mp, len, x, y)) {
mp[x][y] = 'Q';
dfs(mp, len, i + 1,queen+1);
mp[x][y] = '.';
}
}
整合一下，最后的AC代码为:
class Solution {
List<List<String>> ans = new ArrayList<>();
public List<List<String>> solveNQueens(int n) {
char mp[][] = new char[n][n];
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mp[i][j] = '.';
}
}
dfs(mp, n, 0,0);
return ans;
}
public void dfs(char[][] mp, int len, int i,int queen) {
int x = i / len;
int y = i % len;
if ((x >= len || y >= len)) {
if(queen!=len) return;
List<String> list = new ArrayList<>();
for (int a = 0; a < len; a++) {
String tmp = "";
for (int b = 0; b < len; b++) {
tmp += mp[a][b];
}
list.add(tmp);
}
ans.add(list);
return;
}
dfs(mp,len,i+1,queen);
if (ok(mp, len, x, y)) {
mp[x][y] = 'Q';
dfs(mp, len, i + 1,queen+1);
mp[x][y] = '.';
}
}
public boolean ok(char[][] mp, int len, int x, int y) {
// check row
for (int i = 0; i < len; i++) {
if (i == y)
continue;
if (mp[x][i] == 'Q')
return false;
}
// check col
for (int i = 0; i < len; i++) {
if (i == x)
continue;
if (mp[i][y] == 'Q')
return false;
}
// x=1 y=3
int cnt = 0;
int up = 0;
int down = 0;
for(int i=y+1;i<len;i++){
up = (++cnt)*-1+x;
down = cnt*1+x;
if(up<len && up>=0){
//System.out.println("mp[up][i]=["+up+"]["+i+"]");
if(mp[up][i]=='Q')
return false;
}
if(down>=0 && down<len){
//System.out.println("mp[down][i]=["+down+"]["+i+"]");
if(mp[down][i]=='Q'){
return false;
}
}
}
//System.out.println("other");
cnt = 0;
for(int i=y-1;i>=0;i--){
up = (++cnt)*-1+x;
down = cnt*1+x;
if(up<len && up>=0){
//System.out.println("mp[up][i]=["+up+"]["+i+"]");
if(mp[up][i]=='Q')
return false;
}
if(down>=0 && down<len){
//System.out.println("mp[down][i]=["+down+"]["+i+"]");
if(mp[down][i]=='Q'){
return false;
}
}
}
return true;
}
}
最新文章
- Delphi dll 断点调试
- JavaBean出现的目的
- 在IIS6上部署MVC站点，Nhiernate数据库底层
- @SuppressWarnings注解
- nyoj 20 吝啬的国度
- Markdown中实现缩进的方法
- LightOJ 1033 Generating Palindromes（dp）
- 自定义错误页面mvc用法
- cocos2D（五岁以下儿童）---- CCNode
- iOS 开发小技巧
- 基于NHibernate二级缓存的MongoDB组件
- NI笔试——大数加法
- Java开发笔记（四十一）日历工具Calendar
- Git和Gitlab在使用过程中所遇到的问题
- 2018-01-02 JavaScript实现ZLOGO: 用语法树实现多层循环
- 矩阵乘法np.dot()及np.multipy()区别
- spoj220
- TZOJ 2648 小希的迷宫(并查集)
- The 2018 Nobel prizesThe Nobel prize for economics is awarded for work on the climate and economic growth
- Jmeter获取不到cookie（备注：前面和后面的几个步骤都可以获取到cookie）