thảo luận [Học Tập] Topic thuật toán

  • Người tạo chủ đề Người tạo chủ đề unknowpc90
  • Ngày bắt đầu Ngày bắt đầu
Độ khó: HARD
Đề bài: viết một chương trình để giải trò chơi Sudoku bằng cách điền vào ô trống

Một đáp án đúng cho trò Sudoku này là:

1/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 cột
2/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 hàng
3/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong một ô vuông con có kích thước 3 X 3

Ký tự "." (dấu chấm) đại diện cho ô trống

Ví dụ:

250px-Sudoku-by-L2G-20050714.svg.png

Input: board = [["5","3",".",".","7",".",".",".","."],["6",".",".","1","9","5",".",".","."],[".","9","8",".",".",".",".","6","."],["8",".",".",".","6",".",".",".","3"],["4",".",".","8",".","3",".",".","1"],["7",".",".",".","2",".",".",".","6"],[".","6",".",".",".",".","2","8","."],[".",".",".","4","1","9",".",".","5"],[".",".",".",".","8",".",".","7","9"]]
Output: [["5","3","4","6","7","8","9","1","2"],["6","7","2","1","9","5","3","4","8"],["1","9","8","3","4","2","5","6","7"],["8","5","9","7","6","1","4","2","3"],["4","2","6","8","5","3","7","9","1"],["7","1","3","9","2","4","8","5","6"],["9","6","1","5","3","7","2","8","4"],["2","8","7","4","1","9","6","3","5"],["3","4","5","2","8","6","1","7","9"]]
Nhấp để mở rộng...
250px-Sudoku-by-L2G-20050714_solution.svg.png


Giới hạn:

  • Chiều dài bảng input = 9
  • Chiều rộng bảng input = 9
  • Các ô đều là số hoặc dấu chấm
  • Đầu vào được đảm bảo chỉ có 1 đáp số duy nhất

https://leetcode.com/problems/sudoku-solver/

:doubt: Hôm nay pick random được bài này, tạm thời post đề trước, solution sau
 
Aristides đã nói:
Độ khó: HARD
Đề bài: viết một chương trình để giải trò chơi Sudoku bằng cách điền vào ô trống

Một đáp án đúng cho trò Sudoku này là:

1/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 cột
2/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 hàng
3/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong một ô vuông con có kích thước 3 X 3

Ký tự "." (dấu chấm) đại diện cho ô trống

Ví dụ:

250px-Sudoku-by-L2G-20050714.svg.png


250px-Sudoku-by-L2G-20050714_solution.svg.png


Giới hạn:

  • Chiều dài bảng input = 9
  • Chiều rộng bảng input = 9
  • Các ô đều là số hoặc dấu chấm
  • Đầu vào được đảm bảo chỉ có 1 đáp số duy nhất

https://leetcode.com/problems/sudoku-solver/

:doubt: Hôm nay pick random được bài này, tạm thời post đề trước, solution sau
Nhấp để mở rộng...
Dùng backtracking nhé
 
cuongphungvng đã nói:
Bài toán này chỉ có mỗi backtracking chứ chưa có giải thuật nào tốt hơn thì phải ?
Nhấp để mở rộng...
t cũng k biết cách khác, hóng cao nhân. :p
Bài này t làm lâu rồi, thấy nó ngang với medium thôi, chứ chưa phải hard. :big_smile:
C++: 
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solveSudokuRecursive(board);
    }
    
    bool solveSudokuRecursive(vector<vector<char>>& board, int start_i = 0) {
        for (int i = start_i; i< 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.'){
                    vector<bool> presented(9,false);
                    getPresentMap(board, presented, i, j);
                    for (int k = 0; k < presented.size(); k++){
                        if (!presented[k]) {
                            board[i][j] = k + '1';
                            if (solveSudokuRecursive(board, i)){
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
    
    void getPresentMap(const vector<vector<char>>& board, vector<bool> &presented, int i, int j){
        for (int m = 0; m < 9; m++){
            if (board[i][m] >= '1' && board[i][m] <= '9'){
                presented[board[i][m] - '1'] = true;
            }
            if (board[m][j] >= '1' && board[m][j] <= '9'){
                presented[board[m][j] - '1'] = true;
            }
        }
        
        int start_i = i/3*3;
        int start_j = j/3*3;
        for (int i = start_i; i < start_i + 3; i++){
            for (int j = start_j; j < start_j + 3; j++){
                if (board[i][j] >= '1' && board[i][j] <= '9'){
                    presented[board[i][j] - '1'] = true;
                }
            }   
        }
    }
};
 
thuyduong2007 đã nói:
t cũng k biết cách khác, hóng cao nhân. :p
Bài này t làm lâu rồi, thấy nó ngang với medium thôi, chứ chưa phải hard. :big_smile:
C++: 
class Solution {
public:
    void solveSudoku(vector<vector<char>>& board) {
        solveSudokuRecursive(board);
    }
   
    bool solveSudokuRecursive(vector<vector<char>>& board, int start_i = 0) {
        for (int i = start_i; i< 9; i++) {
            for (int j = 0; j < 9; j++) {
                if (board[i][j] == '.'){
                    vector<bool> presented(9,false);
                    getPresentMap(board, presented, i, j);
                    for (int k = 0; k < presented.size(); k++){
                        if (!presented[k]) {
                            board[i][j] = k + '1';
                            if (solveSudokuRecursive(board, i)){
                                return true;
                            }
                            board[i][j] = '.';
                        }
                    }
                    return false;
                }
            }
        }
        return true;
    }
   
    void getPresentMap(const vector<vector<char>>& board, vector<bool> &presented, int i, int j){
        for (int m = 0; m < 9; m++){
            if (board[i][m] >= '1' && board[i][m] <= '9'){
                presented[board[i][m] - '1'] = true;
            }
            if (board[m][j] >= '1' && board[m][j] <= '9'){
                presented[board[m][j] - '1'] = true;
            }
        }
       
        int start_i = i/3*3;
        int start_j = j/3*3;
        for (int i = start_i; i < start_i + 3; i++){
            for (int j = start_j; j < start_j + 3; j++){
                if (board[i][j] >= '1' && board[i][j] <= '9'){
                    presented[board[i][j] - '1'] = true;
                }
            }  
        }
    }
};
Nhấp để mở rộng...
Thím thử tìm cách convert để run parallel xem.
 
Aristides đã nói:
Độ khó: HARD
Đề bài: viết một chương trình để giải trò chơi Sudoku bằng cách điền vào ô trống

Một đáp án đúng cho trò Sudoku này là:

1/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 cột
2/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 hàng
3/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong một ô vuông con có kích thước 3 X 3

Ký tự "." (dấu chấm) đại diện cho ô trống

Ví dụ:

250px-Sudoku-by-L2G-20050714.svg.png


250px-Sudoku-by-L2G-20050714_solution.svg.png


Giới hạn:

  • Chiều dài bảng input = 9
  • Chiều rộng bảng input = 9
  • Các ô đều là số hoặc dấu chấm
  • Đầu vào được đảm bảo chỉ có 1 đáp số duy nhất

https://leetcode.com/problems/sudoku-solver/

:doubt: Hôm nay pick random được bài này, tạm thời post đề trước, solution sau
Nhấp để mở rộng...
Mình thấy bài này mức độ TB thôi, chưa phải khó, bài sử dụng quay lui khó phải có 2, 3 cái quay lui lồng vào nhau cơ
 
Đi phỏng vấn vào phần qhđ thì họ sẽ hỏi gì mấy bác nhỉ? Tại em thấy nhiều câu vẽ bảng đoán công thức cũng được chứ chẳng cần chứng minh tại sao nó vậy. :sweat:
 
Aristides đã nói:
Độ khó: HARD
Đề bài: viết một chương trình để giải trò chơi Sudoku bằng cách điền vào ô trống

Một đáp án đúng cho trò Sudoku này là:

1/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 cột
2/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong 1 hàng
3/Các số từ 1 đến 9 chỉ xuất hiện đúng 1 lần trong một ô vuông con có kích thước 3 X 3

Ký tự "." (dấu chấm) đại diện cho ô trống

Ví dụ:

250px-Sudoku-by-L2G-20050714.svg.png


250px-Sudoku-by-L2G-20050714_solution.svg.png


Giới hạn:

  • Chiều dài bảng input = 9
  • Chiều rộng bảng input = 9
  • Các ô đều là số hoặc dấu chấm
  • Đầu vào được đảm bảo chỉ có 1 đáp số duy nhất

https://leetcode.com/problems/sudoku-solver/

:doubt: Hôm nay pick random được bài này, tạm thời post đề trước, solution sau
Nhấp để mở rộng...

Sudoku 9x9 thì cứ vét cạn là được nhé, chạy chưa đến 1s đâu. Hồi 2006 tôi đã làm Visual Basic vét cạn để ăn tiền của báo Hoa học trò rồi :LOL:
 
em mới tự học lại giải thuật quy hoạch động, có 1 thắc mắc là có cần thiết lúc nào cũng phải chuyển lời giải đệ quy sang iterative(loop, white) ko các bác
 
Em mới nhập môn khoa học máy tính ạ, có bài tập sau em phải trình bày ra slide, về cơ bản em biết cách giải nhưng trình bày thuật toán ra thì em chưa biết thế nào, các bác giúp em với :( em cảm ơn
1633844130664.png
 
WoodyTheEvil đã nói:
em mới tự học lại giải thuật quy hoạch động, có 1 thắc mắc là có cần thiết lúc nào cũng phải chuyển lời giải đệ quy sang iterative(loop, white) ko các bác
Nhấp để mở rộng...
Có :matrix: bất cứ khi nào có thể
Vì nếu recursion quá sâu thì sẽ gặp đủ thứ lỗi mà cách giải quyết tốt nhất vẫn là đừng đệ quy
 
Aristides đã nói:
Có :matrix: bất cứ khi nào có thể
Vì nếu recursion quá sâu thì sẽ gặp đủ thứ lỗi mà cách giải quyết tốt nhất vẫn là đừng đệ quy
Nhấp để mở rộng...
có tips hay tài liệu nào để tham khảo chuyển đổi đệ quy sang loop ko bác :stick:
nhiều bài e vẫn chưa mường tượng ra cách đổi như thế nào nữa
 
Bạn phải đăng nhập hoặc đăng ký để trả lời tại đây.

Chủ đề tương tự

atomwaffen
7 lý do khiến TPHCM ngày càng ngập nặng
2
Trả lời
30
Lượt xem
2K
SpaceXAI
SpaceXAI
Địa Ngục
Mưa lớn là đường Tô Ngọc Vân, chợ Thủ Đức thành sông: Ngóng dự án hơn 5.000 tỉ
Trả lời
15
Lượt xem
622
betappt
betappt
ChatGPT AI
(Trung Quốc) Singapore và Trung Quốc dẫn đầu thế giới về kết quả học tập
Trả lời
0
Lượt xem
168
ChatGPT AI
ChatGPT AI
Ma trận
[Dịch] Kết quả PISA 2025: Điểm đọc và toán giảm mạnh trên toàn thế giới
2 3 4
Trả lời
65
Lượt xem
5K
chenyouxing
chenyouxing
manoao
Khi sự không hoàn hảo làm nên bản sắc của phin cà phê Việt
Trả lời
1
Lượt xem
150
chocoboxx
chocoboxx

Thống kê chủ đề

Ngày tạo
unknowpc90,
Người trả lời cuối
Spaghetti Code,
Trả lời
1.460
Lượt xem
154.039

Chia sẻ trang này

Quay lại
Lên đầu trang