八皇后問(wèn)題問(wèn)題描述：
八皇后問(wèn)題捐康，是一個(gè)古老而著名的問(wèn)題，是回溯算法的典型案例庸蔼。該問(wèn)題是國(guó)際西洋棋棋手馬克斯·貝瑟爾于1848年提出：在8×8格的國(guó)際象棋上擺放八個(gè)皇后解总，使其不能互相攻擊，即任意兩個(gè)皇后都不能處于同一行姐仅、同一列或同一斜線上花枫，問(wèn)有多少種擺法刻盐。之后陸續(xù)有數(shù)學(xué)家對(duì)其進(jìn)行研究，其中包括高斯和康托（高斯認(rèn)為有76種方案）并且將其推廣為更高級(jí)的n皇后擺放問(wèn)題劳翰。八皇后問(wèn)題的第一個(gè)解是在1850年由弗朗茲·諾克給出的敦锌。諾克也是首先將問(wèn)題推廣到更高級(jí)的n皇后擺放問(wèn)題的人之一。1874年佳簸，S.岡德?tīng)柼岢隽艘粋€(gè)通過(guò)行列式來(lái)求解的方法乙墙，這個(gè)方法后來(lái)又被J.W.L.格萊舍加以改進(jìn)。1854年在柏林的象棋雜志上不同的作者發(fā)表了40種不同的解溺蕉，后來(lái)有人用圖論的方法解出92種結(jié)果。計(jì)算機(jī)發(fā)明后悼做，有多種計(jì)算機(jī)語(yǔ)言可以解決此問(wèn)題疯特。
網(wǎng)上有很多關(guān)于C++和JAVA的算法實(shí)現(xiàn) 下面我們用C#語(yǔ)言實(shí)現(xiàn)這個(gè)問(wèn)題。
C#的解決算法：
using System;
using System.Collections.Generic;
namespace QueensSolution
{
class Program
{
static int count = 0;
static void Main(string[] args)
{
int n = Int32.Parse(Console.ReadLine());
List<int> queen = new List<int>(n);
for (int i = 1; i <= n; i++)
{
queen.Add(0);
}
PutQueen(n, queen, 0);
Console.WriteLine(count);
Console.ReadKey();
}
private static void PutQueen(int n, List<int> queen, int row)
{
for (queen[row] = 1; queen[row] <= n; queen[row]++)
{
if (CheckQueens(queen, row))
{
row++;
if (row < n)
{
PutQueen(n, queen, row);
}
else
{
count++;
for (int i = 0; i < n; i++)
{
Console.Write(queen[i].ToString() + " ");
}
Console.WriteLine();
}
row--;
}
}
}
private static bool CheckQueens(List<int> queen, int row)
{
for (int i = 0; i < row; i++)
{
if (Math.Abs(queen[i] - queen[row]) == Math.Abs(i - row) || queen[i] == queen[row])
{
return false;
}
}
return true;
}
}
}
解釋：
1.要想解出在n*n的棋盤上到底有多少種放置皇后的方法肛走，主要用到兩個(gè)方法漓雅，放皇后的PutQueen方法，檢查皇后的CheckQueens方法朽色。
2.在Main函數(shù)里對(duì)動(dòng)態(tài)數(shù)組進(jìn)行初始化邻吞，這個(gè)動(dòng)態(tài)數(shù)組用來(lái)記錄N皇后中每一行所放置的皇后的位置（1就代表放置在該行第一列，n就代表放置在該行的第n列）葫男。
3.row代表的是八皇后棋盤的每一行抱冷。
4.在Main函數(shù)中對(duì)動(dòng)態(tài)數(shù)組進(jìn)行了一下初始化，這一步是必須的梢褐，否則運(yùn)行結(jié)果報(bào)錯(cuò)旺遮。
5.變量count（解的個(gè)數(shù)）聲明在Main函數(shù)外，是靜態(tài)的盈咳。
6.PutQueen方法采用遞歸思想——放皇后（該行中每一列都要放置）耿眉，檢查放皇后的位置是否合理，如果合理則到下一行鱼响，判斷下一行是否存在鸣剪，如果存在——放皇后（該行中每一列都要放置），檢查放皇后的位置是否合理丈积，如果合理則……直到不存在下一行為止每一行都已經(jīng)放置好了皇后筐骇，這時(shí)我們將解的個(gè)數(shù)記錄一下（count++），然后打印該種解法江滨。
7.在遞歸結(jié)束后拥褂，一定要記得返回到上一行（row--），這樣才能讓“for (queen[row] = 1; queen[row] <= n; queen[row]++)”生效牙寞，實(shí)現(xiàn)每一行中的每一列都放置過(guò)皇后饺鹃。一定要注意row--的位置要放在整個(gè)if-else語(yǔ)句塊的后面莫秆！因?yàn)檎麄€(gè)if-else語(yǔ)句塊形成了對(duì)遞歸過(guò)程中狀態(tài)的判斷，有兩種狀態(tài)悔详，第一種狀態(tài)是皇后當(dāng)前在第2到n-1行镊屎，這時(shí)候如果想返回上一行，“row--”的位置其實(shí)可以寫在if語(yǔ)句塊中"PutQueen(n, queen, row);"這一句的后面茄螃；第二種狀態(tài)是皇后當(dāng)前在最后一行（也就是第n行）缝驳，這時(shí)候如果想返回上一行，“row--”的位置其實(shí)可以寫在else語(yǔ)句塊中归苍。因此用狱，我們才將“row--”的位置移到了整個(gè)if-else語(yǔ)句塊的后面。
此時(shí) 我們運(yùn)行程序拼弃，可以得到八皇后的正解92
當(dāng)然我們使用了遞歸的算法 所以 問(wèn)題可以擴(kuò)展到十皇后到N皇后（當(dāng)然了 一般家用臺(tái)式機(jī)夏伊，十皇后以后的計(jì)算就非常耗時(shí)，對(duì)計(jì)算機(jī)的運(yùn)算能力是個(gè)挑戰(zhàn)）
