Giải Sudoku trong C++

Sudoku là lưới 9x9 chia thành 9 ô 3x3. Quy tắc: mỗi hàng, cột, ô 3x3 chứa các chữ số 1-9 không trùng lặp. Sử dụng thuật toán quay lui (backtracking) để giải.

Giải thuật

• isPresentInCol(col, num): kiểm tra num có trong cột không.
• isPresentInRow(row, num): kiểm tra num có trong hàng không.
• isPresentInBox(boxStartRow, boxStartCol, num): kiểm tra num có trong ô 3x3 không.
• findEmptyPlace(row, col): tìm ô trống (giá trị 0), cập nhật row, col.
• isValidPlace(row, col, num): hợp lệ nếu không có trong hàng, cột, ô 3x3.
• solveSudoku():
  • Nếu không còn ô trống → trả về true.
  • Thử số 1-9: nếu hợp lệ → điền, gọi đệ quy, nếu thành công → true, ngược lại xóa (backtrack).
  • Trả về false nếu không tìm được.

Ví dụ minh họa (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()) sudokuGrid();
    else cout << "No solution exists";
    return 0;
}

Đầu vào

Lưới 9x9 với 0 đại diện cho ô trống

Đầu ra

Lưới Sudoku đã giải (in có định dạng)