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

Programming

No.

481

Name.

swindler

Subject.

Sudoku 풀이 #1

Main Cate.

Java

Sub Cate.

Date.

2008-10-16 09:43

Hit.

3137 (210.182.190.136)

File.

일단 만들던거를 당분간 접을듯 해서.
올려놓고 끝내야겠다.

이것은 대각선 스도쿠
가능한 조합 다 찾아서 답을 찾아내는 프로그램이다.

public class Sudoku {

    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 static void main(String [] args)
    {
        Sudoku sudoku = new Sudoku();

        sudoku.init();

        sudoku.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()
    {
        matrix_init();

        long loopCnt = 0;
        int current_position = 0;    // 현재 위치
        int x,y;    // 현재 위치의 x,y 좌표
        int number = 0;

        do {


            if(current_position>80) {
                System.out.println("find solution 2.");
                break;
            }
            // x,y 좌표 변환
            x = current_position % 9;
            y = current_position / 9;

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

            if(fix[x][y]!=0) {        // 고정된 경우

                matrix[x][y]=fix[x][y];
                current_position++;
                continue;
            }

            number = matrix[x][y]+1;

            if(number>9) {            // 해당 위치의 숫자를 9까지 체크한 경우 이전칸으로 이전
                matrix[x][y]=0;
                current_position=get_before(current_position);
                continue;
            }

            if(number_available(x, y, number)==true) {        // 해당 숫자가 들어갈수 있으면 다음칸으로 진행

                if(current_position==80) {        // 마지막칸이 가능한 경우 ok
                    matrix[x][y]=number;
                    System.out.println("find solution");
                    break;
                }
                if(DEBUG) System.out.println("available ("+x+","+y+") : "+number);
                current_position++;
            }

            matrix[x][y]=number;

            loopCnt++;
            if(loopCnt%100000==0) {
                System.out.println("loopCnt : "+loopCnt);
                print_matrix();
            }


        }while(current_position<MATRIX_SIZE*MATRIX_SIZE);

        /*
        if(current_position >= MATRIX_SIZE*MATRIX_SIZE) {
            System.out.println("No Solution.");
            return;
        }
        */

        print_matrix();
    }

    // 이전 위치를 찾는다.
    public int get_before(int current_position)
    {
        int x,y;

        // x,y 좌표 변환
        do {
            current_position--;
            x = current_position % 9;
            y = current_position / 9;

            if(fix[x][y]==0) break;        // 이전칸이 고정칸이 아니면 반환
                                        // 이전칸이 고정칸이면 그 이전으로 이동

        }while(true) ;

        return current_position;
    }

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

        if(fix[x][y]!=0) {            // 값이 고정되어 있는 경우
            if(fix[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();
    }
}

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


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