N皇后问题实验报告

1、N皇后问题算法一、实验目的及要求所要涉及或掌握的知识：1. 了解皇后相互攻击的条件：如果任意两个皇后在同一行，同一列或同一对角线，则她们相互攻击。2. 运用迭代的方法实现 6皇后问题，求解得到皇后不相互攻击的一个解。3. 在运用迭代的方法实现编程时，要注意回溯点。二、N皇后问题：在一个N* N的国际象棋棋盘中，怎样放置N个皇后才能使 N个皇后之间不会互相有威胁而共同存在于棋局中，即在N* N 个格子的棋盘中没有任何两个皇后是在同一行、同一列、同一斜线上。三、问题分析最容易想到的方法就是有序地从第1列的第1行开始，尝试放上一个皇后，然后再尝试第2列的第几行能够放上一个皇后，如果第 2列也放置成功

2、，那么就继续放置第3列，如果此时第3列没有一行可以放置一个皇后，说明目前为止的尝试是无效的(即不可能得到最终解)，那么此时就应该回溯到上一步(即第 2步)，将上一步(第2步)所放 置的皇后的位置再重新取走放在另一个符合要求的地方如此尝试性地遍历加上回溯，就可以慢慢地逼近最终解了。四、具体实现package queen;import java.util.Scanner;public class NQueensll public static void main(Stringargs )Scanner in =new Scanner(System. in);System. out .println

3、(Please enter the number of queen youwant(请输入你要求解的皇后的个数);int n=in .nextInt();Queen( n);/* 用回溯法设计函数 Queen(n) 求解 */public static boolean Place( int x, int k) / 考察皇后 k 放置在 xk 列是否发生冲突for ( int i =1; i k; i +)if ( xk=xi |Math. abs( k- i )=Math. abs(xk- xi ) return false ;return true ;public static void Q

4、ueen( int n)int x= new int n+1;for ( int i =1; i =1)x k= x k+1; / 在下一列放置第 k 个皇后while ( x k= n&! Place ( x, k)x k= x k+1; / 搜索下一列if ( xk= n & k=n) / 得到一个解，输出System. out .println( The answer is( 得到的解是 ): ); for ( int i =1; i =n; i +)System. out .print( ( +i +, +x i + ) + ); System. out .println();retu

5、rn ;else if ( x k= n & kn)k=k+1; / 放置下一个皇后elsex k=0; / 重置 xk ，回溯k=k -1;运行结果:Please enter the number of queen you w日rrt (i青尔套求解店的个埶) 5The answer込(得至i的解是)：(1,1) (2.3) (3,5) (4,2) (5,4)Please enter the number of queen you want(i青输入怖要求鯛的皇后的平数) 8The answer is(得到的解是)：(bD (2,5) (3,8) (4,6)(5,3) (6,7)(7,2) 8,4)Please enter the number of queen you wmnt （清输入你要求解的皇后的个数） 10The answer i班潯至怫解是：（1,1） （2,3） （3,6） （4,8） （5,10） （6,5） （7,9） （8,2） （9,4） （10,7）五、总结 回溯法有“通用解题法”之称，用它可以搜索问题的