n 皇后问题 研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。
给你一个整数 n ,返回 n 皇后问题 不同的解决方案的数量。
示例 1:
输入:n = 4
输出:2
解释:如上图所示,4 皇后问题存在两个不同的解法。
示例 2:
输入:n = 1
输出:1
提示:
1 <= n <= 9
皇后彼此不能相互攻击,也就是说:任何两个皇后都不能处于同一条横行、纵行或斜线上。
来源:力扣(LeetCode)
链接:https://leetcode-cn.com/problems/n-queens-ii
著作权归领扣网络所有。商业转载请联系官方授权,非商业转载请注明出处。
这道题适合用回溯,采用一个数组记录放置皇后的位置,数字表示每一行第几个位置放置皇后。
是否碰撞的判断方式:
1 数字 == 前面的数字
2 数字 + 所处的行号 == 前面的数字 + 前面数字所处的行号
3 数字 - 所处的行号 == 前面的数字 - 前面数字所处的行号
class Solution { public int totalNQueens(int n) { if (n == 1) { return 1; } // 采用回溯 int[] arr = new int[n]; int count = 0; for (int i = 0; i < n; i++) { arr[0] = i; count += totalNQueens(arr, 1, n); } return count; } public static int totalNQueens(int[] arr, int limit, int n) { int count = 0; for (int i = 0; i < n; i++) { // 判断是发横竖斜是否有碰撞。 boolean flag = true; for (int k = 0; k < limit; k++) { int item = arr[k]; if (item == i || item - k == i - limit || item + k == i + limit) { flag = false; } } if (flag) { arr[limit] = i; if (limit == n - 1) { return 1; } else { count += totalNQueens(arr, limit + 1, n); } } } return count; } }
可以实现,不过效率不高。