[백준] 2239, 2580. 스도쿠

스도쿠는 매우 간단한 숫자 퍼즐이다. 9×9 크기의 보드가 있을 때, 각 행과 각 열, 그리고 9개의 3×3 크기의 보드에 1부터 9까지의 숫자가 중복 없이 나타나도록 보드를 채우면 된다. 예를 들어 다음을 보자.

위 그림은 참 잘도 스도쿠 퍼즐을 푼 경우이다. 각 행에 1부터 9까지의 숫자가 중복 없이 나오고, 각 열에 1부터 9까지의 숫자가 중복 없이 나오고, 각 3×3짜리 사각형(9개이며, 위에서 색깔로 표시되었다)에 1부터 9까지의 숫자가 중복 없이 나오기 때문이다.

 

하다 만 스도쿠 퍼즐이 주어졌을 때, 마저 끝내는 프로그램을 작성하시오.

---

입력

9개의 줄에 9개의 숫자로 보드가 입력된다. 아직 숫자가 채워지지 않은 칸에는 0이 주어진다.

출력

9개의 줄에 9개의 숫자로 답을 출력한다. 답이 여러 개 있다면 그 중 사전식으로 앞서는 것을 출력한다. 즉, 81자리의 수가 제일 작은 경우를 출력한다.

---

예제 입력 1 

103000509
002109400
000704000
300502006
060000050
700803004
000401000
009205800
804000107

예제 출력 1 

143628579
572139468
986754231
391542786
468917352
725863914
237481695
619275843
854396127

---

import java.io.BufferedReader;
import java.io.BufferedWriter;
import java.io.InputStreamReader;
import java.io.OutputStreamWriter;
import java.util.Arrays;
import java.util.LinkedList;

public class Main {
    public static int[][] arr;
    public static boolean[][] visited;
    public static LinkedList<Point> list;
    public static BufferedReader br;
    public static BufferedWriter bw;
    public static class Point {
        int r;
        int c;

        public Point(int r, int c) {
            this.r = r;
            this.c = c;
        }
    }
    
    public static void main(String[] args) throws Exception {

        br = new BufferedReader(new InputStreamReader(System.in));
        bw = new BufferedWriter(new OutputStreamWriter(System.out));
        arr = new int[9][9];
        visited = new boolean[9][9];

        list = new LinkedList<Point>();

        for(int i = 0; i < 9; i++) {
            String[] str = br.readLine().split("");
            for(int j = 0; j < 9; j++) {
                arr[i][j] = Integer.parseInt(str[j]);
                if(arr[i][j] == 0) {
                    list.add(new Point(i, j));
                }
            }
        }

        backTrack(0);

        br.close();
        bw.flush();
        bw.close();
    }

    public static void backTrack(int idx) throws Exception {
        if(idx == list.size()) {
            for(int i = 0; i < 9; i++) {
                for(int j = 0; j < 9; j++) {
                    bw.write(Integer.toString(arr[i][j]));
                }
                bw.newLine();
            }
            br.close();
            bw.flush();
            bw.close();
            System.exit(0);
        }
        Point current = list.get(idx);
        // ------------  3*3 가로 세로 체크
        int startR = 0;
        int startC = 0;
        if(current.r >= 3 && current.r < 6) {
            startR = 3;
        } else if (current.r >= 6 && current.r < 9) {
            startR = 6;
        }
        if(current.c >= 3 && current.c < 6) {
            startC = 3;
        } else if (current.c >= 6 && current.c < 9) {
            startC = 6;
        }

        boolean[] visited = new boolean[10];
        Arrays.fill(visited, true);
        for(int i = startR; i < startR + 3; i++) {
            for(int j = startC; j < startC + 3; j++) {
                visited[arr[i][j]] = false;
            }
        }
        for(int i = 0; i < 9; i++) {
            visited[arr[i][current.c]] = false;
            visited[arr[current.r][i]] = false;
        }

        for(int i = 1; i <= 9; i++) {
            if(visited[i]) {
                arr[current.r][current.c] = i;
                backTrack(idx + 1);
                arr[current.r][current.c] = 0;
            }
        }
    }
}