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

八皇后問題：在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  
    {  
        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");  
            }  
        }  
    }  
}  </pre>