回溯法有“通用的解题法“之称。用它可以系统的搜索一个问题的所有解或任一解。会所法是一个既带有系统性又带有跳跃性的搜索算法，他在包含问题的所有解的解空间树中，按照深度有限的策略，从根节点出发搜索解空间树，算法搜索至解空间树的任一节点时，总是先判断该节点是否肯定不包含问题的解。如果肯定不包含，则跳过对该节点为根的子树的系统搜索，逐层向其祖先节点回溯，否则进入该子树，继续按照深度优先的策略进行搜索。回溯法在用来求问题的任一接时，只要搜索到问题的一个解就可以结束。
这种深度优先的解的算法称为回溯法，它适合于解一些组合数较大的问题。

用回溯法解n皇后问题时，可以用一棵完全n叉树来表示其解空间。剪去不满足行列和斜线攻击的子树后，剩下的就是问题的解答。

代码：

package com.sitinspring;

/** *//**
 * 八皇后问题回溯版
 * @author sitinspring（junglesong@gmail.com）
 * @since 2008-7-8 上午10:34:28
 * @vsersion 1.00 创建 sitinspring 2008-7-8 上午10:34:28
 */
public class EightQueenBacktrack{
    // 皇后数量
    private int queenCount;
    
    // 存放皇后纵坐标的数组
    private int[] arr;
    
    /** *//**
     * 构造函数
     * @param queenCount
     */
    public EightQueenBacktrack(int queenCount){
        this.queenCount=queenCount;
        arr=new int[queenCount];
        
        // 从第零个皇后开始放置
        backtrack(0);
    }
    
    /** *//**
     * 显示n皇后在棋盘中位置
     *
     */
    private void displayArr(){
        System.out.println("-------"+queenCount+"------>");
        for(int i=0;i<queenCount;i++){
            for(int j=0;j<queenCount;j++){
                if(arr[i]!=j){
                    System.out.print("■ ");
                }
                else{
                    System.out.print("Q ");
                }
            }
            
            System.out.println();
        }
        System.out.println("<-------"+queenCount+"------");
    }
    
    /** *//**
     * 判断处于第n位的皇后是否与前面的皇后冲突
     * @param n
     * @return
     */
    private boolean isValidPos(int n){
        for(int i=0;i<n;i++){
            // 斜线鉴别和列鉴别。行鉴别无须参与
            if(Math.abs(n-i)==Math.abs(arr[n]-arr[i]) || arr[i]==arr[n]){
                return false;
            }
        }
        
        return true;
    }
    
    /** *//**
     * 回溯依次安放皇后的位置
     * @param column
     */
    private void backtrack(int column){
        if(column==queenCount){    
            // 进入这里表示前面的queenCount个皇后都已经放在了正确的位置
            displayArr();    // 显示皇后    
            return;
        }
        else{
            for(int i=0;i<queenCount;i++){
                // 皇后共有queenCount个位置可选
                arr[column]=i;
                if(isValidPos(column)){
                    // 安放下一个皇后
                    backtrack(column+1);
                }
            }
        }
    }
    
    /** *//**
     * 程序入口
     * @param args
     */
    public static void main(String[] args){
        new EightQueenBacktrack(8);
        
        /**//*for(int i=1;i<20;i++){
            new EightQueenBacktrack(i);
        }*/
    }
}

-------8------>
Q ■ ■ ■ ■ ■ ■ ■ 
■ ■ ■ ■ Q ■ ■ ■ 
■ ■ ■ ■ ■ ■ ■ Q 
■ ■ ■ ■ ■ Q ■ ■ 
■ ■ Q ■ ■ ■ ■ ■ 
■ ■ ■ ■ ■ ■ Q ■ 
■ Q ■ ■ ■ ■ ■ ■ 
■ ■ ■ Q ■ ■ ■ ■ 
<-------8------
-------8------>
Q ■ ■ ■ ■ ■ ■ ■ 
■ ■ ■ ■ ■ Q ■ ■ 
■ ■ ■ ■ ■ ■ ■ Q 
■ ■ Q ■ ■ ■ ■ ■ 
■ ■ ■ ■ ■ ■ Q ■ 
■ ■ ■ Q ■ ■ ■ ■ 
■ Q ■ ■ ■ ■ ■ ■ 
■ ■ ■ ■ Q ■ ■ ■ 
<-------8------
-------8------>
Q ■ ■ ■ ■ ■ ■ ■ 
■ ■ ■ ■ ■ ■ Q ■ 
■ ■ ■ Q ■ ■ ■ ■ 
■ ■ ■ ■ ■