八皇后問題作喘，是一個古老而著名的問題，是回溯算法的典型案例窖贤。

問題的內(nèi)容是在國際象棋棋盤上（8*8）贰锁，放置八個皇后并使其不能互相攻擊。

核心在于皇后的規(guī)則：任意兩個皇后都不能處于同一行授嘀、同一列或同一斜線上锣险。

未來會重寫此算法，以精簡代碼為目的芯肤。

已重寫此算法，重寫后的算法

想法是通過遞歸行的方式來解決問題：

第一行取八個不同的皇后位置盔几，并依次向下遞歸調(diào)用第二行（即每個位置取一次）

第二行也取八個不同的皇后位置掩幢，并判斷是否滿足不能互相攻擊的原則，滿足的再次向下遞歸調(diào)用第三行

直到最后一行處理芯丧，滿足條件的取出來即八皇后問題的解法世曾。

使用C#實現(xiàn)的效果：

image.png

接下來是用C#實現(xiàn)的代碼:

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
using System.IO;

namespace test {
    class Program {
        const int COUNT = 8;

        static int anser = 0;
        static void Main(string[] args) {
            Serach();
            Console.WriteLine("八皇后問題的解法有： " + anser + " 種。");
            Console.ReadLine();
        }

        /// <summary>
        /// 遞歸-每次運行此方法都是以行為基礎(chǔ)向下遞歸
        /// 棋盤上以8*8的二維數(shù)組標(biāo)識骗露，有皇后為1無為0.
        /// </summary>
        /// <param name="chessboard"></param>
        /// <param name="c"></param>
        static void Serach(bool[][] chessboard = null, int c = 0)       
        {
            bool[][] chess;
            //  每次遞歸只運行一行
            for (int i = c; i < COUNT && i < c + 1; i++) {
                if (chessboard == null)         //  這里方便初次調(diào)用不要輸入?yún)?shù)
                    chess = new bool[COUNT][];
                else
                    chess = chessboard;     //  遞歸調(diào)用時拿取上一次的結(jié)果

                if (chess[i] == null) {     //  只有此行為NULL時才執(zhí)行
                    for (int j = 0; j < COUNT; j++) {
                        chess[i] = new bool[COUNT];     //  初始化數(shù)組自動全部會賦值為false
                        chess[i][j] = true;
                        if (Check(chess)) {     //  判斷是否滿足皇后不互相傷害的要求
                            if (chess[7] == null) {     //  若最后一行都沒有問題就可以提交了
                                //  數(shù)組是引用類型每一次遞歸都要復(fù)制一份
                                var temp = new bool[8][];
                                chess.CopyTo(temp, 0);      
                                Serach(temp, c + 1);
                            } else {
                                anser++;
                                Console.WriteLine(view(chess));
                            }
                        }

                    }
                }
            }
        }

        /// <summary>
        /// true為可取萧锉，false為不可取
        /// </summary>
        /// <param name="chess"></param>
        /// <returns></returns>
        static bool Check(bool[][] chess) {
            for (int i = 0; i < COUNT; i++) {
                if (chess[i] == null)
                    break;

                for (int j = 0; j < COUNT; j++)
                    if (chess[i][j]) {      //  判斷此位置是否為皇后位置

                        for (int oi = 0; oi < COUNT; oi++) {
                            if (chess[oi] == null || oi == i)       
                                continue;    //  防止為空和重復(fù)判斷一行

                            for (int oj = 0; oj < COUNT; oj++)
                                if (chess[oi][oj]) {
                                    //  防止同列和斜列（同行的問題已經(jīng)被同行遞歸的方式避免了）
                                    if (j == oj || Math.Abs(oi - i) == Math.Abs(oj - j))
                                        return false;
                                }
                        }
                    }
            }
            return true;
        }

        /// <summary>
        /// 顯示結(jié)果的方法
        /// </summary>
        /// <param name="chess"></param>
        /// <returns></returns>
        static string view(bool[][] chess) {
            string str = "";
            for (int i = 0; i < COUNT; i++) {
                for (int j = 0; j < COUNT; j++) {
                    if (chess[i][j])
                        str += i + "行" + j + "列\(zhòng)n";
                }
            }
            str += "\n=======================================";
            return str;
        }
    }
}