回溯法解八皇后问题

本文主要是介绍回溯法解八皇后问题，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

暑假过了一半多了，前几天看到八皇后问题，就写了出来，使用回溯法。

八皇后问题：在8*8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。

思路：简单的说就是从当前列中依次选取位置，与前面列中选取的位置进行比较，判断是否冲突，若冲突，回溯到上一列寻找，否则进入下一列寻找位置

　　　1、从column=0列中选取一个位置，column+1，转到2。（这里column为当前列值为0~7），

　　 2、从第column列中选取一个位置，转到3。

　　　3、判断是否与前面各列选取位置冲突。

　　　　若冲突：判断column列中位置是否全部判断过，若是转到5，否则直接转到2；

　　　　否则：转到4。

　　　4、判断是否到最后一列。

　　　　若到最后一列说明本次查找成功，记录位置并将结果输出，转到5；

　　　　否则，记录当前位置，进入下一列寻找合适位置，即column+1转到2

　　　5、判断是否回溯到第一列。

　　　　若是：结束。

　　　　否则：继续回溯，回溯到上一列继续选取位置，即column-1转到2 。

代码如下：

View Code

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;

namespace eightQueen
{
//八皇后问题：在8*8格的国际象棋上摆放八个皇后，使其不能互相攻击，
//即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。
class Program
    {
staticvoid Main(string[] args)
        {
            DateTime time1 = DateTime.Now;
            QueenArithmetic(8);              //皇后个数可选
            DateTime time2 = DateTime.Now;
            TimeSpan span = time2 - time1;
            Console.WriteLine("\n执行时间："+span);
            Console.ReadKey();
        }

//定义解决皇后问题方法，使用回溯法，根据皇后数量获取结果
staticvoid QueenArithmetic(int queenNum)
        {
int[] Queen =newint[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）是否与前面冲突
staticbool 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))  //如果在同一行或者同一条斜线上
                {
returntrue;                                                            //即冲突
                }
            }
returnfalse;
        }

//打印输出结果
staticvoid 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");
            }
        }
    }
}