อัลกอริทึมแก้ปริศนา Sudoku

บทนำ

Sudoku เป็นกริดตัวเลข 9×9 แบ่งเป็นกล่อง 3×3 ย่อย 9 กล่อง กฎการแก้:

• ใช้ตัวเลข 1-9
• ตัวเลขซ้ำไม่ได้ในแถวเดียว คอลัมน์เดียว หรือกล่อง 3×3 เดียวกัน

ใช้ Backtracking: เติมตัวเลขในช่องว่าง ตรวจสอบความถูกต้อง หากไม่ถูกต้องลองตัวต่อไป หาก 1-9 ไม่มีตัวไหนถูกต้อง ให้ Backtrack กลับไปแก้ช่องก่อนหน้า

อินพุตและเอาต์พุต

Input: เมทริกซ์ 9x9 ค่าว่างเป็น 0
Output: กริด Sudoku ที่แก้เสร็จแล้ว หากไม่มีคำตอบคืน false

3 1 6 | 5 7 8 | 4 9 2
5 2 9 | 1 3 4 | 7 6 8
4 8 7 | 6 2 9 | 5 3 1
------------------------
2 6 3 | 4 1 5 | 9 8 7
9 7 4 | 8 6 3 | 1 2 5
8 5 1 | 7 9 2 | 6 4 3
------------------------
1 3 8 | 9 4 7 | 2 5 6
6 9 2 | 3 5 1 | 8 7 4
7 4 5 | 2 8 6 | 3 1 9

อัลกอริทึม

isPresentInCol(col, num) - ตรวจสอบตัวเลขในคอลัมน์

isPresentInRow(row, num) - ตรวจสอบตัวเลขในแถว

isPresentInBox(boxStartRow, boxStartCol, num) - ตรวจสอบในกล่อง 3×3

findEmptyPlace(row, col) - หาช่องว่าง (ค่า 0)

isValidPlace(row, col, num) - ตรวจสอบว่าวางตัวเลขได้หรือไม่

solveSudoku() - ฟังก์ชันหลักแก้ปริศนาแบบ Recursive Backtracking

ตัวอย่างโค้ด (C++)

#include <iostream>
#define N 9
using namespace std;

int grid[N][N] = {
    {3, 0, 6, 5, 0, 8, 4, 0, 0},
    {5, 2, 0, 0, 0, 0, 0, 0, 0},
    {0, 8, 7, 0, 0, 0, 0, 3, 1},
    {0, 0, 3, 0, 1, 0, 0, 8, 0},
    {9, 0, 0, 8, 6, 3, 0, 0, 5},
    {0, 5, 0, 0, 9, 0, 6, 0, 0},
    {1, 3, 0, 0, 0, 0, 2, 5, 0},
    {0, 0, 0, 0, 0, 0, 0, 7, 4},
    {0, 0, 5, 2, 0, 6, 3, 0, 0}
};

bool isPresentInCol(int col, int num) {
    for (int row = 0; row < N; row++) if (grid[row][col] == num) return true;
    return false;
}

bool isPresentInRow(int row, int num) {
    for (int col = 0; col < N; col++) if (grid[row][col] == num) return true;
    return false;
}

bool isPresentInBox(int boxStartRow, int boxStartCol, int num) {
    for (int row = 0; row < 3; row++)
        for (int col = 0; col < 3; col++)
            if (grid[row+boxStartRow][col+boxStartCol] == num) return true;
    return false;
}

void sudokuGrid() {
    for (int row = 0; row < N; row++) {
        for (int col = 0; col < N; col++) {
            if(col == 3 || col == 6) cout << " | ";
            cout << grid[row][col] << " ";
        }
        if(row == 2 || row == 5) {
            cout << endl;
            for(int i = 0; i

ผลลัพธ์
3 1 6 | 5 7 8 | 4 9 2
5 2 9 | 1 3 4 | 7 6 8
4 8 7 | 6 2 9 | 5 3 1
------------------------
2 6 3 | 4 1 5 | 9 8 7
9 7 4 | 8 6 3 | 1 2 5
8 5 1 | 7 9 2 | 6 4 3
------------------------
1 3 8 | 9 4 7 | 2 5 6
6 9 2 | 3 5 1 | 8 7 4
7 4 5 | 2 8 6 | 3 1 9