热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

Java编程实践:N皇后问题(LeetCode第51题)

n皇后问题探讨了在n×n的棋盘上放置n个皇后,确保任意两个皇后不会互相攻击的解决方案。本文以8皇后问题为例,展示了该问题的一种可能解法。通过给定整数n,程序将返回所有不同的n皇后问题的有效布局方案。此外,文章还详细介绍了实现这一算法的具体步骤和关键技巧,帮助读者深入理解并掌握这一经典编程挑战。

n 皇后问题研究的是如何将 n 个皇后放置在 n×n 的棋盘上,并且使皇后彼此之间不能相互攻击。

上图为 8 皇后问题的一种解法。

给定一个整数 n,返回所有不同的 n 皇后问题的解决方案。

每一种解法包含一个明确的 n 皇后问题的棋子放置方案,该方案中 'Q' 和 '.' 分别代表了皇后和空位。

示例:

输入: 4
输出: [
 [".Q..",  // 解法 1
  "...Q",
  "Q...",
  "..Q."],

 ["..Q.",  // 解法 2
  "Q...",
  "...Q",
  ".Q.."]
]
解释: 4 皇后问题存在两个不同的解法。

思路:经典的回朔算法,写的比较丑陋,见谅。。。。

class Solution {List> ans=new ArrayList>();List res=new ArrayList();boolean[][] flag=new boolean[30][30];boolean[] mark=new boolean[30];public List> solveNQueens(int n) {dfs(n,n,0);return ans;} private void dfs(int num,int n,int row){if(num==0){StringBuilder tmp=new StringBuilder();for(int i=0;i(res));res.clear();return;}for(int i=0;i=0 && y>=0){if(flag[x][y]){isOk=false;break;}x--;y--;}x=row-1;y=col+1;while(x>=0 && y}

 


推荐阅读
author-avatar
鎏源大哥
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有