首页 > 代码库 > 回溯算法-C#语言解决八皇后问题的写法与优化
回溯算法-C#语言解决八皇后问题的写法与优化
结合问题说方案，首先先说问题：
八皇后问题：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
嗯，这个问题已经被使用各种语言解答一万遍了，大多还是回溯法解决的。
关于回溯算法：个人理解为就是优化的穷举算法，穷举算法是指列出所有的可能情况，而回溯算法则是试探发现问题"剪枝"回退到上个节点，换一条路，能够大大提高求解效率。
具体到8皇后问题上来说，需要考虑以下几点：
1)将8个皇后定义为8行中的相对位置来标识，考虑增加新的皇后时，是否与之前的皇后位置冲突（即可以攻击之前摆放的皇后：位置相等或者斜率1or-1）
2)新放的皇后发生冲突时回溯至上一行继续试探，逐步回溯直至第一行为止
3)已经求出的解再次探索时避免重复
4)从第一行开始放皇后，然后开始循环往下放，可以设计为回调放皇后的方法
说了这么多废话，开始写吧，啪啪啪-- 12秒过去了，写完了，运行-----嘛结果也没有！！
贴上代码及注释
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Queen{ class Program { //定义解的个数 int sum = 0; //定义皇后数组 int[] Queens = new int[8]; static void Main(string[] args) { Program Pro = new Program(); //开始求解 Pro.QueenSort(0); } //排序获取组合（1-8） public void QueenSort(int num) { for (int j = 1; j < 9; j++) { if (num == 8) { sum++; //打印输出 Write(); break; } Queens[num] = j; //判断是否冲突 if (FooConflict(num, j)) { num++; QueenSort(num); } } } /// <summary> /// 判断皇后是否和之前所有的皇后冲突 /// </summary> /// <param name="row">已放置完毕无冲突皇后的列数</param> /// <param name="queen">新放置的皇后值</param> /// <returns>是否冲突</returns> public bool FooConflict(int row, int queen) { if (row == 0) { return true; } else { //循环判断与之前的皇后是否有冲突的 for (int pionter = 0; pionter < row; pionter++) { //如果有，返回false if (!FooCompare(Queens[pionter], row - pionter, queen)) { return false; } } //与之前均无冲突，返回true return true; } } /// <summary> /// 对比2个皇后是否冲突 /// </summary> /// <param name="i">之前的一个皇后</param> /// <param name="row">2个皇后的列数之差</param> /// <param name="queen">新放置的皇后</param> /// <returns></returns> public bool FooCompare(int i, int row, int queen) { //判断2个皇后是否相等或者相差等于列数之差（即处于正反对角线） if ((i == queen) || ((i - queen) == row) || ((queen - i) == row)) { return false; } return true; } //打印皇后图案 public void Write() { //输出皇后的个数排序 Console.WriteLine("第{0}个皇后排列:", sum); for (int i = 0; i < 8; i++) { for (int j = 1; j < 9; j++) { if (j == Queens[i]) { Console.Write("■"); } else { Console.Write("□"); } } //换行 Console.Write("\n"); } } }}
PS:还好我写的方法分的很细，直接锁定QueenSort()这个方法，嗯，一定是它出了问题！
仔细一看num++这一行,本意是循环QueenSort(num+1)查询下一个皇后的解，这样写导致下次循环赋值Queens[num]出现了异常，果断改了，运行OK!
贴上代码：
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Queen{ class Program { //定义解的个数 int sum = 0; //定义皇后数组 int[] Queens = new int[8]; static void Main(string[] args) { Program Pro = new Program(); //开始求解 Pro.QueenSort(0); } //排序获取组合（1-8） public void QueenSort(int num) { for (int j = 1; j < 9; j++) { if (num == 8) { sum++; //打印输出 Write(); break; } //判断是否冲突 if (FooConflict(num, j)) { Queens[num] = j; QueenSort(num+1); } } } /// <summary> /// 判断皇后是否和之前所有的皇后冲突 /// </summary> /// <param name="row">已放置完毕无冲突皇后的列数</param> /// <param name="queen">新放置的皇后值</param> /// <returns>是否冲突</returns> public bool FooConflict(int row, int queen) { if (row == 0) { return true; } else { //循环判断与之前的皇后是否有冲突的 for (int pionter = 0; pionter < row; pionter++) { //如果有，返回false if (!FooCompare(Queens[pionter], row - pionter, queen)) { return false; } } //与之前均无冲突，返回true return true; } } /// <summary> /// 对比2个皇后是否冲突 /// </summary> /// <param name="i">之前的一个皇后</param> /// <param name="row">2个皇后的列数之差</param> /// <param name="queen">新放置的皇后</param> /// <returns></returns> public bool FooCompare(int i, int row, int queen) { //判断2个皇后是否相等或者相差等于列数之差（即处于正反对角线） if ((i == queen) || ((i - queen) == row) || ((queen - i) == row)) { return false; } return true; } //打印皇后图案 public void Write() { //输出皇后的个数排序 Console.WriteLine("第{0}个皇后排列:", sum); for (int i = 0; i < 8; i++) { for (int j = 1; j < 9; j++) { if (j == Queens[i]) { Console.Write("■"); } else { Console.Write("□"); } } //换行 Console.Write("\n"); } } }}运行结果如下图：
OK! 等等 为毛百度了一下C语言的实现只有几行！！ 不过想想咱们的核心代码排序方法也就几行，还行吧,以后有空再考虑优化下
that’s all ！
回溯算法-C#语言解决八皇后问题的写法与优化
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。