3-7 数独

Javaアルゴリズムパズル

数独を解きます。

ソース

public final class suudoku{

    class StackDataDef {
        int[][] ValList = {{0,8,0,7,0,1,0,5,0},   //1
                           {0,0,2,0,4,0,9,0,0},   //2
                           {9,3,0,0,0,0,0,7,4},   //3
                           {8,0,0,1,0,4,0,0,6},   //4
                           {0,0,6,0,0,0,1,0,0},   //5
                           {7,0,0,9,0,3,0,0,8},   //6
                           {2,4,0,0,0,0,0,1,5},   //7
                           {0,0,7,0,5,0,3,0,0},   //8
                           {0,5,0,8,0,7,0,4,0},}; //9;
    }

    //スタック
    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<=8;Y++)
                for(int X=0;X<=8;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) {
        suudoku mi = new suudoku();
        mi.main();
    }

    void main() {
        StackClass st = new StackClass();

        StackDataDef willPush = new StackDataDef();

        int X=0; int Y=0;
        while(willPush.ValList[X][Y] !=0){
            if (++Y == 9){
                X++;Y=0;
            }
        }

        for (int i=1;i<=9;i++){ //Start With句
            willPush.ValList[X][Y] = i;
            if (isValid(willPush.ValList,X,Y)) st.push(willPush);
        }

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

            boolean isOK = true;
            //合格経路なら表示
            for (X=0;X<=8;X++)
                for (Y=0;Y<=8;Y++)
                    if (priInfo.ValList[X][Y] == 0)
                        isOK = false;

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

            X=Y=0;

            while(X!= 9 && priInfo.ValList[X][Y] !=0){
                if (++Y == 9){
                    Y=0;X++;
                }
            }

            if (X==9){
                st.push(priInfo);
                continue;
            }

            for (int i=1;i<=9;i++){ //connect by句
                priInfo.ValList[X][Y] = i;
                if (isValid(priInfo.ValList,X,Y)){
                    st.push(priInfo);
                }
            }
        }
    }

    private boolean isValid(int[][] ValList,int X,int Y){
        int[] counter = new int[10];
        //縦チェック
        for (int LoopY=0;LoopY<=8;LoopY++)
            counter[ValList[X][LoopY]]++;
        for (int i=1;i<=9;i++)
            if (counter[i] >=2) return false;

        //横チェック
        counter = new int[10];
        for (int LoopX=0;LoopX<=8;LoopX++)
            counter[ValList[LoopX][Y]]++;
        for (int i=1;i<=9;i++)
            if (counter[i] >=2) return false;

        //正方形チェック
        counter = new int[10];
        for (int LoopY=Y/3*3;LoopY<=Y/3*3+2;LoopY++)
            for (int LoopX=X/3*3;LoopX<=X/3*3+2;LoopX++)
                counter[ValList[LoopX][LoopY]]++;
        for (int i=1;i<=9;i++)
            if (counter[i] >=2) return false;

        return true;
    }
}

実行結果

解1
6,8,4,7,9,1,2,5,3,
5,7,2,3,4,8,9,6,1,
9,3,1,5,2,6,8,7,4,
8,2,3,1,7,4,5,9,6,
4,9,6,2,8,5,1,3,7,
7,1,5,9,6,3,4,2,8,
2,4,8,6,3,9,7,1,5,
1,6,7,4,5,2,3,8,9,
3,5,9,8,1,7,6,4,2,