일반적으로 아는 스도쿠 문제를 해결한다.
/* baekjoon 2580 */
import java.util.*;
import java.io.*;
public class Sudoku {
static final int SUDOKU_SIZE = 9; // 스도쿠 사이즈
static int[][] problem; // 해결해야할 스도쿠
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
// 스도쿠 문제 입력 시작
problem = new int[SUDOKU_SIZE][SUDOKU_SIZE];
for (int i = 0; i < SUDOKU_SIZE; i++) {
StringTokenizer st = new StringTokenizer(br.readLine());
for (int j = 0; j < SUDOKU_SIZE; j++) {
problem[i][j] = Integer.parseInt(st.nextToken());
}
}
// 스도쿠 문제 입력 완료
// 0,0 부터 탐색 시작
solution(0, 0);
}
// 2d Array 출력 함수
public static void print(int[][] matrix) {
for (int i = 0; i < SUDOKU_SIZE; i++) {
for (int j = 0; j < SUDOKU_SIZE; j++) {
System.out.print(problem[i][j] + " ");
}
System.out.println();
}
}
// DFS + Back Tracking
public static void solution(int r, int c) {
// 가로 방향으로 다 찾으면 세로 방향으로 찾기
if (c == SUDOKU_SIZE) {
solution(r + 1, 0);
return;
}
// 세로방향 다 찾으면 완전히 종료
if (r == SUDOKU_SIZE) {
print(problem);
System.exit(0);
}
if (problem[r][c] == 0) {
for (int i = 1; i <= SUDOKU_SIZE; i++) {
// 1~9 까지 넣어보면서 넣어도 되는지 확인
if (squardCheck(r, c, i, problem) && verticalCheck(c, i, problem) && horizontalCheck(i, problem[r])) {
problem[r][c] = i;
// 가로방향 먼저 탐색
solution(r, c + 1);
}
}
// [r][c] 0으로 초기화(Back Tracking)
problem[r][c] = 0;
return;
}
// 0이 아니면 다음 가로 방향 확인
solution(r, c + 1);
}
// 사각형 확인
public static boolean squardCheck(int r, int c, int v, int[][] matrix) {
int startR = (r / 3) * 3;
int endR = startR + 3;
int startC = (c / 3) * 3;
int endC = startC + 3;
for (int i = startR; i < endR; i++) {
for (int j = startC; j < endC; j++) {
if (matrix[i][j] == v) {
return false;
}
}
}
return true;
}
// 세로 확인
public static boolean verticalCheck(int c, int v, int[][] matrix) {
for (int i = 0; i < SUDOKU_SIZE; i++) {
if (matrix[i][c] == v)
return false;
}
return true;
}
// 가로 확인
public static boolean horizontalCheck(int v, int[] matrix) {
for (int i = 0; i < SUDOKU_SIZE; i++) {
if (matrix[i] == v)
return false;
}
return true;
}
}