ruochen
回溯法 n 皇后问题(Java实现)
原创
关注作者
前往小程序,Get
更优
阅读体验!
立即前往
腾讯云
开发者社区
文档
建议反馈
控制台
首页
学习
活动
专区
工具
TVP
最新优惠活动
文章/答案/技术大牛
搜索
搜索
关闭
发布
登录/注册
首页
学习
活动
专区
工具
TVP
最新优惠活动
返回腾讯云官网
ruochen
首页
学习
活动
专区
工具
TVP
最新优惠活动
返回腾讯云官网
社区首页
>
专栏
>
回溯法 n 皇后问题(Java实现)
回溯法 n 皇后问题(Java实现)
原创
ruochen
关注
修改于 2021-05-17 10:20:42
666
0
修改于 2021-05-17 10:20:42
举报
文章被收录于专栏:
若尘的技术专栏
若尘的技术专栏
n 皇后问题
问题分析
在n×n格的棋盘上放置彼此不受攻击的n个皇后。按照国际象棋的规则,皇后可以攻击与之处在同一行或同一列或同一斜线上的棋子。n后问题等价于在n×n格的棋盘上放置n个皇后,任何2个皇后不放在同一行或同一列或同一斜线上。
xi 表示皇后i 放在棋盘的第i 行的第xi 列 - 不能在同一行 - 不能在同一列 xi 互不相同 - 不能在同一斜线 - 斜率为1 和值相等 - 斜率为-1 差值相等 - 若两个点 (i, j) (k, l), 则有 - i - j = k - l => i - k = j - l - i + j = k + l => i - k = l -j - 即 |i - k| = |j - l| 成立即可Java 源代码/* * 若尘 */ package nqueen; /** * n 皇后问题 * @author ruochen * @version 1.0 */ public class NQueen { /** 皇后个数 */ static int n; /** 当前解 */ static int[] x; /** 当钱已找到的可行方案数 */ static long sum; public static void main(String[] args) { nQueen(5); System.out.println("可行方案个数为: " + sum); } /** * 初始化及返回可行解个数 * @return 可行解个数 */ public static long nQueen(int nn) { n = nn; sum = 0; x = new int[n + 1]; for (int i = 0; i <= n; i++) { // 初始化 x[i] = 0; } backTrack(1); return sum; } /** * 可行性约束 * @param k * @return 是否可行 */ public static boolean place(int k) { for (int j = 1; j < k; j++) { // 对应公式 |i - k| = |j - l| && 列号不能相同 if ((Math.abs(k - j) == Math.abs(x[j] - x[k])) || x[j] == x[k]) return false; } return true; } /** * 回溯搜索 * @param i */ public static void backTrack(int t) { if (t > n) { // 已经找到一种可行解 long temp = sum + 1; System.out.print("第" + temp + "种可行解为: "); for (int k = 1; k <= n; k++) { System.out.print(x[k] + " "); } System.out.println(); sum++; } else { for (int i = 1; i <= n; i++) { x[t] = i; if (place(t)) backTrack(t + 1); } } } }第1种可行解为: 1 3 5 2 4 第2种可行解为: 1 4 2 5 3 第3种可行解为: 2 4 1 3 5 第4种可行解为: 2 5 3 1 4 第5种可行解为: 3 1 4 2 5 第6种可行解为: 3 5 2 4 1 第7种可行解为: 4 1 3 5 2 第8种可行解为: 4 2 5 3 1 第9种可行解为: 5 2 4 1 3 第10种可行解为: 5 3 1 4 2 可行方案个数为: 10
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系
cloudcommunity@tencent.com
删除。
数据结构
原创声明:本文系作者授权腾讯云开发者社区发表,未经许可,不得转载。
如有侵权,请联系
cloudcommunity@tencent.com
删除。
数据结构
评论
登录
后参与评论
0 条评论
热度
最新
推荐阅读
LV.
关注
文章
0
获赞
0
目录
n 皇后问题
问题分析
领券
问题归档
专栏文章
快讯文章归档
关键词归档
开发者手册归档
开发者手册 Section 归档
0
0
0
推荐