Chương trình giải lưới Sudoku một phần trong C++

Giả sử có một lưới Sudoku một phần được điền và ta phải giải nó. Ta biết Sudoku là lưới số 9×9, và toàn bộ lưới cũng được chia thành các ô 3×3. Có một số quy tắc để giải Sudoku:

• Phải dùng chữ số 1 đến 9 để giải.
• Một chữ số không được lặp lại trong một hàng, một cột hoặc một ô 3×3.

Sử dụng thuật toán quay lui (backtracking), ta sẽ thử giải bài Sudoku. Khi một ô được điền một chữ số, nó kiểm tra xem có hợp lệ không. Nếu không hợp lệ, kiểm tra các số khác. Nếu đã kiểm tra tất cả 1-9 và không tìm thấy chữ số hợp lệ để đặt, nó quay lui về tùy chọn trước đó.

Hãy xem triển khai sau để hiểu rõ hơn:

Ví dụ

#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;
}

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

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

int main() {
    if(solveSudoku())
        sudokuGrid();
    else
        cout << "Không có lời giải";
    return 0;
}

Đầu vào

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

Đầu ra

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