经典算法10：回溯法求解八皇后

概述经典算法10：回溯法求解八皇后

下面是内存溢出 jb51.cc 通过网络收集整理的代码片段。

内存溢出小编现在分享给大家，也给大家做个参考。

    VIEw Code             using System;      using System.Collections.Generic;      using System.linq;      using System.Text;            namespace eightQueen      {          //八皇后问题：在8*8格的国际象棋上摆放八个皇后，使其不能互相攻击，          //即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。          class Program          {              static voID Main(string[] args)              {                  DateTime time1 = DateTime.Now;                  QueenArithmetic(8);              //皇后个数可选                  DateTime time2 = DateTime.Now;                  TimeSpan span = time2 - time1;                  Console.Writeline("\n执行时间："+span);                  Console.ReadKey();              }                    //定义解决皇后问题方法，使用回溯法，根据皇后数量获取结果              static voID QueenArithmetic(int queenNum)              {                  int[] Queen = new int[queenNum];    //保存每次成功的结果，索引代表所在列，值代表皇后在该列的位置                  int row = 0;    //当前所在的行                      int column = 0;     //当前所在列                  Queen[0]=-1;                  int count = 0;     //用来记录当前是第几种摆法                        while (true)                  {                      for (row = Queen[column]+1; row < queenNum; row++)    //遍历本次回溯  该列中未被访问到的行                      {                          if (!IsConflict(Queen,column,row))        //如果不冲突                          {                              break;                          }                       }                      if (row >= queenNum)   //没有找到合适的位置                      {                          if (column == 0)   //如果当前已经回溯到了第一列                          {                              break;          //退出while循环，整个过程结束                          }                          else                          {                              Queen[column] = -1;      //否则回溯到上一列                              column--;                          }                      }                      else            //找到了合适的位置                      {                          Queen[column] = row;                          column++;               //为下一列找合适位置                          if (column < queenNum)//如果当前不是最后一列                          {                              Queen[column] = -1;                          }                          else     //说明本次查找完毕，开始打印输出                          {                              PrintQueen(Queen,queenNum,++count);//打印输出当前结果                              column--;               //回溯到上一列继续查找                          }                      }                  }              }                    //根据获得的皇后数组，判断当前位置（row,column）是否与前面冲突              static bool IsConflict(int[] queen,int column,int row)              {                  for (int exsitColumn = 0; exsitColumn < column; exsitColumn++)  //遍历当前列之前的所有列中找到的皇后位置，检测是否与当前位置冲突                  {                      int exsitRow = queen[exsitColumn];                      int span = column - exsitColumn;                      if ((row == exsitRow) || (row == exsitRow + span) || (row == exsitRow - span))  //如果在同一行或者同一条斜线上                      {                          return true;                                                            //即冲突                      }                  }                  return false;              }                    //打印输出结果              static voID PrintQueen(int[] queen,int queenNum,int count)              {                  Console.Writeline("\n第{0}种摆法：",++count);                  for (int c = 0; c < queenNum; c++)                  {                      for (int r = 0; r < queenNum; r++)                      {                          if (r == queen[c])                          {                              Console.Write("Q");                          }                          else                          {                              Console.Write("*");                          }                      }                      Console.Write("\n");                  }              }          }      }  

以上是内存溢出(jb51.cc)为你收集整理的全部代码内容，希望文章能够帮你解决所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。

总结

以上是内存溢出为你收集整理的经典算法10：回溯法求解八皇后全部内容，希望文章能够帮你解决经典算法10：回溯法求解八皇后所遇到的程序开发问题。

如果觉得内存溢出网站内容还不错，欢迎将内存溢出网站推荐给程序员好友。