• 八皇后代码之JAVA修改版

    原代码忘了是在哪里找到的,我只是稍微修改了一点点东西,感觉写的非常不错,里面的注释也不少这里就不说废话了。

    public class q8 {
     private int[] arr = new int[8];//这个数组的元素的值表示皇后的纵坐标,元素的下标表示第几行
     private int x=1;//用来标识每次输出的是第几种方法

     public q8() {//构造方法
      // 从第零个皇后开始放置
      huisu(0);
     }

     private void displayArr() {//显示每一种方法中皇后的放置
      System.out.println(“<—–第”+x+”种方法开始——>”);
      for (int i = 0; i < 8; i++) {
       for (int j = 0; j < 8; j++) {
        if (arr[i] != j) {
         System.out.print(” *”);
        } else {
         System.out.print(” Q”);
        }
       }

       System.out.println();
      }
      System.out.println(“<—–第”+x+++”种方法结束——>”+”\n”);
     }

     private boolean canPutQ(int n) {//该方法判断皇后是否能放置
      for (int i = 0; i < n; i++) {
       
       if ( ((n – i) == Math.abs(arr[n] – arr[i]))// 判断对角线的斜率为1或-1
         || (arr[i] == arr[n])
        )
       {
        return false;
       }
      }

      return true;
     }

     private void huisu(int n) {//回溯
      if (n == 8) {
       displayArr(); // 放置皇后
       return;
      } else {
       for (int i = 0; i < 8; i++) {
        //
        arr[n] = i;
        if (canPutQ(n)) {
         // 放下一个皇后
         huisu(n + 1);
        }
       }
      }
     }

     public static void main(String[] args) {
      new q8();
     }
    }

    >> 什么是八皇后问题

    八皇后问题是一个古老而著名的问题,是回溯算法的典型例题。该问题是十九世纪著名的数学家高斯1850年提出:在8X8格的国际象棋上摆放八个皇后,使其不能互相攻击,即任意两个皇后都不能处于同一行、同一列或同一斜线上,问有多少种摆法。

    高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解,后来有人用图论的方法解出92种结果。

    以上摘自百度百科[地址:http://baike.baidu.com/view/698719.htm]