八皇后问题，是一个古老而著名的问题，是回溯算法的典型例题。

该问题是十九世纪著名的数学家高斯1850年提出：在8X8格的国际象棋上摆放八个皇后，使其不能互相攻击，即任意两个皇后都不能处于同一行、同一列或同一斜线上，问有多少种摆法。 高斯认为有76种方案。1854年在柏林的象棋杂志上不同的作者发表了40种不同的解，后来有人用图论的方法解出92种结果。

计算机发明后，有多种方法可以解决此问题。

 

2010年，在写完中国象棋的核心模块后，当时添加了一个扩展应用模块，N皇后问题。

效果图

算法源码

下面是控制台程序的源码。

/** * 项目名称: FansChineseChess * 版本号：2.0 * 名字：雷文 * 博客: http://FansUnion.cn * CSDN:http://blog.csdn.net/FansUnion * 邮箱: leiwen@FansUnion.cn * QQ：240-370-818 * 版权所有: 2011-2013,leiwen */package cn.fansunion.chinesechess.ext.empress;import java.awt.Point;import java.util.ArrayList;import java.util.List;/** * 求N皇后的所有合法布局 * * 3个约束条件：任何2个棋子都不能占居棋盘上的同一行、或者同一列、或者同一对角线。 * * 棋盘状态的变化情况，可以看作一个N叉树。 * * 求所有合法布局的过程，即为在3个约束条件下先根遍历状态树的过程。 * * 遍历中访问结点的操作为，判断棋谱上是否已经得到一个完整的布局，如果是，则输出该布局； * * 否则依次先根遍历满足约束条件的各棵子树，即首先判断该子树根的布局是否合法，若合法，则 * * 先根遍历该子树，否则减去该子树分支。 * * @author leiwen@fansunion.cn,http://FansUnion.cn, *         http://blog.csdn.net/FansUnion * @since 2.0 */public class EmpressModel {    /**     * 皇后的个数     */    private int num;    /**     * 棋盘数据结构     */    private int[][] array;    /**     * 棋盘中的布局集合，每一种布局采用简写形式     */    private List
    
     
      > lists = new ArrayList
      
       
        >();    /**     * 棋盘中的布局集合，每一种布局采用完整形式     */    private List
        
          advancedLists = new ArrayList     public EmpressModel(int n) {        this.num = n;        array = new int[n + 1][n + 1];// 默认为0    }    // 初始化所有的布局    public void initAllLayout() {        trial(1);        sort();        initAdvancedLists();    }    /**     * 进入本函数时，在n*n棋盘前j-1列已经放置了满足3个条件的j-1个棋子     *     * 现在从第j列起，继续为后续棋子选择合适的位置     *     * 选择列优先，是为了保证在GUI显示布局的变化，看起来是，每一行的棋子都是从左向右移动的。     *     * 行优先时，每列棋子，从上向下移动。     *     * @param j     */    private void trial(int j) {        // 进入本函数时，在n*n棋盘前j-1列已经放置了满足3个条件的j-1个棋子        // 现在从第i行起，继续为后续棋子选择合适的位置        if (j > num) {            // 求得一个合法布局，保存起来            saveCurrentLayout();        } else {            for (int i = 1; i <= num; i++) {                // 在第i行第j列放置一个棋子                array[i][j] = 1;                if (isLegal(i, j)) {                    trial(j + 1);                }                // 移走第i行第j列的棋子                array[i][j] = 0;            }        }    }    /**     * 判断当前布局是否合法     *     * @return     */    private boolean isLegal(int row, int col) {        for (int i = 1; i < array.length; i++) {            int sumI = 0;// 第i行之和            int sumJ = 0;// 第i列之和            for (int j = 1; j < array[i].length; j++) {                sumI += array[i][j];                sumJ += array[j][i];            }            if (sumI >= 2 || sumJ >= 2) {                return false;            }            sumI = 0;            sumJ = 0;        }        // 左上到右下的对角线是否有棋子        int i = row - 1;        for (int j = col - 1; j >= 1; j--) {            if (i >= 1 && array[i][j] == 1) {                return false;            }            i--;        }        // 左下到右上的对角线是否有棋子        i = row + 1;        for (int j = col - 1; j >= 1; j--) {            if (i <= this.num && array[i][j] == 1) {                return false;            }            i++;        }        return true;    }    /**     * 保存当前的布局     */    private void saveCurrentLayout() {        ArrayList
         
           list = new ArrayList
          
           (); for (int i = 1; i < array.length; i++) { for (int j = 1; j < array[i].length; j++) { if (array[i][j] == 1) { list.add(new Point(i, j)); } } } lists.add(list); } /** * 打印所有的布局（最简形式） */ public void printBasicLayout() { int size = lists.size(); for (int i = 0; i < size; i++) { ArrayList
           
             arrayList = lists.get(i); int size2 = arrayList.size(); System.out.println("第" + i + "种布局！"); for (int j = 0; j < size2; j++) { Point point = arrayList.get(j); System.out.print("(" + (int) point.getX() + "," + (int) point.getY() + ")\t"); } System.out.println(); } System.out.println(); } /** * 打印所有的布局（高级形式） */ public void printAddvancedLayout() { int size = advancedLists.size(); for (int i = 0; i < size; i++) { int[][] arr = advancedLists.get(i); System.out.println("第" + i + "种布局！"); for (int j = 1; j <= num; j++) { for (int k = 1; k <= num; k++) { System.out.print(arr[j][k] + "\t"); } System.out.println(); } System.out.println(); } System.out.println(); } /** * 排序是为了，减少抖动，即每次变换布局时，近可能少地换棋子 （每次切换到下一个布局时，棋子的变换尽可能少，视觉上棋子在有规律的移动） */ public void sort() { sortEveryList(); } private void sortEveryList() { /* * System.out.println("冒泡排序之前："); printAllLayout(); */ int size = lists.size(); // 对lists中的每个链表，按照点的纵坐标排序 for (int q = 0; q < size; q++) { ArrayList
            
              arraylist = lists.get(q); int size2 = arraylist.size(); // 冒泡排序 for (int r = 1; r < size2; r++) { // 纵坐标从小到大 for (int s = 0; s < size2 - r; s++) { Point first = arraylist.get(s); double m = first.getY(); Point second = arraylist.get(s + 1); double n = second.getY(); if (m > n) { arraylist.set(s + 1, first); arraylist.set(s, second); } } } } } private void initAdvancedLists() { int size = lists.size(); for (int index = 0; index < size; index++) { ArrayList
             
               list = lists.get(index); int[][] arr = new int[num + 1][num + 1]; int len = list.size(); for (int i = 0; i < len; i++) { int x = (int) list.get(i).getY(); int y = (int) list.get(i).getX(); arr[x][y] = 1; } advancedLists.add(arr); } } public int[][] getArray() { return array; } public int getNum() { return num; } public List
              
               
                > getLists() { return lists; } public List
                
                  getAdvancedLists() { return advancedLists; } public static void main(String[] args) { EmpressModel em4 = new EmpressModel(4); em4.initAllLayout(); em4.printBasicLayout(); // 初始化高级保存需要的布局 //em4.initAdvancedLists(); em4.printAddvancedLayout(); }}
                
               
              
             
            
           
          
         
        
       
      
     
    

 

设计思想

算法(模型)和界面相分离。

算法构造数据，界面展示数据。

展示分2种：中国象棋棋盘中和控制台中。

源码出处

本算法源码摘自

中国象棋程序-源码，扩展应用模块--N皇后

原文参见：