回溯法(英语:backtracking)是穷尽搜索算法(英语:Brute-force search)中的一种。 回溯法采用试错的思想,它尝试分步的去解决一个问题。在分步解决问题的过程中,当它通过尝试发现现有的分步答案不能得到有效的正确的解答的时候,它将取消上一步甚至是上几步的计算,再通过其它的可能的分步解答再次尝试寻找问题的答案。回溯法通常用最简单的递归方法来实现,在反复重复上述的步骤后可能出现两种情况: * 找到一个可能存在的正确的答案 * 在尝试了所有可能的分步方法后宣告该问题没有答案 在最坏的情况下,回溯法会导致一次复杂度为指数时间的计算。 |
procedure PLACE(k) //如果一个皇后能放在第K行和X(k)列,则返回true,否则返回false。X是一个全程数组,进入此过程时已设置了k个值。ABS(r)过程返回r的绝对值// global X(1:k);integer i,k i←1 while i<k do if X(i)=X(k) or ABS(X(i)-X(k))=ABS(i-k) then return (false) endif i←i+1 repeat return (true) end PLACE |
procedure NQUEENS(n) //此过程使用回溯法求出在一个n*n棋盘上放置n个皇后,使其不能互相攻击的所有可能位置// integer k,n,X(1:n) X(1)←0;k←1 //k是当前行,X(k)是当前行的位置 while k>0 do X(k)←X(k)+1 //移到下一个位置 while X(k)<=n and not PLACE(k) do //此处能放这个皇后吗? X(k)←X(k)+1 repeat if X(k)<=n //找到一个位置// then if k=n //是一个完整的解吗?// then print(X) //是,打印数组// else k←k+1;X(k)←0 //转向下一行// endif else k←k-1 //否则,回溯上一行// endif repeat end NQUEENS |
#include <stdio.h> #include <stdlib.h> #define max 8 int queen[max], sum=0; /* max为棋盘最大坐标 */ void show() /* 输出所有皇后的坐标 */ { int i; printf("("); for(i = 0; i < max; i++) { printf(" %d", queen[i]); } printf(")\n"); sum++; } int PLACE(int n) /* 检查当前列能否放置皇后 */ { int i; for(i = 0; i < n; i++) /* 检查横排和对角线上是否可以放置皇后 */ { if(queen[i] == queen[n] || abs(queen[i] - queen[n]) == (n - i)) { return 1; } } return 0; } void NQUEENS(int n) /* 回溯尝试皇后位置,n为横坐标 */ { int i; for(i = 0; i < max; i++) { queen[n] = i; /* 将皇后摆到当前循环到的位置 */ if(!PLACE(n)) { if(n == max - 1) { show(); /* 如果全部摆好,则输出所有皇后的坐标 */ } else { NQUEENS(n + 1); /* 否则继续摆放下一个皇后 */ } } } } int main() { NQUEENS(0); /* 从横坐标为0开始依次尝试 */ printf("%d", sum); system("pause"); return 0; } |
评论