Tạo bài viết
Đăng ký
01/10/2018, 17:33

Giải game Sudoku bằng thuật quay lui bị lỗi ở một số tests

Hi mọi người. Mình có đang giải 1 problem về game Sudoku sau: http://ntucoder.net/Submission/Problem/3261
Ý tưởng của mình sẽ là quay lui từng ô từ trái sang phải trên mỗi dòng từ trên xuống dưới, tại mỗi ô đang xét (có giá trị 0) mình sẽ dùng hàm isSafe() để kiểm tra tính hợp lệ của giá trị đặt vào ô đó. Nếu thỏa mãn tiếp tục đệ quy chạy tiếp, không thì chuyển sang giá trị khác (1 -> 9), nếu ko giá trị nào thỏa mãn thì quay lui lại trường hợp trước.
Mình cài đặt thuật toán như sau: https://ideone.com/4AxU4F

#include <iostream>
#include <vector>
#define N 9

using namespace std;

bool isSafe(const vector<vector<int>> &board, int row, int col, int val)
{
    // check row
    for (int i = 0; i < N; ++i) {
        if (board[row][i] == val)
            return false;
    }
    // check column
    for (int i = 0; i < N; ++i) {
        if (board[i][col] == val)
            return false;
    }
    // first 3x3 square
    if (row <= 2 && col <= 2) {
        for (int i = 0; i <= 2; ++i) {
            for (int j = 0; j <= 2; ++j) {
                if (board[i][j] == val)
                    return false;
            }
        }
    }
    // second 3x3 square
    if (row <= 2 && col >= 3 && col <= 5) {
        for (int i = 0; i <= 2; ++i) {
            for (int j = 3; j <= 5; ++j) {
                if (board[i][j] == val)
                    return false;
            }
        }
    }
    // third 3x3 square
    if (row <= 2 && col >= 6 && col <= 8) {
        for (int i = 0; i <= 2; ++i) {
            for (int j = 6; j <= 8; ++j) {
                if (board[i][j] == val)
                    return false;
            }
        }
    }
    // fourth 3x3 square
    if (row >= 3 && row <= 5 && col <= 2) {
        for (int i = 3; i <= 5; ++i) {
            for (int j = 0; j <= 2; ++j) {
                if (board[i][j] == val)
                    return false;
            }
        }
    }
    // fifth 3x3 square
    if (row >= 3 && row <= 5 && col >= 3 && col <= 5) {
        for (int i = 3; i <= 5; ++i) {
            for (int j = 3; j <= 5; ++j) {
                if (board[i][j] == val)
                    return false;
            }
        }
    }
    // sixth 3x3 square
    if (row >= 3 && row <= 5 && col >= 6 && col <= 8) {
        for (int i = 3; i <= 5; ++i) {
            for (int j = 6; j <= 8; ++j) {
                if (board[i][j] == val)
                    return false;
            }
        }
    }
    // seventh 3x3 square
    if (row >= 6 && row <= 8 && col <= 2) {
        for (int i = 6; i <= 8; ++i) {
            for (int j = 0; j <= 2; ++j) {
                if (board[i][j] == val)
                    return false;
            }
        }
    }
    // eighth 3x3 square
    if (row >= 6 && row <= 8 && col >= 3 && col <= 5) {
        for (int i = 6; i <= 8; ++i) {
            for (int j = 3; j <= 5; ++j) {
                if (board[i][j] == val)
                    return false;
            }
        }
    }
    // ninth 3x3 square
    if (row >= 6 && row <= 8 && col >= 6 && col <= 8) {
        for (int i = 6; i <= 8; ++i) {
            for (int j = 6; j <= 8; ++j) {
                if (board[i][j] == val)
                    return false;
            }
        }
    }
    return true;
}

bool solveSudoku(vector<vector<int>> &board, int row = 0, int col = 0)
{
    // if reaching the final square of sudoku board
    if (row == N && col == N) {
        return true;
    }
    // if reaching the final square of each row
    if (row < N && col == N) {
        if (solveSudoku(board, row + 1)) {
            return true;
        }
        return false;
    }
    // if the square doesn't have a number
    if (board[row][col] == 0)
    {
        for (int i = 1; i <= 9; ++i)
        {
            if (isSafe(board, row, col, i))
            {
                board[row][col] = i;
                if (solveSudoku(board, row, col + 1))
                    return true;
                board[row][col] = 0; // backtrack
            }
        }
        return false;
    }
    else {
        // if the final square on each row has a number
        if (row < N - 1 && col == N - 1) {
            if (solveSudoku(board, row + 1, 0))
                return true;
        }
        // if the final square of sudoku board has a number
        if (row == N - 1 && col == N - 1) {
            if (solveSudoku(board, row + 1, col + 1))
                return true;
        }
        // normal
        else {
            if (solveSudoku(board, row, col + 1))
                return true;
        }
        return false;
    }
}

int main()
{
    vector<vector<int>> sudoku(N);
    for (int i = 0; i < N; ++i) {
        sudoku[i].resize(N);
        for (int j = 0; j < N; ++j) {
            cin >> sudoku[i][j];
        }
    }
    if (solveSudoku(sudoku)) {
        for (int i = 0; i < N; ++i)
        {
            for (int j = 0; j < N; ++j)
            {
                cout << sudoku[i][j] << " ";
            }
            cout << endl;
        }
    }
    else cout << -1;
    return 0;
}

Vì code khá dài dòng nên mình chú thích cho mọi người đọc dễ hiểu hơn tí.
Khi submit thì mình chỉ đúng 6/10 tests, cụ thể như sau: https://ideone.com/IPIVMf
(mình bị runtime error ở test 2, 3, 7, 9)
Dò mãi vẫn không biết code chạy vô tận ở chỗ nào, mong mọi người giúp đỡ ạ !
Xin cảm ơn.

‏ viết 19:49 ngày 01/10/2018

do chạy chậm thôi em. Em giải Sudoku bằng tay như thế nào? Viết cho máy chơi như thế ấy :V Đầu tiên là lấy loại bỏ những giá trị cho trước khỏi các ô trống, mỗi ô trống ban đầu có thể có 9 giá trị, từ từ bị gạch bớt, ô trống nào chỉ có thể có 1 giá trị thì điền vô. Rồi khi chỉ còn lại các ô còn lại 2 hoặc nhiều hơn 2 giá trị thì mới dfs hoặc bfs mấy ô đó, ưu tiên mấy ô còn 2 giá trị trước :V Chứ mới vô nhào vô mò liền + ko gạch bỏ giá trị mà mỗi lần check isSafe xài 27 lần if else e là chậm

http://norvig.com/sudoku.html cách giải của ông già nào đó đây :V

Secret viết 19:37 ngày 01/10/2018

Em cũng chả rành sudoku lắm anh, chỉ biết là một giá trị chỉ tồn tại duy nhất trên 1 hàng, cột và khu vực 3x3 chứa nó. Em hiện tại cũng chưa tìm hiểu tới được DFS và BFS nữa!
Đoạn code trên khi submit là bị RE chứ không phải TLE như em copy nhầm trong link IDEone anh (edit: https://ideone.com/IPIVMf), vậy là có phải do chạy vô tận ko ạ?

‏ viết 19:46 ngày 01/10/2018

em xài quay lui tức là DFS rồi đó

RE là cái gì? runtime error thì em bật debug lên mà mò coi sai ở đâu

à coi cái hàm solveSudoku của em có check row == N && col == N, row < N && col == N, ko có check row == N && col < N, chắc thiếu cái này làm runtime error?

edit: có thể ko phải, cái if else tùm lum nhìn hoa mắt quá =)

‏ viết 19:37 ngày 01/10/2018

code C++ giải sudoku cũ của anh đây (giải thuật của ông Norvig)

#define DFS //or BFS
#include <iostream>
#include <string>
#include <vector>
#include <queue>
#include <iomanip>
#include <cctype>
#include <fstream>
#include <algorithm>
#ifdef DFS
#include <stack>
#elif defined BFS
#include <queue>
#endif

class SudokuBoard
{
typedef std::vector<std::string>       GridValues;
typedef std::vector<std::vector<int> > GridPeers;
typedef std::vector<std::vector<int> > GridGroups;

public: //methods
    SudokuBoard(const std::string& = "");
    bool parse(const std::string&);
    bool valid()const;
    bool solve();
    void print();
    bool isAssigned(int)const;
    int  getCellValue(int)const;
private: // constants
    static const GridPeers  PEERS;  //20 peers each cell of total 81 cells
    static const GridGroups GROUPS; //27 groups (best=23)
private: // methods
    static GridPeers  getPeers();
    static GridGroups getGroups();
    static bool       erase(char, std::string&);
    static bool       reduce(GridValues&, int = -1);
    static GridValues dfs(const GridValues&);
    static void       printChars(char, size_t);
    void              parseGrid(const std::string&);
private: //members
    GridValues values;
};

const SudokuBoard::GridPeers  SudokuBoard::PEERS  = SudokuBoard::getPeers();
const SudokuBoard::GridGroups SudokuBoard::GROUPS = SudokuBoard::getGroups();

int main()
{
    std::string grid;
    for (std::string line; std::cin >> line; grid += line);
    SudokuBoard board(grid);
    if (board.solve()) board.print();
}


SudokuBoard::SudokuBoard(const std::string& grid)
{
    parseGrid(grid);
}

SudokuBoard::GridPeers SudokuBoard::getPeers()
{
    GridPeers peers(81);
    for (size_t i = 0; i < 81; ++i)
    {
        size_t row = i/9;
        size_t col = i%9;
        size_t box = row/3*3 + col/3;
        for (size_t j = 0; j < 81; ++j)
        {
            if (j == i) continue;
            size_t jrow = j/9;
            size_t jcol = j%9;
            size_t jbox = jrow/3*3 + jcol/3;
            if (jrow == row || jcol == col || jbox == box)
                peers[i].push_back(j);
        }
    }
    return peers;
}

SudokuBoard::GridGroups SudokuBoard::getGroups()
{
    GridGroups groups(27);
    // rows
    for (size_t i = 0; i < 9; ++i)
        for (size_t j = 0; j < 9; ++j)
            groups[i].push_back(9*i + j);
    // columns
    for (size_t i = 0; i < 9; ++i)
        for (size_t j = 0; j < 9; ++j)
            groups[i+9].push_back(i + 9*j);
    // boxes
    for (size_t i = 0; i < 9; ++i)
        for (size_t j = 0; j < 9; ++j)
            groups[i+18].push_back(i/3*27 + i%3*3 + j/3*9 + j%3);
    return groups;
}

void SudokuBoard::parseGrid(const std::string& grid)
{
    values.resize(81, "123456789");
    for (size_t i = 0, j = 0; i < grid.size() && j < 81; ++i)
    {
        if (grid[i] == '0' || grid[i] == '.')
            j++;
        else if (grid[i] >= '1' && grid[i] <= '9')
            values[j++] = grid.substr(i,1);
    }
}

bool SudokuBoard::isAssigned(int id)const
{
    return values[id].length() == 1;
}

int SudokuBoard::getCellValue(int id)const
{
    if (!isAssigned(id)) return 0;
    return values[id][0] - '0';
}

bool SudokuBoard::valid()const
{
    if (values.empty()) return false;
    for (size_t i = 0; i < GROUPS.size(); ++i)
    {
        std::vector<int> count(9, 0);
        for (size_t j = 0; j < GROUPS[i].size(); ++j)
        {
            size_t cell = GROUPS[i][j];
            if (isAssigned(cell)) //only check assigned values
                ++count[getCellValue(cell)-1];
        }
        for (int c = 0; c < 9; ++c)
            if (count[c] > 1)
                return false;
    }
    return true;
}

bool SudokuBoard::parse(const std::string& grid)
{
    parseGrid(grid);
    return valid();
}

bool SudokuBoard::erase(char c, std::string& s)
{
    size_t pos = s.find(c);
    if (pos != s.npos) {
        std::swap(s[pos], s[s.size()-1]);
        s.erase(s.size()-1);
        return true;
    }
    return false;
}

bool SudokuBoard::reduce(GridValues& values, int at)
{
    #ifdef DFS
    std::stack<int> q;
    #elif defined BFS
    std::queue<int> q;
    #endif
    if (at != -1) q.push(at);
    else {
        for (size_t i = 0; i < values.size(); ++i)
            if (values[i].size() == 1)
                q.push(i);
    }
    while (!q.empty())
    {
        #ifdef DFS
        int id = q.top();
        #elif defined BFS
        int id = q.front();
        #endif
        char c = values[id][0];
        q.pop();
        // (1)
        for (size_t i = 0; i < PEERS[id].size(); ++i)
        {
            int p = PEERS[id][i];
            if (erase(c, values[p])) {
                if (values[p].empty())     return false;
                if (values[p].size() == 1) q.push(p);
            }
        }
        // (2)
        for (size_t i = 0; i < GROUPS.size(); ++i)
        {
            std::vector<int> dplaces;
            dplaces.reserve(9);
            for (size_t j = 0; j < GROUPS[i].size(); ++j)
            {
                int cell = GROUPS[i][j];
                if (values[cell].find(c) != std::string::npos)
                    dplaces.push_back(cell);
            }
            if (dplaces.empty())
                return false;
            if (dplaces.size() == 1 && values[dplaces[0]].size() != 1) {
                q.push(dplaces[0]);
                values[dplaces[0]] = values[id];
            }
        }
    }
    return true;
}

SudokuBoard::GridValues SudokuBoard::dfs(const GridValues& values)
{
    size_t minId = values.size();
    size_t minlen = 10;
    for (size_t i = 1; i < values.size(); ++i)
        if (values[i].size() < minlen && values[i].size() != 1)
            minId = i, minlen = values[i].size();
    // Solved!
    if (minId == values.size())
        return values;

    for (size_t i = 0; i < values[minId].size(); ++i)
    {
        GridValues g = values;
        g[minId] = values[minId].substr(i, 1);
        if (reduce(g, minId)) {
            GridValues gnext = dfs(g);
            if (!gnext.empty())
                return gnext;
        }
    }
    return GridValues();
}

bool SudokuBoard::solve()
{
    if (!reduce(values)) return false;
    values = dfs(values);
    return valid();
}

void SudokuBoard::printChars(char c, size_t count)
{
    for (size_t i = 0; i < count; ++i)
        std::cout << c;
}

void SudokuBoard::print()
{
    for (int i = 0; i < 9; ++i)
    {
        std::string line;
        for (int j = 0; j < 9; ++j)
            line += values[i*9 + j] + ' ';
        std::cout << line << "\n";
    }
}

cách xài đơn giản 4 dòng trong main, sau này gặp sudoku thì láy ra xài thoi khỏi mất công nửa tiếng 1 tiếng ngồi giải =)

Secret viết 19:44 ngày 01/10/2018

OOP với cái thuật toán đó là em hoa mắt mất anh @@

‏ viết 19:34 ngày 01/10/2018

em bật chế độ debug lên debug code của em đi :V nó gặp runtime error chỗ nào nó nhảy tới đúng dòng đó liền mà

Secret viết 19:36 ngày 01/10/2018

em bật chế độ debug lên debug code của em đi :V nó gặp runtime error chỗ nào nó nhảy tới đúng dòng đó liền mà

CB của em bị ngáo chẳng debug được, đặt breakpoint vào xong start thì nó hiện ra màn hình console cho mình nhập, nhập xong tắt chứ ko next line hay step into được gì cả :((

à coi cái hàm solveSudoku của em có check row == N && col == N , row < N && col == N , ko có check row == N && col < N , chắc thiếu cái này làm runtime error?

Em nghi nó bị lỗi chỗ này nè anh:

if (row == N && col == N) {
    return true;
}
// if reaching the final square of each row
if (row < N && col == N) {
    if (solveSudoku(board, row + 1)) {
        return true;
    }
    return false;
}

Khi row = N - 1 và col = N thì do hàm solveSudoku(board, row + 1) nó sẽ nhảy thành solveSudoku(board, N, 0), mà trong hàm ko có điều kiện nào set row == N && col == 0 nên bị RE ?

‏ viết 19:44 ngày 01/10/2018

chắc vậy, sửa lại mấy cái if else sao cho nó rõ ràng đi =)

trước khi truy cập board[row][col] em phải bảo đảm row và col nằm trong khoảng 0 tới N-1, ở trên em chưa lọc trường hợp row == N && col < N nên sẽ có trường hợp nó truy cập board[N] gây lỗi thôi

Secret viết 19:46 ngày 01/10/2018

trước khi truy cập board[row][col] em phải bảo đảm row và col nằm trong khoảng 0 tới N-1, ở trên em chưa lọc trường hợp row == N && col < N nên sẽ có trường hợp nó truy cập board[N] gây lỗi thô

Em nghĩ là trường hợp row == N && col < N sẽ ko xảy ra (trừ trường hợp solveSudoku(board, N, 0) như em nói trên, mình sẽ set riêng) do trong hàm em ko gọi đệ quy solveSudoku(board, row + 1, col) !

Có vẻ suy đoán ở trên của em đúng anh :v

Khi row = N - 1 và col = N thì do hàm solveSudoku(board, row + 1) nó sẽ nhảy thành solveSudoku(board, N, 0) , mà trong hàm ko có điều kiện nào set row == N && col == 0 nên bị RE ?

Em sửa thằng if() đầu tiên trong hàm solveSudoku thành:

// if reaching the final square of sudoku board
    if ((row == N && col == N) || (row == N && col == 0)) {
        return true;
    }

thì code đã AC :v

‏ viết 19:50 ngày 01/10/2018

test cases bèo quá đây mà :V

em thử cái input này xem =)

0 0 0 0 0 5 0 8 0 
0 0 0 6 0 1 0 4 3 
0 0 0 0 0 0 0 0 0 
0 1 0 5 0 0 0 0 0 
0 0 0 1 0 6 0 0 0 
3 0 0 0 0 0 0 0 5 
5 3 0 0 0 0 0 6 1 
0 0 0 0 0 0 0 0 4 
0 0 0 0 0 0 0 0 0

thấy bảo là impossible 1400 giây mới ra =)

Secret viết 19:46 ngày 01/10/2018

Đúng thiệt chứ
Để em nghiên cứu lại mấy cái DFS BFS với thuật toán anh nói xem cần cải thiện chỗ nào !

Btw, code trên hình như thuần quay lui chứ chưa có nhánh cận đúng ko anh? (vì em thấy problem này đặt trong category quay lui, nhánh cận) ?

em thử cái input này xem =)

OK, nó đứng luôn rồi anh !

‏ viết 19:44 ngày 01/10/2018

nhánh cận là cái gì anh có biết đâu, hồi đó học hết giờ do ông thầy ổng ghiền phân tích big-O quá bỏ 2 3 tuần solo cái big-O nên tuần 12+ trở đi ổng lướt lướt phần đồ thị và quy hoạch động nên có nhớ gì đâu =) Sau này đồ thị chỉ biết mỗi DFS BFS còn QHĐ thì ú ớ toàn tập

Secret viết 19:38 ngày 01/10/2018

Thuật toán này có vẻ đpt lũy thừa nên siêu chậm rồi!

Btw, đoạn input trên sau tầm 20 phút chạy thì KQ là ko có solution !!

Bài liên quan

Secret

0 chủ đề

0 bài viết

Tác giả nổi bật
Từ khóa nổi bật
AngularJS Blog Bootstrap C / C++ Cấu trúc dữ liệu & Giải thuật Cơ sở dữ liệu Codeigniter Công cụ lập trình CSS CSS cơ bản CSS3 Học Excel HTML HTML cơ bản HTML5 Java Javascript jQuery Json Lập trình mobile Laravel Linux MongoDB MySQL NodeJS Oracle Pascal PHP PHP cơ bản PHP nâng cao Python React Native ReactJS Ruby SEO SQL Server Swift Visual Basic VueJS WordPress XML
Chủ đề nổi bật
0
Các chủ đề đang được quan tâm
phần mềm lập trình php | lập trình web php + mysql | khóa học lập trình php | tự học lập trình php | học php cơ bản thachpham | Bat mi ky thuat in decal tem nhan chong nuoc, chong phai mau | blancanhu | Uu diem vuot troi cua in tem nhan ky thuat so cho doanh nghiep | Code24h | Cho thuê phòng trọ hà nội | Cho thuê phòng trọ bình thạnh | Cho thuê phòng trọ | Cho thuê nhà trọ
Đăng ký

Đăng ký nhận thông báo

Các bài học thú vị sẽ được gửi đến inbox của bạn

HỖ TRỢ HỌC VIÊN
VỀ CODE24H
HỢP TÁC VÀ LIÊN KẾT
KẾT NỐI VỚI CHÚNG TÔI
TẢI ỨNG DỤNG TRÊN ĐIỆN THOẠI

CCode 24h, code mọi lúc, mọi nơi

© Copy right 2018 - 2024