2580번 스도쿠 ( JAVA )

접근방법

1. 백트래킹을 사용하는데 모든 칸을 확인한다.
2. 칸을 확인하면서 빈칸인 부분에 들어갈 수 있는 숫자를 구한다.
3. 숫자를 칸에 넣고 백트래킹~ 후 다시 복귀

입 / 출력

입력	0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 8 0 0 0 0 0 4 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 2 0 0 0 0 0 0 0 0 0 0 0 0 0 0	5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9	0 0 3 0 2 0 6 0 0 9 0 0 3 0 5 0 0 1 0 0 1 8 0 6 4 0 0 0 0 8 1 0 2 9 0 0 7 0 0 0 0 0 0 0 8 0 0 6 7 0 8 2 0 0 0 0 2 6 0 9 5 0 0 8 0 0 2 0 3 0 0 9 0 0 5 0 1 0 3 0 0	5 0 0 0 0 8 0 0 0 0 3 0 0 0 0 0 0 4 0 0 7 0 0 0 0 0 0 0 6 0 0 0 0 0 0 0 0 0 0 0 9 0 0 0 0 0 0 0 0 0 0 0 5 0 0 0 0 0 0 0 4 0 0 9 0 0 0 0 0 0 2 0 0 0 0 6 0 0 0 0 1
출력	1 2 3 4 5 6 7 8 9  4 5 7 8 1 9 2 3 6 6 9 8 3 2 7 1 5 4 2 1 4 5 3 8 6 9 7 3 8 6 7 9 1 5 4 2 5 7 9 6 4 2 3 1 8 7 3 1 9 6 4 8 2 5 8 4 5 2 7 3 9 6 1 9 6 2 1 8 5 4 7 3	5 3 4 6 7 8 9 1 2 6 7 2 1 9 5 3 4 8 1 9 8 3 4 2 5 6 7 8 5 9 7 6 1 4 2 3 4 2 6 8 5 3 7 9 1 7 1 3 9 2 4 8 5 6 9 6 1 5 3 7 2 8 4 2 8 7 4 1 9 6 3 5 3 4 5 2 8 6 1 7 9	4 8 3 9 2 1 6 5 7  9 6 7 3 4 5 8 2 1 2 5 1 8 7 6 4 9 3 5 4 8 1 3 2 9 7 6 7 2 9 5 6 4 1 3 8 1 3 6 7 9 8 2 4 5 3 7 2 6 8 9 5 1 4 8 1 4 2 5 3 7 6 9 6 9 5 4 1 7 3 8 2	5 1 2 3 4 8 6 7 9  6 3 8 2 7 9 5 1 4 4 9 7 1 5 6 2 3 8 1 6 3 4 2 5 8 9 7 2 7 5 8 9 1 3 4 6 8 4 9 7 6 3 1 5 2 3 2 1 9 8 7 4 6 5 9 8 6 5 1 4 7 2 3 7 5 4 6 3 2 9 8 1

 

코드

import java.io.BufferedReader;
import java.io.FileReader;
import java.io.IOException;
import java.io.InputStreamReader;

public class Main {
    static int map[][];

    static boolean back() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (map[i][j] == 0) {
                    boolean[] check = new boolean[9];
                    for (int k = 0; k < 9; k++) {
                        if (map[k][j] != 0)
                            check[map[k][j] - 1] = true;
                    }
                    for (int k = 0; k < 9; k++) {
                        if (map[i][k] != 0)
                            check[map[i][k] - 1] = true;
                    }
                    int nextY = i / 3 * 3;
                    int nextX = j / 3 * 3;
                    for (int k = 0; k < 3; k++) {
                        for (int l = 0; l < 3; l++) {
                            if (map[nextY + k][nextX + l] != 0) {
                                check[map[nextY + k][nextX + l] - 1] = true;
                            }
                        }
                    }
                    for (int k = 0; k < 9; k++) {
                        if (!check[k]) {
                            map[i][j] = k + 1;
                            if (back()) {
                                return true;
                            }
                            map[i][j] = 0;
                        }
                    }
                    return false;
                }
            }
        }
        return true;

    }

    public static void main(String[] args) throws IOException {

        // BufferedReader br = new BufferedReader(new FileReader("input.txt")); 파일입출력 테스트
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        map = new int[9][9];
        for (int i = 0; i < 9; i++) {
            String[] line = br.readLine().split(" ");
            for (int j = 0; j < 9; j++) {
                map[i][j] = Integer.parseInt(line[j]);
            }
        }
        if (back()) {
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(map[i][j] + " ");
                }
                System.out.println();
            }
        }
    }
}