본문 바로가기

Programming/BOJ

BOJ 2580 · 스도쿠


알고리즘 분류 : 백트래킹


스도쿠는 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)




참고



태그