Từ 1 tới 5 trên tổng số 5 kết quả

Đề tài: Tạo một bài toán Sudoku có phân bổ ngẫu nhiên và có ít nhất 1 lời giải.

  1. #1
    Ngày gia nhập
    02 2014
    Nơi ở
    TP.HCM
    Bài viết
    999

    Mặc định Tạo một bài toán Sudoku có phân bổ ngẫu nhiên và có ít nhất 1 lời giải.

    Đang hướng dẫn cho một bạn sinh viên xây dựng trò chơi Sudoku mà vướng mắc thuật toán tạo đề bài, mã như bên dưới

    Visual C++ Code:
    1.     // Tạo đề bài ngẫu nhiên
    2.     void CreateValueRandom(CCell cell[81])
    3.     {
    4.         // Thiết lập lại tất cả các ô
    5.         for (int i = 0; i < 81; i++)
    6.         {
    7.             cell[i].setValue(rand() % 9 + 1);   // Tạo giá trị ngẫu nhiên trong miền [1,9] cho tất cả 81 ô
    8.             cell[i].setHard(false);
    9.             cell[i].setTextColor(m_crSoftCell);
    10.         }
    11.         // Kiểm tra trên mỗi hàng ngang: nếu có hơn 1 ô trùng giá trị thì xóa hết chỉ chừa lại 1
    12.         for (int row = 0; row < 9; row++)
    13.         {
    14.             for (int i = 1; i < 10; i++)                            // Xét từng giá trị có thể có trong hàng
    15.             {
    16.                 vector<int> vt;                                     // vector lưu lại các ô trùng giá trị
    17.                 for (int col = 0; col < 9; col++)
    18.                 {
    19.                     if (cell[row * 9 + col].getValue() == i)        // Ô này trùng giá trị đang xét
    20.                         vt.push_back(row * 9 + col);                // Lưu nó vào vector
    21.                 }
    22.                 int size = (int)vt.size();                          // Lấy số phần tử của vector
    23.                 if (size > 1)                                       // Nếu nó lớn hơn 1
    24.                 {
    25.                     int index = vt[rand() % size];                  // Lấy 1 ô ngẫu nhiên trong vector
    26.                     for (int j = 0; j < size; j++)
    27.                         cell[vt[j]].setValue(0);                    // Xóa tất cả các ô có chỉ mục trong vector
    28.                     cell[index].setValue(i);                        // Thiết lập giá trị cho ô ngẫu nhiên
    29.                 }
    30.             }
    31.         }
    32.         // Kiểm tra trên mỗi hàng dọc: nếu có hơn 1 ô trùng giá trị thì xóa hết chỉ chừa lại 1
    33.         for (int col = 0; col < 9; col++)
    34.         {
    35.             for (int i = 1; i < 10; i++)
    36.             {
    37.                 vector<int> vt;
    38.                 for (int row = 0; row < 9; row++)
    39.                 {
    40.                     if (cell[row * 9 + col].getValue() == i)
    41.                         vt.push_back(row * 9 + col);
    42.                 }
    43.                 int size = (int)vt.size();
    44.                 if (size > 1)
    45.                 {
    46.                     int index = vt[rand() % size];
    47.                     for (int j = 0; j < size; j++)
    48.                         cell[vt[j]].setValue(0);
    49.                     cell[index].setValue(i);
    50.                 }
    51.             }
    52.         }
    53.         // Kiểm tra trên khung 3x3: nếu có hơn 1 ô trùng giá trị thì xóa hết chỉ chừa lại 1
    54.         for (int row = 0; row < 9; row += 3)
    55.         {
    56.             for (int col = 0; col < 9; col += 3)
    57.             {
    58.                 for (int i = 1; i < 10; i++)
    59.                 {
    60.                     vector<int> vt;
    61.                     for (int r = row; r < row + 3; r++)
    62.                         for (int c = col; c < col + 3; c++)
    63.                             if (cell[r * 9 + c].getValue() == i)
    64.                                 vt.push_back(r * 9 + c);
    65.                     int size = (int)vt.size();
    66.                     if (size > 1)
    67.                     {
    68.                         int index = vt[rand() % size];
    69.                         for (int j = 0; j < size; j++)
    70.                             cell[vt[j]].setValue(0);
    71.                         cell[index].setValue(i);
    72.                     }
    73.                 }
    74.             }
    75.         }
    76.         // Gán các thuộc tính cho các ô có giá trị > 0
    77.         for (int i = 0; i < 81; i++)
    78.             if (cell[i].getValue())
    79.             {
    80.                 cell[i].setHard(true);
    81.                 cell[i].setTextColor(m_crHardCell);
    82.             }
    83.     }

    Vướng mắc là : Muốn đề bài phải có ít nhất 1 lời giải, nếu chạy giải thuật lấy lời giải để xem nó có lời giải không nếu không có thì tạo lại đề bài, hướng này rất mất thời gian.
    Thấy việc này cũng thú vị, có thể đưa lên xem bạn nào có ý thì trợ giúp.

    Attached Files Attached Files

  2. #2
    Ngày gia nhập
    12 2015
    Nơi ở
    Đà Nẵng
    Bài viết
    612

    Có trang này không biết có giúp được bạn không?
    https://www.101computing.net/sudoku-...tor-algorithm/
    Cách nó đề xuất là tạo bảng đầy đủ rồi xóa từng ô 1 cách ngẫu nhiên, nếu giải được thì tiếp tục xóa ô...
    Nó có code viết bằng python

  3. #3
    Ngày gia nhập
    02 2014
    Nơi ở
    TP.HCM
    Bài viết
    999

    Cách mà bạn gợi ý trên là từ một mảng khởi tạo 0, thêm vào từng vị trí ngẫu nhiên một giá trị ngẫu nhiên và kiểm tra xem giá trị đó tại vị trí đó có hợp lệ không (check trên toàn board 9*9).
    Ưu điểm của nó là tránh được rủi ro vòng lặp vô tận. Theo mình thì nó vẫn mang một tính chất "trâu cày" nào đó, nhưng nó cũng là hướng tốt khi chưa tìm ra hướng nào tốt hơn.
    .
    .

  4. #4
    Ngày gia nhập
    02 2014
    Nơi ở
    TP.HCM
    Bài viết
    999

    Mặc định Một cách tạo đề bài dùng đệ quy

    Bên dưới là một hướng mã cho đề bài

    Visual C++ Code:
    1.     ///////////////////////////////// Các hàm thuật toán tạo đề bài ////////////////////////////////////////////
    2.     // Tạo đề bài ngẫu nhiên
    3.     void CreateValueRandom(CCell cell[81])
    4.     {
    5.         // Khởi tạo mảng với 0
    6.         int arValue[81] =
    7.         {
    8.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    9.             0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,0,
    10.         };
    11.         // Bắt đầu lặp
    12.         Loop(0, arValue);
    13.         // Đã có được sắp xếp đúng trên toàn board
    14.         // Chúng ta chỉ việc xóa bớt một số ô là có đề bài hoàn chỉnh và đúng - chưa làm lúc này - còn chạy thử để kiểm tra.
    15.         // Thiết lập cho tất cả các ô
    16.         for (int i = 0; i < 81; i++)
    17.         {
    18.             int value = arValue[i];
    19.             cell[i].setValue(value);
    20.             cell[i].setHard(value);
    21.             cell[i].setTextColor(value ? m_crHardCell : m_crSoftCell);  // Màu Hard cho các ô đề bài, màu Soft cho các ô lời giải
    22.         }
    23.     }
    24.     // Hàm hoán vị
    25.     void Swap(int * p1, int * p2)
    26.     {
    27.         int temp = *p1; *p1 = *p2; *p2 = temp;
    28.     }
    29.     // Hàm kiểm tra chiều dọc
    30.     bool CheckVert(int value, int index, int arValue[81])
    31.     {
    32.         int col = index % 9;
    33.         for (int row = 0; row < 9; row++)
    34.             if (arValue[row * 9 + col] == value)
    35.                 return false;
    36.         return true;
    37.     }
    38.     // Hàm kiểm tra chiều ngang
    39.     bool CheckHorz(int value, int index, int arValue[81])
    40.     {
    41.         int row = index / 9;
    42.         for (int col = 0; col < 9; col++)
    43.             if (arValue[row * 9 + col] == value)
    44.                 return false;
    45.         return true;
    46.     }
    47.     // Hàm kiểm tra trên khối 3x3
    48.     bool CheckBlock(int value, int index, int arValue[81])
    49.     {
    50.         int row = index / 9, col = index % 9;
    51.         for (int r = row / 3 * 3, maxr = r + 3; r < maxr; r++)
    52.             for (int c = col - col % 3, maxc = c + 3; c < maxc; c++)
    53.                 if (arValue[r * 9 + c] == value)
    54.                     return false;
    55.         return true;
    56.     }
    57.     // Vòng lặp đệ quy tạo ra một sắp xếp đúng ngẫu nhiên
    58.     bool Loop(int iCur, int arValue[81])
    59.     {
    60.         if (iCur > 80)                      // Đã tới chỉ mục cuối - thành công
    61.             return true;
    62.         vector<int> values;                 // Tìm tập hợp các giá trị có thể gán vào chỉ mục hiện tại iCur
    63.         for (int i = 1; i < 10; i++)
    64.             if (CheckVert(i, iCur, arValue) && CheckHorz(i, iCur, arValue) && CheckBlock(i, iCur, arValue))
    65.                 values.push_back(i);
    66.         int size = (int)values.size();
    67.         if (!size)                          // Thất bại
    68.             return false;
    69.         if (size > 1)                       // Hoán vị ngẫu nhiên các giá trị trong tập hợp
    70.             for (int i = 0; i < size; i++)
    71.                 Swap(&values[rand() % size], &values[rand() % size]);
    72.         for (int i = 0; i < size; i++)
    73.         {
    74.             arValue[iCur] = values[i];      // Đi thử từng giá trị trong tập hợp
    75.             if (Loop(iCur + 1, arValue))    // Đệ quy sâu hơn
    76.                 return true;
    77.         }
    78.         arValue[iCur] = 0;                  // Quay lui
    79.         return false;                       // Không thành công ở node này
    80.     }
    81.     ///////////////////////////////// Hết các thuật toán tạo đề bài ///////////////////////////////////////////////////

    Vài thể hiện khi nhấn nút <Random>

    Attached Files Attached Files

  5. #5
    Ngày gia nhập
    02 2014
    Nơi ở
    TP.HCM
    Bài viết
    999

    Chơi như này thì nhà phát hành Sudoku chịu gì thấu



    Trao giải thưởng ngay lần đầu

    Attached Files Attached Files

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn