3-5 8王妃問題

Javaアルゴリズムパズル

Eight queens puzzleを解きます。

ソース

public final class hatiouhi{

    class StackDataDef {
        int[][] ValList = new int[8][8];
    }

    //スタック
    class StackClass {
        int stackP;
        StackDataDef stackData[];

        StackClass(){
            stackP = 0;
            stackData = new StackDataDef[99999];
        }

        private void push(StackDataDef pushData){
            stackData[stackP] = new StackDataDef();

            for(int Y=0;Y<=7;Y++)
                for(int X=0;X<=7;X++)
                    stackData[stackP].ValList[X][Y] = pushData.ValList[X][Y];
            stackP++;
        }

        private StackDataDef pop(){
            return stackData[--stackP];
        }
        boolean isEmpty(){ return stackP == 0; }
    }

    public static void main(String[] args) {
        hatiouhi mi = new hatiouhi();
        mi.main();
    }

    void main() {
        StackClass st = new StackClass();
        StackDataDef willPush = new StackDataDef();
        int X;int Y;

        for (Y=0;Y<=7;Y++){ //Start With句
            willPush.ValList[0][Y] = 1;
            st.push(willPush);
            willPush.ValList[0][Y] = 0;
        }

        int ansCnt=0;
        while (st.isEmpty() == false){
            StackDataDef priInfo = st.pop();

            int queenCnt = 0;
            //合格経路なら表示
            for (X=0;X<=7;X++)
                for (Y=0;Y<=7;Y++)
                    if (priInfo.ValList[X][Y] == 1)
                        queenCnt++;

            if (queenCnt == 8){
                System.out.println("解" + Integer.toString(++ansCnt));
                String willOut ="";
                for(X=0;X<=7;X++){
                    for(Y=0;Y<=7;Y++){
                        willOut += priInfo.ValList[X][Y] + ",";
                    }
                    System.out.println(willOut); willOut="";
                }
                continue;
            }

            for (Y=0;Y<=7;Y++){ //connect by句
                priInfo.ValList[queenCnt][Y] = 1;
                if (isValid(priInfo.ValList,queenCnt,Y)){
                    st.push(priInfo);
                }
                priInfo.ValList[queenCnt][Y] = 0;
            }
        }
    }

    private boolean isValid(int[][] ValList,int X,int Y){
        int counter = 0;int LoopX;int LoopY;

        //横チェック
        for (LoopX=0;LoopX<=X;LoopX++) counter+= ValList[LoopX][Y];
        if (counter >=2) return false;

        //左下チェック
        counter = 0;
        for (LoopX=X,LoopY=Y;
             0 <= LoopX && LoopX <= 7 &&
             0 <= LoopY && LoopY <= 7;
             LoopX--,LoopY++) counter+= ValList[LoopX][LoopY];
        if (counter >=2) return false;

        //左上チェック
        counter = 0;
        for (LoopX=X,LoopY=Y;
             0 <= LoopX && LoopX <= 7 &&
             0 <= LoopY && LoopY <= 7;
             LoopX--,LoopY--) counter+= ValList[LoopX][LoopY];
        if (counter >=2) return false;

        return true;
    }
}

実行結果

解1
0,0,0,0,0,0,0,1,
0,0,0,1,0,0,0,0,
1,0,0,0,0,0,0,0,
0,0,1,0,0,0,0,0,
0,0,0,0,0,1,0,0,
0,1,0,0,0,0,0,0,
0,0,0,0,0,0,1,0,
0,0,0,0,1,0,0,0,
解2
0,0,0,0,0,0,0,1,
0,0,1,0,0,0,0,0,
1,0,0,0,0,0,0,0,
0,0,0,0,0,1,0,0,
0,1,0,0,0,0,0,0,
0,0,0,0,1,0,0,0,
0,0,0,0,0,0,1,0,
0,0,0,1,0,0,0,0,
以下略