C#用递归算法解决八皇后问题

时间:2022-02-18 04:28:29

1.引子

  中国有一句古话,叫做“不撞南墙不回头",生动的说明了一个人的固执,有点贬义,但是在软件编程中,这种思路确是一种解决问题最简单的算法,它通过一种类似于蛮干的思路,一步一步地往前走,每走一步都更靠近目标结果一些,直到遇到障碍物,我们才考虑往回走。然后再继续尝试向前。通过这样的波浪式前进方法,最终达到目的地。当然整个过程需要很多往返,这样的前进方式,效率比较低下。

2.适用范围

  适用于那些不存在简明的数学模型以阐明问题的本质,或者存在数学模型,但是难于实现的问题。

3.应用场景

  在8*8国际象棋棋盘上,要求在每一行放置一个皇后,且能做到在竖方向,斜方向都没有冲突。国际象棋的棋盘如下图所示:

C#用递归算法解决八皇后问题

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行找到一个不受任何已经现有皇后攻击的位置,而第五列,我们会发现找不到皇后的安全位置了,前面四列的摆放如下:

C#用递归算法解决八皇后问题

第五列的时候,摆放任何行都会上图所示已经存在的皇后的攻击,这时候我们认为我们撞了南墙了,是回头的时候了,我们后退一列,将原来摆放在第四列的皇后(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)是否是安全位置的算法:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
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列后的皇后摆放方法:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
/// <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;
}

调用方法:

?
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
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皇后问题的示例程序:

eightqueens.rar