C语言：试探算法解决“八皇后”问题

#include <stdio.h>

#define N 4

int solution[N], j, k, count, sols;

int place(int row, int col)

{

  for (j = 0; j <row; j++)

  {

    if (row - j == solution[row] - solution[j] || row + solution[row] == j + solution[j] || solution[j] == solution[row])

      return 0;

  }

  return 1;

}

void backtrack(int row)

{

  count++;

  if (N == row)

  {

    sols++;

    for (k = 0; k <N; k++)

      printf("%d\t", solution[k]);

    printf("\n\n");

  }

  else

  {

    int i;

    for (i = 0; i <N; i++)

    {

      solution[row] = i;

      if (place(row, i))

        backtrack(row + 1);

    }

  }

}

void queens()

{

  backtrack(0);

}

int main(void)

{

  queens();

  printf("总共方案: %d\n", sols);

  getch();

  return 0;

}

算法分析：首先将这个问题简化，设为4x4的棋盘，每行都从0开始，即行数row为0,1,2,3;每列都从0开始，即列数col也为0,1,2,3,第0行的任意一个数都不存在被攻击，对于第一行第二行第三行的数，满足下面三个条件之一都会被攻击：1）、棋盘反斜线上横坐标之差等于纵坐标之；2）、棋盘正斜线上横坐标与纵坐标之和相等；3）、同一列上纵坐标相等；如果该行的所有方格都被攻击，则不会进入下一行。若果进入第三行仍然不存在攻击，则会发生N==row,此时会打印出solution[0],solution[1],solution[2],solution[3]。另外，solution[row]=i的作用是每行逐个将i的值(0,1,2,3)即列的值进行试探，最后得到solution[row],即最终得到solution[0],solution[1],solution[2],solution[3]。

巴特西

C语言：试探算法解决“八皇后”问题

最新文章

热门文章