یک حل کننده سودوکو در پایتون ایجاد کنید

این کد را با دقت مطالعه کنید و یک راه هوشمندانه برای استفاده از بازگشت برای حل آن پازل های سودوکو پیدا کنید.

سودوکو یک پازل اعداد محبوب است که از یک شبکه 9×9 با ارقام 1 تا 9 تشکیل شده است. این پازل شامل ترکیبی از اعداد و برخی فضاهای خالی است که باید آنها را پر کنید.

هنگام پر کردن فضاهای خالی، هر سطر، ستون و زیرشبکه 3×3 باید شامل تمام ارقام از 1 تا 9 باشد.

یک اسکریپت ساده پایتون می تواند به حل یک پازل سودوکو برای شما کمک کند. می تواند تمام فضاهای خالی روی برد سودوکو را تجزیه و تحلیل کند و یک عدد ممکن برای پر کردن هر فضای خالی پیدا کند.

نحوه ایجاد و نمایش صفحه سودوکو

در داخل یک اسکریپت پایتون، باید از فهرستی از آرایه ها برای ذخیره مقادیر پازل حل نشده سودوکو استفاده کنید.

کد مورد استفاده در این پروژه در این مخزن GitHub تحت مجوز MIT موجود است.

1. در داخل یک اسکریپت پایتون جدید به نام sudoku.py، تمام مقادیر شبکه 9×9 را ذخیره کنید. هر سطر و ستون نشان دهنده 9 عدد در سرتاسر پازل سودوکو است. برای نشان دادن فضاهایی که نیاز به حل دارند 0 ها را اضافه کنید: تخته = [  [5، 3، 0، 0، 7، 0، 0، 0، 0]،  [6، 0، 0، 1، 9، 5، 0، 0، 0]،  [0، 9، 8، 0، 0، 0، 0، 6، 0]،  [8، 0، 0، 0، 6، 0، 0، 0، 3]،  [4، 0، 0، 8، 0، 3، 0، 0، 1]،  [7، 0، 0، 0، 2، 0، 0، 0، 6]،  [0، 6، 0، 0، 0، 0، 0، 2، 8، 0]،  [0، 0، 0، 4، 1، 9، 0، 0، 5]،  [0، 0، 0، 0، 8، 0، 0، 7، 9]]
2. در داخل یک تابع جدید به نام print_board، از یک حلقه for برای پردازش هر ردیف در شبکه استفاده کنید: def print_board(board):  برای ردیف در محدوده (9):
3. برای جدا کردن هر ردیف به یک سوم، بررسی کنید که آیا سطر بر سه بخش پذیر است یا خیر، و یک خط اضافه کنید:     اگر سطر % 3 == 0 و سطر != 0:       print(“- – – – – – – – – – – – – -“)
4. در هر ردیف، از طریق هر ستون حلقه بزنید. همچنین می‌توانید با بررسی تقسیم‌پذیری ستون بر سه، ستون‌ها را به یک سوم تقسیم کنید:     برای col در محدوده(9):       اگر col % 3 == 0 و col != 0:         print(” | “, end=””)
5. مقدار عدد ذخیره شده در شبکه را چاپ کنید. اگر ستون آخرین ستون برای آن سطر خاص است، یک خط شکست اضافه کنید، به طوری که ردیف زیر در یک خط جدید ظاهر شود:        اگر col == 8:         print(board[row][col])        other:        print(str( board[row][col]) + ” “، end=””)
6. برای چاپ برد، تابع را فراخوانی کنید: print_board(board)
7. در یک خط فرمان، به پوشه ای که اسکریپت پایتون خود را در آن ذخیره کرده اید بروید، به عنوان مثال: cd Desktop
8. برای اجرای اسکریپت سودوکو از دستور پایتون استفاده کنید. پازل چاپ شده روی صفحه را مشاهده کنید: python sudoku.py

board = [
  [5, 3, 0, 0, 7, 0, 0, 0, 0],
  [6, 0, 0, 1, 9, 5, 0, 0, 0],
  [0, 9, 8, 0, 0, 0, 0, 6, 0],
  [8, 0, 0, 0, 6, 0, 0, 0, 3],
  [4, 0, 0, 8, 0, 3, 0, 0, 1],
  [7, 0, 0, 0, 2, 0, 0, 0, 6],
  [0, 6, 0, 0, 0, 0, 2, 8, 0],
  [0, 0, 0, 4, 1, 9, 0, 0, 5],
  [0, 0, 0, 0, 8, 0, 0, 7, 9]
]

def print_board(board):
  for row in range(9):

    if row % 3 == 0 and row != 0:
      print("- - - - - - - - - - - - - - ") 

    for col in range(9):
      if col % 3 == 0 and col != 0:
        print(" | ", end="")

      if col == 8:
        print(board[row][col])
      else:
        print(str(board[row][col]) + " ", end="")

print_board(board)

cd Desktop

python sudoku.py

نحوه شناسایی فضاهای خالی برای حل

می‌توانید از میان فهرست‌ها عبور کنید و فضاهایی را که از 0 تشکیل شده‌اند پیدا کنید. اینها تعیین می کنند که کدام فضاها نیاز به حل دارند.

1. در یک تابع جدید به نام find_empty()، از میان هر سطر و ستون روی تابلو حلقه بزنید: def find_empty(board):  برای ردیف در محدوده (9):    برای col در محدوده (9):
2. اگر مقدار سلول فعلی 0 باشد، موقعیت فعلی سلول خالی را برگردانید:       if board[row][col] == 0:         return (ردیف، ستون)
3. اگر اسکریپت به انتهای تابع برسد، به این معنی است که اسکریپت نمی‌تواند سلول‌هایی با مقدار 0 پیدا کند. در این حالت، چیزی برنگردانید:   بازگردان هیچکدام
4. در یک تابع جدید به نامsol()، از تابع find برای پیدا کردن اولین فضای خالی روی تابلو استفاده کنید: defsol(board):  find = find_empty(board)
5. تابع find_empty() موقعیت سلول را در قالب تاپل برمی گرداند، به عنوان مثال، (0، 2). این مقادیر را به طور جداگانه در متغیرهای ردیف و col ذخیره کنید. در غیر این صورت، true را برگردانید تا نشان دهد که هیچ فضای خالی برای حل باقی نمانده است:   اگر پیدا نشد:    return True  else:    row, col = find

def find_empty(board):
  for row in range(9):
    for col in range(9):

      if board[row][col] == 0:
        return (row, col)

  return None

def solve(board):
  find = find_empty(board)

  if not find:
    return True
  else:
    row, col = find

چگونه معما را برای هر ردیف، ستون و شبکه 3×3 حل کنیم

اکنون که می توانید اولین فضای خالی را برای حل مشخص کنید، باید سعی کنید یک عدد مناسب برای پر کردن آن فضا و حل پازل پیدا کنید.

با استفاده از بازگشت، تابع ()sol را در درون خود فراخوانی کنید تا هر ترکیب ممکنی از مقادیر را برای تمام فضاهای دیگر نیز امتحان کنید.

1. در داخل تابعsol()، پس از یافتن اولین فضای خالی، هر عدد را از 1 تا 9 حلقه کنید. این اعداد نشان دهنده اعداد احتمالی هستند که می توانند فضای حل نشده را پر کنند:   برای num در محدوده (1، 10):
2. برد، عدد ممکن و موقعیت سلول خالی را در یک تابع جدید وارد کنید. اگر آن عدد یک عدد معتبر باشد که بتواند آن فضای خالی را حل کند، تابع جدید true خواهد شد. اگر معتبر است، آن عدد را به سلول روی تابلو اختصاص دهید:     if is_valid(board, num, (row, col)):      board[row][col] = num
3. تابع is_valid() را با پارامترهای منطبق ایجاد کنید: def is_valid(board, num, pos):
4. از این تابع برای بررسی اینکه آیا قرار دادن شماره در آن موقعیت، قوانین بازی سودوکو را نقض می کند یا خیر، استفاده کنید. ابتدا، بررسی کنید که آیا آن عدد از قبل در سطر یا ستون سلول وجود دارد:   برای col در محدوده(9):    if board[pos[0]][col] == num و pos[1] != col:      return False برای ردیف در محدوده(9):    اگر تخته[ردیف][pos[1]] == num و pos[0] != ردیف:      return False
5. شبکه 3×3 که سلول به آن تعلق دارد را دریافت کنید. می توانید این کار را با تقسیم موقعیت سلول بر سه انجام دهید:   box_row = pos[0] // 3  box_col = pos[1] // 3
6. برای هر سطر و ستون در آن شبکه 3×3، بررسی کنید که آیا عدد از قبل وجود دارد یا خیر. اگر چنین شد، false را برگردانید:   برای ردیف در محدوده (box_row*3, box_row*3 + 3):    برای col in range (box_col*3, box_col*3 + 3):       if board[row][col] == num و (ردیف، ستون) != پوز:         return False
7. اگر اسکریپت به پایان عملکرد برسد، به این معنی است که هیچ یک از قوانین سودوکو شکست خورده است. Return true:   Return True
8. تابع is_valid() فقط بررسی می‌کند که آیا قرار دادن عدد معتبر است، اما این بدان معنا نیست که پاسخ صحیح به راه‌حل کلی است. در تابع ()sol، تابع ()sol را دوباره با برد به روز شده فراخوانی کنید. تابعsol() ممکن است به حالتی برسد که دیگر نتواند از هیچ عددی برای پر کردن هیچ فاصله ای استفاده کند. در این حالت، کل تابع false را برمی‌گرداند، آن سلول خاص را به 0 بازنشانی می‌کند و به عقب برمی‌گردد. تابعsol() فقط زمانی true برمی‌گرداند که اسکریپت بتواند تمام فضاها را پر کند:   برای num در محدوده (1، 10):    if is_valid (board, num, (row, col)):      board[row][col] = num                   if is_valid حل (تابلو):         return True                   board[row][col] = 0  return False
9. برای شروع حل پازل، تابعsol() را با برد اصلی، در پایین اسکریپت، پس از اعلام تابعsol() فراخوانی کنید:sol(board)
10. چاپ نتیجه نهایی: print(“حل شد:”)print_board(board)
11. در خط فرمان، از دستور پایتون برای اجرای مجدد اسکریپت استفاده کنید. پازل حل شده چاپ شده روی صفحه را مشاهده کنید: python sudoku.py

  for num in range(1, 10):

    if is_valid(board, num, (row, col)):
      board[row][col] = num

def is_valid(board, num, pos):

  for col in range(9):
    if board[pos[0]][col] == num and pos[1] != col:
      return False

  for row in range(9):
    if board[row][pos[1]] == num and pos[0] != row:
      return False

  box_row = pos[0] // 3
  box_col = pos[1] // 3

  for row in range(box_row*3, box_row*3 + 3):
    for col in range(box_col*3, box_col*3 + 3):
      if board[row][col] == num and (row, col) != pos:
        return False

  return True

  for num in range(1, 10):
    if is_valid(board, num, (row, col)):
      board[row][col] = num
            
      if solve(board):
        return True
            
      board[row][col] = 0

  return False

solve(board)

print("Solved:")
print_board(board)

python sudoku.py

ساخت بازی با استفاده از پایتون

سودوکو تنها یکی از بازی‌هایی است که می‌توانید با پایتون ایجاد و حل کنید. می‌توانید از پایتون برای ایجاد بازی‌های مختلف دیگر، مانند یک کلمه درهم آمیخته، یک بازی ماجراجویی مبتنی بر متن یا یک بازی رنگی استفاده کنید.

منبع مقاله