반응형
알고리즘 분류 : 백트래킹
스도쿠는 9 x 9 칸에 숫자를 채워 넣는 퍼즐 게임이다. 워낙 유명한 게임이니, 부연 설명은 생략. 이 문제는 비워진 칸에 숫자를 채워 넣어야 한다. N-퀸과 마찬가지로 백트래킹 알고리즘을 쓰면 된다.
- 가로 줄, 세로 줄, 서브 사각형을 체크할 변수를 각각 2차원 배열로 선언한다.
- row는 가로 줄(행)을 나타내며, 인덱스는 [행 번호] [채워 넣은 숫자] 이다.
- col은 세로 줄(열)을 나타내며, 인덱스는 [열 번호] [채워 넣은 숫자] 이다.
- squ는 3 x 3 사이즈의 서브 사각형을 나타내며, 인덱스는 [서브 사각형 번호] [채워 넣은 숫자] 이다.
- 서브 사각형은 왼쪽 위에서부터 오른쪽 아래까지 0~8로 번호를 매긴다.
- 1칸의 인덱스를 (X, Y)로 나타낸다고 할 때, 3 x 3 서브 사각형의 번호는 (X/3)*3 + (Y/3)으로 나타낼 수 있다.
- 숫자를 입력받으면서, 0이 아닌 경우 row, col, squ에 번호를 채워 넣는다.
- 0인 경우, 0의 개수를 카운트하고, 별도의 배열에 좌표를 집어넣는다. 아래의 코드에서는 0의 좌표를 (X, Y)라고 할 때, X*9 + Y로 압축하여 b 배열에 집어넣었다. 이후, X = b/9, Y = b%9로 언팩하여 사용한다.
- 재귀 함수를 호출하기 전에, 해당 번호를 해당 칸에 채워 넣을 수 있는지 먼저 확인한다. 가능한 숫자라면, 채워 넣고 다음 재귀 함수를 호출한다.
- 0의 개수인 N번의 깊이만큼 들어가고, 모든 숫자를 채워 넣었다면, 스도쿠를 출력하고 프로그램을 종료한다.
C++ 소스코드
#include <cstdio> #include <cstdlib> bool row[9][10], col[9][10], squ[9][10]; int n, a[9][9], b[81]; int s(int i, int j) { return i/3*3 + j/3; } void solve(int idx) { if (idx == n) { for (int i=0; i<9; i++) { for (int j=0; j<9; j++) { printf("%d ", a[i][j]); } printf("\n"); } exit(0); } int x = b[idx]/9, y = b[idx]%9; for (int i=1; i<10; i++) { if (row[x][i] || col[y][i] || squ[s(x,y)][i]) continue; row[x][i] = col[y][i] = squ[s(x,y)][i] = true; a[x][y] = i; solve(idx+1); a[x][y] = 0; row[x][i] = col[y][i] = squ[s(x,y)][i] = false; } } int main() { for (int i=0; i<9; i++) { for (int j=0; j<9; j++) { scanf("%d", &a[i][j]); int k = a[i][j]; if (!k) b[n++] = i*9+j; else { row[i][k] = true; col[j][k] = true; squ[s(i,j)][k] = true; } } } solve(0); return 0; }
Python 3 소스코드
a = [list(map(int, input().split())) for _ in range(9)] b, n = [0]*81, 0 row = [[False]*10 for _ in range(9)] col = [[False]*10 for _ in range(9)] squ = [[False]*10 for _ in range(9)] def s(i, j): return i//3*3 + j//3 def solve(idx): if idx == n: for i in range(9): print(' '.join(map(str, a[i]))) exit(0) x, y = b[idx]//9, b[idx]%9 for i in range(1, 10): if not (row[x][i] or col[y][i] or squ[s(x,y)][i]): row[x][i] = col[y][i] = squ[s(x,y)][i] = True a[x][y] = i solve(idx+1) a[x][y] = 0 row[x][i] = col[y][i] = squ[s(x,y)][i] = False for i in range(9): for j in range(9): k = a[i][j] if k: row[i][k] = True col[j][k] = True squ[s(i,j)][k] = True else: b[n] = i*9 + j n += 1 solve(0)
참고
반응형