Thuật toán

Chia sẻ đầy đủ về các thuật toán và lời giải các bài toán cơ bản

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

Đề 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.

Các 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, các bạn chắc đã biết về sudoku. Còn nếu các 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:

(Các 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 tôi 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 tôi 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 các bạn.)

Code C/C++:

#include<iostream>
using namespace std;
 
int Matrix[9][9];               // Lưu ma trận suduku
bool Answer;                    // Kết quả bài toán, Answer = true => có giải pháp, Answer = false nghĩa là không có
bool Row[9][10], Col[9][10];    // 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
 
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;
}

Code by Phạm Văn Lâm

597 views

3 bình luận

  1. Phạm Văn Lâm

    Trên đây là đề bài và lời giải bài EASUDOKU – Easy sudoku trên trang spoj.com. Rất mong nhận được sự ủng hộ và phản hồi từ các bạn.

    Trân trọng,
    Phạm Văn Lâm.

  2. Duy

    Cho em hỏi trong hàm Check sao answer = true rồi còn viết đoạn sau ạ?
    row = old_row;
    col = old_col;
    Row[row][i] = false;
    Col[col][i] = false;
    Matrix[row][col] = 0;
    Và đoan này có ý nghĩa gì ạ?

    1. Phạm Văn Lâm

      * Ý bạn là đoạn này phải không:
      if(Answer) return;

      row = old_row;
      col = old_col;
      Row[row][i] = false;
      Col[col][i] = false;
      Matrix[row][col] = 0;
      * Rõ ràng rồi bạn, nếu (Answer == false) thì sẽ có đoạn sau, ngược lại khi (Answer == true) thì return, nghĩa là ta đã thoát khỏi hàm Check, nên đoạn sau sẽ không được chạy qua nữa.

      * Mình giải thích như vậy, bạn thấy đúng không?

Để lại bình luận

Email của bạn sẽ không được hiển thị công khai. Các trường bắt buộc được đánh dấu *