欧美bbbwbbbw肥妇,免费乱码人妻系列日韩,一级黄片

C#用遞歸算法解決八皇后問(wèn)題

 更新時(shí)間:2016年06月15日 10:34:49   作者:張玉彬  
在軟件編程中,這種思路確是一種解決問(wèn)題最簡(jiǎn)單的算法,它通過(guò)一種類似于蠻干的思路,一步一步地往前走,每走一步都更靠近目標(biāo)結(jié)果一些,直到遇到障礙物,我們才考慮往回走。

1.引子

  中國(guó)有一句古話,叫做“不撞南墻不回頭",生動(dòng)的說(shuō)明了一個(gè)人的固執(zhí),有點(diǎn)貶義,但是在軟件編程中,這種思路確是一種解決問(wèn)題最簡(jiǎn)單的算法,它通過(guò)一種類似于蠻干的思路,一步一步地往前走,每走一步都更靠近目標(biāo)結(jié)果一些,直到遇到障礙物,我們才考慮往回走。然后再繼續(xù)嘗試向前。通過(guò)這樣的波浪式前進(jìn)方法,最終達(dá)到目的地。當(dāng)然整個(gè)過(guò)程需要很多往返,這樣的前進(jìn)方式,效率比較低下。

2.適用范圍

  適用于那些不存在簡(jiǎn)明的數(shù)學(xué)模型以闡明問(wèn)題的本質(zhì),或者存在數(shù)學(xué)模型,但是難于實(shí)現(xiàn)的問(wèn)題。

3.應(yīng)用場(chǎng)景

  在8*8國(guó)際象棋棋盤上,要求在每一行放置一個(gè)皇后,且能做到在豎方向,斜方向都沒(méi)有沖突。國(guó)際象棋的棋盤如下圖所示:

http://img.jbzj.com/file_images/article/201606/201606151029091.jpg

4.分析

  基本思路如上面分析一致,我們采用逐步試探的方式,先從一個(gè)方向往前走,能進(jìn)則進(jìn),不能進(jìn)則退,嘗試另外的路徑。首先我們來(lái)分析一下國(guó)際象棋的規(guī)則,這些規(guī)則能夠限制我們的前進(jìn),也就是我們前進(jìn)途中的障礙物。一個(gè)皇后q(x,y)能被滿足以下條件的皇后q(row,col)吃掉

1)x=row(在縱向不能有兩個(gè)皇后)

2)y=col(橫向)

3)col + row = y+x;(斜向正方向)

4)col - row = y-x;(斜向反方向)

遇到上述問(wèn)題之一的時(shí)候,說(shuō)明我們已經(jīng)遇到了障礙,不能繼續(xù)向前了。我們需要退回來(lái),嘗試其他路徑。

我們將棋盤看作是一個(gè)8*8的數(shù)組,這樣可以使用一種蠻干的思路去解決這個(gè)問(wèn)題,這樣我們就是在8*8=64個(gè)格子中取出8個(gè)的組合,C(64,80) = 4426165368,顯然這個(gè)數(shù)非常大,在蠻干的基礎(chǔ)上我們可以增加回溯,從第0列開(kāi)始,我們逐列進(jìn)行,從第0行到第7行找到一個(gè)不受任何已經(jīng)現(xiàn)有皇后攻擊的位置,而第五列,我們會(huì)發(fā)現(xiàn)找不到皇后的安全位置了,前面四列的擺放如下:

http://img.jbzj.com/file_images/article/201606/201606151029092.png

第五列的時(shí)候,擺放任何行都會(huì)上圖所示已經(jīng)存在的皇后的攻擊,這時(shí)候我們認(rèn)為我們撞了南墻了,是回頭的時(shí)候了,我們后退一列,將原來(lái)擺放在第四列的皇后(3,4)拿走,從(3,4)這個(gè)位置開(kāi)始,我們?cè)俚谒牧兄袑ふ蚁乱粋€(gè)安全位置為(7,4),再繼續(xù)到第五列,發(fā)現(xiàn)第五列仍然沒(méi)有安全位置,回溯到第四列,此時(shí)第四列也是一個(gè)死胡同了,我們?cè)倩厮莸降谌?,這樣前進(jìn)幾步,回退一步,最終直到在第8列上找到一個(gè)安全位置(成功)或者第一列已經(jīng)是死胡同,但是第8列仍然沒(méi)有找到安全位置為止

總結(jié)一下,用回溯的方法解決8皇后問(wèn)題的步驟為:

1)從第一列開(kāi)始,為皇后找到安全位置,然后跳到下一列

2)如果在第n列出現(xiàn)死胡同,如果該列為第一列,棋局失敗,否則后退到上一列,在進(jìn)行回溯

3)如果在第8列上找到了安全位置,則棋局成功。

8個(gè)皇后都找到了安全位置代表棋局的成功,用一個(gè)長(zhǎng)度為8的整數(shù)數(shù)組queenList代表成功擺放的8個(gè)皇后,數(shù)組索引代表棋盤的col向量,而數(shù)組的值為棋盤的row向

量,所以(row,col)的皇后可以表示為(queenList[col],col),如上圖中的幾個(gè)皇后可表示為:

queenList[0] = 0;  queenList[1] = 3;   queenList[2] = 1;  queenList[3] = 4;   queenList = 2;

我們看一下如何設(shè)計(jì)程序:

首先判斷(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;
}

設(shè)定一個(gè)函數(shù),用于查找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) //結(jié)束標(biāo)志
 {
  //當(dāng)處理完第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;
}

調(diào)用方法:

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列后的皇后的安全擺放位置,如果該函數(shù)返回了false,表示當(dāng)前進(jìn)入了死胡同,需要進(jìn)行回溯,直到為0-7列都找

到了安全位置或者找遍這些列都找不到安全位置的時(shí)候終止。

用遞歸算法解決8皇后問(wèn)題的示例程序:

http://xiazai.jb51.net/201606/yuanma/EightQueens(jb51.net).rar

相關(guān)文章

  • unity自定義彈出框功能

    unity自定義彈出框功能

    這篇文章主要為大家詳細(xì)介紹了unity自定義彈出框功能,文中示例代碼介紹的非常詳細(xì),具有一定的參考價(jià)值,感興趣的小伙伴們可以參考一下
    2019-11-11
  • .NET企業(yè)級(jí)項(xiàng)目中遇到的國(guó)際化問(wèn)題和解決方法

    .NET企業(yè)級(jí)項(xiàng)目中遇到的國(guó)際化問(wèn)題和解決方法

    這篇文章主要介紹了.NET企業(yè)級(jí)項(xiàng)目中遇到的國(guó)際化問(wèn)題和解決方法,說(shuō)明了理國(guó)際化問(wèn)題的一些典型例子和經(jīng)驗(yàn)之談,需要的朋友可以參考下
    2014-07-07
  • C#_SqlDependency的使用詳解

    C#_SqlDependency的使用詳解

    SqlDependency對(duì)象表示應(yīng)用程序和 SQL Server 實(shí)例間的查詢通知依賴關(guān)系,這篇文章主要介紹了C#_SqlDependency的使用,需要的朋友可以參考下
    2023-06-06
  • C# Winfom 中ListBox的簡(jiǎn)單用法詳解

    C# Winfom 中ListBox的簡(jiǎn)單用法詳解

    這篇文章主要介紹了C# Winfom 中ListBox的簡(jiǎn)單用法詳解,文中通過(guò)示例代碼介紹的非常詳細(xì),對(duì)大家的學(xué)習(xí)或者工作具有一定的參考學(xué)習(xí)價(jià)值,需要的朋友們下面隨著小編來(lái)一起學(xué)習(xí)學(xué)習(xí)吧
    2019-12-12
  • C#使用泛型實(shí)現(xiàn)刪除數(shù)組中重復(fù)元素

    C#使用泛型實(shí)現(xiàn)刪除數(shù)組中重復(fù)元素

    這篇文章主要為大家詳細(xì)介紹了C#如何使用泛型實(shí)現(xiàn)刪除數(shù)組中重復(fù)元素,文中的示例代碼講解詳細(xì),感興趣的小伙伴可以跟隨小編一起學(xué)習(xí)一下
    2024-02-02
  • C# 設(shè)計(jì)模式系列教程-裝飾模式

    C# 設(shè)計(jì)模式系列教程-裝飾模式

    每個(gè)裝飾對(duì)象只關(guān)心自己的功能,不需要關(guān)心如何被添加到對(duì)象鏈當(dāng)中。它是由Decorator的SetComponent方法來(lái)實(shí)現(xiàn)的,因而它們的職責(zé)是單一的。
    2016-06-06
  • C#實(shí)現(xiàn)的ZPL條碼打印類完整實(shí)例

    C#實(shí)現(xiàn)的ZPL條碼打印類完整實(shí)例

    這篇文章主要介紹了C#實(shí)現(xiàn)的ZPL條碼打印類,結(jié)合實(shí)例形式詳細(xì)分析了C#實(shí)現(xiàn)條碼打印的原理與使用方法,代碼注釋中備有詳盡的說(shuō)明,便于理解使用,需要的朋友可以參考下
    2016-06-06
  • WCF實(shí)現(xiàn)的計(jì)算器功能實(shí)例

    WCF實(shí)現(xiàn)的計(jì)算器功能實(shí)例

    這篇文章主要介紹了WCF實(shí)現(xiàn)的計(jì)算器功能,結(jié)合具體實(shí)例形式較為詳細(xì)的分析了WCF實(shí)現(xiàn)計(jì)算器功能的具體步驟與相關(guān)操作技巧,需要的朋友可以參考下
    2017-06-06
  • C#調(diào)用易語(yǔ)言寫的Dll文件方法

    C#調(diào)用易語(yǔ)言寫的Dll文件方法

    在本篇內(nèi)容里小編給大家分享的是關(guān)于C#調(diào)用易語(yǔ)言寫的Dll文件的方法內(nèi)容,需要的參考下。
    2018-12-12
  • C#虛函數(shù)用法實(shí)例分析

    C#虛函數(shù)用法實(shí)例分析

    這篇文章主要介紹了C#虛函數(shù)用法,實(shí)例分析了C#中虛函數(shù)的功能與基本使用技巧,需要的朋友可以參考下
    2015-07-07

最新評(píng)論