김효원, Swindler, coolx 님의 홈페이지

Programming

No.

483

Name.

swindler

Subject.

Sudoku 풀이 #3

Main Cate.

Java

Sub Cate.

Date.

2008-10-16 09:45

Hit.

2793 (210.182.190.136)

File.

이것은 사람이 푸는것처럼 풀려고 만들었는데,
step2인가 거기 만들다 중단했음.
현재 상태는 기본값들만 찾다보니
전체 해결책을 못 찾을 수 있는 상태임.

import java.util.ArrayList;

public class HumanSudoku {

    public static boolean DEBUG = false;
    public static int MATRIX_SIZE = 9;        // matrix 크기
    public int[][] fix = new int[MATRIX_SIZE][MATRIX_SIZE];        // 고정된 값
    public int[][] matrix= new int[MATRIX_SIZE][MATRIX_SIZE];    // 계산용 matrix

    public XYList xyList = new XYList();        // 들어갈수 없는 숫자에 대한 정보

    public static void main(String [] args)
    {
        HumanSudoku hsudoku = new HumanSudoku();

        hsudoku.init();

        hsudoku.find();
    }

    public void init()
    {
        // 6122
        /*
        fix[0][0] = 1;
        fix[8][0] = 9;

        fix[2][1] = 5;
        fix[5][1] = 1;

        fix[7][2] = 8;

        fix[1][3] = 7;
        fix[4][3] = 4;

        fix[3][4] = 3;
        fix[5][4] = 8;

        fix[4][5] = 6;
        fix[7][5] = 2;

        fix[1][6] = 2;

        fix[3][7] = 8;
        fix[6][7] = 6;

        fix[0][8] = 7;
        fix[8][8] = 5;
        */


        // 6121
        fix[8][0] = 7;

        fix[2][1] = 3;
        fix[8][1] = 9;

        fix[2][2] = 6;
        fix[3][2] = 5;

        fix[1][3] = 5;
        fix[4][3] = 4;

        fix[1][4] = 8;
        fix[7][4] = 9;

        fix[4][5] = 1;
        fix[7][5] = 4;

        fix[5][6] = 7;
        fix[6][6] = 4;

        fix[0][7] = 3;
        fix[6][7] = 7;

        fix[0][8] = 8;
        // */



    }

    public void matrix_init()
    {
        for(int i=0; i<MATRIX_SIZE; i++) {

            for(int j=0; j<MATRIX_SIZE; j++) {

                matrix[i][j]=fix[i][j];
            }
        }
    }

    public void find()
    {
        DrawSudoku d = new DrawSudoku(matrix);
        d.draw();


        matrix_init();

        print_matrix();

        int match_count=0;
        int match = 0;
        int pos = 0;

        do {

            match_count=0;

            // 가로줄 검색
            for(int i=0; i<MATRIX_SIZE; i++) {

                for(int num=1; num<=MATRIX_SIZE; num++) {

                    match = 0;
                    for(int j=0; j<MATRIX_SIZE; j++) {

                        if(number_available(j,i,num)==true && matrix[j][i]!=num) {
                            pos = j;
                            match++;
                        }
                    }

                    if(match==1) {
                        match_count++;
                        System.out.print("find 가로줄 ");
                        System.out.println("("+pos+","+i+") : "+num);

                        matrix[pos][i]=num;
                    }
                }
            }


            // 세로줄 검색
            for(int i=0; i<MATRIX_SIZE; i++) {

                for(int num=1; num<=MATRIX_SIZE; num++) {

                    match = 0;
                    for(int j=0; j<MATRIX_SIZE; j++) {


                        if(number_available(i,j,num)==true && matrix[i][j]!=num){
                            pos = j;
                            match++;
                        }
                    }

                    if(match==1) {
                        match_count++;
                        System.out.print("find 세로줄 ");
                        System.out.println("("+i+","+pos+") : "+num);

                        matrix[i][pos]=num;
                    }
                }
            }

            // 대각선 검색 (우하향)
            for(int num=1; num<=MATRIX_SIZE; num++) {

                match = 0;
                for(int i=0; i<MATRIX_SIZE; i++) {

                    if(number_available(i,i,num)==true && matrix[i][i]!=num){
                        pos = i;
                        match++;
                    }

                }

                if(match==1) {
                    match_count++;
                    System.out.print("find 우하향 ");
                    System.out.println("("+pos+","+pos+") : "+num);

                    matrix[pos][pos]=num;
                }
            }

            // 대각선 검색 (우상향)
            for(int num=1; num<=MATRIX_SIZE; num++) {

                match = 0;
                for(int i=0; i<MATRIX_SIZE; i++) {

                    if(number_available(i,MATRIX_SIZE-i-1,num)==true && matrix[i][MATRIX_SIZE-i-1]!=num){
                        pos = i;
                        match++;
                    }

                }

                if(match==1) {
                    match_count++;
                    System.out.print("find 우상향 ");
                    System.out.println("("+pos+","+(MATRIX_SIZE-pos-1)+") : "+num);

                    matrix[pos][MATRIX_SIZE-pos-1]=num;
                }
            }

            // 작은 박스 검색
            int x,y;
            for(int i=0; i<MATRIX_SIZE; i++) {

                // 시작좌표 계산
                x = (i%3)*3;
                y = (i/3)*3;


                for(int num=1; num<=MATRIX_SIZE; num++) {

                    match = 0;
                    for(int j=0; j<MATRIX_SIZE; j++) {

                        if(number_available(x+(j%3),y+(j/3),num)==true && matrix[x+(j%3)][y+(j/3)]!=num){
                            pos = j;
                            match++;
                        }
                    }

                    if(match==1) {
                        match_count++;
                        System.out.print("find 소박스("+i+") ");
                        System.out.println("("+(x+(pos%3))+","+(y+(pos/3))+") : "+num);

                        matrix[x+(pos%3)][y+(pos/3)]=num;
                    }
                }

            }


            System.out.println("\nmatch count : "+match_count);
            print_matrix();

            if(match_count==0)
                match_count=find_step2();

        }while(match_count>0);

        // 완료여부 출력
        if(is_end()==true)
            System.out.println("======== Success =======");
        else
            System.out.println("======== Fail =======");

        print_matrix();
    }

    /*
     * 2단계로 매칭을 시도하고 매칭된 갯수를 반환한다.
     * 매칭된게 하나도 없으면 0을 반환
     */
    public int find_step2()
    {
        int match_count=0;

        boolean is_exist = false;
        int aval_count = 0 ;
        int x=0;
        int y=0;

        for(int num=1; num<=MATRIX_SIZE; num++) {

            is_exist=false;
            aval_count = 0;

            // 이미 숫자가 있는지 확인
            for(int i=0; i<9; i++){
                for(int j=0; j<9; j++) {

                    if(matrix[i][j]==num)
                        is_exist = true;

                    // 빈칸인데 숫자가 들어갈수 없으면 저장
                    if(matrix[i][j]==0 & number_available(i, j, num)==false){
                        xyList.add(i,j,num);
                    }
                }
            }

            if(is_exist==true)
                continue;
        }


        xyList.print();

        return match_count;
    }

    // 해당 라인에 숫자가 이미 있는지 체크
    public boolean number_exist(int x, int y, int num)
    {
        for(int i=0; i<MATRIX_SIZE; i++) {

            if(x==-1 && matrix[i][y]==num)        // 가로줄 검색
                return true;

            if(y==-1 && matrix[x][i]==num)        // 세로줄 검색
                return true;

            if(x!=-1 && y!=-1 && matrix[x][y]==num)    // 대각선 검색
                return true;
        }

        return false;
    }

    // 해당 위치에 그 숫자가 들어갈수 있는지 판단
    public boolean number_available(int x, int y, int number)
    {

        if(matrix[x][y]!=0) {            // 값이 고정되어 있는 경우
            if(matrix[x][y]==number)    // 고정된 값과 같으면 true
                return true;
            else                    // 고정된 값과 다르면 false
                return false;
        }

        if(DEBUG) System.out.println("(x,y) : ("+x+","+y+")");

        for(int i=0; i<MATRIX_SIZE; i++) {

            if(DEBUG) System.out.println("--("+i+","+y+") : "+matrix[i][y]);
            if(matrix[i][y]==number) {    // 같은 x축에 동일 숫자가 있는지 체크
                if(DEBUG) System.out.println("match 1");
                return false;
            }

            if(matrix[x][i]==number) {    // 같은 y축에 동일 숫자가 있는지 체크
                if(DEBUG) System.out.println("match 2");
                return false;
            }

            if(x==y && matrix[i][i]==number) {    // 대각선에 있는 경우 동일숫자가 있는지 체크
                if(DEBUG) System.out.println("match 3");
                return false;
            }

            if((x+y+1)%9==0 && matrix[MATRIX_SIZE-i-1][i]==number) {    // 대각선에 있는 경우 동일숫자가 있는지 체크
                if(DEBUG) System.out.println("match 4");
                return false;
            }

        }

        // 작은 박스안에 동일숫자가 있는지 체크
        int gx = x/3;
        gx = gx * 3;
        int gy = y/3;
        gy = gy * 3;

        for(int i=0; i<3; i++) {
            for(int j=0; j<3; j++) {

                if(matrix[gx+i][gy+j]==number) {
                    if(DEBUG) System.out.println("match 5");
                    return false;
                }
            }
        }

        return true;

    }

    public void print_matrix()
    {
        for(int i=0; i<MATRIX_SIZE; i++) {

            for(int j=0; j<MATRIX_SIZE; j++) {

                if(matrix[j][i]==0)
                    System.out.print(". ");
                else
                    System.out.print(matrix[j][i]+" ");
            }
            System.out.println();
        }
        System.out.println();
    }

    /*
     * 전부 완료되었는지 여부를 반환한다.
     */
    public boolean is_end()
    {
        for(int i=0; i<MATRIX_SIZE; i++) {
            for(int j=0; j<MATRIX_SIZE; j++) {

                if(matrix[i][j]==0)
                    return false;
            }
        }

        return true;
    }

    public class XYList
    {
        private ArrayList<XY> list = null;


        public XYList()
        {
            list = new ArrayList<XY>();
        }

        public void add(int x, int y, int num)
        {
            list.add(new XY(x,y,num));
        }


        public void print()
        {
            XY xy = null;

            System.out.println("--------- XY List Print --------");
            for(int i=0; i<list.size(); i++) {

                xy = (XY)list.get(i);
                System.out.println("("+xy.getX()+","+xy.getY()+") : "+xy.getNum());
            }

            System.out.println("--------------------------------");
        }

    }


    // 좌표를 저장하는 클래스
    public class XY
    {
        private int x;
        private int y;
        private int num;

        public XY(int x, int y, int num)
        {
            this.x = x;
            this.y = y;
            this.num = num;
        }

        public int getX()
        {
            return x;
        }

        public int getY()
        {
            return y;
        }

        public int getNum()
        {
            return num;
        }
    }
}

[바로가기 링크] : http://coolx.net/cboard/develop/483


[Modify] [Delete]		[Reply] [List]