문제
스도쿠는 매우 간단한 숫자 퍼즐이다. 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
접근
구현 느낌이 많이 나는 백트래킹 문제라고 생각이 되었다...
특히나 사전식으로 앞서는 것을 출력하라는 조건은 작은 수부터 백트래킹을 하라고 오히려 알려주는 느낌이 들었다ㅋㅋ
일단 배열에 0이 저장되어 있는 칸을 찾은 후 그 칸에 들어갈 수 있는 숫자들의 후보를 찾아야 한다.
그 후보들은 1~9 숫자 중에서 가로, 세로, 3*3 내에 존재하지 않는 수들이 될 것이다.
이렇게 찾은 수들을 작은 것부터 순서대로 넣어 보며 재귀 호출을 해서 스도쿠 완성이 가능한지 확인해 보고, 불가능하다고 확인되면 그 다음 숫자를 넣어보고... 하는 것을 반복하면 된다.
어떤 행 또는 열에 0이 많이 존재하면 그 칸에 들어갈 수 있는 숫자들의 후보도 많아지기 때문에, 우선순위 큐를 써서 0이 제일 적게 들어 있는 행 또는 열부터 탐색을 해야 되나...? 싶은 생각도 들었는데 굳이 그렇게까지 할 건 없을 것 같아 하지 않았다.
구현
import java.io.*;
class Main {
static int[][] board = new int[9][9];
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int zeroCount = 0;
int startRow = -1;
int startCol = -1;
for (int i = 0; i < 9; i++) {
String input = br.readLine();
for (int j = 0; j < 9; j++) {
board[i][j] = input.charAt(j) - '0';
if (board[i][j] == 0) {
zeroCount++;
if (startRow == -1) {
startRow = i;
startCol = j;
}
}
}
}
if (zeroCount == 0) {
printBoard();
return;
}
sudoku(startRow, startCol, zeroCount);
printBoard();
}
private static boolean sudoku(int row, int col, int leftZero) {
// 가장 먼저 모든 칸이 채워진 경우가 사전 순으로 가장 앞서는 경우이므로 출력하고 탐색 종료
if (leftZero == 0) {
printBoard();
System.exit(0);
}
// (row, col) 위치부터 탐색 시작
for (int i = row; i < 9; i++) {
for (int j = (i == row)? col : 0; j < 9; j++) {
// 안 채워진 칸을 발견하면
if (board[i][j] == 0) {
// 해당 칸이 존재하는 행, 열, 3*3 범위를 확인
// isPossible[i]: i라는 숫자가 해당 칸에 들어갈 수 있는지 여부
boolean[] isPossible = findPossibleNumbers(i, j);
// 사전 순으로 앞서는 수가 먼저 탐색되도록 1에서부터 9까지 오름차순으로 증가시키며 확인
for (int num = 1; num <= 9; num++) {
// num이라는 숫자가 해당 칸에 들어갈 수 있다면
if (isPossible[num]) {
// 해당 칸에 num을 넣기
board[i][j] = num;
// 재귀 호출 -> 다음 0인 칸을 찾아 같은 과정 반복
// 재귀 호출의 리턴 값이 false면 해당 칸에 num을 넣었을 때 스도쿠를 완성하는 것이 불가능하다는 뜻.
if (!sudoku(i, j + 1, leftZero - 1)) {
// 현재 칸의 숫자를 다시 0으로 초기화하여 이후 다시 탐색되도록 함
board[i][j] = 0;
}
}
}
// 해당 칸에 1부터 9까지 모두 넣어 보았음에도 들어갈 수 있는 숫자가 없었다면,
// (== 다음 칸을 채우기 위한 재귀 호출이 발생하지 않았다면,)
// false를 리턴해 이전 칸에 넣었던 숫자를 다른 것으로 바꾸기
return false;
}
}
}
return true;
}
private static boolean[] findPossibleNumbers(int row, int col) {
boolean[] isPossible = new boolean[10];
Arrays.fill(isPossible, true);
for (int i = 0; i < 9; i++) {
if (board[row][i] != 0) {
isPossible[board[row][i]] = false;
}
if (board[i][col] != 0) {
isPossible[board[i][col]] = false;
}
}
int startRow = (row / 3) * 3;
int startCol = (col / 3) * 3;
for (int i = startRow; i < startRow + 3; i++) {
for (int j = startCol; j < startCol + 3; j++) {
if (board[i][j] != 0) {
isPossible[board[i][j]] = false;
}
}
}
return isPossible;
}
private static void printBoard() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
sb.append(board[i][j]);
}
sb.append("\n");
}
System.out.print(sb.toString());
}
}
그런데 이 글을 작성하면서 이 코드의 비효율적인 부분을 발견했다...
if (board[i][j] == 0) {
// 해당 칸이 존재하는 행, 열, 3*3 범위를 확인
// isPossible[i]: i라는 숫자가 해당 칸에 들어갈 수 있는지 여부
boolean[] isPossible = findPossibleNumbers(i, j);
for (int num = 1; num <= 9; num++) {
// 중략
if (!sudoku(i, j + 1, leftZero - 1)) {
// 현재 칸의 숫자를 다시 0으로 초기화하여 이후 다시 탐색되도록 함
board[i][j] = 0;
}
}
}스도쿠가 완성되지 못하면 배열을 0으로 초기화하고 이후에 다시 탐색되도록 하는데, 이렇게 되면 findPossibleNumbers(i, j)가 다시 호출됨으로써 이미 이전에 찾아뒀던 (i, j)에 들어갈 수 있는 숫자 후보를 중복으로 찾게 되는 것이다.
그런데 각 칸마다 이 후보들이 존재할 수 있을 테니 이렇게 찾은 결과인 길이 10인 boolean 배열을 각 칸마다 무작정 다 저장하는 것도 메모리 소모가 클 것 같고..
그래서 1~9 중에서 사용할 수 없는 숫자를 비트마스킹하는 방식으로 다시 구현해봤다.
비트마스킹 사용
import java.io.*;
class Main {
static int[][] board = new int[9][9];
static int[] rowMask = new int[9]; // 각 행에서 사용된 숫자들
static int[] colMask = new int[9]; // 각 열에서 사용된 숫자들
static int[][] boxMask = new int[3][3]; // 3x3 박스에서 사용된 숫자들
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int zeroCount = 0;
for (int i = 0; i < 9; i++) {
String input = br.readLine();
for (int j = 0; j < 9; j++) {
board[i][j] = input.charAt(j) - '0';
if (board[i][j] != 0) {
int num = board[i][j];
int bit = 1 << num; // num에 해당하는 비트값
rowMask[i] |= bit;
colMask[j] |= bit;
boxMask[i / 3][j / 3] |= bit;
} else {
zeroCount++;
}
}
}
if (zeroCount == 0) {
printBoard();
return;
}
sudoku(0, 0, zeroCount);
}
private static boolean sudoku(int row, int col, int leftZero) {
if (leftZero == 0) {
printBoard();
System.exit(0);
}
if (col == 9) {
return sudoku(row + 1, 0, leftZero); // 다음 행으로 이동
}
if (row == 9) {
return true; // 스도쿠 해결 완료
}
if (board[row][col] != 0) {
return sudoku(row, col + 1, leftZero); // 이미 숫자가 있으면 다음 칸으로
}
int boxRow = row / 3, boxCol = col / 3;
int usedMask = rowMask[row] | colMask[col] | boxMask[boxRow][boxCol]; // 사용 불가능한 숫자
int possibleNumbers = (~usedMask) & 0b1111111110; // 1~9에서 가능한 숫자 추출
for (int num = 1; num <= 9; num++) {
int bit = 1 << num;
if ((possibleNumbers & bit) != 0) { // num이 사용 가능하면 배치
board[row][col] = num;
rowMask[row] |= bit;
colMask[col] |= bit;
boxMask[boxRow][boxCol] |= bit;
if (sudoku(row, col + 1, leftZero - 1)) {
return true;
}
// 백트래킹 (되돌리기)
board[row][col] = 0;
rowMask[row] &= ~bit;
colMask[col] &= ~bit;
boxMask[boxRow][boxCol] &= ~bit;
}
}
return false; // 해결 불가능한 경우
}
private static void printBoard() {
StringBuilder sb = new StringBuilder();
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
sb.append(board[i][j]);
}
sb.append("\n");
}
System.out.print(sb.toString());
}
}
비트마스킹을 사용해도 메모리를 훨씬 더 잡아먹는 건 어쩔 수 없는 것 같다...
