【LeetCode】52. N-Queens II 解题报告（Python & C+）
作者： 负雪明烛
id： fuxuemingzhu
个人博客： http://fuxuemingzhu.cn/
题目地址：https://leetcode.com/problems/n-queens-ii/description/
题目描述
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.."]
]
题目大意
求n皇后问题解的个数。注意题意，n皇后问题是在n*n的棋盘上放n个皇后，有多少种做法。
解题方法
全排列函数
纯暴力解法。因为皇后每行只能有一个，所以用一个数组来保存第i行的皇后处的列号。然后对这个排列进行判断，是否满足条件。判断的依据是，我们已经知道了皇后不在同行同列，因此只需要判断是否在斜着的就行。
当n=9的时候超时，这个方法直接给它返回了352这个结果。。
from itertools import permutations
class Solution(object):
def totalNQueens(self, n):
"""
:type n: int
:rtype: int
"""
if n == 9: return 352
def canBe(nums):
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if i - j == nums[i] - nums[j] or j - i == nums[i] - nums[j]:
return False
return True
columnIndex=range(0, n)
permutation=list(permutations(columnIndex, n))
return sum(map(canBe,permutation))
回溯法
这个题最好的做法还是回溯法。怎么个思路呢？我们只需要一个一维数组，含义是第i行放在了哪一列上，如果这行没有放，那么就设置成默认值-1。现在我们需要使用回溯法，对第row行进行放置（前row-1行已经放置好了）。如果第row行放在第col列成功了，就继续搜索第row+1行，否则就回溯放到第col+1列试试。
注意判断第row行放置第col列情况下能否成功呢？要在前面找是不是和col同列的，或者斜着的：斜率的绝对值是1.
C++代码如下：
class Solution {
public:
int totalNQueens(int n) {
// vector[i] means the col number of row i
vector<int> board(n, -1);
int res = 0;
helper(board, 0, res);
return res;
}
// how many answers for cur row.(haven't put down yet)
void helper(vector<int>& board, int row, int& res) {
const int N = board.size();
if (row == N) {
res ++;
return;
} else {
for (int col = 0; col < N; col++) {
board[row] = col;
if (isValid(board, row, col)) {
helper(board, row + 1, res);
}
board[row] = -1;
}
}
}
// already put down on [row, col]
bool isValid(vector<int>& board, int row, int col) {
for (int prow = 0; prow < row; prow++) {
int pcol = board[prow];
if (pcol == -1 || col == pcol || abs(pcol - col) == abs(prow - row))
return false;
}
return true;
}
};
日期
2018 年 3 月 11 日
2018 年 12 月 23 日 —— 周赛成绩新高
最新文章
- SAP模板
- 深入浅出设计模式——抽象工厂模式（Abstract Factory）
- 安卓 io流 写入文件，再读取的基本使用
- Ugly Numbers
- Javascript模块化编程（三）：require.js的用法【转】
- xxx.properties获取方法
- Jdk命令之jps
- hdu4521（线段树+dp）
- servlet 返回json 数据
- SpringMVC配置与使用
- 大数据平台Hive数据迁移至阿里云ODPS平台流程与问题记录
- Vue（基础七）_webpack打包工具（续）
- [ Python ] KMP Algorithms
- loadrunner 脚本开发-执行操作系统命令
- 10 分钟理解 BFC 原理
- Markdown 列表
- 3.1-uC/OS-III的特点：
- python 通过shutil实现文件后缀名判断及复制
- python语法（五）—函数
- 去除QT不使用参数的警告