C语言基于回溯算法解决八皇后问题的方法

时间:2022-06-25 02:36:55

本文实例讲述了C语言基于回溯算法解决八皇后问题的方法。分享给大家供大家参考,具体如下:

问题描述:

八皇后问题,是一个古老而著名的问题,是回溯算法的典型案例:在8X8格的国际象棋棋盘上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

问题求解:

采用回溯算法,即从第一行开始,依次探查可以放置皇后的位置,若找到,则放置皇后,开始探查下一行;若该行没有位置可以放置皇后,则回溯至上一行,清除该行放置皇后的信息,从该行原本放置皇后的下一个位置开始探查可以放置皇后的位置。求所有解时,每找到一组解,就清除这一组解最后一个皇后的位置信息,开始探查该行另外一个可以放置皇后的位置,依次回溯求解。

存储结构:

一维数组:col[8]:存放第i列有无皇后的标记信息
一维数组:left[15]:存放每一条左斜线上的有无皇后的标记信息
一维数组:right[15]:存放每一条右直线上有无皇后的标记信息
一维数组:Q[8]:存放第i行的皇后的列下标

代码实现:

?
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
46
47
48
49
50
51
52
53
54
55
56
#include<stdio.h>
#define N 8
int col[N] = { 0 };
int right[2 * N - 1] = { 0 };
int left[2 * N - 1] = { 0 };
int Q[N];
int cnt = 0;
void Print()
{
  int i;
  for (i = 0; i < N; i++)
  {
    for (int j = 0; j < N; j++)
    {
      if (Q[i] == j)
        printf("■");
      else
        printf("□");
    }
    printf("\n");
  }
  printf("==========================\n");
  cnt++;
}
void Queen(int i)
{
  int j;
  for (j = 0; j < N; j++)
  {
    if ((!col[j]) && (!left[i + j]) && (!right[7 + i - j]))
    {
      Q[i] = j;//放皇后
      col[j] = 1;
      left[i + j] = 1;
      right[N - 1 + i - j] = 1;//已有皇后的标记
      if (i < N - 1)
      {
        Queen(i + 1);
      }
      else
      {
        Print();
      }
      col[j] = 0;
      right[N - 1 + i - j] = 0;
      left[i + j] = 0;//清除标记,查找下一组解
    }
  }
}
int main(void)
{
  Queen(0);
  printf("%d", cnt);
  getchar();
  return 0;
}

运行结果:

一共92组解,前面结果略去。。

C语言基于回溯算法解决八皇后问题的方法

希望本文所述对大家C语言程序设计有所帮助。

原文链接:https://blog.csdn.net/panda_m/article/details/42616981