C#用遞歸算法處理八皇後成績。本站提示廣大學習愛好者：（C#用遞歸算法處理八皇後成績）文章只能為提供參考，不一定能成為您想要的結果。以下是C#用遞歸算法處理八皇後成績正文
1.引子
中國有一句古話，叫做“不撞南牆不回頭"，活潑的解釋了一小我的執拗，有點褒義，然則在軟件編程中，這類思緒確是一種處理成績最簡略的算法，它經由過程一品種似於蠻干的思緒，一步一步地往前走，每走一步都更接近目的成果一些，直到碰到妨礙物，我們才斟酌往回走。然後再持續測驗考試向前。經由過程如許的海浪式進步辦法，終究到達目標地。固然全部進程須要許多往復，如許的進步方法，效力比擬低下。
2.實用規模
實用於那些不存在簡明的數學模子以說明成績的實質，或許存在數學模子，然則難於完成的成績。
3.運用場景
在8*8國際象棋棋盤上，請求在每行放置一個皇後，且能做到在豎偏向，斜偏向都沒有抵觸。國際象棋的棋盤以下圖所示：
4.剖析
根本思緒如下面剖析分歧，我們采取慢慢摸索的方法，先從一個偏向往前走，能進則進，不克不及進則退，測驗考試別的的途徑。起首我們來剖析一下國際象棋的規矩，這些規矩可以或許限制我們的進步，也就是我們進步途中的妨礙物。一個皇後q(x,y)能被知足以下前提的皇後q(row,col)吃失落
1）x=row(在縱向不克不及有兩個皇後)
2）y=col（橫向）
3）col + row = y+x;（斜向正偏向）
4）col - row = y-x;（斜向反偏向）
碰到上述成績之一的時刻，解釋我們曾經碰到了妨礙，不克不及持續向前了。我們須要退回來，測驗考試其他途徑。
我們將棋盤看做是一個8*8的數組，如許可使用一種蠻干的思緒去處理這個成績，如許我們就是在8*8=64個格子中掏出8個的組合，C(64,80) = 4426165368,明顯這個數異常年夜，在蠻干的基本上我們可以增長回溯，從第0列開端，我們逐列停止，從第0行到第7行找到一個不受任何曾經現有皇後進擊的地位，而第五列，我們會發明找不到皇後的平安地位了，後面四列的擺放以下:
第五列的時刻，擺聽任何行都邑上圖所示曾經存在的皇後的進擊，這時候候我們以為我們撞了南牆了，是回頭的時刻了，我們撤退退卻一列，將本來擺放在第四列的皇後（3，4）拿走，從（3，4）這個地位開端，我們再第四列中尋覓下一個平安地位為（7，4），再持續到第五列，發明第五列依然沒有平安地位，回溯到第四列，此時第四列也是一個逝世胡同了，我們再回溯到第三列，如許進步幾步，回退一步，終究直到在第8列上找到一個平安地位（勝利）或許第一列曾經是逝世胡同，然則第8列依然沒有找到平安地位為止
總結一下，用回溯的辦法處理8皇後成績的步調為：
1）從第一列開端，為皇後找到平安地位，然後跳到下一列
2）假如在第n列湧現逝世胡同，假如該列為第一列，棋局掉敗，不然撤退退卻到上一列，在停止回溯
3）假如在第8列上找到了平安地位，則棋局勝利。
8個皇後都找到了平安地位代表棋局的勝利，用一個長度為8的整數數組queenList代表勝利擺放的8個皇後，數組索引代表棋盤的col向量，而數組的值為棋盤的row向
量，所以(row,col)的皇後可以表現為(queenList[col],col),如上圖中的幾個皇後可表現為：
queenList[0] = 0; queenList[1] = 3; queenList[2] = 1; queenList[3] = 4; queenList = 2;
我們看一下若何設計法式:
起首斷定(row,col)能否是平安地位的算法：
bool IsSafe(int col,int row,int[] queenList)
{
//只檢討後面的列
for (int tempCol = 0; tempCol < col; tempCol++)
{
int tempRow = queenList[tempCol];
if (tempRow == row)
{
//統一行
return false;
}
if (tempCol == col)
{
//統一列
return false;
}
if (tempRow - tempCol == row - col || tempRow + tempCol == row + col)
{
return false;
}
}
return true;
}
設定一個函數，用於查找col列後的皇後擺放辦法：
/// <summary>
/// 在第col列尋覓平安的row值
/// </summary>
/// <param name="queenList"></param>
/// <param name="col"></param>
/// <returns></returns>
public bool PlaceQueue(int[] queenList, int col)
{
int row = 0;
bool foundSafePos = false;
if (col == 8) //停止標記
{
//當處置完第8列的完成
foundSafePos = true;
}
else
{
while (row < 8 && !foundSafePos)
{
if (IsSafe(col, row, queenList))
{
//找到平安地位
queenList[col] = row;
//找下一列的平安地位
foundSafePos = PlaceQueue(queenList, col + 1);
if (!foundSafePos)
{
row++;
}
}
else
{
row++;
}
}
}
return foundSafePos;
}
挪用辦法：
static void Main(string[] args)
{
EightQueen eq = new EightQueen();
int[] queenList = new int[8];
for (int j = 0; j < 8; j++)
{
Console.WriteLine("-----------------"+j+"---------------------");
queenList[0] = j;
bool res = eq.PlaceQueue(queenList, 1);
if (res)
{
Console.Write(" ");
for (int i = 0; i < 8; i++)
{
Console.Write(" " + i.ToString() + " ");
}
Console.WriteLine("");
for (int i = 0; i < 8; i++)
{
Console.Write(" "+i.ToString()+" ");
for (int a = 0; a < 8; a++)
{
if (i == queenList[a])
{
Console.Write(" q ");
}
else
{
Console.Write(" * ");
}
}
Console.WriteLine("");
}
Console.WriteLine("---------------------------------------");
}
else
{
Console.WriteLine("不克不及完成棋局，棋局掉敗！");
}
}
Console.Read();
}
遞歸算法PlaceQueue,完成如許的功效：它尋覓第col列後的皇後的平安擺放地位，假如該函數前往了false,表現以後進入了逝世胡同，須要停止回溯，直到為0-7列都找
到了平安地位或許找遍這些列都找不到平安地位的時刻終止。
用遞歸算法處理8皇後成績的示例法式：
http://xiazai.jb51.net/201606/yuanma/EightQueens(jb51.net).rar
