n皇后问题

qiyeu 贡献于2012-09-16

作者 yueshiqiang  创建于2012-05-24 14:19:00   修改者yueshiqiang  修改于2012-05-25 06:25:00字数3167

文档摘要:N皇后问题在国际象棋中,皇后的势力范围包括上、下、左、右、左上、左下、右上、右下八个方向。N皇后问题就是求在一个N*N的棋盘中放置N个皇后的解法。首先,讨论4x4棋盘中如何放置4个皇后,从中探讨出解决N皇后问题的规则假设有4x4棋盘如下:01231、(0,0
关键词:

N皇后问题 在国际象棋中,皇后的势力范围 包括 上、下、左 、右、左上、左下、右上、右下八个方向。N皇后问题就是求在一个N*N的棋盘中放置N个皇后的解法。 首先,讨论4x4棋盘中如何放置4个皇后,从中探讨出解决N皇后问题的规则 假设有4x4棋盘如下: 0 1 2 3 1、(0,0)------放置 皇后 2、(1,0)-----放置失败(第一列已有1个皇后) (1,1)-----放置失败(左上角已有1个皇后) (1,2)-----放置 皇后 X X 皇后 3、(2,0)(2,1)(2,2)(2,3)-----放置失败(原因同上) 皇后 皇后 X X X X 4、第三行无法放任何皇后,所以回到(0,0)继续讨论 5、(1,3)------放置成功 皇后 皇后 6、(2,0)-----放置失败 (2,1)-----放置 皇后 皇后 X 皇后 7、(3,0)(3,1)(3,2)(3,3)-------放置失败 皇后 皇后 皇后 X X X X 8、第四行无法放置任何皇后,所以回到(1,3)继续讨论 9、(2,2)(2,3)-----放置失败 皇后 皇后 X X 10、第三行无法放置任何皇后,所以回到起点继续讨论 11、(0,1)-----放置成功 皇后 12、(1,0)(1,1)(1,2)----放置失败 (1,3)------放置成功 皇后 皇后 13(2,0)------放置成功 皇后 皇后 皇后 14、(3,0)(3,1)------失败 (3,2)-----放置成功 皇后 皇后 皇后 皇后 根据以上实例,总结解决该问题的构思: 首先判断传入坐标位置是否可以放置皇后(八个方向是否有其他皇后,有返回false,无返回true)。 假设传入坐标为(X,Y),棋盘大小为NxN 坐标上方:(X,Y-1)到(X,0)是否有其他皇后 坐标下方:(X,Y+1)到(X,N-1)是否有其他皇后 坐标左方:(X-1,Y)到(0,Y)是否有其他皇后 坐标右方:(X+1,Y)到(N-1,Y)是否有其他皇后 坐标左上方:(X-1,Y-1)到(X,0)或(0,Y)是否有其他皇后 坐标右上方:(X+1,Y-1)到(X,0)或(N-1,Y)是否有其他皇后 坐标左下方:(X-1,Y+1)到(X,N-1)或(0,Y)是否有其他皇后 坐标右下方:(X+1,Y+1)到(X,N+1)或(N-1,Y)是否有其他皇后 递归结束的条件:N个皇后都放置成功 递归执行部分:判断传入坐标是否可放置皇后,可以则依次递归放置下一个 详细程序代码: package Queue; public class queue { public static char ChessBoard[][] = new char[8][8]; public static void main(String[] args) { int i,j; for(i = 0;i<8;i++){ for(j =0;j<8;j++){ ChessBoard[i][j] = 'X'; } } N_Queues(0,0,0); System.out.println("The graph of Queues on the ChessBoard"); System.out.println(" 0 1 2 3 4 5 6 7 "); System.out.println(" +---+---+---+---+---+---+---+---+"); for(i = 0 ;i<8;i++){ System.out.print(" "+i+" "); for(j = 0;j<8;j++){ System.out.print("-"+ChessBoard[i][j]+"-|"); } System.out.println(""); System.out.println(" +---+---+---+---+---+---+---+---+"); } } //递归解决N皇后问题 public static int N_Queues(int LocX,int LocY,int Queues){ int i,j; int Result = 0; if(Queues == 8){ return 1; }else if(QueuePlace(LocX,LocY)){ ChessBoard[LocX][LocY] = 'Q'; for(i = 0;i<8;i++){ for(j = 0;j<8;j++){ Result += N_Queues(i, j, Queues+1); if(Result>0){ break; } } } if(Result>0){ return 1; }else{ ChessBoard[LocX][LocY] = 'X'; return 0; } }else return 0; } private static boolean QueuePlace(int LocX, int LocY) { int i,j; if(ChessBoard[LocX][LocY]!='X'){ return false; } for(j = LocY-1;j>=0;j--){ if(ChessBoard[LocX][j] != 'X'){ return false; } } for(j = LocY+1;j<8;j++){ if(ChessBoard[LocX][j]!='X'){ return false; } } for(i = LocX-1;i>=0;i--){ if(ChessBoard[i][LocY]!='X'){ return false; } } for(i = LocX+1;i<8;i++){ if(ChessBoard[i][LocY]!='X'){ return false; } } i = LocX-1; j = LocY-1; while(i>=0 && j>=0){ if(ChessBoard[i--][j--] !='X'){ return false; } } i = LocX+1; j = LocY-1; while(i<8 && j>=0){ if(ChessBoard[i++][j--] !='X'){ return false; } } i = LocX-1; j = LocY+1; while(i>=0&& j<8 ){ if(ChessBoard[i--][j++] !='X'){ return false; } } i = LocX+1; j = LocY+1; while(i<8 && j<8){ if(ChessBoard[i++][j++] !='X'){ return false; } } return true; } } 显示结果为: The graph of Queues on the ChessBoard 0 1 2 3 4 5 6 7 +---+---+---+---+---+---+---+---+ 0 -Q-|-X-|-X-|-X-|-X-|-X-|-X-|-X-| +---+---+---+---+---+---+---+---+ 1 -X-|-X-|-X-|-X-|-Q-|-X-|-X-|-X-| +---+---+---+---+---+---+---+---+ 2 -X-|-X-|-X-|-X-|-X-|-X-|-X-|-Q-| +---+---+---+---+---+---+---+---+ 3 -X-|-X-|-X-|-X-|-X-|-Q-|-X-|-X-| +---+---+---+---+---+---+---+---+ 4 -X-|-X-|-Q-|-X-|-X-|-X-|-X-|-X-| +---+---+---+---+---+---+---+---+ 5 -X-|-X-|-X-|-X-|-X-|-X-|-Q-|-X-| +---+---+---+---+---+---+---+---+ 6 -X-|-Q-|-X-|-X-|-X-|-X-|-X-|-X-| +---+---+---+---+---+---+---+---+ 7 -X-|-X-|-X-|-Q-|-X-|-X-|-X-|-X-| +---+---+---+---+---+---+---+---+ 对于N皇后,递归一条龙 同理可得! 白宇的博客详细介绍了有关八皇后的几种不同算法,有空就去看看。

下载文档到电脑,查找使用更方便

文档的实际排版效果,会与网站的显示效果略有不同!!

需要 3 金币 [ 分享文档获得金币 ] 0 人已下载

下载文档