👉 스도쿠 솔버 (Sudoku Solver)
규칙에 맞게 작성된 스도쿠 문제라면 빈 칸이 얼만큼 있든지 전부 풀어주는 프로그램이다.
✨ 풀이
먼저 스도쿠 프로그램을 풀 때 일반적으로 어떻게 접근하는지 생각해볼 필요가 있다. 난이도에 따라 다르겠지만 보통은 스도쿠의 세 가지 규칙에 따라 검증한다.
- 같은 행의 숫자는 서로 중복하면 안 된다.
- 같은 열의 숫자는 서로 중복하면 안 된다.
- 같은 칸(3X3)의 숫자는 서로 중복하면 안 된다.
이 세 가지 규칙에 부합하는 숫자가 바로 떠오른다면 그것을 채우고, 후보가 여러 개 있을 때는 차례대로 넣어보며 검증한다. 풀이 도중 후보 숫자가 행, 열, 칸의 숫자들과 겹치는 오류가 있으면 이전에 채운 숫자들로 돌아가 다시 확인하고 수정한다.
보통 스도쿠를 푸는 방식을 프로그램에도 그대로 적용해서 만들면 된다.
public class SudokuSolver {
private static final int GRID_SIZE = 9;
public static void main(String[] args) {
int[][] board = {
{7, 0, 2, 0, 5, 0, 6, 0, 0},
{0, 0, 0, 0, 0, 3, 0, 0, 0},
{1, 0, 0, 0, 0, 9, 5, 0, 0},
{8, 0, 0, 0, 0, 0, 0, 9, 0},
{0, 4, 3, 0, 0, 0, 7, 5, 0},
{0, 9, 0, 0, 0, 0, 0, 0, 8},
{0, 0, 9, 7, 0, 0, 0, 0, 5},
{0, 0, 0, 2, 0, 0, 0, 0, 0},
{0, 0, 7, 0, 4, 0, 2, 0, 3}
};
}SudokuSolver라는 클래스의 메인 메서드에 예제로 활용할 스도쿠 보드를 int[][] 배열로 넣어주고, main 메서드 위에 보드/그리드의 사이즈를 초기화해준다.
// row에 숫자가 있는지 확인하는 불린 메서드 (파라미터: 검사할 수도쿠 보드, 검사할 숫자, 검사할 행 넘버)
private static boolean isNumberInRow(int[][] board, int number, int row) {
for(int i = 0; i < GRID_SIZE; i++) {
// 행에 있는 숫자가 number와 일치하면 true
if(board[row][i] == number) {
return true;
}
}
// 불일치 == 숫자가 없으면 false
return false;
}
// column에 숫자가 있는지 확인하는 불린 메서드 (파라미터: 검사할 수도쿠 보드, 검사할 숫자, 검사할 열 넘버)
private static boolean isNumberInColumn(int[][] board, int number, int column) {
for(int i = 0; i < GRID_SIZE; i++) {
if(board[i][column] == number) {
return true;
}
}
return false;
}
// 3x3 박스 마다 숫자가 있는지 확인하는 불린 메서드 (파라미터: 검사할 수도쿠 보드, 검사할 숫자, 박스내 행 넘버, 박스내 열 넘버)
// 박스내 검사는 가장 왼쪽 상단에 있는 칸부터 옆으로 옮겨가며 실행
private static boolean isNumberInBox(int[][] board, int number, int row, int column) {
// 행과 열 넘버가 들어왔을 때, 그 숫자가 있는 박스내의 가장 왼쪽 상단 칸의 행과 열 인덱스 변수
int localBoxRow = row - row % 3;
int localBoxColumn = column - column % 3;
for(int i = localBoxRow; i < localBoxRow + 3; i++) {
for(int j = localBoxColumn; j < localBoxColumn + 3; j++) {
// +3 해주는 이유 = 3X3 박스를 순회하기 위함
if(board[i][j] == number) {
return true;
}
}
}
return false;
}그 다음 위에 적어놓은 접근 순서에 따라 행, 열, 박스내의 숫자를 검증하는 메서드를 만들어준다.
// 위 세 가지를 전부 체크해주는 메서드
private static boolean isValid(int[][] board, int number, int row, int column) {
return !isNumberInRow(board, number, row) &&
!isNumberInColumn(board, number, column) &&
!isNumberInBox(board, number, row, column);
}이따 그리드를 채울 때마다 세 가지의 메서드를 개별로 돌면 너무 복잡하니까, 이것들을 합쳐서 전부 체크해해주는 메서드 isValid를 만든다.
private static boolean solveBoard(int[][] board) {
// 보드 전체를 순회하는 for문
for(int row = 0; row < GRID_SIZE; row++) {
for(int column = 0; column < GRID_SIZE; column++) {
if(board[row][column] == 0) {
for(int numberToTry = 1; numberToTry <= GRID_SIZE; numberToTry++) {
if(isValid(board, numberToTry, row, column)) {
board[row][column] = numberToTry;
// 재귀 사용
/*위에서 빈 칸을 채웠으니, 재귀로 이 메서드를 다시 실행해 채운 빈 칸은 넘어가고
그 다음 빈 칸부터 찾아 채우도록 함.
solveBoard(board) == true의 의미: 앞에서의 빈 칸들을 성공적으로 채웠다.*/
if(solveBoard(board)) {
return true;
}
// 성공적으로 채우지 못했을 때, 다시 0로 설정.
/*이유: isValid를 통과한 numberToTry 수를 빈 칸에 할당했는데,
solveBoard(board)에서 false가 뜨면 Valid하지만 칸에 맞는 수가 아니라는 의미이다.
때문에 다시 0으로 설정한다. 다시 numberToTry for문으로 돌아가 다른 수를 검사한다.*/
else {
board[row][column] = 0;
}
}
}
// 전부 isValid를 통과하지 못할 경우 false
return false;
}
}
}
return true;
}이제 검증하는 메서드는 전부 만들었으니, 차근차근 그리드를 채울 차례다. 채울 칸은 0이 값으로 들어있는 칸이다. 우선 2중 for문과 if문으로 그리드를 순회하며 값이 0인 칸을 찾는다. 그후 백트래킹 알고리즘을 활용해서 칸을 채우는데, 백트래킹에 대해 간단하게 알아보자.
😮 백트래킹 알고리즘 (Backtracking Algorithm)
백트래킹 알고리즘은 대게 어떤 제약 조건에 만족하는지를 모든 경우의 수를 고려해 탐색하고, 부적합한 경우라는 것을 알아채는 즉시 후보를 버리는 알고리즘이다. 주로 체스판 문제, 크로스워드 퍼즐, 스도쿠 등 다양한 제약 조건이 있는 퍼즐 문제에 사용되며, 논리 프로그래밍의 기반이 되어주기도 한다. (보다 상세한 설명은 하단 참고 자료의 첫번째 링크를 클릭해보는 것을 추천합니다.)
for(int numberToTry = 1; numberToTry <= GRID_SIZE; numberToTry++) {
if(isValid(board, numberToTry, row, column)) {
board[row][column] = numberToTry;
// 재귀 사용
/*위에서 빈 칸을 채웠으니, 재귀로 이 메서드를 다시 실행해 채운 빈 칸은 넘어가고
그 다음 빈 칸부터 찾아 채우도록 함.
solveBoard(board) == true의 의미: 앞에서의 빈 칸들을 성공적으로 채웠다.*/
if(solveBoard(board)) {
return true;
}
// 성공적으로 채우지 못했을 때, 다시 0로 설정.
/*이유: isValid를 통과한 numberToTry 수를 빈 칸에 할당했는데,
solveBoard(board)에서 false가 뜨면 Valid하지만 칸에 맞는 수가 아니라는 의미이다.
때문에 다시 0으로 설정한다. 다시 numberToTry for문으로 돌아가 다른 수를 검사한다.*/
else {
board[row][column] = 0;
}
}
}
// 전부 isValid를 통과하지 못할 경우 false
return false;다시 스도쿠 프로그램으로 돌아와서, 백트래킹 알고리즘이 적용된 부분이다. 먼저 이 코드의 흐름을 글로 표현하면 다음과 같다.
- 빈 칸을 맞딱드렸을 때 1~9까지의 숫자를 넣어보며 isValid한지 확인
- isValid 검사인 row, column, box와 비교했을 때 겹치지 않는 숫자를 입력한 후 다음 칸으로 이동
- 실행중 빈 칸에 1~9까지 모든 수가 isValid하지 못할 때,
이전에 채운 빈칸으로 돌아가 지우고 Valid한 다른 숫자를 입력하고 풀던 곳으로 돌아와 이어서 실행
컴퓨터가 아닌 사람이 풀 때와 비슷한 방식으로 우선 적합한 후보가 있다면 입력하고, 다음 칸에서 문제가 발생했을 때 돌아와 지우고 다른 후보를 넣는 방식이다. 백트래킹 알고리즘과 재귀는 한 몸이라고 봐야하는데, 백트래킹의 핵심인 '부적합한 후보가 있으면 버리고, 이전으로 돌아간다.'의 돌아간다를 재귀가 도와준다. (적합하다면 계속 탐색하게 해주는 것도 재귀의 역할이다.)
💁♀️ 출력 결과
// main() 안에 추가
if(solveBoard(board)) {
System.out.println("Solved successfully!");
}
else {
System.out.println("Unsolvable board :( ");
}
printBoard(board);
// 출력 메서드 생성
private static void printBoard(int[][] board) {
for(int row = 0; row < GRID_SIZE; row++) {
for(int column = 0; column < GRID_SIZE; column++) {
System.out.print(board[row][column]);
}
System.out.println();
}
}
// 출력 결과
Solved successfully!
732458619
956173824
184629537
871564392
643892751
295317468
329786145
418235976
567941283참고 자료
