求C语言中的回溯法,举一个简单的小例子,说明回溯法的运行过程!

来源:学生作业帮助网 编辑:作业帮 时间:2024/05/13 15:15:03

求C语言中的回溯法,举一个简单的小例子,说明回溯法的运行过程!
求C语言中的回溯法,举一个简单的小例子,说明回溯法的运行过程!

求C语言中的回溯法,举一个简单的小例子,说明回溯法的运行过程!
比如八皇后问题,要在8×8的棋盘上放置8个皇后,使8个皇后不相互攻击,即使所有皇后不能位于同一横行、同一竖行或同一斜行.我们在程序中,首先考虑在第一列放置第一个皇后的情况,有8种放法.接下来考虑在第二行放第二个皇后,也是有8种放法,但是有一些放法是不合法,因为这些方法使第一个皇后和第二个皇后相互攻击了.对于这样一些产生了矛盾的算法,我们必须马上把它和它的解空间子树剪掉,这就是“剪枝”.如果发现在第j列放置第j个皇后的所有情况都会与前面出现矛盾时,那这时候我们要回到第j-1列,考虑换一个位置放第j-1个皇后,这就是回溯.
以上答案,纯粹逐字打出来的.