حل سودوکو در پایتون – انجمن DEV

Summarize this content to 400 words in Persian Lang
ایجاد حل‌کننده‌های سودوکو می‌تواند راهی عالی برای آشنایی با پس‌گردهای بازگشتی و حل الگوریتم باشد. در این پست وبلاگ، ما برخی از توابع کمکی از پروژه بازی سودوکو خط فرمان را که برای نشان دادن این روش ها ایجاد کردم، بررسی خواهیم کرد. این فایل حاوی توابع کمکی ضروری است که حل پازل سودوکو را تسهیل می کند. ما توابع کلیدی را تجزیه می کنیم: 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

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

بررسی سطر و ستون: اطمینان حاصل می کند که شماره قبلاً در همان سطر یا ستون وجود ندارد.بررسی زیرشبکه: اطمینان حاصل می کند که عدد در زیرشبکه 3×3 وجود ندارد.

یافتن یک سلول خالی

تابع 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

وارد حالت تمام صفحه شوید

از حالت تمام صفحه خارج شوید

تکرار: برای یافتن یک سلول خالی از طریق صفحه تکرار می شود.بازگشت: مختصات اولین سلول خالی یافت شده یا 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 برای مکان یابی سلول خالی بعدی استفاده می کند.Backtracking: سعی می کند اعداد 1-9 را در سلول خالی قرار دهد و اعتبار را با is_valid بررسی کند.

حل بازگشتی: به صورت بازگشتی برای حل تخته تلاش می کند. اگر قرار دادن به یک راه حل منجر شود، برد حل شده را برمی گرداند.Backtrack: اگر قرار دادن به راه حلی منجر نشود، سلول را بازنشانی می کند و عدد بعدی را امتحان می کند.

نتیجه گیری

توابع کمکی برای عملکرد حل کننده سودوکو ما بسیار مهم هستند. را is_valid عملکرد تضمین می کند که قوانین سودوکو رعایت می شود، find_empty به یافتن سلول بعدی برای پر کردن کمک می کند solve برای یافتن راه‌حل از پس‌گرد بازگشتی استفاده می‌کند. درک این توابع کمکی بینشی را در مورد منطق پشت حل معماهای سودوکو به صورت برنامه ای فراهم می کند.

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

def find_empty(board):
    for i in range(9):
        for j in range(9):
            if board[i][j] == 0:
                return (i, j)
    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