Python으로 스도쿠 풀기

스도쿠 해결사를 만드는 것은 재귀적 역추적 및 알고리즘 해결에 익숙해지는 좋은 방법이 될 수 있습니다. 이 블로그 게시물에서는 이러한 방법을 보여주기 위해 제가 만든 명령줄 스도쿠 게임 프로젝트의 몇 가지 도우미 기능을 살펴보겠습니다. 이 파일에는 스도쿠 퍼즐을 쉽게 풀 수 있도록 도와주는 필수 도우미 기능이 포함되어 있습니다. is_valid, find_empty,solve 등 주요 기능을 분석해 보겠습니다.

번호 유효성 확인
is_valid 함수는 주어진 셀에 특정 숫자를 배치하는 것이 스도쿠 규칙에 따라 유효한지 여부를 확인합니다.

def is_valid(board, row, col, num):
    # Check if the number is not present in the same row and column
    if num in board[row] or num in [board[i][col] for i in range(9)]:
        return False

    start_row, start_col = 3 * (row // 3), 3 * (col // 3)
    for i in range(start_row, start_row + 3):
        for j in range(start_col, start_col + 3):
            if board[i][j] == num:
                return False
    return True

행 및 열 확인: 숫자가 동일한 행이나 열에 이미 존재하지 않는지 확인합니다.
하위 그리드 확인: 3x3 하위 그리드에 숫자가 없는지 확인합니다.

빈 셀 찾기

find_empty 함수는 보드에서 다음 빈 셀(0으로 표시)을 찾습니다.

def find_empty(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i, j)
    return None

반복: 보드 전체를 반복하여 빈 셀을 찾습니다.
Return: 발견된 첫 번째 빈 셀의 좌표를 반환하거나 보드가 가득 찬 경우 None을 반환합니다.

스도쿠 퍼즐 풀기

해결 기능은 역추적을 사용하여 스도쿠 퍼즐을 해결합니다.

def solve(board):
    empty_cell = find_empty(board)
    # Board is solved
    if not empty_cell:
        return board

    row, col = empty_cell

    numbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
    random.shuffle(numbers)

    for num in numbers:
        if is_valid(board, row, col, num):
            board[row][col] = num
            if solve(board):
                return board
            # Backtrack if current placement doesn't lead to a solution
            board[row][col] = 0
        # No valid number for current empty cell
    return False

빈 셀 찾기: find_empty를 사용하여 다음 빈 셀을 찾습니다.
역추적: 빈 셀에 1~9의 숫자를 배치하고 is_valid로 유효성을 확인합니다.

재귀적 해결: 보드를 반복적으로 해결하려고 시도합니다. 배치가 해결 방법으로 연결되면 해결된 보드를 반환합니다.
역추적: 배치가 해결로 이어지지 않으면 셀을 재설정하고 다음 숫자를 시도합니다.

결론

도우미 기능은 스도쿠 해결사 기능에 매우 중요합니다. is_valid 함수는 스도쿠 규칙을 준수하는지 확인하고, find_empty는 채울 다음 셀을 찾는 데 도움을 주며,solv는 재귀 역추적을 사용하여 솔루션을 찾습니다. 이러한 도우미 기능을 이해하면 스도쿠 퍼즐을 프로그래밍 방식으로 해결하는 논리에 대한 통찰력을 얻을 수 있습니다.

위 내용은 Python으로 스도쿠 풀기의 상세 내용입니다. 자세한 내용은 PHP 중국어 웹사이트의 기타 관련 기사를 참조하세요!