stlab.adobe.com Adobe Systems Incorporated
dancing_links.hpp
Go to the documentation of this file.
1 /*
2  Copyright 2005-2007 Adobe Systems Incorporated
3  Distributed under the MIT License (see accompanying file LICENSE_1_0_0.txt
4  or a copy at http://stlab.adobe.com/licenses.html)
5 */
6 
7 /****************************************************************************************************/
8 
9 #ifndef ADOBE_dancing_links_t_HPP
10 #define ADOBE_dancing_links_t_HPP
11 
12 /****************************************************************************************************/
13 
14 #include <adobe/config.hpp>
15 
16 #include <vector>
17 
18 #if ADOBE_STD_SERIALIZATION
19 #include <iostream>
20 #endif
21 
22 #include <boost/function.hpp>
23 #include <boost/noncopyable.hpp>
24 
25 #include <adobe/implementation/toroid.hpp>
26 
27 #define ADOBE_DLX_VERBOSE 0
28 
29 #if ADOBE_STD_SERIALIZATION && ADOBE_DLX_VERBOSE
30 #include <adobe/iomanip.hpp>
31 #endif
32 
33 /****************************************************************************************************/
34 
35 namespace adobe {
36 
37 /****************************************************************************************************/
38 
39 #ifndef ADOBE_NO_DOCUMENTATION
40 
41 /****************************************************************************************************/
42 
43 namespace implementation {
44 
45 /****************************************************************************************************/
46 
47 struct do_nothing_callback_t
48 {
49  inline void operator () (std::size_t, bool) const
50  { }
51 };
52 
53 /****************************************************************************************************/
54 
55 struct select_right_heuristic_t
56 {
57  inline toroid_header_t* operator () (byte_toroid_t& toroid) const
58  { return toroid.right_of(&toroid.header_m); }
59 };
60 
61 /****************************************************************************************************/
62 
63 struct select_most_constrained_heuristic_t
64 {
65  inline toroid_header_t* operator () (byte_toroid_t& toroid) const
66  {
67  toroid_header_t* c(toroid.right_of(&toroid.header_m));
68  std::size_t sz(c->size_m);
69 
70  for (toroid_header_t* p(toroid.right_of(c)); p != &toroid.header_m; p = toroid.right_of(p))
71  {
72  if (p->size_m < sz)
73  {
74  c = p;
75  sz = p->size_m;
76  }
77 
78  if (sz == 1) break;
79  }
80 
81  return c;
82  }
83 };
84 
85 /****************************************************************************************************/
86 
87 } // namespace implementation
88 
89 /****************************************************************************************************/
90 
91 #endif
92 
93 /****************************************************************************************************/
94 
95 class dancing_links_t : boost::noncopyable
96 {
97 public:
98 #ifndef ADOBE_NO_DOCUMENTATION
99  dancing_links_t(std::size_t row_count, std::size_t column_count) :
100  toroid_m(row_count, column_count),
101  output_m(column_count, 0),
102  solutions_m(0)
103 #if ADOBE_DLX_VERBOSE
104  , tab_count_m(0)
105 #endif
106  { }
107 #endif
108 
109  inline void set(std::size_t row, std::size_t col, char color = 0)
110  { toroid_m.set(row, col, color); }
111 
112  inline void set_secondary_column(std::size_t col)
113  { toroid_m.set_secondary_column(col); }
114 
115  template <typename ResultCallback, typename SearchHeuristic>
116  inline std::size_t search(std::size_t max_solutions,
117  ResultCallback callback,
118  SearchHeuristic heuristic)
119  {
120  max_solutions_m = max_solutions;
121 
122  toroid_m.finalize();
123 
124  do_search(0, callback, heuristic);
125 
126  return solutions_m;
127  }
128 
129  inline std::size_t search(std::size_t max_solutions)
130  {
131  return search(max_solutions,
132  implementation::do_nothing_callback_t(),
133  implementation::select_most_constrained_heuristic_t());
134  }
135 
136 #if ADOBE_STD_SERIALIZATION
137  friend std::ostream& operator<<(std::ostream& s, const dancing_links_t& dancing_links_t)
138  { return s << dancing_links_t.toroid_m; }
139 #endif
140 
141 private:
142  template <typename ResultCallback, typename SearchHeuristic>
143  void do_search(std::size_t k, ResultCallback callback, SearchHeuristic heuristic)
144  {
145  if (toroid_m.right_of(&toroid_m.header_m) == &toroid_m.header_m)
146  {
147  ++solutions_m;
148 
149  #if ADOBE_DLX_VERBOSE
150  std::cout << adobe::indents(tab_count_m) << "<solved/>" << std::endl;
151  #endif
152 
153  for (std::size_t i(0); i < k; ++i)
154  callback(toroid_m.row_index_of(output_m[i]), i + 1 == k);
155 
156  return;
157  }
158 
159  std::size_t next_k(k + 1);
160 
161  toroid_header_t* c(heuristic(toroid_m));
162 
163  #if ADOBE_DLX_VERBOSE
164  ++tab_count_m;
165  std::cout << adobe::indents(tab_count_m) << "<c" << toroid_m.column_index_of(toroid_m.down_of(c)) << ">" << std::endl;
166  #endif
167 
168  toroid_m.cover_column(c);
169 
170  // branch on each node in this column
171  for (toroid_node_t* r(toroid_m.down_of(c)); r != c; r = toroid_m.down_of(r))
172  {
173  #if ADOBE_DLX_VERBOSE
174  std::cout << adobe::indents(tab_count_m) << "<r" << toroid_m.row_index_of(r) << ">" << std::endl;
175  #endif
176 
177  output_m[k] = r;
178 
179  // cover or purify each node on the same row as the node we're branching on
180  for (toroid_node_t* j(toroid_m.right_of(r)); j != r; j = toroid_m.right_of(j))
181  {
182  if (j->color_m == 0)
183  {
184  #if ADOBE_DLX_VERBOSE
185  std::cout << adobe::indents(tab_count_m) << "<c" << toroid_m.column_index_of(j) << ">" << std::endl;
186  #endif
187  toroid_m.cover_column(toroid_m.column_of(j));
188  }
189  else if (j->color_m > 0)
190  {
191  #if ADOBE_DLX_VERBOSE
192  std::cout << adobe::indents(tab_count_m) << "<p" << toroid_m.column_index_of(j) << ">" << std::endl;
193  #endif
194  toroid_m.purify(j);
195  }
196  }
197 
198  #if ADOBE_DLX_VERBOSE
199  // std::cout << *this << std::endl;
200  #endif
201 
202  do_search(next_k, callback, heuristic);
203 
204  if (solutions_m >= max_solutions_m)
205  return;
206 
207  r = output_m[k];
208 
209  c = toroid_m.column_of(r);
210 
211  // undo the cover/purify
212  for (toroid_node_t* j(toroid_m.left_of(r)); j != r; j = toroid_m.left_of(j))
213  {
214  if (j->color_m == 0)
215  {
216  #if ADOBE_DLX_VERBOSE
217  std::cout << adobe::indents(tab_count_m) << "</c" << toroid_m.column_index_of(j) << ">" << std::endl;
218  #endif
219  toroid_m.uncover_column(toroid_m.column_of(j));
220  }
221  else if (j->color_m > 0)
222  {
223  #if ADOBE_DLX_VERBOSE
224  std::cout << adobe::indents(tab_count_m) << "</p" << toroid_m.column_index_of(j) << ">" << std::endl;
225  #endif
226  toroid_m.unpurify(j);
227  }
228  }
229 
230  #if ADOBE_DLX_VERBOSE
231  std::cout << adobe::indents(tab_count_m) << "</r" << toroid_m.row_index_of(r) << ">" << std::endl;
232  #endif
233  }
234 
235  toroid_m.uncover_column(c);
236 
237  #if ADOBE_DLX_VERBOSE
238  std::cout << adobe::indents(tab_count_m) << "</c" << toroid_m.column_index_of(toroid_m.down_of(c)) << ">" << std::endl;
239  --tab_count_m;
240  #endif
241  };
242 
243  byte_toroid_t toroid_m;
244  std::vector<toroid_node_t*> output_m;
245  std::size_t solutions_m;
246  std::size_t max_solutions_m;
247 #if ADOBE_DLX_VERBOSE
248  std::size_t tab_count_m;
249 #endif
250 };
251 
252 /****************************************************************************************************/
253 
254 } // namespace adobe
255 
256 /****************************************************************************************************/
257 
258 #endif
259 
260 /****************************************************************************************************/
void callback(std::ios_base::event ev, std::ios_base &strm, int idx)
Definition: iomanip.hpp:315
boost::range_const_iterator< ForwardRange1 >::type search(const ForwardRange1 &range1, const ForwardRange2 &range2)
search implementation
Definition: search.hpp:41

Copyright © 2006-2007 Adobe Systems Incorporated.

Use of this website signifies your agreement to the Terms of Use and Online Privacy Policy.

Search powered by Google