原创

【回溯算法】之 八皇后问题 -- Java实现


八皇后问题:

在一个8x8的棋盘上,放置八颗棋子,每颗棋子的上下左右,对角线上均不能有第二颗棋子,求总共有多少种解法。

 

回溯算法的处理思想:

把问题求解分解为多个阶段,如果某一阶段不符合要求,则退回到上一个阶段,穷举所有的可能解法,以找到满足的解。

我们把这个问题分为八个阶段,每一行看作一个阶段。如果当前行满足放置要求,则进行放置,接着处理下一行,如果当前行不满足放置条件,则选择另外一种方法再次尝试。

 


代码实现:

 

import org.junit.Test;

public class EeightQueen {
    
    int[] states = new int[8];              //下标表示所摆放的行数,值表示列   states[0] = 1  代表第0行第一列摆放棋子
    int count = 0;                              //记录总的摆放次数
    
    @Test
    public void testQueen(){
        putVal(0);
        System.out.println("count: " + count);
    }
    
    public void putVal(int i){
        if(i == 8){
            printQueen(states);
            count++;
            return;
        }
        for(int col=0;col<8;col++){
            if(isOk(i,col)){
                states[i] = col;
                putVal(i+1);
            }
        }
        
    }
    
    
    public boolean isOk(int row, int col){
        int leftUp = col-1,rightUp = col+1;
        row = row - 1;
        while(row >= 0){
            if(states[row] == col){
                return false;
            }
            
            if(leftUp >= 0){
                if(states[row] == leftUp){
                    return false;
                }
            }
            
            if(rightUp <= 7){
                if(states[row] == rightUp){
                    return false;
                }
            }
            row--;
            leftUp--;
            rightUp++;
        }
        
        return true;
    }
    
    public void printQueen(int[] results){
        for(int row=0;row<8;row++){
            for(int col=0;col<8;col++){
                if(results[row] == col){
                    System.out.print("Q ");
                }else{
                    System.out.print("* ");
                }
            }
            System.out.println();
        }
        System.out.println();
    }
    
}

Java