[Python] 파이썬으로 스도쿠 문제 풀기

갑자기 스도쿠??

대학을 졸업하고 1년 동안 취준 끝에 판교에 있는 회사에 AI 엔지니어로 입사하게 되었다.

서울에서 통근을 하며 1시간 동안 무엇을 할까 하다가 무슨 바람이 불었는지 요즘 스도쿠에 빠졌다.

지하철에 있는 시간 동안 쉬운 문제는 5분, 어려운 문제는 10~15분 문제를 풀게 되는데

출, 퇴근하면서 약 8문제 정도 푸는 것 같다.

지루한 출, 퇴근길이 그나마 시간을 빠르게 해주는 것 같아 나름 괜찮다.

 

참고로 내가 스도쿠를 푸는 사이트는 이곳이다.

https://sudoku.com/ko

지금 무료 스도쿠 퍼즐을 즐겨보세요!

 

 

특히 토너먼트가 있는데 스도쿠 문제를 풀면 점수를 부여해서 사람들과 순위 경쟁을 할 수 있다.

이 게임은 난이도 별로 스도쿠 문제를 풀 수 있는데 난도가 높은 문제를 풀수록 더 많은 점수를 받을 수 있다.

스도쿠 순위 경쟁

 

 

아마 게임을 좋아하는 사람들, 특히 순위 경쟁을 좋아하는 사람들은 한 번씩 이런 생각을 해봤을 것이다.

점수를 빠르게 높게 올리고 싶다. (비록 핵을 쓰더라도)

물론 잘못된 방법을 사용하면 안 되지만 무슨 짓을 저질러서라도 점수를 갱신하고 순위를 높이는 것은 뭔지 모를 짜릿함이 있다.

 

그래서 이 글의 결론은 파이썬으로 스도쿠를 빨리 풀어서 점수를 높이고 싶다는 것이다.

당연히 정정당당하게 게임을 즐기는 것이 맞다고 생각한다. 하지만 오늘만큼은 그러고 싶지 않다.

 

스도쿠가 뭔데?

스도쿠는 가로 9칸, 세로 9칸으로 이루어져 있는 표에 1부터 9까지의 숫자를 채워 넣는 퍼즐이다.

참고로 스도쿠는 일본어이다. 

1984년 일본 니코리사의 잡지 <퍼즐통신 니코리>에서 스도쿠라는 이름을 붙여 수록하며 대중화되었다.

스도쿠의 의미는 数字は独身に限る (숫자는 한 번만 쓸 수 있다.)라는 문장을 줄여 数 独 (스도쿠)가 되었다.

 

스도쿠의 규칙은 3가지다.

1. 가로줄에 1~9가 중복 없이 하나씩 들어간다.

2. 세로줄에 1~9가 중복 없이 하나씩 들어간다.

3. 3x3 box 안에 1~9가 중복 없이 하나씩 들어간다.

 

Python Code

코드를 보기 앞서 실행 결과는 다음과 같다.

 

스도쿠 문제를 입력해 주세요.
공백은 0으로 입력
400970000
097050060
200000700
000003040
002000000
075100300
013500400
900000000
000060008

해결된 스도쿠 퍼즐:
4 3 6  |  9 7 2  |  8 5 1
8 9 7  |  4 5 1  |  2 6 3
2 5 1  |  8 3 6  |  7 9 4
- - - - - - - - - - - -
1 8 9  |  7 2 3  |  6 4 5
3 4 2  |  6 8 5  |  1 7 9
6 7 5  |  1 4 9  |  3 8 2
- - - - - - - - - - - -
7 1 3  |  5 9 8  |  4 2 6
9 6 8  |  2 1 4  |  5 3 7
5 2 4  |  3 6 7  |  9 1 8

 

이와 같이 공백은 0으로 입력하고 0에 적절한 숫자를 넣어 퍼즐을 완성시킨다.

 

1. main code

def main():
    print('스도쿠 문제를 입력해 주세요.')
    print('공백은 0으로 입력')
    board = make_board()
    print("\n해결된 스도쿠 퍼즐:")
    solve(board)
    print_board(board)

 

• 사용자에게 스도쿠 문제를 입력하도록 한다.
• make_board 함수를 사용하여 스도쿠 보드를 생성한다.
• solve 함수를 사용하여 스도쿠를 해결한다.
• 해결된 스도쿠를 출력 형태에 맞게 출력한다.

 

2. make_board code

def make_board():
    return [list(map(int, list(input()))) for _ in range(9)]

 

• 사용자에게 입력을 받아 각 숫자를 int 형으로 변환한다.
• 9x9 스도쿠를 만들어 2차원 리스트 형태로 변환한다.

 

3. print_board code

def print_board(bo):
    for i in range(9):
        if i % 3 == 0 and i != 0:  # 가로 구분선
            print('- ' * 12)

        for j in range(9):
            sep = '  |  ' if j in [2, 5] else ' '  # 세로 구분선
            sep = '\n' if j == 8 else sep  # 줄바꿈
            print(bo[i][j], end = sep)

 

• 행과 열 사이의 구분선을 추가하여 3x3 박스를 구분하게 출력한다.
• 3번째 6번째 행을 출력하기 전 가로 구분선을 출력한다.
• 3번째 6번째 열 후에 세로 구분선을 출력한다.
• 행의 마지막 열에서는 다음 행으로 가는 줄 바꿈 문자를 설정한다.

 

4. find_empty code

def find_empty(bo):
    for i in range(9):
        for j in range(9):
            if bo[i][j] == 0:
                return (i, j)  # row, col
    return None

 

• 숫자를 채우기 위해 스도쿠에 비어 있는 칸 (값이 0인 칸)을 찾는다.
• 행과 열의 인덱스를 사용해 현재 위치의 값이 0인지 확인한다.
• 비어 있는 칸이면 좌표를 반환한다.
• 모든 칸을 확인했지만 비어 있는 칸이 없으면 None을 반환한다.

 

5. valid code

def valid(bo, num, pos):
    row, col = pos

    # Check row
    if any(bo[row][i] == num for i in range(9) if i != col):
        return False

    # Check column
    if any(bo[i][col] == num for i in range(9) if i != row):
        return False

    # Check box
    box_x, box_y = col // 3 * 3, row // 3 * 3

    if any(bo[i][j] == num for i in range(box_y, box_y+3) for j in range(box_x, box_x+3) if (i, j) != pos):
        return False

    return True

 

• 특정 숫자 (num)를 특정 위치 (pos)에 넣을 수 있는지 검증한다.
• 행, 열, 3x3 박스 내에 중복된 숫자가 있는지 확인한다.
• pos를 각각 row, col에 할당한다.
• 현재 row의 모든 col을 반복한다. => 현재 col을 제외한 위치에 num이 있다. => 행에 중복된 숫자가 존재하므로 False 반환
• 현재 col의 모든 row를 반복한다. => 현재 row를 제외한 위치에 num이 있다. => 열에 중복된 숫자가 존재하므로 False 반환
• 현재 row, col에 속한 3x3 박스의 시작 좌표인 box_x, box_y를 구한다.
• 3x3 박스 내의 모든 셀을 반복한다. => 현재 위치 pos를 제외한 위치에 num이 있다 => 박스 내에 중복된 숫자가 존재하므로 False를 반환
• 행, 열, 3x3 박스 모두 중복된 숫자 없으면 True 반환 => num이 해당 위치인 pos에 배치한다.

 

6. solve code

def solve(bo):
    find = find_empty(bo)
    if not find:
        return True
    
    row, col = find

    for i in range(1, 10):
        if valid(bo, i, (row, col)):
            bo[row][col] = i

            if solve(bo):
                return True

            bo[row][col] = 0

    return False

 

• 백트래킹 알고리즘을 사용하여 스도쿠 퍼즐을 해결한다.
• find_empty를 통해 비어 있는 칸을 찾는다.
• 만약 빈칸이 없다면 퍼즐을 해결한 것이므로 True를 반환하여 재귀를 마친다.
• 빈칸이 있다면 빈칸의 위치를 찾는다.
• 1부터 9까지 숫자를 빈칸에 넣는다. => valid를 통해 해당 숫자를 빈칸에 넣을 수 있는지 확인한다.
• solve를 재귀 호출하여 다음 빈칸을 해결한다.
• => 만약 True를 반환하면 퍼즐이 완성된 것이므로 재귀를 종료한다.
• => 만약 False를 반환하면 현재 숫자가 위치에 적절하지 않다. 따라서 해당 칸은 0으로 다시 비운다.
• 모든 숫자가 유효하지 않으면 False를 반환 => 이전 단계로 돌아간다.

 

 

전체 code

def make_board():
    return [list(map(int, list(input()))) for _ in range(9)]

def print_board(bo):
    for i in range(9):
        if i % 3 == 0 and i != 0:  # 가로 구분선
            print('- ' * 12)

        for j in range(9):
            sep = '  |  ' if j in [2, 5] else ' '  # 세로 구분선
            sep = '\n' if j == 8 else sep  # 줄바꿈
            print(bo[i][j], end = sep)

def find_empty(bo):
    for i in range(9):
        for j in range(9):
            if bo[i][j] == 0:
                return (i, j)  # row, col
    return None

def valid(bo, num, pos):
    row, col = pos

    # Check row
    if any(bo[row][i] == num for i in range(9) if i != col):
        return False

    # Check column
    if any(bo[i][col] == num for i in range(9) if i != row):
        return False

    # Check box
    box_x, box_y = col // 3 * 3, row // 3 * 3

    if any(bo[i][j] == num for i in range(box_y, box_y+3) for j in range(box_x, box_x+3) if (i, j) != pos):
        return False

    return True

def solve(bo):
    find = find_empty(bo)
    if not find:
        return True
    
    row, col = find

    for i in range(1, 10):
        if valid(bo, i, (row, col)):
            bo[row][col] = i

            if solve(bo):
                return True

            bo[row][col] = 0

    return False

def main():
    print('스도쿠 문제를 입력해 주세요.')
    print('공백은 0으로 입력')
    board = make_board()
    print("\n해결된 스도쿠 퍼즐:")
    solve(board)
    print_board(board)

if __name__ == "__main__":
    main()