โปรแกรมแก้ปริศนา Sudoku ที่กรอกบางส่วนใน C++

ภาพรวมปัญหา

แก้ปริศนา Sudoku 9×9 ที่กรอกบางส่วน กฎ: แต่ละแถว, คอลัมน์, และกล่อง 3×3 ต้องมีตัวเลข 1-9 ครั้งละ 1 ครั้ง

แนวทางแก้ปัญหา (Backtracking)

1. หาช่องว่าง (ค่า 0)
2. ลองใส่ตัวเลข 1-9
3. ตรวจสอบความถูกต้อง: ไม่ซ้ำในแถว, คอลัมน์, กล่อง 3×3
4. ถ้าถูกต้อง ใส่ตัวเลข และ recursion แก้ต่อ
5. ถ้าแก้เสร็จ (ไม่มีช่องว่าง) คืนค่า true
6. ถ้าไม่ได้ ลองตัวเลขถัดไป (backtrack)
7. ถ้าลอง 1-9 หมดไม่ได้ คืนค่า false (backtrack ไปขั้นก่อน)

โค้ดตัวอย่าง (สมบูรณ์และแก้ไขแล้ว)

#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 isPresentInRow(int row, int num) {
    for (int col = 0; col < N; col++)
        if (grid[row][col] == num) return true;
    return false;
}

bool isPresentInCol(int col, int num) {
    for (int row = 0; row < N; row++)
        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;
}

bool isValidPlace(int row, int col, int num) {
    return !isPresentInRow(row, num) &&
           !isPresentInCol(col, num) &&
           !isPresentInBox(row - row % 3, col - col % 3, num);
}

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

bool solveSudoku() {
    int row, col;
    if (!findEmptyPlace(row, col)) return true; // แก้เสร็จ
    
    for (int num = 1; num <= 9; num++) {
        if (isValidPlace(row, col, num)) {
            grid[row][col] = num;
            if (solveSudoku()) return true;
            grid[row][col] = 0; // backtrack
        }
    }
    return false; // trigger backtracking
}

void printGrid() {
    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 < N; i++) cout << "---";
        }
        cout << endl;
    }
}

int main() {
    if (solveSudoku())
        printGrid();
    else
        cout << "No solution exists";
    return 0;
}

ผลลัพธ์

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

การเพิ่มประสิทธิภาพ (Bitmask)

ใช้ bitmask 9 บิต แทนตัวเลข 1-9 ที่ใช้ไปในแต่ละแถว, คอลัมน์, กล่อง

• rowMask[9], colMask[9], boxMask[9]
• ตรวจสอบและอัปเดตใน O(1) ด้วย bitwise operations
• เร็วกว่าการวนลูปตรวจสอบมาก

ความซับซ้อน

• เวลา: O(9^M) โดย M = จำนวนช่องว่าง (Worst case exponential แต่ Backtracking pruning ทำให้เร็วจริง)
• พื้นที่: O(N²) สำหรับ grid + O(N) recursion stack

หมายเหตุ

โค้ดต้นฉบับมีโค้ดซ้ำและไม่สมบูรณ์ (ฟังก์ชัน isValidPlace ไม่สมบูรณ์, sudokuGrid ซ้ำ) โค้ดข้างต้นเป็นเวอร์ชันที่แก้ไขและทำงานได้สมบูรณ์