今天我用代码实现了一个八皇后的问题，我所用的策略是将在一个皇后先放在a1位置上然后用一个数组将棋盘上其他皇后还能放的位置标记下，然后在b纵列上放皇后，如果此位置能放皇后将此位置记住，进入下一层放第3个皇后，如果第三层没有位置不能方皇后，那么返回上一层，将这一层的当前放皇后的位置设为可放置，然后以同样地方法探索b2位置可放皇后吗？以这样的方法类推直到找出所有可能的位置。当我写完程序时，发现这个程序很繁琐，而且循环很多，大括号很容易弄错，我想问一下有什么效率更优的策略吗?请大神指点。

1. import java.util.*;
   
2. /*
   
3. * 8皇后问题
   
4. *  步骤：
   
5. *      1. 用二维数组表示棋盘，i行j列为0，表示未放置皇后，为1表示已放置皇后
   
6. *      2. 对每一行，遍历各列，尝试放置皇后
   
7. *      3. 第i行j列放置完毕，递归放置之后的行列
   
8. *      4. 如果8行全部放置好皇后，输出这种摆法
   
9. *
   
10. */
    
11. public class EightQueens {
    
12.     public static final int QUEENS = 8;
    
13.     public static void main(String[] args) {
    
14.         // 棋盘定义为8行8列的二维数组
    
15.         // 如果i行j列没有放置皇后，a[i][j] = 0;否则a[i][j]=1
    
16.         int[][] board = int[QUEENS][QUEENS];
    
17.         Arrays.fill(board, 0);
    
18. 
    
19.         fillBoard(board, 0);
    
20. 
    
21. 
    
22.     }
    
23. 
    
24.     // fillBoard: 在棋盘board的第row行放置皇后
    
25.     public static void fillBoard(int[][] board, int row) {
    
26.         // 如果已放置的皇后数达到要求，则输出当前的棋盘状况
    
27.         if (row == QUEENS - 1)
    
28.             printBoard(board, QUEENS);
    
29. 
    
30.         // 从列0到列8之中选一列放置皇后
    
31.         for (int col = 0; col < QUEENS; i++) {
    
32.             // 如果row行col列放置皇后与之前的皇后不冲突
    
33.             if (canPlace(board, row, col) {
    
34.                 // 在row行col列放置皇后
    
35.                 board[row][col] = 1;
    
36.     // 递归，以当前棋盘状况为基础，遍历row+1行到第8行放置皇后的所有方法
    
37.                 fillBoard(board, row + 1);
    
38.                 // 取消col列放置的皇后，继续for循环，准备在col+1列放置皇后
    
39.                 board[row][col] = 0;
    
40.             }
    
41.         }
    
42.     }
    
43. 
    
44.     // canPlace: 能否在row行col列放置皇后
    
45.     public static boolean canPlace(int[][] board, int row, int col) {
    
46.         // 从row-1行开始，检测每一行的皇后是否与row行col列的皇后冲突
    
47.         for (int i = row - 1, colOffset = 1; i >= 0; i--, colOffset++) {
    
48.             int aboveLeft = col - colOffset; // 左上对角线
    
49.             int aboveRight = col + colOffset; // 右上对角线
    
50. 
    
51.             if (board[i][col] == 1 // 不能与之前的皇后同列
    
52.                     ||
    
53.                 // 左上对角线不能有皇后
    
54.                 aboveLeft >= 0 && board[i][aboveLeft] == 1
    
55.                     ||
    
56.                 // 右上对角线不能有皇后
    
57.                 aboveRight < QUEENS && board[i][aboveRight] == 1)
    
58.                 return false;
    
59.         }
    
60.         return true;
    
61.     }
    
62. 
    
63.     // printBoard: 打印出八皇后在棋盘上的每一种摆法
    
64.     public static void printBoard(int[][] board, int size) {
    
65.         for (int i = 0; i < size; i++)
    
66.         {
    
67.             for (int j = 0; j < size; j++)
    
68.                 System.out.print(board[i][j] + " ");
    
69.             System.out.println();
    
70.         }
    
71.     }
    
72. 
    
73. }
    

复制代码

fantacyleo 发表于 2014-8-1 23:08

我选用的策略和你差不多，由于我忽略了用递归，造成的我程序的复杂，除了这种策略外还有其他策略吗？

Moriarty 发表于 2014-8-1 23:31
我选用的策略和你差不多，由于我忽略了用递归，造成的我程序的复杂，除了这种策略外还有其他策略吗？ ...

百度了一下，似乎没有。我想可能需要找一些CS的paper来看了。。。

我明白了谢谢。