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

Đề tài: Thuật toán DLX (Dancing Link - Algorithm X) giải thích thế nào?

  1. #1
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Mặc định Thuật toán DLX (Dancing Link - Algorithm X) giải thích thế nào?

    Search google để tìm thuật toán giải Sudoku, để đưa vào phần mềm giải sudoku bằng webcam. Quét ảnh từ camera, sau đó giải, xuất kết quả trên màng hình. Ngặt nỗi, muốn nó chạy nhanh nhất. Search một hồi thì có thấy nhiều người bảo là dùng DLX. Mới nghe lần đầu, khá là lạ. :3 Sau đó search thì tìm thấy một số code impl thuật toán này. Nhưng đọc chẳng hiểu thuật toán đó ra sao???

    - Hiện tại thì đã tham khảo qua link này:
    __http://gieseanw.wordpress.com/2011/06/16/solving-sudoku-revisited/

    nhưng đọc không hiểu. Một phần do kém eng, một phần là ngu thuật toán. :v

    - Và đoạn code bên dưới, cái đầu tiên bị leak memory. Nhưng cái đầu sửa được cái thứ 2 thì thua. Vãi cái thuật toán.

    Bác nào có kiến thức uyên thâm về thuật toán thì xin giúp em thông não ạ. Hoặc gợi ý giúp em là cái thuật toán này thuộc loại nào. AI? Để tìm tài liệu, hoặc các bác chia sẻ thì cám ơn (tiếng Việt thì cám ơn rất nhiều ạ.) . Nghe nói đây là thuật toán cao cấp? :v

    C++ Code:
    1. #include <iostream>
    2. #include <vector>
    3. #include <iterator>
    4. #include <cstdint>
    5.  
    6. namespace dlx {
    7.  
    8. struct header;
    9.  
    10. /**
    11.   * Node structure.
    12.   * Take a note, that for performance reasons, no constructor is given, thus
    13.   * all members take default values.
    14.   */
    15. struct node {
    16.   header* head_; /**< Link to the current column's header */
    17.   node*   left_; /**< Node to the left */
    18.   node*  right_; /**< Node to the right */
    19.   node*     up_; /**< Node above */
    20.   node*   down_; /**< Node below */
    21. };
    22.  
    23.  
    24. /**
    25.  * Header structure.
    26.  * Take a note, that for performance reasons, no constructor is given, thus
    27.  * all members take default values.
    28.  */
    29. struct header:
    30.   public node {
    31.  
    32.   int size_; /**< Size, i.e. number of 1's in this column */
    33.   int name_; /**< Name of current header */
    34. };
    35.  
    36. /**
    37.  * Solves generalized exact cover problem using DLX algorithm.
    38.  * Single-threaded.
    39.  *
    40.  * @tparam _Derived Static polymorphism via CRTP. Used to return results
    41.  *         to user-defined functions.
    42.  */
    43.  
    44. template <typename _Derived>
    45. class solver {
    46. public:
    47.   solver(
    48.   ):headers_(1) // create master header
    49.   {}
    50.  
    51.   solver(const solver&);
    52.  
    53.   ~solver(
    54.   ) {
    55.     for (auto& i : headers_) {
    56.       node* c = i.up_;
    57.  
    58.       while (i.size_-- > 0) {
    59.         node* n = c->up_;
    60.         delete c;
    61.         c = n;
    62.       }
    63.     }
    64.   }
    65.  
    66.   template <typename _InIter>
    67.   void add_row(_InIter, _InIter);
    68.  
    69.   void set_column_number(std::uint32_t p, std::uint32_t s = 0);
    70.  
    71.   void search(std::uint32_t k = 0);
    72.  
    73.   const std::vector<node*> get_results(
    74.   ) {
    75.     return result_;
    76.   }
    77.  
    78.   /**
    79.    * Interface to user-defined function.
    80.    * Uses CRTP to achieve static-polymorphism. Calls user-defined method of the same
    81.    * name.
    82.    *
    83.    * To get results, user should:
    84.    *  - for every selected row i = 0, 1, ..., k-1
    85.    *  - for every kpfp::node *n = result_[i], result_[i]->right_, result_[i]->right_->right_... (until n==result_[i] again).
    86.    *  - get column number with n->head_->name_
    87.    *
    88.    * @param k Rows that cover the search-space.
    89.    */
    90.   void solution(
    91.     std::uint32_t k
    92.   ) {
    93.     static_cast<_Derived*>(this)->solution(k);
    94.   }
    95. protected:
    96.   void cover  (header*);
    97.   void uncover(header*);
    98.  
    99.   std::vector<header> headers_; /**< Headers. headers_[0] is master header. */
    100.   std::vector<node* >  result_; /**< Result vector. */
    101. };
    102.  
    103. /**
    104.  * Fills the search matrix.
    105.  * This method doesn't check assumptions. Each row shall contain numbers in range
    106.  * [1; p+s] (in ascending order) that indicate, in which columns are 1s.
    107.  *
    108.  * @attention set_column_number must be called first.
    109.  *
    110.  * @tparam _InIter Iterator type (as described in SGI's STL documentation).
    111.  * @param _first Iterator pointing to integers (each x: 0 < x <= p+s) in ascending order.
    112.  * @param _last Iterator's _last point.
    113.  * @see set_column_number
    114.  */
    115.  
    116. template <typename _Derived>
    117. template <typename _InIter>
    118. void solver<_Derived>::add_row(
    119.   _InIter _first,
    120.   _InIter _last
    121. ) {
    122.   node s; /* sentry */
    123.   s.right_ = &s;
    124.  
    125.   node *l = &s; /* node to the left */
    126.  
    127.   for(; _first != _last; ++_first) {
    128.     node* n = new node();
    129.    
    130.     int hN = *_first;
    131.  
    132.     ++headers_[hN].size_;
    133.        
    134.     n->head_  = &headers_[hN];
    135.     n->up_    =  headers_[hN].up_;
    136.     n->down_  = &headers_[hN];
    137.     n->left_  = l;
    138.  
    139.     l->right_ = n;
    140.  
    141.     headers_[hN].up_->down_ = n;
    142.     headers_[hN].up_ = n;
    143.     l = n;
    144.   }
    145.  
    146.   l->right_ = s.right_;
    147.   s.right_->left_ = l;
    148. }
    149.  
    150.  
    151. /**
    152.  * Set column count.
    153.  * Reserves required capacity for output and columns.
    154.  *
    155.  * @param p Primary columns
    156.  * @param s Secondary columns
    157.  */
    158. template <typename _Derived>
    159. void solver<_Derived>::set_column_number(
    160.   std::uint32_t p,
    161.   std::uint32_t s
    162. ) {
    163.   std::uint32_t sum = p + s;
    164.  
    165.   result_.resize(sum);
    166.   headers_.resize(sum + 1);
    167.  
    168.   headers_[0].right_ = &headers_[0];
    169.  
    170.   std::uint32_t i = 1;
    171.   for(; i <= p; ++i) {
    172.     headers_[i].left_ = &headers_[i - 1];
    173.     headers_[i].left_->right_ = &headers_[i];
    174.     headers_[i].up_ = headers_[i].down_ = &headers_[i];
    175.     headers_[i].name_ = i;
    176.   }
    177.  
    178.   headers_[p].right_ = &headers_[0];
    179.   headers_[0].left_  = &headers_[p];
    180.  
    181.   for(; i <= sum; ++i) {
    182.     headers_[i].left_ = headers_[i].right_ = headers_[i].up_ = headers_[i].down_ = &headers_[i];
    183.     headers_[i].name_ = i;
    184.   }
    185. }
    186.  
    187. template <typename _Derived>
    188. void solver<_Derived>::search(
    189.   std::uint32_t k
    190. ) {
    191.   header &m = headers_[0];
    192.  
    193.   if (m.right_ == &m && m.left_ == &m) { // termination condition
    194.     solution(k);
    195.     return;
    196.   }
    197.  
    198.   // select column (to minimize branching factor)
    199.   header *col = static_cast<header*>(m.right_);
    200.   int siz = col->size_;
    201.  
    202.   for (node *i = m.right_; i != static_cast<node*>(&m); i = i->right_) {
    203.     if (static_cast<header*>(i)->size_ < siz) {
    204.       col = static_cast<header*>(i);
    205.       siz = col->size_;
    206.     }
    207.   }
    208.  
    209.   cover(col); // cover column col
    210.  
    211.   for (node *row = col->down_; row != col; row = row->down_) { // for each row...
    212.    
    213.     result_[k] = row;
    214.     for (node *i = row->right_; i != row; i = i->right_) // for each column of this node...
    215.       cover(i->head_);
    216.  
    217.     search(k + 1);
    218.  
    219.     row = result_[k];
    220.     col = row->head_;
    221.  
    222.     for(node *i = row->left_; i != row; i = i->left_)
    223.       uncover(i->head_);
    224.   }
    225.  
    226.   uncover(col); //uncover column col
    227. }
    228.  
    229. template <typename _Derived>
    230. void solver<_Derived>::cover(
    231.   header *col
    232. ) {
    233.   col->right_->left_ = col->left_;
    234.   col->left_->right_ = col->right_;
    235.  
    236.   for (node* i = col->down_; i != static_cast<node*>(col); i = i->down_) {
    237.     for (node* j = i->right_; j != i; j = j->right_) {
    238.       j->down_->up_ = j->up_;
    239.       j->up_->down_ = j->down_;
    240.       --(j->head_->size_);
    241.     }
    242.   }
    243. }
    244.  
    245. template <typename _Derived>
    246. void solver<_Derived>::uncover(
    247.   header *col
    248. ) {
    249.   for (node* i = col->up_; i != static_cast<node*>(col); i = i->up_) {
    250.     for (node* j = i->left_; j != i; j = j->left_) {
    251.       ++(j->head_->size_);
    252.       j->down_->up_ = j;
    253.       j->up_->down_ = j;
    254.     }
    255.   }
    256.  
    257.   col->left_->right_ = col;
    258.   col->right_->left_ = col;
    259. }
    260.  
    261. }
    262.  
    263.  
    264. struct Printer:
    265.   public dlx::solver<Printer> {
    266.    
    267.   void solution(
    268.     std::uint32_t k
    269.   ) {
    270.     for(std::uint32_t i = 0; i < k; ++i) {
    271.       std::cout << '(' << result_[i]->head_->name_;
    272.      
    273.       for(dlx::node* n = result_[i]->right_; n != result_[i]; n = n->right_) {
    274.         std::cout << " " << n->head_->name_;
    275.       }
    276.  
    277.       std::cout << ") ";
    278.     }
    279.    
    280.     std::cout << std::endl;
    281.   }
    282. };
    283.  
    284.  
    285. int main() {
    286.   {
    287.     int cols, rows, currCols;
    288.     Printer a;
    289.  
    290.     std::cin >> cols >> rows;
    291.     std::cin.ignore();
    292.    
    293.     a.set_column_number(cols);
    294.  
    295.     while(rows--) {
    296.       std::cin >> currCols;
    297.       vector<int> cols;
    298.       int tmp;
    299.       while(currCols--) {
    300.         std::cin >> tmp;
    301.         std::cin.ignore();
    302.  
    303.         cols.push_back(tmp);
    304.       }
    305.       a.add_row(cols.begin(), cols.end());
    306.     }
    307.     a.search(0);
    308.   }
    309.   std::cin.get();
    310.   return 0;
    311. }

    C++ Code:
    1.  
    2. #include <iostream>
    3. #include <time.h>
    4. #define MAX_SUDOKU_IN_FILE 50000
    5. #define SOLUTION_LIMIT 100000
    6. #define BOX_WIDTH 3
    7. #define BOX_HEIGHT 3
    8. #define UNIT_SIZE (BOX_WIDTH * BOX_HEIGHT)
    9. #define GRID_SIZE (UNIT_SIZE * UNIT_SIZE)
    10. //#define COLNAMES
    11.  
    12. char sudokus[MAX_SUDOKU_IN_FILE][GRID_SIZE];
    13.  
    14. ///////////////////////
    15. // Forward declarations
    16. ///////////////////////
    17.  
    18. class head_t;
    19. class candidate_t;
    20. class cell_t;
    21.  
    22. ////////////////////
    23. // Class definitions
    24. ////////////////////
    25.  
    26. // Node class definition
    27. // Besides the constructors, there are no methods. Node data is only manipulated by other objects.
    28.  
    29. class node_t {
    30. protected:
    31.   // Protected node_t constructor for head_t
    32.   node_t(
    33.     bool is_head,
    34.     node_t* up,
    35.     node_t* down
    36.   ):is_head_  (is_head),
    37.     head_     (nullptr),
    38.     up_       (up),
    39.     down_     (down),
    40.     peer1_    (nullptr),
    41.     peer2_    (nullptr),
    42.     peer3_    (nullptr),
    43.     candidate_(nullptr)
    44.   {}
    45. public:
    46.   node_t(
    47.     head_t *head,
    48.     candidate_t *candidate
    49.   ):is_head_  (false),
    50.     head_     (head),
    51.     up_       (head->up_),
    52.     down_     (head),
    53.     peer1_    (nullptr),
    54.     peer2_    (nullptr),
    55.     peer3_    (nullptr),
    56.     candidate_(candidate)
    57.   {
    58.     up_->down_ = this;
    59.     down_->up_ = this;
    60.     head_->size_++;
    61.   }
    62.  
    63.   ~node_t() {}
    64.  
    65.   // The properties below are only used in detail nodes.
    66.   // They will not be set for header nodes.
    67.   bool  is_head_;
    68.   head_t*  head_;
    69.   node_t*    up_;
    70.   node_t*  down_;
    71.   node_t* peer1_;
    72.   node_t* peer2_;
    73.   node_t* peer3_;
    74.   candidate_t *candidate_;
    75. };
    76.  
    77.  
    78.  
    79. // Public constructor for detail nodes
    80. // Each node links a candidate to a column header
    81.  
    82. // Header class definition
    83.  
    84. class head_t:
    85.   public node_t {
    86. public:
    87.   head_t(
    88.   ):node_t(true, this, this),
    89.     is_root_(true),
    90.     size_(99),
    91.     left_(this),
    92.     right_(this)
    93.   {
    94. #ifdef COLNAMES
    95.     szName[0] = '\0';
    96.     strcat_s(szName, "root_");
    97. #endif
    98.   }
    99.  
    100.   // Constructor for a column header
    101.   // Each constraint (cell, row+digit, column+digit, box+digit) has a column header
    102.  
    103. #ifdef COLNAMES
    104.   char szName[40];
    105.   head_t(
    106.     head_t *root,
    107.     const char *fmt,
    108.     int d1,
    109.     int d2
    110.   ):
    111. #else
    112.   head_t(
    113.     head_t *root
    114.   ):
    115. #endif
    116.     node_t(true, this, this),
    117.     is_root_(false),
    118.     size_(0),
    119.     left_(root->left_),
    120.     right_(root)
    121.   {
    122. #ifdef COLNAMES
    123.     sprintf_s(szName, fmt, d1, d2);
    124. #endif
    125.     left_->right_ = this;
    126.     right_->left_ = this;
    127.   }
    128.  
    129.   ~head_t() {}
    130.  
    131.   // cover method.
    132.   // Removes the header from the linked list that connects _first to the root node.
    133.   // Removes the peers of all detail nodes below this header.
    134.  
    135.   void cover(
    136.   ) {
    137.     left_->right_ = right_;
    138.     right_->left_ = left_;
    139.    
    140.     for (node_t *b = down_; !b->is_head_ ; b = b->down_) {
    141.       b->peer1_->down_->up_ = b->peer1_->up_;
    142.       b->peer1_->up_->down_ = b->peer1_->down_;
    143.       b->peer1_->head_->size_--;
    144.      
    145.       b->peer2_->down_->up_ = b->peer2_->up_;
    146.       b->peer2_->up_->down_ = b->peer2_->down_;
    147.       b->peer2_->head_->size_--;
    148.      
    149.       b->peer3_->down_->up_ = b->peer3_->up_;
    150.       b->peer3_->up_->down_ = b->peer3_->down_;
    151.       b->peer3_->head_->size_--;
    152.     }
    153.   }
    154.  
    155.   // uncover method.
    156.   // Restores the peers of all detail nodes below this header.
    157.   // Reinserts the header in the linked list that connects _first to the root node.
    158.  
    159.   void uncover(
    160.   ) {
    161.     for (node_t *b = up_; !b->is_head_; b = b->up_) {
    162.       b->peer3_->down_->up_ = b->peer3_->up_->down_ = b->peer3_;
    163.       b->peer3_->head_->size_++;
    164.      
    165.       b->peer2_->down_->up_ = b->peer2_->up_->down_ = b->peer2_;
    166.       b->peer2_->head_->size_++;
    167.      
    168.       b->peer1_->down_->up_ = b->peer1_->up_->down_ = b->peer1_;
    169.       b->peer1_->head_->size_++;
    170.     }
    171.     left_->right_ = right_->left_ = this;
    172.   }  
    173.  
    174.   bool is_root_;
    175.   int     size_;
    176.   head_t*  left_;
    177.   head_t* right_;
    178. };
    179.  
    180.  
    181. // candidate_ class definition
    182. // This class links 4 nodes to a cell.
    183.  
    184. class candidate_t {
    185. public:
    186.   candidate_t(
    187.     cell_t*  _cell,
    188.     int     _dx
    189.   ):disabled_(false),
    190.     digit_   (_dx + 1),
    191.     cell_    (_cell  ),
    192.     cel_node_(nullptr),
    193.     row_node_(nullptr),
    194.     col_node_(nullptr),
    195.     box_node_(nullptr)
    196.   {}
    197.  
    198.   ~candidate_t(
    199.   ) {
    200.     delete cel_node_;
    201.     delete row_node_;
    202.     delete col_node_;
    203.     delete box_node_;
    204.   }
    205.  
    206.   // Disable candidate
    207.   // This happens when the associated cell is set to another digit.
    208.   // All detail nodes are disconnected from their respective column chains.
    209.  
    210.   void disable(
    211.   ) {
    212.     if (!disabled_) {
    213.       disabled_ = true;
    214.  
    215.       cel_node_->up_->down_ = cel_node_->down_;
    216.       cel_node_->down_->up_ = cel_node_->up_;
    217.       cel_node_->up_ = cel_node_->down_ = cel_node_;
    218.       cel_node_->head_->size_--;
    219.      
    220.       row_node_->up_->down_ = row_node_->down_;
    221.       row_node_->down_->up_ = row_node_->up_;
    222.       row_node_->up_ = row_node_->down_ = row_node_;
    223.       row_node_->head_->size_--;
    224.  
    225.       col_node_->up_->down_ = col_node_->down_;
    226.       col_node_->down_->up_ = col_node_->up_;
    227.       col_node_->up_ = col_node_->down_ = col_node_;
    228.       col_node_->head_->size_--;
    229.  
    230.       box_node_->up_->down_ = box_node_->down_;
    231.       box_node_->down_->up_ = box_node_->up_;
    232.       box_node_->up_ = box_node_->down_ = box_node_;
    233.       box_node_->head_->size_--;
    234.     }
    235.   }
    236.  
    237.   // Enable candidate
    238.   // This happens when the associated cell is cleared after the solver is finished.
    239.   // All detail nodes are reconnected to their respective column chains.
    240.  
    241.   void enable(
    242.   ) {
    243.     if (disabled_) {
    244.       box_node_->up_ = box_node_->head_->up_;
    245.       box_node_->down_ = box_node_->head_;
    246.       box_node_->up_->down_ = box_node_->down_->up_ = box_node_;
    247.       box_node_->head_->size_++;
    248.  
    249.       col_node_->up_ = col_node_->head_->up_;
    250.       col_node_->down_ = col_node_->head_;
    251.       col_node_->up_->down_ = col_node_->down_->up_ = col_node_;
    252.       col_node_->head_->size_++;
    253.      
    254.       row_node_->up_ = row_node_->head_->up_;
    255.       row_node_->down_ = row_node_->head_;
    256.       row_node_->up_->down_ = row_node_->down_->up_ = row_node_;
    257.       row_node_->head_->size_++;
    258.  
    259.       cel_node_->up_ = cel_node_->head_->up_;
    260.       cel_node_->down_ = cel_node_->head_;
    261.       cel_node_->up_->down_ = cel_node_->down_->up_ = cel_node_;
    262.       cel_node_->head_->size_++;
    263.  
    264.       disabled_ = false;
    265.     }
    266.   }
    267.  
    268.   bool   disabled_;
    269.   int       digit_;
    270.   cell_t*     cell_;
    271.   node_t* cel_node_;
    272.   node_t* row_node_;
    273.   node_t* col_node_;
    274.   node_t* box_node_;
    275. };
    276.  
    277. // cell_ class definition
    278. // Keeps track of the cell solving status and provides access to the candidates.
    279.  
    280. class cell_t {
    281. public:
    282.   cell_t(
    283.     int _index
    284.   ):given_     (0),
    285.     selected_  (0),
    286.     solution_  (0),
    287.     index_     (_index),
    288.     offset_row_(_index),
    289.     offset_col_((_index % UNIT_SIZE) * UNIT_SIZE),
    290.     offset_box_(_index + (_index % UNIT_SIZE) * BOX_HEIGHT),
    291.     candidates_(nullptr)
    292.   {
    293.     candidates_ = new candidate_t*[UNIT_SIZE];
    294.   }
    295.  
    296.   ~cell_t() {
    297.     delete[] candidates_;
    298.   }
    299.  
    300.   // Set the given digit for a cell.
    301.   // All other candidates are disabled as a result.
    302.   void set_given(
    303.     char digit
    304.   ) {
    305.     given_ = digit;
    306.     for (int dx = 0; dx < UNIT_SIZE; dx++) {
    307.       if (dx != (given_-1))
    308.         candidates_[dx]->disable();
    309.     }
    310.   }
    311.  
    312.   // Clear the given digit.
    313.   // All other candidates are enabled.
    314.   void clear_given(
    315.   ) {
    316.     for (int dx = UNIT_SIZE - 1; dx >= 0; dx--) {
    317.       if (dx != (given_ - 1))
    318.         candidates_[dx]->enable();
    319.     }
    320.     given_ = 0;
    321.   }
    322.  
    323.   int      given_;  // Nonzero for a cell with a given digit
    324.   int   selected_;  // Currently selected digit in the DLX algorithm
    325.   int   solution_;  // digit_ recorded in the (first) solution
    326.  
    327.   int      index_;
    328.   int offset_row_;
    329.   int offset_col_;
    330.   int offset_box_;
    331.  
    332.   candidate_t **candidates_;
    333. };
    334.  
    335. // Solver class
    336.  
    337. class solver_t   {
    338. public:
    339.   solver_t(
    340.   ):abort_         (false),
    341.     solution_count_(0),
    342.     solution_limit_(SOLUTION_LIMIT),    
    343.     root_          (new head_t())
    344.   {
    345.     // Initialize the column headers.
    346.     for(int n = 0; n < GRID_SIZE; ++n) {
    347.       cells_[n] = new cell_t(n);
    348. #ifdef COLNAMES
    349.       int un = (n/UNIT_SIZE)+1;
    350.       int dg = (n%UNIT_SIZE)+1;
    351.       hdr_cel_[n] = new head_t(root_, "cell_t row%dc%d"  , un, dg);
    352.       hdr_row_[n] = new head_t(root_, "Row %d digit %d", un, dg);
    353.       hdr_col_[n] = new head_t(root_, "Col %d digit %d", un, dg);
    354.       hdr_box_[n] = new head_t(root_, "Box %d digit %d", un, dg);
    355. #else
    356.       hdr_cel_[n] = new head_t(root_);
    357.       hdr_row_[n] = new head_t(root_);
    358.       hdr_col_[n] = new head_t(root_);
    359.       hdr_box_[n] = new head_t(root_);
    360. #endif
    361.     }
    362.  
    363.     for (int cx = 0; cx < GRID_SIZE; cx++) {
    364.       for (int dx = 0; dx < UNIT_SIZE; dx++) {
    365.         cells_[cx]->candidates_[dx] = new candidate_t(cells_[cx], dx);
    366.         cells_[cx]->candidates_[dx]->cel_node_ = new node_t(hdr_cel_[cx]                          , cells_[cx]->candidates_[dx]);
    367.         cells_[cx]->candidates_[dx]->row_node_ = new node_t(hdr_row_[cells_[cx]->offset_row_ + dx], cells_[cx]->candidates_[dx]);
    368.         cells_[cx]->candidates_[dx]->col_node_ = new node_t(hdr_col_[cells_[cx]->offset_col_ + dx], cells_[cx]->candidates_[dx]);
    369.         cells_[cx]->candidates_[dx]->box_node_ = new node_t(hdr_box_[cells_[cx]->offset_box_ + dx], cells_[cx]->candidates_[dx]);
    370.      
    371.         cells_[cx]->candidates_[dx]->cel_node_->peer1_ = cells_[cx]->candidates_[dx]->row_node_;
    372.         cells_[cx]->candidates_[dx]->cel_node_->peer2_ = cells_[cx]->candidates_[dx]->col_node_;
    373.         cells_[cx]->candidates_[dx]->cel_node_->peer3_ = cells_[cx]->candidates_[dx]->box_node_;
    374.      
    375.         cells_[cx]->candidates_[dx]->row_node_->peer1_ = cells_[cx]->candidates_[dx]->cel_node_;
    376.         cells_[cx]->candidates_[dx]->row_node_->peer2_ = cells_[cx]->candidates_[dx]->col_node_;
    377.         cells_[cx]->candidates_[dx]->row_node_->peer3_ = cells_[cx]->candidates_[dx]->box_node_;
    378.      
    379.         cells_[cx]->candidates_[dx]->col_node_->peer1_ = cells_[cx]->candidates_[dx]->cel_node_;
    380.         cells_[cx]->candidates_[dx]->col_node_->peer2_ = cells_[cx]->candidates_[dx]->row_node_;
    381.         cells_[cx]->candidates_[dx]->col_node_->peer3_ = cells_[cx]->candidates_[dx]->box_node_;
    382.      
    383.         cells_[cx]->candidates_[dx]->box_node_->peer1_ = cells_[cx]->candidates_[dx]->cel_node_;
    384.         cells_[cx]->candidates_[dx]->box_node_->peer2_ = cells_[cx]->candidates_[dx]->row_node_;
    385.         cells_[cx]->candidates_[dx]->box_node_->peer3_ = cells_[cx]->candidates_[dx]->col_node_;
    386.       }
    387.     }
    388.   }
    389.  
    390.   ~solver_t() {}
    391.  
    392.   int solve(
    393.     bool all
    394.   ) {
    395.     if (!all)
    396.       solution_limit_ = 2;
    397.    
    398.     abort_ = false;
    399.     solution_count_ = 0;
    400.  
    401.     recurse();
    402.  
    403.     return solution_count_;
    404.   }  
    405. private:
    406.   void recurse(
    407.   ) {
    408.     // Increment solution count when all Heads are covered.
    409.     if (root_->right_->is_root_) {
    410.       if (solution_count_ == 0) {
    411.         for (int cx = 0; cx < GRID_SIZE; cx++)
    412.           cells_[cx]->solution_ = cells_[cx]->selected_;
    413.       }
    414.      
    415.       abort_ = solution_count_++ >= solution_limit_;
    416.       return;
    417.     }
    418.  
    419.     // Find the smallest size with CHeads attached
    420.     head_t *col = root_->right_;
    421.    
    422.     if (col->size_ > 1) {
    423.       for (head_t *col = col->right_; !col->is_root_; col = col->right_) {
    424.         if (col->size_ < col->size_) {
    425.           col = col;
    426.           if (col->size_ <= 1)
    427.             break;
    428.         }
    429.       }
    430.     }
    431.    
    432.     // Skip processing rows for a size 0 column.
    433.     if (col->size_ == 0)
    434.       return;
    435.    
    436.     // cover the selected column once, so _first does not need to be covered for each row.
    437.     col->cover();
    438.    
    439.     // Process each row below this column.
    440.     for (node_t *rn = col->down_; !rn->is_head_; rn = rn->down_) {
    441.       // cover the columns for the 3 peer nodes.
    442.       rn->candidate_->cell_->selected_ = rn->candidate_->digit_;
    443.  
    444.       rn->peer1_->head_->cover();
    445.       rn->peer2_->head_->cover();
    446.       rn->peer3_->head_->cover();
    447.  
    448.       // Next recursion level.
    449.       recurse();
    450.  
    451.       // uncover the columns for the 3 peer nodes.
    452.       rn->peer3_->head_->uncover();
    453.       rn->peer2_->head_->uncover();
    454.       rn->peer1_->head_->uncover();
    455.  
    456.       // Abort further processing when multiple solutions were found.
    457.       if (abort_)
    458.         break;
    459.     } // Next row node
    460.    
    461.     // uncover the selected column header.
    462.     col->uncover();
    463.   }
    464.  
    465.   bool           abort_;
    466.   int   solution_count_;
    467.   int   solution_limit_;
    468.  
    469.   head_t* root_;
    470.   head_t* hdr_cel_[GRID_SIZE];
    471.   head_t* hdr_row_[GRID_SIZE];
    472.   head_t* hdr_col_[GRID_SIZE];
    473.   head_t* hdr_box_[GRID_SIZE];
    474. public:
    475.   cell_t*   cells_[GRID_SIZE];
    476. };
    477.  
    478. int ReadSudokus(
    479.   const char *filename
    480. ) {
    481.   FILE *input;
    482.  
    483.   // Open file explicitly in binary mode, otherwise the CRLF characters are converted to LF
    484.   // and the file length is returned incorrectly.
    485.  
    486.   if (fopen_s(&input, filename, "rb") != 0)
    487.     return 0;
    488.  
    489.   fseek(input, 0L, SEEK_END);    // Position to _last of file
    490.   long lFileLen = ftell(input);  // Get file length
    491.   rewind(input);                 // Back to start of file
    492.  
    493.   char *cFile = (char *) calloc(lFileLen + 1, sizeof(char));
    494.   if(cFile == NULL)
    495.     return 0;       // Not enough memory
    496.   fread(cFile, lFileLen, 1, input); // Read the file into a character buffer
    497.   fclose(input);
    498.  
    499.   int puzzleIndex = 0;
    500.   int cellIndex = 0;
    501.   bool comment = false;
    502.   char *cRead = cFile;
    503.  
    504.   while (*cRead) {
    505.     switch (*cRead) {
    506.     case 10: // LF character
    507.     case 13: // CR character
    508.       if (cellIndex == GRID_SIZE)
    509.         ++puzzleIndex;
    510.       cellIndex = 0;
    511.       comment = false;
    512.       break;
    513.     case 26: // DOS EOF character. Not used often, but renders remainder of file invalid.
    514.       if (cellIndex == GRID_SIZE)
    515.         ++puzzleIndex;
    516.       return puzzleIndex;
    517.     case '#': // Comment character. Ignore remainder of this line.
    518.       comment = true;
    519.       break;
    520.     default:
    521.       if (!comment && (cellIndex < GRID_SIZE)) {
    522.         if ((*cRead > 48) && (*cRead < 58))                    // Digits 1-9
    523.           sudokus[puzzleIndex][cellIndex++] = *cRead - 48;
    524.         else if (*cRead == '0' || *cRead == '.')
    525.           sudokus[puzzleIndex][cellIndex++] = 0;
    526.       }
    527.     }
    528.     ++cRead;
    529.   }
    530.   return puzzleIndex;
    531. }
    532.  
    533. int main(int argc, char *argv[])
    534. {
    535.    char *filename = "testfile.sdm";
    536.    if (argc>=2) filename = argv[1];
    537.  
    538.    int rounds = ReadSudokus(filename);
    539.  
    540.    solver_t solver;
    541.  
    542.    clock_t start, finish;
    543.    start = clock();
    544.  
    545.    for(int j = 0; j < rounds; j++) {
    546.  
    547.       for (int i = 0; i < GRID_SIZE; i++) if (sudokus[j][i]) solver.cells_[i]->set_given(sudokus[j][i]);
    548.  
    549.       // Change this call to solve(true) if you really want to know the number of solutions.
    550.       // solve(false) returns 2 for all problems with multiple solutions, but _first is a lot faster.
    551.  
    552.       int DLX_sol = solver.solve(false);
    553.  
    554.       for (int i = GRID_SIZE-1; i >= 0; i--) if (sudokus[j][i]) solver.cells_[i]->clear_given();
    555.  
    556.     }
    557.    finish = clock();
    558.    printf("time: %2.3f sec\n",(double)(finish - start)/CLOCKS_PER_SEC);
    559.    printf("%d problems processed!\n", rounds);
    560.    return(0);
    561. }
    Đã được chỉnh sửa lần cuối bởi doicanhden : 29-05-2013 lúc 11:12 AM.
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  2. #2
    Ngày gia nhập
    12 2012
    Nơi ở
    TIN5A - UNETI
    Bài viết
    167

    bạn làm cái khó thế

  3. #3
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Hiện tại thì chưa tìm thấy impl nào của giải thuật này mà toàn vẹn cả. Hầu hết cái nào cũng có leak memory. :( Muốn tìm hiểu để tự impl một cái khác, nhưng đếch hiểu nổi.
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  4. #4
    Ngày gia nhập
    07 2011
    Bài viết
    474

    thử cái python này xem :-" Ta cũng ko à chưa hiểu mặc dù sưu tầm lâu rồi :">



    Python Code:
    1. # Sudoku solver for Udacity CS258.
    2.  
    3. def get_groups():
    4.     q = lambda f:[[f(i,j) for j in range(9)] for i in range(9)]
    5.     return q(lambda i,j:(i,j)) + q(lambda i,j:(j,i)) + q(lambda i,j:(i/3*3+j/3,i%3*3+j%3))
    6.     # I think this is more readable than the one-liner:
    7.     # >> return [l for i in range(9) for l in zip(*[[(i,j),(j,i),(i/3*3+j/3,i%3*3+j%3)] for j in range(9)])]
    8.  
    9. def check_sudoku(grid):
    10.     if len(grid) != 9: return None
    11.     if set(map(len,grid)) != set([9]): return None
    12.     if min(map(min,grid)) < 0: return None
    13.     if max(map(max,grid)) > 9: return None
    14.     for s in get_groups():
    15.         l = filter(None,[grid[i][j] for i,j in s])
    16.         if len(l) != len(set(l)): return False
    17.     return True
    18.  
    19. def solve_sudoku (grid):
    20.     check = check_sudoku(grid)
    21.     if not check: return check
    22.     grid = [row[:] for row in grid]
    23.     groups = get_groups()
    24.     pairs = [[set(t for s in groups if (i,j) in s for t in s) for j in range(9)] for i in range(9)]
    25.     def go(x,y):
    26.         if y==9: return True
    27.         if grid[y][x]: return go((x+1)%9,y+x/8)
    28.         for o in set(range(1,10)) - set(grid[i][j] for (i,j) in pairs[y][x]):
    29.             grid[y][x] = o
    30.             if go((x+1)%9,y+x/8): return True
    31.         grid[y][x] = 0
    32.     return grid if go(0,0) else False
    33.  
    34.  
    35. def print_sudoku(grid):
    36.     r = 0
    37.     for row in grid:
    38.         r += 1
    39.         row_line = '{0} {1} {2}   {3} {4} {5}   {6} {7} {8}'
    40.         print row_line.format(*row)
    41.         if not r%3: print ''
    42.  
    43. # test case
    44. grid = [[5,0,0,0,0,0,0,0,0],
    45.         [8,0,2,0,3,0,0,0,0],
    46.         [3,0,0,0,0,4,9,0,0],
    47.         [0,0,0,6,0,0,8,0,0],
    48.         [0,0,0,4,0,7,0,0,0],
    49.         [0,0,7,0,0,8,0,0,0],
    50.         [0,0,8,7,0,0,0,0,9],
    51.         [0,0,0,0,6,0,4,0,5],
    52.         [0,0,0,0,0,0,0,0,0]]
    53.  
    54. grid = solve_sudoku(grid)
    55. print_sudoku(grid)
    56.  
    57. # chay thu
    58. '''
    59. import pprint
    60.  
    61. grid = []
    62. i = 0
    63. while i < 9:
    64.    row = ''
    65.    while len(row) != 9:
    66.        row = raw_input('Row ' + str(i+1) + ": ")
    67.    grid.append([int(c) for c in row])
    68.    i = i + 1
    69. '''

  5. #5
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Trích dẫn Nguyên bản được gửi bởi INTP Xem bài viết
    thử cái python này xem :-" Ta cũng ko à chưa hiểu mặc dù sưu tầm lâu rồi :">
    Python Code:
    1. def solve_sudoku (grid):
    2. ......
    3.     def go(x,y): //<------------- Tôi nghĩ là py cho phép định nghĩa hàm trong hàm, giống javascript.
    4. .........
    5.             grid[y][x] = o // <------------- Đánh dấu.
    6.             if go((x+1)%9,y+x/8): return True //<-------- Gọi đệ quy.
    7.         grid[y][x] = 0 // <----------- Bỏ đánh dấu.
    8. .........
    Không biết py, nhưng xem qua code thì đây chỉ là giải thuật backtracking bình thường. Chẳng có gì để nói. :3.
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  6. #6
    Ngày gia nhập
    10 2006
    Nơi ở
    In Your Bugs
    Bài viết
    823

    Mặc định Thuật toán DLX (Dancing Link - Algorithm X) giải thích thế nào?

    Hi DoiCanhDen,

    Trước mình giải sudoku, nhưng thời sinh viên thì cũng chỉ backtracking với chút AI để cắt nhánh.
    Bạn có trang mô tả giải thuật ko ?

    Sudoku 9x9 thì ko tốn mem lắm, rẽ nhánh cũng ko nhiều nên backtracking chạy khá ổn.
    Nếu bạn viết mobile thì có thể test backtracking thử mình nghĩ nó cũng khá nhanh. Nếu ko bạn có thể dựng service rồi gởi request để giải giúp cũng ok.

  7. #7
    Ngày gia nhập
    04 2010
    Nơi ở
    Binh Thanh, Hồ Chí Minh, Vietnam, Vietnam
    Bài viết
    504

    Trích dẫn Nguyên bản được gửi bởi kidkid Xem bài viết
    Hi DoiCanhDen,

    Trước mình giải sudoku, nhưng thời sinh viên thì cũng chỉ backtracking với chút AI để cắt nhánh.
    Bạn có trang mô tả giải thuật ko ?

    Sudoku 9x9 thì ko tốn mem lắm, rẽ nhánh cũng ko nhiều nên backtracking chạy khá ổn.
    Nếu bạn viết mobile thì có thể test backtracking thử mình nghĩ nó cũng khá nhanh. Nếu ko bạn có thể dựng service rồi gởi request để giải giúp cũng ok.
    Mình có tìm thấy một vài link:
    __http://gieseanw.wordpress.com/2011/06/16/solving-sudoku-revisited/
    __http://members.inode.at/w.laun/backtrack/backtrack.html
    __http://en.wikipedia.org/wiki/Knuth's_Algorithm_X
    __http://kunigami.wordpress.com/2013/04/28/the-algorithm-x-and-the-dancing-links/
    __http://www.slideshare.net/ljsking/dancing-links-11376810
    __http://cgi.cse.unsw.edu.au/~xche635/dlx_sodoku/
    Nhưng mày mò thì không hiểu gốc gác của cái thuật toán, nhiều cái chỉ giải thích phần liên quan đến Sudoku là nhiều. Mình cần cả phần mô tả rõ về thuật toán, ứng dụng...

    Algorithm DLX = Dancing Links + Algorithm X.

    Dancing Links: __http://www.scribd.com/doc/65645552/DLX
    Algorithm X: __http://en.wikipedia.org/wiki/Knuth's_Algorithm_X
    Đã được chỉnh sửa lần cuối bởi doicanhden : 29-05-2013 lúc 03:20 PM.
    Kết bạn với tôi <3
    Skype: giautm
    Facebook:
    https://fb.com/giautm.duongntt
    Email:
    giau.tmg@gmail.com

  8. #8
    Ngày gia nhập
    11 2010
    Bài viết
    589

    @doicanhden: đọc cho kỹ cái link cuối cùng. Có đoạn không hiểu thì đem lên đây.
    Ngày trước mình cũng đọc trên đó nhưng mà giờ lười giải thích đầy đủ quá.


    Tóm tắt cái link:
    - Giới thiệu về bài toán Extract Cover
    - Sử dụng algorithm X để giải bài toàn extract cover
    - Sử dụng kỹ thuật dancing link trong cài đặt thuật toán X. (Dancing link không phải là 1 thuật toán)
    - Đưa bài toán Sodoku về bài toán Extract Cover, giải bằng các phương pháp như trên.


    Đây cũng là thuật toán đệ quy quay lui như bình thường thôi, nhưng không gian vét cạn ít hơn (do việc đưa về extract cover), và thực hiện nhanh hơn do sử dụng dancing link.

    Tặng thêm cái dancing link không đệ quy:

    C++ Code:
    1. // =====================================================================================
    2. //
    3. //       Filename:  sodoku_dlx.cc
    4. //
    5. //    Description:  
    6. //
    7. //        Version:  1.0
    8. //        Created:  07/04/2012 04:28:34 PM
    9. //       Revision:  none
    10. //       Compiler:  g++
    11. //
    12. //         Author:  YOUR NAME (), boss14420@gmail.com
    13. //        Company:  
    14. //
    15. // =====================================================================================
    16.  
    17. #include <iostream>
    18. #include <fstream>
    19. #include <cstdlib>
    20. #include <ctime>
    21.  
    22. #define SIZE 9
    23. #define SQRT_SZ 3
    24. #define SQ_SZ (SIZE*SIZE)
    25.  
    26. #define COLS (SIZE*SIZE*4)
    27. #define ROWS (SIZE*SIZE*SIZE)
    28.  
    29. #define SQ_OFFSET 0
    30. #define RW_OFFSET (SIZE*SIZE)
    31. #define CL_OFFSET (2*RW_OFFSET)
    32. #define BX_OFFSET (3*RW_OFFSET)
    33.  
    34.  
    35. struct node {
    36.     node *left, *right, *up, *down;
    37.     node* head;
    38.     int idx;
    39. };
    40.  
    41. node Column[COLS];
    42. node *Row[ROWS];
    43. node ObjectPool[SIZE*COLS];
    44. node RootNode;
    45. int Result[SQ_SZ];
    46. size_t nResult = 0;
    47.  
    48. // Functions that extract data from a given 3-digit integer index number in the format [N] [R] [C].
    49. inline int retNb(int N) { return N/SQ_SZ; }
    50. inline int retRw(int N) { return (N/SIZE)%SIZE; }
    51. inline int retCl(int N) { return N%SIZE; }
    52. inline int retBx(int N) { return ((retRw(N)/SQRT_SZ)*SQRT_SZ) + (retCl(N)/SQRT_SZ); }
    53. inline int retSq(int N) { return retRw(N)*SIZE + retCl(N); }
    54. inline int retRn(int N) { return retNb(N)*SIZE + retRw(N); }
    55. inline int retCn(int N) { return retNb(N)*SIZE + retCl(N); }
    56. inline int retBn(int N) { return retNb(N)*SIZE + retBx(N); }
    57. // Function that get 3-digit integer index from given info
    58. inline int getCand(int Nb, int Rw, int Cl) { return Nb*SQ_SZ+ Rw*SIZE + Cl; }
    59.  
    60.  
    61. void BuildMatrix() {
    62.     node *LastCandidate[COLS];
    63.     for(int i = 0; i != COLS; ++i) {
    64.         LastCandidate[i] = &Column[i];
    65.         Column[i].up = &Column[i];
    66.         Column[i].down = &Column[i];
    67.         Column[i].head = &Column[i];
    68. //        Column[i].size = 0;
    69.     }
    70.  
    71.     Column[0].left = &RootNode, RootNode.right = &Column[0];
    72.     for(int i = 1; i != COLS; ++i) {
    73.         Column[i].left = &Column[i-1];
    74.         Column[i-1].right = &Column[i];
    75.     }
    76.     Column[COLS-1].right = &RootNode, RootNode.left = &Column[COLS-1];
    77.  
    78.     node *nds = ObjectPool;
    79.     for(int a = 0; a != SIZE; ++a)
    80.         for(int b = 0; b != SIZE; ++b)
    81.             for(int c = 0; c != SIZE; ++c) {
    82.                 int Candidate = getCand(c,a,b);
    83.                
    84.                 node **tmp;
    85.                
    86.                 //Constraint 1: Only 1 per square
    87.                 Row[Candidate] = nds;
    88.                 nds->left = nds+3, (nds+3)->right = nds;
    89.                 tmp = &LastCandidate[SQ_OFFSET + retSq(Candidate)];
    90.                 nds->head = (*tmp)->head;//, ++nds->head->size;
    91.                 nds->up = *tmp, (*tmp)->down = nds, *tmp = nds, nds->idx = Candidate;
    92.                
    93.                 //Constraint 2: Only 1 of per number per Row
    94.                 tmp = &LastCandidate[RW_OFFSET + retRn(Candidate)];
    95.                 nds->right = nds+1, (nds+1)->left = nds, ++nds;
    96.                 nds->head = (*tmp)->head;//, ++nds->head->size;
    97.                 nds->up = *tmp, (*tmp)->down = nds, *tmp = nds, nds->idx = Candidate;
    98.                
    99.                 //Constraint 3: Only 1 of per number per Column
    100.                 tmp = &LastCandidate[CL_OFFSET + retCn(Candidate)];
    101.                 nds->right = nds+1, (nds+1)->left = nds, ++nds;
    102.                 nds->head = (*tmp)->head;//, ++nds->head->size;
    103.                 nds->up = *tmp, (*tmp)->down = nds, *tmp = nds, nds->idx = Candidate;
    104.                
    105.                 //Constraint 4: Only 1 of per number per Box
    106.                 tmp = &LastCandidate[BX_OFFSET + retBn(Candidate)];
    107.                 nds->right = nds+1, (nds+1)->left = nds, ++nds;
    108.                 nds->head = (*tmp)->head;//, ++nds->head->size;
    109.                 nds->up = *tmp, (*tmp)->down = nds, *tmp = nds,
    110.                     nds->idx = Candidate, nds++;
    111.             }
    112.  
    113.     for(int i = 0; i != COLS; ++i) {
    114.         Column[i].up = LastCandidate[i];
    115.         LastCandidate[i]->down = &Column[i];
    116.     }
    117. }
    118.  
    119. void Cover(node* colnode) {
    120.     colnode->left->right = colnode->right;
    121.     colnode->right->left = colnode->left;
    122.     node *rownode, *rightnode;
    123.     for(rownode = colnode->down; rownode != colnode; rownode = rownode->down) {
    124. //        rownode->down->up = rownode->up, rownode->up->down = rownode->down;
    125.         for(rightnode = rownode->right; rightnode != rownode; rightnode=rightnode->right) {
    126.             rightnode->up->down = rightnode->down;
    127.             rightnode->down->up = rightnode->up;
    128.         }
    129.     }
    130. }
    131.  
    132. void UnCover(node* colnode) {
    133.     node *rownode, *rightnode;
    134.     for(rownode = colnode->down; rownode != colnode; rownode = rownode->down) {
    135.         for(rightnode = rownode->right; rightnode != rownode; rightnode=rightnode->right) {
    136.             rightnode->up->down = rightnode;
    137.             rightnode->down->up = rightnode;
    138.         }
    139. //        rownode->down->up = rownode, rownode->up->down = rownode;
    140.     }
    141.     colnode->left->right = colnode;
    142.     colnode->right->left = colnode;
    143. }
    144.  
    145. void PrintResult();
    146.  
    147. // Co su dung de quy
    148. void Solve() {
    149.     if(RootNode.right == &RootNode) {
    150.         if(nResult == SQ_SZ)
    151.             PrintResult();
    152.         return;
    153.     }
    154.  
    155.     node *min_col = RootNode.right;
    156.  
    157.     Cover(min_col);
    158.     node* candidate = min_col->down, *rightnode;
    159.     for(; candidate != min_col; candidate = candidate->down) {
    160.         // Cover 3 other col
    161.         rightnode = candidate->right;
    162.         for(; rightnode != candidate; rightnode = rightnode->right)
    163.             Cover(rightnode->head);
    164.        
    165.         Result[nResult++] = candidate->idx;
    166.         Solve(); // Recursive
    167.         Result[--nResult] = 0;
    168.  
    169.         rightnode = candidate->right;
    170.         for(; rightnode != candidate; rightnode = rightnode->right)
    171.             UnCover(rightnode->head);
    172.     }
    173.     UnCover(min_col);
    174. }
    175.  
    176. // Khong su dung de quy
    177. void Solve2() {
    178.     node *first_col = NULL;
    179.     node *curr_cdd, *rightnode;
    180.     node *Candidates[SQ_SZ] = { NULL };
    181.     size_t const K = nResult;
    182.    
    183.     if(RootNode.right == &RootNode) {
    184.         if(nResult == SQ_SZ)
    185.             PrintResult();
    186.         return;
    187.     }
    188.    
    189.     curr_cdd = first_col = RootNode.right;
    190.     Cover(first_col);
    191.  
    192.     while(true) {
    193.         if( (Candidates[nResult] = curr_cdd = curr_cdd->down) != first_col ) {
    194.             // Cover 3 other cols
    195.             rightnode = curr_cdd->right;
    196.             for(; rightnode != curr_cdd; rightnode = rightnode->right)
    197.                 Cover(rightnode->head);
    198.  
    199.             Result[nResult] = curr_cdd->idx;
    200.             if(RootNode.right != &RootNode) {
    201.                 ++nResult;
    202.                 curr_cdd = first_col = RootNode.right;
    203.                 Cover(first_col);
    204.             } else {
    205.                 if(nResult == SQ_SZ - 1)
    206.                     PrintResult();
    207.  
    208.                 // UnCover
    209.                 rightnode = curr_cdd->right;
    210.                 for(; rightnode != curr_cdd; rightnode = rightnode->right)
    211.                     UnCover(rightnode->head);
    212.             }
    213.  
    214.            
    215.         } else if(nResult > K) {
    216.             UnCover(first_col);
    217.  
    218.             curr_cdd = Candidates[--nResult];
    219.             // UnCover
    220.             rightnode = curr_cdd->right;
    221.             for(; rightnode != curr_cdd; rightnode = rightnode->right)
    222.                 UnCover(rightnode->head);
    223.  
    224.             Cover(first_col = curr_cdd->head);
    225.         } else
    226.             break;
    227.     }
    228. }
    229.  
    230. void PrintResult() {
    231.     int Matrix[SIZE][SIZE];
    232.     for(int a = 0; a != SIZE; ++a)
    233.         for(int b = 0; b != SIZE; ++b)
    234.             Matrix[a][b] = -1;
    235.  
    236.     for(int i = 0; i != SQ_SZ; ++i) {
    237.         int idx = Result[i];
    238.         Matrix[retRw(idx)][retCl(idx)] = retNb(idx);
    239.     }
    240.  
    241.     std::cout << "------------- Solution found -------------\n";
    242.  
    243. //    for(int a=0;a<SIZE;a++) {
    244. //        for(int b=0;b<SIZE;b++) {
    245. //            if(a>0&&a%SQRT_SZ==0&&b==0) { for(int c=0;c<SIZE;c++) std::cout << "--"; std::cout << '\n';} //horizontal lines
    246. //            if(Matrix[a][b]>=0) std::cout << Matrix[a][b]+1 << (b%SQRT_SZ==SQRT_SZ-1?'|':' ');
    247. //            else std::cout << ". ";
    248. //        }
    249. //        std::cout << '\n';
    250. //    }
    251.     for(int a = 0; a < SIZE; ++a) {
    252.         for(int b = 0; b < SIZE; ++b) {
    253.             std::cout << Matrix[a][b] + 1<< ' ';
    254.         }
    255.         std::cout << '\n';
    256.     }
    257.  
    258.     std::exit(0);
    259. }
    260.  
    261. void AddNumber(int r, int c, int number) {
    262. //    for(int i = 0; i != number; ++i)
    263. //        Disable(Row[getCand(i, r, c)]);
    264. //    for(int i = number + 1; i != SIZE; ++i)
    265. //        Disable(Row[getCand(i, r, c)]);
    266.     int idx = getCand(number, r, c);
    267.     node *rownode = Row[idx], *rightnode = rownode->right;
    268.     Cover(rownode->head);
    269.     for(; rightnode != rownode; rightnode = rightnode->right)
    270.         Cover(rightnode->head);
    271.     Result[nResult++] = idx;
    272. }
    273.  
    274. void LoadSudoku(std::istream& is) {
    275.     int number;
    276.     for(int a = 0; a != SIZE; ++a)
    277.         for(int b = 0; b != SIZE; ++b) {
    278.             is >> number;
    279.             if( (number > 0) && (number <= SIZE) )
    280.                 AddNumber(a, b, number - 1);
    281.         }
    282. }
    283.  
    284. int main(int argc, char *argv[]) {
    285. //    std::cout.sync_with_stdio(false);
    286.  
    287.     BuildMatrix();
    288.    
    289.     if(argc > 1) {
    290.         std::ifstream f(argv[1]);
    291.         LoadSudoku(f);
    292.         f.close();
    293.     } else LoadSudoku(std::cin);
    294.  
    295.     Solve2();
    296.  
    297.     return 0;
    298. }

    Một ví dụ đầu vào (xuât thành file gì đó, gs sdk.txt)
    Code:
    9 0 0 0 0 1 8 0 0
    0 6 0 0 3 0 0 0 0
    0 0 2 5 0 0 0 0 7
    0 0 9 0 0 0 0 0 6
    0 5 0 0 0 0 0 2 0
    4 0 0 0 0 0 3 0 0
    3 0 0 0 0 8 0 0 0
    0 0 0 0 4 0 0 0 0
    0 0 7 9 0 0 0 0 0
    Chạy:
    Code:
    ./sodoku sdk.txt
    Kết quả:
    Code:
    ------------- Solution found -------------
    9 3 4 2 7 1 8 6 5 
    7 6 5 8 3 4 1 9 2 
    1 8 2 5 6 9 4 3 7 
    2 1 9 3 8 5 7 4 6 
    6 5 3 4 1 7 9 2 8 
    4 7 8 6 9 2 3 5 1 
    3 4 6 1 2 8 5 7 9 
    5 9 1 7 4 6 2 8 3 
    8 2 7 9 5 3 6 1 4
    Đã được chỉnh sửa lần cuối bởi boss14420 : 29-05-2013 lúc 10:05 PM.

  9. #9
    Ngày gia nhập
    04 2013
    Nơi ở
    $HOME
    Bài viết
    48

    Mình thấy bài báo của D.E. Knuth (http://arxiv.org/abs/cs/0011047) giải thích rất kĩ càng thuật toán X để tìm lời giải cho bài toán exact cover, cũng như việc sử dụng dancing links (circular, double links) để làm cho việc cài đặt thuật toán X được nhanh hơn.

    Việc chuyển đổi từ bài toán Sudoku sang bài toán exact cover được nói trong bài ở trên Wikipedia. Đoạn giải thích trong bài này http://www.ams.org/samplings/feature-column/fcarc-kanoodle cũng khá dễ hiểu, nếu bạn muốn tìm hiểu thêm.

  10. #10
    Ngày gia nhập
    04 2013
    Nơi ở
    $HOME
    Bài viết
    48

    Đây là code của mình, làm theo cách làm như trong bài báo của Knuth và tham khảo code của bạn boss.

    C++ Code:
    1. #include <cstdio>
    2. #include <cstdlib>
    3. #include <cctype>
    4.  
    5. #define BOX_SIZE    3
    6. #define TABLE_SIZE  9
    7.  
    8. class Node {
    9. public:
    10.     Node() {left = right = up = down = this;}
    11.  
    12.     Node *left, *right, *up, *down;
    13.     int  head;      // index of the head node in array root (declared below)
    14.     int  digit;     // digit to be filled in the Sudoku table
    15. };
    16.  
    17. class HeadNode : public Node {
    18. public:
    19.     HeadNode() : Node() {count = 0;}
    20.    
    21.     int count;  // number of nodes in the column pointed to by this head node
    22. };
    23.  
    24. /* Array root represents the matrix for the exact cover problem converted from a Sudoku puzzle.  */
    25. HeadNode root[4 * (TABLE_SIZE * TABLE_SIZE)];
    26.  
    27. /* Array sudoku contains answer digits for the input Sudoku puzzle.  */
    28. int sudoku[TABLE_SIZE][TABLE_SIZE];
    29.  
    30. void
    31. print_sudoku()
    32. {
    33.     for (int i = 0; i < TABLE_SIZE; ++i) {
    34.         for (int j = 0; j < TABLE_SIZE; ++j) {
    35.             printf(" %d", sudoku[i][j]);
    36.         }
    37.         printf("\n");
    38.     }
    39. }
    40.  
    41. /* The function updates the array sudoku when a particular row in the matrix
    42.  * represented by root is chosen.  */
    43. void
    44. fill_sudoku(Node *p)
    45. {
    46.     /* Get to the node in the row corresponding to a cell constraint.  */
    47.     while (p->head >= (TABLE_SIZE * TABLE_SIZE)) p = p->right;
    48.    
    49.     int i = p->head / TABLE_SIZE;   // #row of the cell in the Sudoku table
    50.     int j = p->head % TABLE_SIZE;   // #column of the cell in the Sudoku table
    51.     sudoku[i][j] = p->digit;
    52. }
    53.  
    54. /* The function reads a Sudoku puzzle and converts it into an equivalent exact
    55.  * cover problem by initializing the array root of head nodes.  */
    56. void
    57. build_xcsudoku(char *filename)
    58. {
    59.     /* Implementation not given.  */
    60. }
    61.  
    62. /* The function picks a column to cover it.  */
    63. HeadNode *
    64. pick_column()
    65. {
    66.     return (HeadNode *) root->right;
    67. }
    68.  
    69. void
    70. cover_column(HeadNode *c)
    71. {
    72.     /* Remove c from the list of header nodes.  */
    73.     c->right->left = c->left;
    74.     c->left->right = c->right;
    75.  
    76.     /* Remove rows in the row list of c from columns intersecting with them.  */
    77.     for (Node *r = c->down; r != c; r = r->down) {
    78.         for (Node *p = r->right; p != r; p = p->right) {
    79.             p->up->down = p->down;
    80.             p->down->up = p->up;
    81.  
    82.             root[p->head].count--;
    83.         }
    84.     }
    85. }
    86.  
    87. void
    88. uncover_column(HeadNode *c)
    89. {
    90.     /* Insert back the rows that are removed in cover_column.  */
    91.     for (Node *r = c->up; r != c; r = r->up) {
    92.         for (Node *p = r->left; p != r; p = p->left) {
    93.             p->up->down = p;
    94.             p->down->up = p;
    95.  
    96.             root[p->head].count++;
    97.         }
    98.     }
    99.  
    100.     /* Insert back the column to the list of head nodes.  */
    101.     c->right->left = c;
    102.     c->left->right = c;
    103. }
    104.  
    105. /* Function dlx finds all exact covers for the matrix represented by root.  */
    106. void
    107. dlx()
    108. {
    109.     HeadNode *c =  pick_column();
    110.     cover_column(c);
    111.  
    112.     for (Node *r = c->down; r != c; r = r->down) {
    113.         fill_sudoku(r);
    114.         for (Node *p = r->right; p != r; p = p->right) {
    115.             cover_column(&root[p->head]);
    116.         }
    117.  
    118.         if (root->right == root) print_sudoku();
    119.         else dlx();
    120.  
    121.         for (Node *p = r->left; p != r; p = p->left) {
    122.             uncover_column(&root[p->head]);
    123.         }
    124.     }
    125.  
    126.     uncover_column(c);
    127. }
    128.  
    129. int
    130. main(int argc, char *argv[])
    131. {
    132.     if (argc < 2) {
    133.         fprintf(stderr, "Usage: %s filename\n", argv[0]);
    134.         exit(EXIT_FAILURE);
    135.     }
    136.  
    137.     build_xcsudoku(argv[1]);
    138.     dlx(); 
    139.    
    140.     return 0;
    141. }

Các đề tài tương tự

  1. Cần Link tổng hợp thuật toán trong C#
    Gửi bởi nhimcon74 trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 2
    Bài viết cuối: 20-12-2012, 09:03 AM
  2. Giải thuật Giải thuật Chia để trị, hướng đi với giải thuật này thế nào?
    Gửi bởi maivivan13 trong diễn đàn Thắc mắc CTDL & Giải thuật
    Trả lời: 0
    Bài viết cuối: 23-10-2012, 10:22 PM
  3. giải đáp thắc mắc sp của hãng TP-LINK
    Gửi bởi huubk8x trong diễn đàn Nhập môn lập trình C#, ASP.NET
    Trả lời: 0
    Bài viết cuối: 07-08-2012, 03:01 PM
  4. Thủ thuật get link mediafire trong C# như thế nào?
    Gửi bởi thuchobiet trong diễn đàn Thắc mắc lập trình C#
    Trả lời: 6
    Bài viết cuối: 29-09-2010, 09:12 AM
  5. [ Solved ] Cấu trúc dữ liệu và giải thuật-Link List
    Gửi bởi Nemo_wf trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 1
    Bài viết cuối: 22-09-2008, 12:40 PM

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