[BOJ/백준] 2239 - 스도쿠

2239번: 스도쿠

---

백트래킹

---

---

• 제목

스도쿠

---

• 조건

시간 제한 : 2 초

메모리 제한 : 256 MB 

---

• 문제

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

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

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

---

• 입력

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

---

• 출력

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

---

예제 입력1	예제 출력1
103000509 002109400 000704000 300502006 060000050 700803004 000401000 009205800 804000107	143628579 572139468 986754231 391542786 468917352 725863914 237481695 619275843 854396127

---

import java.io.*;
import java.util.*;

public class Main {
    static BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
    static StringBuilder sb = new StringBuilder();
    static StringTokenizer st;

    static Integer[][] sudoku = new Integer[9][9];

    static boolean able(int curr, int num){
        int x = curr / 9;
        int y = curr % 9;
        for (int i = x / 3 * 3; i < x / 3 * 3 + 3; i++) {
            for (int j = y / 3 * 3; j < y / 3 * 3 + 3; j++) {
                if(sudoku[i][j] == num) return false;
            }
        }
        for (int i = 0; i < 9; i++) {
            if(sudoku[i][y] == num && i != x) return false;
            if(sudoku[x][i] == num && i != y) return false;
        }
        return true;
    }
    static boolean backtracking(int curr){
        if(curr == 81) return true;
        int x = curr / 9;
        int y = curr % 9;
        if(sudoku[x][y] != 0) return backtracking(curr + 1);
        for(int i = 1; i <= 9; i++){
            if(able(curr, i)){
                sudoku[x][y] = i;
                if(backtracking(curr + 1)){
                    return true;
                }
                sudoku[x][y] = 0;
            }
        }
        return false;
    }

    public static void main(String[] args) throws Exception {
        for (int i = 0; i < 9; i++) {
            String temp = br.readLine();
            for (int j = 0; j < 9; j++) {
                sudoku[i][j] = temp.charAt(j) - '0';
            }
        }
        backtracking(0);

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