Cách tạo công cụ giải Sudoku bằng Python

Python là một ngôn ngữ lập trình tuyệt vời có thể giúp bạn tạo ra cả công cụ giải Sudoku. Dưới đây là hướng dẫn chi tiết cách tạo trình giải Sudoku bằng Python.

Sudoku là một game ô số, bao gồm một bảng kẻ ô có kích thước 9x9 với các con số từ 1 tới 9. Game giải đố này bao gồm một kết hợp số cùng các khoảng trống mà bạn cần lấp đầy.

Khi điền vào những khoảng trống đó, mỗi hàng, cột và đường kẻ ô phụ 3x3 sẽ chứa tất cả các con số từ 1 tới 9. Một tập lệnh Python đơn giản có thể giúp giải câu đố Sudoku cho bạn. Nó có thể phân tích tất cả các khoảng trống trên bảng Sudoku, và tìm một số có thể để điền vào từng ô trống.

Cách tạo và hiện bảng Sudoku

Trong một tập lệnh Python, bạn cần dùng một danh sách mảng để chứa các giá trị của câu đố Sudoku chưa được giải.

1. Trong tập lệnh Python mới mang tên sudoku.py, lưu tất cả giá trị cho bảng kẻ ô 9x9. Mỗi hàng và cột đại diện cho 9 số trên và dưới trong game Sudoku. Thêm số 0 để thể hiện các khoảng trống cần giải:

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]
]

2. Bên trong một hàm mới mang tên print_board, dùng for loop để xử lý từng hàng trong bảng ô số:

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

3. Để tách từng hàng thành 3 phần, hãy kiểm tra xem hàng đó có chia hết cho 3 hay không và thêm một dòng:

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

4. Trong từng hàng, lặp qua mỗi cột. Bạn cũng có thể tách cột thành 3 phần bằng cách kiểm tra xem cột có thể chia hết cho 3 hay không:

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

5. In giá trị số được lưu trữ trong bảng ô số. Nếu cột đó là cột cuối cùng cho hàng cụ thể, hãy thêm một dòng ngắt để hàng sau xuất hiện trên một dòng mới:

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

6. Gọi hàm để in bảng:

print_board(board)

7. Trong dòng lệnh, điều hướng tới thư mục nơi bạn lưu trữ tập lệnh Python, ví dụ:

cd Desktop

8. Dùng lệnh Python để chạy script Sudoku. Xem câu đố được hiện trên màn hình:

python sudoku.py

Cách xác định các trường trống cần giải ô số

Bạn có thể duyệt qua danh sách để tìm các khoảng trống chứa số 0. Chúng xác định những ô trống cần giải.

1. Ở hàm mới mang tên find_empty(), lặp qua từng hàng và cột trên bảng:

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

2. Nếu giá trị của ô hiện tại là 0, trả về vị trí hiện tại của ô trống:

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

3. Nếu tập lệnh chạy tới cuối hàm, điều đó có nghĩa script đó không thể tìm thấy bất kỳ ô chứa giá trị 0. Trong trường hợp này, không trả lại bất kỳ giá trị nào.

  return None

4. Trong một hàm mới mang tên solve(), dùng hàm find để tìm trường trống đầu tiên trên bảng:
Hàm find_empty() trả về vị trí ô ở định dạng theo bộ (tuple), ví dụ: (0,2). Lưu riêng từng giá trị này thành các biến row và col. Nếu không, trả về true để chỉ báo rằng không còn ô trống cần giải:

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

Cách giải game Sudoku cho từng hàng, cột và ô 3x3

Sử dụng đệ quy, gọi hàm solve() để thử mọi khả năng kết hợp các giá trị có thể cho tất cả những ô trống khác.

1. Trong hàm solve(), sau khi tìm thấy trường trống đầu tiên, lặp qua từng số từ 1 tới 9. Những số này đại diện cho các con số có thể điền vào ô trống chưa giải:

  for num in range(1, 10):

2. Nhập vào bảng con số có thể, và vị trí ô trống vào hàm mới. Hàm mới này sẽ trả về true nếu đó là một số hợp lệ mà có thể giải ô trống đó. Nếu hợp lệ, gắn số đó cho ô trên bảng:

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

3. Tạo hàm _valid() với các tham số phù hợp:

def is_valid(board, num, pos):

4. Dùng hàm này để kiểm tra xem việc đặt số ở vị trí đó có vi phạm quy tắc nào của game Sudoku hay không. Đầu tiên, kiểm tra xem số đó đã tồn trại trong hàng hay cột của ô:

  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

5. Lấy vùng 3x3 chứa ô đó. Bạn có thể làm việc này bằng cách chia vị trí của ô cho 3:

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

6. Đối với từng hàng và cột ở bảng kẻ ô 3x3, hãy kiểm tra xem liệu số đó đã tồn tại hay chưa. Nếu có, trả về false:

  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

7. Nếu tập lệnh này chạy tới cuối của hàm, điều đó có nghĩa không có quy tắc Sudoku nào sai. Trả về true:

  return True

8. Hàm is_valid chỉ kiểm tra vị trí số hợp lệ, nhưng điều đó không có nghĩa nó là câu trả lời sai cho giải pháp tổng thể. Ở hàm solve(), gọi lại solve() với bảng được cập nhật. Hàm solve() có thể đạt tới trạng thái mà nó có có thể không còn điền được số vào trường trống. Trong trường hợp này, toàn bộ hàm trả về false, thiết lập lại ô cụ thể đó về 0 và quay lại. Hàm solve() chỉ trả về true khi tập lệnh có thể lấp đầy tất cả khoảng trống:

  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

9. Để bắt đầu giải câu đố, gọi hàm solve() với bảng gốc, ở phía dưới của tập lệnh, sau đó khai báo hàm solve():

solve(board)

10. In kết quả cuối cùng:

print("Solved:")
print_board(board)

11. Trên dòng lệnh, dùng lệnh Python để chạy lại script. Xem câu đố đã giải được hiện trên màn hình:

python sudoku.py

Sudoku chỉ là một trong số nhiều game có thể tạo và giải bằng Python. Nếu đang học ngôn ngữ lập trình này, đừng ngại thử nghiệm với nhiều kiểu game khác nữa nhé!