八皇后问题详细的解法.ppt

1234561.按什么顺序去查找所有的解a.盲目的枚举算法voidmain(){intx[100];for(x[1]=1;x[1]<=10;x[1]++)for(x[2]=1;x[2]<=10;x[2]++)for(x[3]=1;x[3]<=10;x[3]++)for(x[4]=1;x[4]<=10;x[4]++)for(x[5]=1;x[5]<=10;x[5]++)for(x[6]=1;x[6]<=10;x[6]++)for(x[7]=1;x[7]<=10;x[7]++)for(x[8]=1;x[8]<=10;x[8]++)if(check(x)==0){printf(x);}}该如何解决冲突的问题呢？
1.行；我们是按照行枚举的，保证了一行一个皇后；
2.列：判断是否存在x[i]=x[j]
3.对角线：主对角线的i-j与从对角线的i+j存在特殊关系，如图：
91011121314只要当前枚举到的状态可行，就继续枚举下去。当找到一种方案或者无法继续枚举下去时，就退回到上一状态。退回到上一状态的过程叫做回溯，枚举下一个状态的过程叫做递归。
回溯就是像人走迷宫一样，先选择一个前进方向尝试，一步步试探，在遇到死胡同不能再往前的时候就会退到上一个分支点，另选一个方向尝试，而在前进和回撤的路上都设置一些标记，以便能够正确返回，直到达到目标或者所有的可行方案都已经尝试完为止。

16我们可以依次确定每一行皇后的位置1819202123