还剩1页未读,继续阅读
文本内容:
上机实验3八皇后问题【实验目的】1了解回溯算法的思路从一条路往前走,能进则进,不能进则退回来,换一条路再试2通过对八皇后问题的解决,掌握回溯算法的应用【实验内容】在8X8格的国际象棋上摆放8个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法【实验步骤】1算法分析
①数组a、b、c分别用来标记冲突
②数组a代表列冲突,a⑼〜a⑺代表第0列到第7列,如果某列上已经有皇后,则为1,否则为0
③数组b代表主对角线冲突,为b[i-j+7],即b
[0]〜b
[14],如果某条主对角线上已经有皇后,则为1,否则为0
④数组c代表从对角线冲突,为c[i+j],即c⑼〜c
[14],如果某条从对角线上已经有皇后,则为1,否则为02优化算法第一个皇后在1〜4格,最后乘以2,即为总解数3代码实现【参考源代码】#include nstdio.h nstatic charQueen
[8]
[8];static inta
[8];static intb
[15];static intc
[15];static intiQueenNum=0;〃记录总的棋盘状态数void quinti;〃参数i代表行int mainint iLine,iColumn;foriLine=0;iLine8;iLine++〃棋盘初始化,空格为*,放置皇后的地方为@a[iLine]=0;〃列标记初始化,表示无列冲突foriColumn=0;iColumn8;iColumn++Queen[iLine][iColumn]=,*1;foriLine=0;iLine15;iLine++〃主、从对角线标记初始化,表示没有冲突b[iLine]=c[iLine]=0;qu0;return0;void quinti intiColumn;foriColumn=0;iColumn8;iColumn++ifa[iColumn]==0b[i-iColumn+7]==0c[i+iColumn]==0〃如果无冲突Queen[i][iColumn]=,@;〃放皇后a[iColumn]=l;〃标记,下一次该列上不能放皇后b[i-iColumn+7]=1;〃标记,下一次该主对角线上不能放皇后c[i+iColumn]=l;〃标记,下一次该从对角线上不能放皇后ifi7qui+l;〃如果行还没有遍历完,进入下一行else〃否则输出〃输出棋盘状态int iLine,iColumn;printf第%d种状态为:\n,++iQueenNum;foriLine=0;iLine8;iLine++foriColumn=0;iColumn8;iColumn++printf H%c H,Queen[iLine][iColumn];printf\n;printf n\n\n H;〃如果前次的皇后放置导致后面的放置无论如何都不能满足要求,则回溯,重Queen[i][iColumn a[iColumn]=0;b[i-iColumn+7]=0;c[i+iColumn]=0;【运行结果】运行结果如附图3所示附图3上机实验3运行结果【实验总结】通过八皇后问题,了解了回溯算法的思路在问题求解中有些被求解的问题不仅其环境或条件随着时间不断变化,甚至连其求解的目标也随时间变化而变化因此,在问题搜索过程中,如果遇到困难需要回溯搜索,可能要按时间的顺序来搜索,则优先搜索,即回溯到最新发生的事件上通过对八皇后问题的解决,掌握回溯算法在实践中的应用。