Sudoku Solver ใน C++

สมมติว่าเรามีกริดСудอะกุและต้องแก้ปริศนาตัวเลขชื่อดังนี้ สูดอะกุเป็นกริด 9x9 และกริดทั้งหมดแบ่งเป็นกล่อง 3x3 มีกติกาในการแก้:

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

ใช้อัลกอริทึมแบ็กทแร็กกิ้ง (backtracking) ในการแก้ เมื่อกรอกตัวเลขในเซลล์ จะตรวจสอบว่าถูกต้องหรือไม่ ถ้าไม่ถูกต้อง ลองตัวเลขอื่น ถ้าลอง 1-9 ครบแล้วไม่มีตัวเลขที่วางได้ จะย้อนกลับ (backtrack) ไปตัวเลือกก่อนหน้า

ขั้นตอนการแก้ปัญหา

• กำหนดเมธอด isPresentInCol() รับคอลัมน์และตัวเลข
• for แต่ละแถว r ในกริด ถ้า grid[r, col] = num คืนค่า true
• คืนค่า false มิฉะนั้น
• กำหนดเมธอด isPresentInRow() รับแถวและตัวเลข
• for แต่ละคอลัมน์ c ในกริด ถ้า grid[row, c] = num คืนค่า true
• คืนค่า false มิฉะนั้น
• กำหนดเมธอด isPresentInBox() รับ boxStartRow, boxStartCol, num
• for แต่ละแถว r ใน boxStartRow ถึง 3 แถวถัดไป
  • for แต่ละคอลัมน์ c ใน boxStartCol ถึง 3 คอลัมน์ถัดไป
    • ถ้า grid[r, c] = num คืนค่า true
• คืนค่า false มิฉะนั้น
• กำหนดเมธอด findEmptyPlace() รับแถวและคอลัมน์
• for แต่ละแถว r ในกริด
  • for แต่ละคอลัมน์ c ในกริด
    • ถ้า grid[r, c] = 0 คืนค่า true
• คืนค่า false
• กำหนดเมธอด isValidPlace() รับแถว คอลัมน์ ตัวเลข
• ถ้า isPresentInRow, isPresentInCol, isPresentInBox ล้วนเป็น false คืนค่า true
• กำหนดเมธอด solveSudoku() รับกริด
• ถ้าไม่มีที่ว่างในกริด คืนค่า true
• for ตัวเลข 1 ถึง 9
  • ถ้า isValidPlace(row, col, number) แล้ว
    • grid[row, col] := number
    • ถ้า solveSudoku = true คืนค่า true
    • grid[row, col] := 0
• คืนค่า false

ตัวอย่างโค้ด 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 < N; i++)
                cout << "---";
        }
        cout << endl;
    }
}

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 isValidPlace(int row, int col, int num){
    return !isPresentInRow(row, num) && !isPresentInCol(col, num) && !isPresentInBox(row - row%3, col - col%3, num);
}

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;
        }
    }
    return false;
}

int main(){
    if (solveSudoku() == true)
        sudokuGrid();
    else
        cout << "No solution exists";
}

อินพุต

{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}

เอาต์พุต

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