Sudoku in Python

สร้างปริศนา Sudoku ด้วย AI แบบ Backtracking

Image by Microsoft

ก่อนอื่นเลย เราต้องมาเริ่มที่กฎของซูโดกุกันก่อน ซูโดกุเป็นเกมที่เราต้องแก้ปัญหา โดยเล่นอยู่ในกระดาน9x9 โดยแบ่งเป็นกระดาน 3x3 อยู่ด้วยกัน 9 ช่อง ใน 1 กระดานเล็กต้องมีตัวเลข 1 ถึง 9 อยู่ในกระดาน 3x3 โดยจะต้องไม่มีตัวเลขซ้ำกันในแต่ละคอลัมน์ แถว และในแต่ละกระดาน 3x3 ด่านล่างนี้คือตัวอย่างซูโดกุ ที่จะแสดงกระดาน 3 x3 โดยใช้สีเขียว

Image by Ben Bellerose

รายละเอียดเกี่ยวกับ AI Code

ตัวโค้ดนี้ไม่ได้จัดอยู่ในกลุ่ม Machine Learning เพราะไม่ได้ใช้ข้อมูลขนาดใหญ่ หรือการปรับแต่งพารามิเตอร์ เพื่อฝึกสอนตัวโมเดล แต่เขียนขึ้นโดยใช้หลักการ Depth-First Search โดยใช้ Recursion และ Backtracking เพื่อใช้ในการแก้ปัญหาซูโดกุ โดยเติมตัวเลขลงในกระดาน โดยตัวปัญหาของซูโดกุ จัดอยู่ในรูปแบบ Constraint Satisfaction Problem (การใช้ข้อบังคับในปัญหา มาลดตัวเลือกในการค้นหา) ที่มีตัวแปร (ตัวเลขบนกระดาน) ข้อจำกัด (กฎที่ตัวเลขต้องไม่ซ้ำกันในแถว คอลัมน์ และกระดาน 3x3) และชุดของค่าที่เป็นไปได้ (ตัวเลข 1 ถึง 9)

ขั้นตอนที่ 1 การนำเข้าไลบรารี

import random

• บรรทัดนี้เราจะนำเข้าโมดูล random ซึ่งใช้สำหรับการสุ่มค่าตัวเลขในโค้ดของเรา

ขั้นตอนที่ 2 ฟังก์ชัน print_board

def print_board(board):
    for row in board:
        print(" ".join(row))

ฟังก์ชันนี้จะรับพารามิเตอร์ board ซึ่งก็คือกระดานของซูโดกุ ที่เป็น 2D list

• for row in board:

เพื่อวนลูปทีละแถวของกระดาน โดยจะใช้ print(“ “.join(row)) เพื่อทำการพิมพ์ช่องว่าง แล้วนำไปรวมค่าในแถว ช่วยให้เกิดการสร้างตารางขึ้นมา

ขั้นตอนที่ 3 ฟังก์ชัน is_valid

def is_valid(board, row, col, num):
    # ตรวจสอบแถว
    for x in range(9):
        if board[row][x] == num:
            return False
    # ตรวจสอบคอลัมน์
    for x in range(9):
        if board[x][col] == num:
            return False
    # ตรวจสอบกระดาน 3x3
    start_row = row - row % 3
    start_col = col - col % 3
    for i in range(3):
        for j in range(3):
            if board[start_row + i][start_col + j] == num:
                return False
    return True

ฟังก์ชันนี้เพื่อตรวจสอบว่าการวางตัวเลข (1–9) ลงในตำแหน่ง แถว คอลัมน์ ของกระดาน นั้นถูกต้องตามกฎของซูโดกุ รึเปล่า

• for x in range(9):

ใช้ board[row][x] == num: เพื่อตรวจสอบแถว โดยวนลูปผ่านทุกคอลัมน์ (0–8) ของแถวนั้น ๆ หากพบว่ามีเลขซ้ำกันในแถวเดียวกัน ให้รีเทิร์นค่า False ทันที

ใช้ board[x][col] == num: เพื่อตรวจสอบคอลัมน์ โดยวนลูปผ่านทุกแถว (0–8) ของคอลัมน์นั้น ๆ หากพบว่ามีเลขซ้ำกันในแถวเดียวกัน ให้รีเทิร์นค่า False ทันที

• ตรวจสอบกระดาน 3x3:

คำนวณตำแหน่งของกระดาน 3x3 โดยใช้

start_row = row - row % 3 หาตำแหน่งแถวแรกของกระดาน

start_col = col - col % 3 หาตำแหน่งคอลัมน์แรกของกระดาน

โดยวนลูปซ้อนสองชั้น ด้วย for i in range(3) และ for j in range(3)เพื่อสามารถตรวจสอบทุกช่อง ในกระดาน 3x3 ว่ามีตัวเลขซ้ำกันในกระดาน ให้รีเทิร์นค่า False และถ้าหากม่พบว่ามีการซ้ำในแถว คอลัมน์ หรือกระดาน 3x3 หมายความว่าการวางตัวเลขในตำแหน่งนี้ ถูกต้องตามกฎของซูโดกุ ให้รีเทิร์นค่า True

Get Theethawat’s stories in your inbox

Join Medium for free to get updates from this writer.

Remember me for faster sign in

ขั้นตอนที่ 4 ฟังก์ชัน solve_sudoku

def solve_sudoku(board):
    for row in range(9):
        for col in range(9):
            if board[row][col] == '.':
                candidates = [str(i) for i in range(1, 10)]
                random.shuffle(candidates)  # randomize ตัวเลข
                for num in candidates:
                    if is_valid(board, row, col, num):
                        board[row][col] = num
                        if solve_sudoku(board):
                            return True
                        board[row][col] = '.'  # backtrack
                return False
    return True

• def solve_sudoku(board):
  ฟังก์ชันนี้ใช้แก้ปริศนาซูโดกุ โดยค้นหาตำแหน่งที่ว่าง (“.”) ทีละช่องบนกระดานและลองเติมตัวเลขจาก 1 ถึง 9 โดยใช้ recursive backtracking
• for row in range(9) และ for col in range(9):
  วนลูปผ่านทุกตำแหน่งบนกระดาน 9x9 ด้วยการใช้ลูปซ้อนกัน เมื่อวนลูปแล้วจะได้ค่าตัวแปร แถว (row) และ คอลัมน์ (col) ที่ใช้แทนตำแหน่งในกระดาน
• if board[row][col] == ‘.’:
  ตรวจสอบว่าในตำแหน่ง (row, col) ว่างรึเปล่า ถ้าว่าง ให้ดำเนินการเติมตัวเลข candidate เข้าไป
• candidates = [str(i) for i in range(1, 10)]
  สร้างลิสต์ของ candidate ตัวเลขจาก 1 ถึง 9 โดยใช้ list comprehension โดยการแปลงตัวเลขเป็นสตริง
• random.shuffle(candidates)
  สุ่มลำดับ candidate เพื่อให้มีความเป็นไปได้ในการสุ่มมากที่สุด โดยแต่ระการรันผลลัพธ์จะไม่ซ้ำกัน
• for num in candidates:
  วนลูปผ่านตัวเลขใน candidate ทีละตัว
• if is_valid(board, row, col, num):
  ตรวจสอบว่าการวางตัวเลข ในแต่ละตำแหน่ง (row, col) สามารถผ่านฟังก์ชัน is_valid รึเปล่า หากผ่านหมายความว่าเป็นการเติมตัวเลขที่ถูกต้องตามกฎของซูโดกุ
• board[row][col] = num
  ถ้าถูกต้องให้เติมตัวเลข ลงในตำแหน่งที่ว่างนั้น
• if solve_sudoku(board)
  เรียกใช้ฟังก์ชัน solve_sudoku(board) แบบ recursive เพื่อแก้ปริศนา สำหรับส่วนที่เหลือของกระดาน หากเรียกใช้แบบ recursive สำเร็จ ให้รีเทิร์นค่า True ทันที ซึ่งหมายความว่าปริศนาได้รับการแก้ไขหมดแล้ว
• board[row][col] = ‘.’
  ถ้า recursive call ไม่สามารถหาคำตอบที่ถูกต้องให้เติมกลับเป็นช่องว่างเพื่อกลับไปลองตัวเลข candidate ตัวถัดไป โดยใช้หลักการการ backtracking
  หลังจากลองตัวเลข candidate หากไม่พบคำตอบที่ถูกต้อง ให้รีเทิร์นค่า False เพื่อให้การ backtracking ทำงานต่อไป
• return True
  เมื่อวนลูปทั้งหมดเสร็จสิ้น ไม่พบช่องว่างเหลือแล้ว หมายความว่ากระดานถูกแก้ไขครบถ้วนแล้ว จึงรีเทิร์นค่า True

ขั้นตอนที่ 5 ฟังก์ชัน generate_complete_board

def generate_complete_board():
    board = [['.' for _ in range(9)] for _ in range(9)]
    solve_sudoku(board)
    return board

• def generate_complete_board():
  ฟังก์ชันนี้ใช้สำหรับสร้างกระดานซูโดกุ แบบสมบูรณ์แบบ (Complete Board) โดยเริ่มจากกระดานว่าง 9x9 จากนั้นใช้ฟังก์ชัน solve_sudoku เพื่อเติมตัวเลขให้ครบทุกช่องตามกฎ
• board = [[‘.’ for _ in range(9)] for _ in range(9)]
  ใช้ list comprehension สร้างกระดาน 9x9 โดยกำหนดให้แต่ละช่องเริ่มต้นเป็น “.” โดยลูปนอกวนผ่านแถว 9 ครั้ง และลูปในวนผ่านคอลัมน์ 9 ครั้ง ผลลัพธ์ที่ได้จะเป็น list สองชั้นที่มี 81 ช่อง
• solve_sudoku(board)
  เรียกฟังก์ชัน solve_sudoku ซึ่งจะเติมตัวเลขในช่องว่างทั้งหมด จนได้กระดานที่ถูกต้องครบถ้วน โดยในขั้นตอนนี้ กระดานจะเปลี่ยนจาก “.” ทั้งหมดเป็นตัวเลข 1 ถึง 9 แบบสุ่มและสอดคล้องกับกฎของซูโดกุ
• return board
  คืนค่ากระดานที่ได้รับการแก้ไขแล้ว (complete board)

ขั้นตอนที่ 6 ฟังก์ชัน mask_board

def mask_board(board, hints=30):
    puzzle = [row.copy() for row in board]
    total_cells = 81
    remove_count = total_cells - hints
    indices = list(range(total_cells))
    random.shuffle(indices)
    for idx in indices[:remove_count]:
        r = idx // 9
        c = idx % 9
        puzzle[r][c] = '.'
    return puzzle

• def mask_board(board, hints=30):
  ฟังก์ชันนี้ใช้สำหรับสร้างปริศนา (Puzzle Board) โดยการสุ่มซ่อนตัวเลขบางส่วนจาก complete board โดยพารามิเตอร์ hints คือจำนวนตัวเลขที่ต้องการให้คงอยู่บนกระดาน โดยช่องที่เหลือจะถูกแสดงเป็น “.”
• puzzle = [row.copy() for row in board]
  ทำสำเนากระดานที่ได้รับมาเพื่อไม่ให้มีการแก้ไข complete board โดยตรง
• total_cells = 81:
  กำหนดจำนวนช่องทั้งหมดบนกระดานซูโดกุ
• remove_count = total_cells — hints
  คำนวณจำนวนช่องที่ต้องการเปลี่ยนให้เป็น “.” โดยลบ hints ออกจากจำนวนช่องทั้งหมด
• indices = list(range(total_cells))
  สร้างลิสต์ของตัวเลข 0 ถึง 80 ซึ่งแทนตำแหน่งทั้งหมดบนกระดาน
• random.shuffle(indices)
  สุ่มลำดับของ indices เพื่อให้ตำแหน่งไม่ซ้ำจากเดิม
• for idx in indices[:remove_count]:
  วนลูปผ่าน indices โดยใช้จำนวน remove_count ที่สุ่มออกมา โดยแต่ละ idx แทนตำแหน่งที่เราต้องการ mask
• r = idx // 9 และ c = idx % 9
  แปลงค่า index (0–80) ให้อยู่ในรูปแบบของแถวและคอลัมน์บนกระดาน 9x9
• r = index หารด้วย 9 จะได้หมายเลขแถว
• c = index โมดูล 9 จะได้หมายเลขคอลัมน์
• puzzle[r][c] = ‘.’
  กำหนดให้ตำแหน่ง (r, c) เปลี่ยนค่าเป็น “.” เพื่อทำการซ่อนตัวเลข
• return puzzle:
  คืนค่ากระดานปริศนาที่ได้หลังจากทำการ mask ไปแล้ว

ขั้นตอนที่ 7 ส่วนหลักของโมเดลนี้

complete_board = generate_complete_board()
puzzle_board = mask_board(complete_board, hints=30)

print("Random Sudoku Puzzle (Hints = 30):")
print_board(puzzle_board)

print("\nComplete Sudoku Board (Solution):")
print_board(complete_board)

• complete_board = generate_complete_board():
  เรียกใช้ฟังก์ชันเพื่อสร้าง complete board โดยใช้ recursive backtracking
  จะได้ผลลัพธ์คือกระดานซูโดกุ ที่ถูกแก้ไขเรียบร้อยตามกฎ
• puzzle_board = mask_board(complete_board, hints=30):
  สร้างปริศนา (Puzzle Board) ด้วยการคัดลอก complete board แล้วสุ่มซ่อนตัวเลขออกโดยคงไว้เพียงตัวเลขเดิม จำนวน 30 ช่องที่แสดงตัวเลข ซึ่งหมายความว่า ทั้งหมด 81 ช่อง จะมีตัวเลขเดิมจำนวน 30 ช่อง และตัวเลขที่ทำการซ่อนจำนวน 51 ช่องจะถูกแสดงเป็น “.”
• print(“Random Sudoku Puzzle (Hints = 30):”) และ print_board(puzzle_board):
  แสดงข้อความและ พิมพ์กระดานปริศนาที่ได้จากการซ่อนตัวเลขไว้
• print(“\nComplete Sudoku Board (Solution):”) และ print_board(complete_board):
  แสดงข้อความ และพิมพ์กระดานที่แก้ไขครบทุกช่อง

ผลลัพธ์ที่ได้

ผลลัพธ์จากการรันโค้ดใน Google Colab

จากการรันตัวโค้ดนี้ จะได้ผลลัพธ์ด้วยกันสองอย่างคือ

• Random Sudoku Puzzle

จะแสดงให้เห็นว่าระบบ ได้ทำการสุ่มสร้างคำตอบ และทำการซ่อน จนเหลือตัวเลขไว้ให้ผู้เล่น 30 ช่อง

• Complete Sudoku Board

จะแสดงให้เห็นว่าระบบทำการสร้างกระดาน ที่มีตัวเลขครบ 1–9 ในทุก ๆ แถว และ ทุก ๆ คอลัมน์ โดยตรงตามกฎของซูโดกุ ถือเป็นคำตอบจากปริศนาด้านบน

สรุป

บทความนี้ นำเสนอการสร้าง และแก้ปริศนาของเกมซูโดกุ โดยใช้แนวทางในงาน AI แบบ Constraint Satisfaction Problem ซึ่งอาศัยหลักการ recursive backtracking Depth-First Search ในการเติมตัวเลขในกระดานให้ถูกตามกฎของซูโดกุ โดยสามารถนำไปต่อยอดใช้ในงานอื่น ๆ ที่มีลักษณะคล้ายกันได้ โดยมีการแยกความรับผิดชอบของแต่ละฟังก์ชันที่ชัดเจน และมีการกำหนดกฎที่ตายตัว

Reference : https://medium.com/data-science/sudoku-solver-48cb2744fbd4

Ben Bellerose Published in TDS Archive 27 Febuary 2022