2580. 스도쿠 (자바, Java)

스도쿠 규칙은 단순한 편인데, 문제는 어떻게 백트래킹으로 구현하느냐 이다.

일단 9x9 배열에 각 숫자를 담고, 하나씩 탐색하다가

빈칸인 0을 만나면 빈칸을 채워주는 알고리즘을 발동한다.

가로, 세로, 그리고 3*3 정사각형에 중복되는 숫자가 있으면 안 되는데, 우리가 탐색하는 빈칸 외에도 다른 빈칸이 있는 경우 중복되는 후보군이 있을 수 있다.

따라서, 일단 그 중 하나 (순서대로 반복문 돌릴경우 작은수부터)를 입력한 후, 중간에 알맞는 빈칸이 없으면 탐색을 중단하고 '이전 지점으로 돌아와서' 다른 값을 입력해줘야한다.

 

처음에 이 부분을 구현하지 않아서, 즉 백트래킹이 아닌 브루트-포스로 풀어서 이 문제를 틀렸다.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[][] sdk;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //스도쿠를 담을 배열
        sdk = new int[9][9];
        StringTokenizer st;

        for (int i=0; i<9; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j=0; j<9; j++) {
                sdk[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                if (sdk[i][j]==0) {
                    for (int k=1; k<=9; k++) {
                        if (search(i, j, k)) {
                            sdk[i][j]=k;
                        }
                    }
                }
            }
        }

        StringBuilder sb = new StringBuilder();
        for (int i=0; i<9; i++) {
            for (int j=0; j<9; j++) {
                sb.append(sdk[i][j]).append(" ");
            }
            sb.append("\n");
        }
        System.out.println(sb);
    }

    

    // 스도쿠의 값을 찾아 입력가능한지를 판단하는 method
    static boolean search(int x, int y, int value) {

        for (int i=0; i<9; i++) {
            // 같은 열에서 숫자가 반복되면 안 된다.
            if (sdk[i][y]==value) {
                return false;
            }
            // 같은 행에서 숫자가 반복되면 안 된다.
            else if (sdk[x][i]==value) {
                return false;
            }
        }

        // 3*3 정사각형을 따질때 필요한 수들 (반복문에 들어가면 반복하므로, 여기서 미리 만들어줌)
        int a = x/3*3;
        int b = y/3*3;

        // 3x3 정사각형 안에서도 숫자가 반복되면 안된다.
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                if (sdk[a+i][b+j]==value) {
                    return false;
                }
            }
        }

        // 이 외에는 입력 가능.
        return true;
    }
}

 

이 풀이의 문제는, 백트래킹이 아닌 브루트 포스라, 일단 빈칸에 맞는 수가 있으면 채워넣은뒤, 다른 빈칸을 고려하면 사실 오답인 경우에도 후퇴를 하지 못한다는 것이다. 따라서, 뒷 부분은 빈칸을 채우지 못한채로 그대로 답으로 제출하게 된다.

케이스가 부족했기 때문에, 다른 여러가지 테스트 케이스를 구글링했는데, 내가 찾았던 가장 단순한 테스트 케이스는

0으로 도배하는 것이었다.

 

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0

 

따라서, 적절한 값이 하나도 없는 경우, 탐색을 중단하고 다시 되돌아갈 수 있도록 바꿔주어야 한다.

맞게 푼 다음 시도.

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

    static int[][] sdk;

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        //스도쿠를 담을 배열
        sdk = new int[9][9];
        StringTokenizer st;

        for (int i=0; i<9; i++) {
            st = new StringTokenizer(br.readLine(), " ");
            for (int j=0; j<9; j++) {
                sdk[i][j] = Integer.parseInt(st.nextToken());
            }
        }

        sudoku(0, 0);
    }

    // 스도쿠 칸 채우기
    static void sudoku(int x, int y) {

        if (y==9) {
            sudoku(x+1, 0);
            return;
        }

        if (x==9) {
            StringBuilder sb = new StringBuilder();
            for (int i=0; i<9; i++) {
                for (int j=0; j<9; j++) {
                    sb.append(sdk[i][j]).append(" ");
                }
                sb.append("\n");
            }
            System.out.println(sb);
            System.exit(0);
        }

        if (sdk[x][y]==0) {
            for (int i=1; i<=9; i++) {
                if (search(x, y, i)) {
                    sdk[x][y] = i;
                    sudoku(x, y+1);
                }
            }
            // 오답인 경우, 기입했던 값을 초기화하고 해당 위치부터 재탐색
            sdk[x][y] = 0;
            return;
        }

        sudoku(x, y+1);
    }

    // 스도쿠의 값을 찾아 입력가능한지를 판단하는 method
    static boolean search(int x, int y, int value) {

        for (int i=0; i<9; i++) {
            // 같은 열에서 숫자가 반복되면 안 된다.
            if (sdk[i][y]==value) {
                return false;
            }
            // 같은 행에서 숫자가 반복되면 안 된다.
            else if (sdk[x][i]==value) {
                return false;
            }
        }

        // 3*3 정사각형을 따질때 필요한 수들 (반복문에 들어가면 반복하므로, 여기서 미리 만들어줌)
        int a = x/3*3;
        int b = y/3*3;

        // 3x3 정사각형 안에서도 숫자가 반복되면 안된다.
        for (int i=0; i<3; i++) {
            for (int j=0; j<3; j++) {
                if (sdk[a+i][b+j]==value) {
                    return false;
                }
            }
        }

        // 이 외에는 입력 가능.
        return true;
    }
}