SPOJ.COM - Thuật toán bài EASUDOKU - Easy sudoku

Posted on September 25th, 2016

Đề bài:

Bạn được yêu cầu tìm thuật toán để giải quyết bài toán sudoku cơ bản.

Đầu vào

Dòng đầu vào bao gồm số lượng test case t, 1 <= t <= 15. Mỗi test case bao gồm 81 số từ 0 đến 9 được phân cách nhau bởi dấu cách, và 9 số trên 1 dòng. Số 0 nghĩa là số cần phải điền.

Đầu ra

Nếu không tồn tại giải pháp để giải quyết bài toán thì in ra "No solution". Ngược lại thì bạn phải in 81 số đó ra, và phân cách nhau giống như đầu vào.

Bạn có thể tham khảo đề bài tiếng anh và submit code tại: http://www.spoj.com/problems/EASUDOKU/

Phân tích

Trước khi giải bài toán này, bạn chắc đã biết về sudoku. Còn nếu bạn chưa biết về sudoku thì sau đây mình sẽ giới thiệu qua về luật chơi, như sau:

Có nhiều loại sudoku, ở đây là bài toán sudoku cơ bản. Kích thước là 9×9. Và được chia ra làm 9 khối nhỏ hơn có kích thước 3×3. Sudoku được giải khi tất cả các số trên ma trận đã được điền hết.

Thoả mãn yêu cầu: Trên mỗi hàng, mỗi cột, và mỗi khối 3×3 nhỏ phải được điền các số từ 1 đến 9, mỗi số xuất hiện đúng 1 lần, tức là không số nào được lặp lại từ 2 lần trở lên;

Qua đó, thuật toán có thể sử dụng ở đây đó là thuật toán quay lui có điều kiện - backtracking. Nghĩa là, tại mỗi ô cần giải, ta sẽ điền thử từ 1 đến 9. Nếu ta có thể điền hết thì đó chính là giải pháp. Ngược lại thì sẽ không có giải pháp cho bài toán.

Lời giải

Bạn nên tự mình nghĩ ra thuật toán của bài toán trước khi tham khảo code của mình nhé. Hãy phát huy tối đa khả năng sáng tạo của bản thân. Hơn nữa code mình viết ra cũng chưa thật sự tối ưu. Nên rất mong nhận được sự chia sẻ của bạn.

Code C/C++

#include<iostream>
using namespace std;

// Lưu ma trận suduku
int Matrix[9][9];

// Kết quả bài toán, Answer = true => có giải pháp, Answer = false nghĩa là không có
bool Answer;

// Lưu trạng thái tại từng hàng, cột từ 0 đến 9, các số từ 1 đến 9 đã có chưa
bool Row[9][10], Col[9][10];

void Next(int &row, int &col)
{
    if(col < 8) col++;
    else
    {
        col = 0;
        row++;
    }
}

bool IsValid(int row, int col, int value)
{
    // Kiểm tra xem tại cột đang xét, giá trị 'value' này đã có chưa
    if(Col[col][value] == true) return false;

    // Kiểm tra xem tại hàng đang xét, giá trị 'value' này đã có chưa
    if(Row[row][value] == true) return false;

    // Kiểm tra xem trong khối nhỏ 3x3 đã có giá trị 'value' hay chưa
    int sr = row - row % 3;
    int sc = col - col % 3;

    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++)
            if(Matrix[i + sr][j + sc] == value) return false;

    return true;
}

void Check(int row, int col)
{
    // Nếu đi được hết các dòng thì có nghĩa là đã có giải pháp
    if(row == 9)
    {
        Answer = true;
        return;
    }

    // Nếu tại ô đó đã có giá trị khác 0 thì ta sẽ kiểm tra đến ô tiếp theo
    if (Matrix[row][col] != 0)
    {
        Next(row, col);
        Check(row, col);
    }
    else // Nếu ô đó = 0 thì bắt đầu điền thử giá trị từ 1 đến 9
    {
        int old_row, old_col;

        for(int i = 1; i <= 9; i++)
        {
            // Kiểm tra xem nếu ô tại hàng row, và cột col,
            // điền giá trị i có hợp lệ không. Nếu hợp lệ thì điền thử
            if(IsValid(row, col, i))
            {
                old_row = row;
                old_col = col;

                Matrix[row][col] = i;
                Row[row][i] = true;
                Col[col][i] = true;
                Next(row,col);

                Check(row,col);

                if(Answer) return;

                row = old_row;
                col = old_col;
                Row[row][i] = false;
                Col[col][i] = false;
                Matrix[row][col] = 0;
            }
        }
    }
}

int main()
{
    ios::sync_with_stdio(false);

    // Comment dòng này trước khi submit
    freopen("input.txt","r",stdin);

    int T;
    cin >> T;

    for(int tc = 0; tc < T; tc++)
    {
        Answer = false;
        for(int i = 0; i < 9; i++)
            for(int j = 1; j <= 9; j++)
                Row[i][j] = Col[i][j] = 0;

        // Nhập vào ma trận
        // đồng thời kiểm lưu trạng thái các số đã có hay chưa tại từng hàng, cột
        for(int i = 0; i < 9; i++)
            for(int j = 0; j < 9; j++)
            {
                int tmp;
                cin >> tmp;
                Matrix[i][j] = tmp;

                // Tại dòng i, số có giá trị tmp đã xuất hiện
                Row[i][tmp] = true;
                // Tại cột j, số có giá tị tmp đã xuất hiện
                Col[j][tmp] = true;
            }

        // Bắt đầu xét từ ô đầu tiên hàng = 0 và cột = 0
        Check(0, 0);

        // In kết quả
        if(Answer)
        {
            for(int i = 0; i < 9; i++)
            {
                for(int j = 0; j < 9; j++)
                    cout << Matrix[i][j] << " ";
                cout << endl;
            }
        }
        else cout << "No solution" << endl;

    }

    return 0;
}

★ Nếu bạn thấy bài viết này hay thì hãy theo dõi mình trên Facebook để nhận được thông báo khi có bài viết mới nhất nhé: