문제
스도쿠는 18세기 스위스 수학자가 만든 '라틴 사각형'이랑 퍼즐에서 유래한 것으로 현재 많은 인기를 누리고 있다. 이 게임은 아래 그림과 같이 가로, 세로 각각 9개씩 총 81개의 작은 칸으로 이루어진 정사각형 판 위에서 이뤄지는데, 게임 시작 전 일부 칸에는 1부터 9까지의 숫자 중 하나가 쓰여 있다.
나머지 빈 칸을 채우는 방식은 다음과 같다.
- 각각의 가로줄과 세로줄에는 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
- 굵은 선으로 구분되어 있는 3x3 정사각형 안에도 1부터 9까지의 숫자가 한 번씩만 나타나야 한다.
위의 예의 경우, 첫째 줄에는 1을 제외한 나머지 2부터 9까지의 숫자들이 이미 나타나 있으므로 첫째 줄 빈칸에는 1이 들어가야 한다.
또한 위쪽 가운데 위치한 3x3 정사각형의 경우에는 3을 제외한 나머지 숫자들이 이미 쓰여있으므로 가운데 빈 칸에는 3이 들어가야 한다.
이와 같이 빈 칸을 차례로 채워 가면 다음과 같은 최종 결과를 얻을 수 있다.
게임 시작 전 스도쿠 판에 쓰여 있는 숫자들의 정보가 주어질 때 모든 빈 칸이 채워진 최종 모습을 출력하는 프로그램을 작성하시오.
입력
홉 줄에 걸쳐 한 줄에 9개씩 게임 시작 전 스도쿠판 각 줄에 쓰여 있는 숫자가 한 칸씩 띄워서 차례로 주어진다. 스도쿠 판의 빈 칸의 경우에는 0이 주어진다. 스도쿠 판을 규칙대로 채울 수 없는 경우의 입력은 주어지지 않는다.
출력
모든 빈 칸이 채워진 스도쿠 판의 최종 모습을 아홉 줄에 걸쳐 한 줄에 9개씩 한 칸씩 띄워서 출력한다.
스도쿠 판을 채우는 방법이 여럿인 경우는 그 중 하나만을 출력한다.
풀이
기본 백트래킹 문제이다.
- 값이 0인 칸, 즉 빈 칸을 탐색하고, 그 칸에 숫자를 넣어 promising 여부를 판단.
- promising하다면 다른 빈 칸 선택 후 반복
- non-promising하다면 다른 숫자를 넣어 promising 여부를 판단한다.
import java.io.*;
import java.util.*;
class _2580{
static int[][] board;
static ArrayList<int[]> list;
public static void main(String[] args) throws Exception{
board = new int[9][9];
list = new ArrayList<>();
// 입력 받아 보드 갱신
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
for(int i = 0; i < 9; i++){
StringTokenizer st = new StringTokenizer(br.readLine());
for(int j = 0; j < 9; j++){
int cur = Integer.parseInt(st.nextToken());
if(cur == 0)
list.add(new int[]{j, i});
board[i][j] = cur;
}
}
sudoku(list.size());
// 출력
StringBuilder sb = new StringBuilder();
for(int i = 0; i < 9; i++){
for(int j = 0; j < 9; j++)
sb.append(board[i][j]).append(' ');
sb.append("\n");
}
System.out.println(sb);
}
// 백트래킹 함수
public static boolean sudoku(int rest){
// 빈 칸이 더 이상 없는 경우
if(rest == 0)
return true;
// 빈 칸의 좌표를 가져옴
int[] coor = list.get(rest-1);
// 백트래킹 반복문
for(int i=1; i <= 9; i++){
board[coor[1]][coor[0]] = i;
// promising 여부 판단
if(isPromising(coor[0], coor[1])){
if(sudoku(rest-1))
return true;
}
}
return false;
}
// promising 여부 판단 함수
public static boolean isPromising(int x, int y){
// 3×3 square check
int rx = x / 3, ry = y / 3;
for(int i = 0; i < 3; i++){
for(int j = 0; j < 3; j++){
if(rx*3+j == x && ry*3+i == y)
continue;
if(board[y][x] == board[ry*3+i][rx*3+j])
return false;
}
}
// 세로 방향 check
for(int i = 0; i < 9; i++){
if(i == y)
continue;
if(board[y][x] == board[i][x])
return false;
}
// 가로 방향 check
for(int j = 0; j < 9; j++){
if(j == x)
continue;
if(board[y][x] == board[y][j])
return false;
}
return true;
}
}