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

    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");  
                }  
            }  
        }  
    }