八皇后問題：在8*8格的國際象棋上擺放八個(gè)皇后，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。

思路：簡(jiǎn)單的說就是 從當(dāng)前列中依次選取位置，與前面列中選取的位置進(jìn)行比較，判斷是否沖突，若沖突，回溯到上一列尋找，否則進(jìn)入下一列尋找位置

1、從column=0列中選取一個(gè)位置，column+1，轉(zhuǎn)到2。（這里column為當(dāng)前列 值為0~7），

   2、從第column列中選取一個(gè)位置，  轉(zhuǎn)到3。

3、判斷是否與前面各列選取位置沖突。

  若沖突：判斷column列中位置是否全部判斷過，若是 轉(zhuǎn)到5，否則 直接轉(zhuǎn)到2；

  否則：轉(zhuǎn)到4。

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

 若到最后一列說明本次查找成功，記錄位置并將結(jié)果輸出，轉(zhuǎn)到5；

否則，記錄當(dāng)前位置，進(jìn)入下一列尋找合適位置，即column+1轉(zhuǎn)到2

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

若是：結(jié)束。

否則：繼續(xù)回溯，回溯到上一列繼續(xù)選取位置，即column-1轉(zhuǎn)到2 。

    View Code   
      
    using System;  
    using System.Collections.Generic;  
    using System.Linq;  
    using System.Text;  
      
    namespace eightQueen  
    {  
        //八皇后問題：在8*8格的國際象棋上擺放八個(gè)皇后，使其不能互相攻擊，  
        //即任意兩個(gè)皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法。  
        class Program  
        {  
            static void Main(string[] args)  
            {  
                DateTime time1 = DateTime.Now;  
                QueenArithmetic(8);              //皇后個(gè)數(shù)可選  
                DateTime time2 = DateTime.Now;  
                TimeSpan span = time2 - time1;  
                Console.WriteLine("\n執(zhí)行時(shí)間："+span);  
                Console.ReadKey();  
            }  
      
            //定義解決皇后問題方法，使用回溯法，根據(jù)皇后數(shù)量獲取結(jié)果  
            static void QueenArithmetic(int queenNum)  
            {  
                int[] Queen = new int[queenNum];    //保存每次成功的結(jié)果，索引代表所在列，值代表皇后在該列的位置  
                int row = 0;    //當(dāng)前所在的行      
                int column = 0;     //當(dāng)前所在列  
                Queen[0]=-1;  
                int count = 0;     //用來記錄當(dāng)前是第幾種擺法  
      
                while (true)  
                {  
                    for (row = Queen[column]+1; row < queenNum; row++)    //遍歷本次回溯  該列中未被訪問到的行  
                    {  
                        if (!IsConflict(Queen, column, row))        //如果不沖突  
                        {  
                            break;  
                        }   
                    }  
                    if (row >= queenNum)   //沒有找到合適的位置  
                    {  
                        if (column == 0)   //如果當(dāng)前已經(jīng)回溯到了第一列  
                        {  
                            break;          //退出while循環(huán)，整個(gè)過程結(jié)束  
                        }  
                        else  
                        {  
                            Queen[column] = -1;      //否則回溯到上一列  
                            column--;  
                        }  
                    }  
                    else            //找到了合適的位置  
                    {  
                        Queen[column] = row;  
                        column++;               //為下一列找合適位置  
                        if (column < queenNum)//如果當(dāng)前不是最后一列  
                        {  
                            Queen[column] = -1;  
                        }  
                        else     //說明本次查找完畢，開始打印輸出  
                        {  
                            PrintQueen(Queen, queenNum, ++count);//打印輸出當(dāng)前結(jié)果  
                            column--;               //回溯到上一列繼續(xù)查找  
                        }  
                    }  
                }  
            }  
      
            //根據(jù)獲得的皇后數(shù)組，判斷當(dāng)前位置（row,column）是否與前面沖突  
            static bool IsConflict(int[] queen, int column, int row)  
            {  
                for (int exsitColumn = 0; exsitColumn < column; exsitColumn++)  //遍歷當(dāng)前列之前的所有列中找到的皇后位置，檢測(cè)是否與當(dāng)前位置沖突  
                {  
                    int exsitRow = queen[exsitColumn];  
                    int span = column - exsitColumn;  
                    if ((row == exsitRow) || (row == exsitRow + span) || (row == exsitRow - span))  //如果在同一行或者同一條斜線上  
                    {  
                        return true;                                                            //即沖突  
                    }  
                }  
                return false;  
            }  
      
            //打印輸出結(jié)果  
            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");  
                }  
            }  
        }  
    }  

標(biāo)簽：

版權(quán)申明：本站文章部分自網(wǎng)絡(luò)，如有侵權(quán)，請(qǐng)聯(lián)系：west999com@outlook.com
特別注意：本站所有轉(zhuǎn)載文章言論不代表本站觀點(diǎn)！
本站所提供的圖片等素材，版權(quán)歸原作者所有，如需使用，請(qǐng)與原作者聯(lián)系。