TAOCP 7.2.2.1: Dancing Links

Section 7.2.2.1 exercises: 446/442 solved.

446 items

Section 7.2.2.1. Dancing Links

Exercises from TAOCP Volume 4 Section 7.2.2.1: 446/442 solved.

# Rating Category Status Time
1 ▶ [M25] math-medium solved 5m25s
2 [M30] math-hard solved 5m18s
3 [20] medium solved 1m16s
4 [M30] math-hard solved 2m22s
5 [18] medium solved 3m31s
6 [15] simple solved 3m57s
7 [16] medium solved 5m07s
8 [22] medium solved 5m11s
9 [18] medium solved 3m03s
10 [20] medium solved 5m09s
11 ▶ [21] medium solved 5m11s
12 ▶ [23] medium solved 4m20s
13 [16] medium solved 4m10s
14 ▶ [20] medium solved 5m08s
15 [20] medium verified 2m23s
16 [16] medium solved 2m39s
17 [16] medium solved 4m48s
18 [10] simple solved 5m19s
19 ▶ [21] medium solved 3m12s
20 ▶ [25] medium solved 4m36s
21 [22] medium solved 3m10s
22 ▶ [28] hard solved 2m27s
23 [38] project solved 2m13s
24 [20] medium verified 2m
25 [20] medium solved 2m42s
26 [21] medium solved 3m55s
27 [22] medium verified 1m17s
28 [M23] math-medium solved 1m31s
29 [26] hard solved 2m47s
30 [23] medium solved 2m29s
31 [M21] math-medium verified 1m05s
32 [**] solved 4m31s
33 [M16] math-medium solved 1m12s
34 [M25] math-medium solved 5m40s
35 [M21] math-medium solved 4m18s
36 ▶ [25] medium solved 3m04s
37 [M46] math-research solved 3m54s
38 [M25] math-medium verified 2m31s
39 ▶ [M21] math-medium verified 1m23s
40 ▶ [21] medium solved 1m29s
41 [25] medium solved 4m02s
42 [M21] math-medium solved 1m12s
43 [M30] math-hard solved 3m10s
44 [M04] math-simple verified 2m07s
45 [11] simple solved 2m47s
46 [19] medium solved 2m50s
47 [19] medium solved 3m30s
48 ▶ [24] medium solved 54s
49 ▶ [24] medium solved 5m31s
50 [20] medium verified 1m05s
51 [22] medium solved 3m02s
52 [40] project solved 3m34s
53 [M26] math-hard solved 6m15s
54 ▶ [35] hard solved 4m03s
55 [34] hard solved 3m51s
56 [47] research solved 4m40s
57 [22] medium solved 5m02s
58 ▶ [22] medium solved 3m41s
59 [30] hard solved 3m12s
60 [30] hard solved 1m28s
61 [21] medium solved 2m07s
62 ▶ [24] medium solved 1m15s
63 [29] hard solved 3m59s
64 [23] medium solved 2m43s
65 [24] medium solved 3m23s
66 ▶ [30] hard solved 1m14s
67 ▶ [22] medium solved 1m28s
68 [28] hard solved 3m35s
69 ▶ [30] hard solved 2m10s
70 [21] medium solved 4m06s
71 [20] medium solved 1m04s
72 [M23] math-medium solved 3m14s
73 [46] research solved 4m20s
74 [22] medium solved 3m35s
75 ▶ [M24] math-medium solved 4m24s
76 [21] medium verified 4m30s
77 [M21] math-medium verified 2m35s
78 [16] medium verified 1m59s
79 [M20] math-medium solved 2m14s
80 [19] medium solved 3m15s
81 [21] medium solved 1m49s
82 [21] medium verified 1m03s
83 ▶ [20] medium solved 2m23s
84 ▶ [25] medium verified 2m21s
85 [28] hard verified 2m26s
86 ▶ [M35] math-hard solved 37s
87 [30] hard solved 1m05s
88 [27] hard solved 2m52s
89 [21] medium solved 2m01s
90 ▶ [22] medium solved 3m05s
91 [40] project solved 1m12s
92 [22] medium solved 1m43s
93 [22] medium solved 1m05s
94 [20] medium verified 1m06s
95 ▶ [20] medium solved 3m12s
96 [M46] math-research solved 1m43s
97 [M21] math-medium verified 59s
98 [25] medium solved 3m32s
99 [20] medium solved 1m51s
100 ▶ [30] hard solved 5m12s
101 ▶ [25] medium solved 5m14s
102 ▶ [25] medium solved 5m12s
103 [M28] math-hard solved 4m56s
104 [M28] math-hard solved 5m21s
105 [22] medium solved 5m07s
106 [22] medium solved 5m11s
107 ▶ [23] medium solved 5m21s
108 ▶ [32] hard solved 3m
109 [28] hard solved 5m21s
110 [30] hard solved 5m17s
111 [21] medium solved 5m07s
112 ▶ [28] hard solved 2m41s
113 [21] medium solved 5m14s
114 [M25] math-medium solved 4m08s
115 [M25] math-medium solved 5m07s
116 ▶ [M25] math-medium solved 5m18s
117 ▶ [21] medium solved 5m05s
118 [21] medium solved 5m09s
119 [27] hard solved 5m02s
120 [M29] math-hard solved 5m11s
121 [M29] math-hard solved 5m22s
122 ▶ [28] hard solved 5m08s
123 [M30] math-hard solved 5m20s
124 [M22] math-medium solved 5m28s
125 [M20] math-medium solved 5m15s
126 [29] hard solved 5m15s
127 [M8] math-simple solved 4m16s
128 [25] medium solved 5m09s
129 ▶ [M14] math-simple solved 3m11s
130 [**] solved 2m25s
131 [28] hard solved 5m14s
132 [40] project solved 5m09s
133 [21] medium solved 5m13s
134 [23] medium solved 4m06s
135 [23] medium solved 5m15s
136 ▶ [HM48] hm-research solved 4m56s
137 [22] medium solved 5m12s
138 [25] medium solved 5m
139 [**] solved 5m22s
140 [29] hard solved 8m04s
141 [**] solved 5m17s
142 ▶ [**] solved 5m06s
143 ▶ [M25] math-medium solved 7m02s
144 [**] solved 5m18s
145 ▶ [M28] math-hard solved 4m23s
146 ▶ [M30] math-hard solved 5m15s
147 [30] hard solved 4m10s
148 [24] medium solved 4m02s
149 [M22] math-medium solved 2m44s
150 [24] medium solved 2m38s
151 ▶ [30] hard solved 5m12s
152 [30] hard solved 4m15s
153 [25] medium solved 5m08s
154 [M30] math-hard solved 4m04s
155 [20] medium solved 3m59s
156 ▶ [30] hard solved 5m11s
157 [22] medium solved 5m13s
158 [25] medium solved 5m14s
159 ▶ [21] medium solved 5m07s
160 [21] medium solved 3m31s
161 ▶ [23] medium solved 5m09s
162 [24] medium solved 4m16s
163 [20] medium solved 1m25s
164 [17] medium solved 5m15s
165 [M30] math-hard solved 5m11s
166 [21] medium solved 4m45s
167 [22] medium solved 5m18s
168 ▶ [15] simple solved 3m49s
169 ▶ [22] medium solved 3m10s
170 [22] medium solved 3m39s
171 [25] medium solved 6m39s
172 ▶ [29] hard solved 5m07s
173 ▶ [39] project solved 4m55s
174 [35] hard solved 3m29s
175 ▶ [M21] math-medium solved 5m05s
176 ▶ [M26] math-hard solved 3m55s
177 [M21] math-medium solved 3m09s
178 [M23] math-medium solved 4m58s
179 [15] simple solved 2m42s
180 ▶ [M28] math-hard solved 4m12s
181 [M20] math-medium solved 3m14s
182 [21] medium solved 5m18s
183 [16] medium solved 4m52s
184 ▶ [M22] math-medium solved 4m51s
185 [M22] math-medium solved 1m31s
186 [M24] math-medium solved 4m16s
187 [HM39] hm-project solved 6m42s
188 [M21] math-medium solved 4m53s
189 [HM31] hm-hard solved 4m57s
190 [HM46] hm-research solved 3m56s
191 [HM22] hm-medium solved 3m58s
192 [M29] math-hard solved 3m28s
193 [M31] math-hard solved 3m57s
194 [HM25] hm-medium solved 5m04s
195 ▶ [M22] math-medium solved 5m06s
196 ▶ [M29] math-hard solved 4m41s
197 [M25] math-medium solved 3m54s
198 [M25] math-medium solved 6m54s
199 [M25] math-medium solved 4m58s
200 ▶ [HM25] hm-medium solved 2m13s
201 ▶ [M30] math-hard solved 3m05s
202 [13] simple solved 2m06s
203 [M15] math-simple verified 1m26s
204 [M25] math-medium verified 42s
206 [29] hard solved 2m28s
207 [35] hard solved 3m05s
208 ▶ [21] medium verified 1m18s
209 [29] hard verified 1m30s
210 [21] medium solved 2m34s
211 [29] hard solved 3m02s
212 ▶ [M21] math-medium solved 1m55s
213 [M21] math-medium solved 2m12s
214 [21] medium solved 1m54s
215 ▶ [M30] math-hard solved 2m36s
216 [25] medium solved 2m13s
217 [M32] math-hard solved 2m17s
218 [20] medium solved 23s
219 [30] hard solved 2m08s
220 [28] hard verified 1m48s
221 [28] hard solved 2m04s
222 [22] medium solved 2m15s
223 [20] medium solved 1m57s
224 ▶ [M21] math-medium verified 1m51s
225 [21] medium solved 2m14s
226 [M30] math-hard verified 1m47s
227 [10] simple verified 1m43s
228 [M30] math-hard solved 2m23s
229 [25] medium solved 2m28s
230 [20] medium verified 1m31s
231 [21] medium solved 2m03s
232 [20] medium verified 1m43s
233 [20] medium verified 1m58s
234 [M20] math-medium solved 2m27s
235 ▶ [21] medium verified 2m07s
236 ▶ [M21] math-medium solved 2m24s
237 ▶ [M21] math-medium solved 1m51s
238 [24] medium solved 2m22s
239 ▶ [M27] math-hard solved 1m50s
240 [16] medium solved 2m17s
241 [11] simple verified 59s
242 ▶ [M23] math-medium solved 1m01s
243 [M20] math-medium solved 1m57s
244 [M21] math-medium solved 2m32s
245 [23] medium solved 2m24s
246 [22] medium solved 2m08s
247 [27] hard solved 2m30s
248 [22] medium verified 1m42s
249 [21] medium solved 2m16s
250 [21] medium verified 1m46s
251 [18] medium verified 1m30s
252 ▶ [20] medium solved 1m56s
253 ▶ [21] medium verified 1m32s
254 ▶ [28] hard solved 2m25s
255 [HM29] hm-hard solved 3m05s
256 ▶ [M23] math-medium solved 2m22s
257 ▶ [20] medium verified 1m53s
258 [HM21] hm-medium solved 4m15s
259 [M25] math-medium solved 2m39s
261 ▶ [23] medium solved 2m23s
262 ▶ [M27] math-hard solved 2m28s
263 [24] medium solved 2m36s
264 [M21] math-medium verified 1m09s
267 [18] medium solved 1m06s
268 ▶ [21] medium verified 1m13s
269 [21] medium solved 1m20s
270 [22] medium solved 1m12s
271 [20] medium solved 2m09s
272 [23] medium solved 2m40s
273 [25] medium solved 2m29s
274 [21] medium solved 4m43s
275 [21] medium solved 2m57s
276 [18] medium solved 3m35s
277 [25] medium solved 4m36s
278 ▶ [22] medium solved 1m45s
279 [40] project solved 1m50s
280 ▶ [M26] math-hard solved 2m30s
281 [20] medium solved 2m13s
282 ▶ [22] medium solved 3m
283 [22] medium solved 2m11s
284 ▶ [27] hard solved 2m21s
285 [21] medium solved 2m24s
286 [21] medium solved 2m27s
287 ▶ [23] medium solved 2m24s
288 [21] medium solved 2m02s
289 ▶ [29] hard solved 1m50s
290 [21] medium solved 2m50s
291 [21] medium solved 4m24s
292 [20] medium verified 2m47s
293 [41] project solved 1m55s
294 ▶ [30] hard solved 3m06s
295 [41] project solved 2m26s
296 [41] project solved 1m38s
297 [46] research solved 2m04s
298 ▶ [22] medium solved 5m33s
299 [39] project solved 2m10s
300 ▶ [23] medium solved 3m03s
301 [25] medium solved 2m23s
302 [26] hard solved 5m04s
303 ▶ [HM25] hm-medium solved 5m37s
306 ▶ [30] hard verified 1m25s
307 [M21] math-medium verified 1m36s
308 [22] medium solved 3m50s
309 [**] solved 2m46s
310 [**] solved 3m25s
311 ▶ [30] hard solved 1m17s
312 [22] medium solved 3m16s
313 ▶ [29] hard solved 2m52s
314 ▶ [28] hard solved 2m14s
315 [20] medium verified 1m14s
316 [20] medium solved 2m46s
317 [22] medium verified 1m15s
318 ▶ [20] medium solved 4m08s
319 [21] medium verified 1m18s
320 ▶ [M38] math-project solved 1m51s
321 [42] project verified 1m02s
322 [25] medium verified 1m13s
323 [M25] math-medium solved 3m57s
324 ▶ [30] hard verified 2m34s
325 [27] hard solved 2m44s
326 ▶ [M25] math-medium solved 3m32s
327 [24] medium solved 2m58s
328 ▶ [M23] math-medium solved 1m10s
329 [22] medium solved 1m09s
330 [25] medium verified 2m44s
331 [M40] math-project solved 2m27s
332 [30] hard solved 3m23s
333 [21] medium solved 3m28s
334 ▶ [M32] math-hard solved 3m53s
335 [30] hard solved 3m48s
336 [21] medium solved 1m07s
337 [29] hard solved 2m56s
338 [22] medium solved 57s
339 [25] medium solved 1m
340 [30] hard solved 3m08s
341 ▶ [25] medium solved 57s
342 [25] medium solved 1m03s
343 [10] simple solved 2m35s
344 [10] simple solved 1m18s
345 [20] medium verified 2m18s
346 [M30] math-hard solved 4m04s
347 ▶ [M21] math-medium solved 1m46s
348 [M41] math-project solved 5m56s
349 ▶ [M27] math-hard solved 4m35s
350 [22] medium solved 4m29s
351 [M46] math-research solved 3m18s
352 [21] medium solved 3m35s
353 [39] project solved 1m13s
354 ▶ [M30] math-hard solved 4m45s
355 [25] medium solved 1m52s
356 [27] hard solved 3m40s
357 [M0] math-immediate verified 58s
358 [HM1] hm-simple solved 3m42s
359 [29] hard solved 1m05s
360 ▶ [30] hard solved 5m03s
361 [M25] math-medium solved 5m21s
362 [10] simple solved 4m48s
363 [20] medium solved 1m51s
366 ▶ [25] medium verified 1m17s
367 [20] medium verified 1m19s
368 [M21] math-medium solved 4m28s
369 [27] hard solved 2m42s
370 ▶ [23] medium solved 1m10s
371 [24] medium verified 1m21s
372 ▶ [M35] math-hard solved 2m24s
373 [26] hard solved 3m19s
374 [M28] math-hard solved 1m21s
375 [M29] math-hard solved 3m26s
376 ▶ [M25] math-medium solved 4m05s
377 [M28] math-hard solved 5m29s
378 [M30] math-hard solved 4m55s
379 ▶ [25] medium solved 1m17s
380 [35] hard solved 3m31s
381 ▶ [20] medium verified 1m12s
382 [18] medium solved 3m42s
383 [29] hard solved 1m57s
384 [34] hard solved 1m07s
385 [M36] math-project solved 1m09s
386 ▶ [M31] math-hard solved 3m21s
387 ▶ [M26] math-hard solved 1m30s
388 ▶ [21] medium solved 1m01s
389 [29] hard verified 1m25s
390 ▶ [21] medium solved 4m43s
391 [29] hard solved 5m18s
392 ▶ [25] medium solved 4m04s
393 [25] medium solved 9m10s
394 [29] hard solved 4m51s
395 [25] medium solved 4m47s
396 ▶ [35] hard solved 2m57s
397 ▶ [30] hard solved 1m40s
398 [23] medium solved 2m45s
399 ▶ [22] medium verified 1m12s
400 [21] medium verified 1m54s
401 [22] medium solved 4m15s
402 [24] medium verified 3m23s
403 ▶ [31] hard solved 5m13s
404 ▶ [25] medium solved 3m30s
405 [21] medium solved 1m04s
406 [16] medium solved 4m08s
407 ▶ [20] medium solved 3m33s
408 [28] hard solved 1m13s
409 ▶ [30] hard verified 1m13s
410 [22] medium solved 4m40s
411 [20] medium solved 4m07s
412 ▶ [22] medium solved 1m23s
413 [30] hard verified 1m38s
414 [25] medium solved 4m39s
415 [M33] math-hard solved 5m12s
416 [M30] math-hard solved 5m29s
417 [M46] math-research solved 4m06s
418 [M29] math-hard solved 2m33s
419 [30] hard solved 2m39s
420 [M22] math-medium solved 4m15s
421 ▶ [20] medium solved 4m22s
422 [21] medium solved 3m04s
423 ▶ [M25] math-medium solved 1m07s
424 [36] project solved 3m48s
425 [25] medium solved 2m35s
426 ▶ [37] project solved 1m51s
427 ▶ [25] medium solved 3m31s
428 [M28] math-hard solved 3m59s
429 [21] medium solved 3m18s
430 ▶ [26] hard solved 1m44s
431 ▶ [30] hard solved 3m44s
432 ▶ [M25] math-medium solved 3m14s
433 [26] hard solved 3m28s
434 [39] project solved 59s
435 [27] hard solved 3m03s
436 ▶ [20] medium solved 4m19s
437 ▶ [27] hard verified 1m22s
438 [30] hard solved 4m17s
439 [M30] math-hard solved 2m37s
440 [21] medium solved 3m20s
441 [18] medium solved 58s
442 ▶ [M23] math-medium verified 3m53s
443 ▶ [M30] math-hard solved 4m37s
444 [M27] math-hard solved 1m17s
445 ▶ [M22] math-medium solved 3m13s
446 ▶ [44] project verified 4m12s
447 [22] medium verified 3m27s
448 [22] medium solved 1m04s
449 [40] project solved 1m05s
450 [42] project solved 3m23s
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 1

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 2

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 3

The system is interpreted exactly as written: x_2 + x_3 = x_3 + x_5 + x_6 = x_2 + x_5 = x_3 + x_4 = x_1 + x_4 = x_2 + x_3 + x_4 + x_6 = x_1 + x_6 = 1, with each $x_k \in {0,1}$ for $1 \le k \le 6$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 4

Let $G = (V, E)$ be a (simple, undirected) graph.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 5

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 6

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 simple Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 7

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 8

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 9

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 10

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 11

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 12

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 13

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 14

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 15

Let the positions be $1,2,\dots,2n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 16

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 17

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 18

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 simple Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 19

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 20

Let $m$ be the number of options in the pairwise ordering construction of (a6).
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 21

The flaw in the original solution is fundamental: it attempts to encode each index $j \in \{0,\dots,m-1\}$ using $L+1$ bits where $L=\lfloor \lg m \rfloor$, violating the requirement that each option...
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 22

An $n$-queens solution is a set $S \subseteq {1,\dots,n}^2$ with exactly one queen in each row and each column, satisfying the two diagonal constraints.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 23

Let $n \times n$ chessboard coordinates be $(i,j)$ with $1 \le i,j \le n$.
taocp mathematics algorithms volume-4 project Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 24

An $n$-queens solution is a permutation $p$ of ${1,\dots,n}$ such that queens are placed at $(i,p(i))$ and no two attack each other.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 25

Let $Q_8$ be the graph whose vertices are the $64$ squares of an $8\times 8$ chessboard, with two vertices adjacent when a queen placed on one square attacks the other along a row, column, or diagonal...
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 26

The original solution fails at the only place where the problem becomes genuinely global: it replaces a coupled partition problem by a product of independent 7-queen counts.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 27

Let Langford’s problem be represented in the usual exact-cover form of Section 7.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 28

Formula (27) expresses the estimated completion ratio in the form $\prod_{j=0}^{t} \frac{c_j}{t_j}$ with integers satisfying $1 \le c_j \le t_j$.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 29

In particular, the missing points that must be fixed in a genuine solution are: 1.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 30

All such trees can arise as backtrack trees of Algorithm X.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 31

The active item list in Algorithm X is maintained as a circular doubly linked list via $\text{LLINK}$ and $\text{RLINK}$ pointers on item headers.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 32

Let $S,S'$ be solutions and identify them with sets of chosen options.
taocp mathematics algorithms volume-4 Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 33

Let the given exact cover instance be specified by the $M\times N$ matrix $A$, with item set $U$ and option set $\mathcal{O}$.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 34

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 35

The flaw in the previous solution is structural: it tries to “forbid” padding rows using gadgets that violate the degree constraint, and it loses track of the invariant that every column must end with...
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 36

The key mistake is the assumption that a local heuristic such as MRV, even with deterministic tie-breaking, can enforce a global lexicographic optimum for the sequence (z_1, z_2, z_3, \dots).
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 37

Solution to TAOCP 7.2.2.1 Exercise 37.
taocp mathematics algorithms volume-4 math-research Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 38

Let $g_n$ be defined as in exercise 37: a greedy placement of nonattacking queens on the infinite board, with $g_n$ the column of the queen in row $n$.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 39

We study the expected number of exact covers in two random models of an $m \times n$ instance.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 40

The database after processing rows $r_1,\ldots,r_{k-1}$ consists of pairs $(s_j,c_j)$ where $s_j$ is an $n$-bit mask representing the union of selected rows and $c_j$ counts the number of ways to obta...
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 41

The reviewer correctly identifies a single structural failure: the DP transition does not enforce the _at-most-once_ constraint of exact cover.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 42

Exercise 40 stores, for each reachable item set $s$, only the number $c$ of partial selections that produce $s$.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 43

Let the Sudoku be of order $n^2$.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 44

Let the first $33$ digits of $\pi$ in decimal expansion (including the initial digit $3$) be placed, in the order specified by the encoding (29a), into the first $33$ cells of the Sudoku grid.
taocp mathematics algorithms volume-4 math-simple Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 45

The exercise, as presented in the prompt, cannot be solved because the essential input data are missing.
taocp mathematics algorithms volume-4 simple Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 46

A hidden single is a pair $(U,d)$, where $U$ is a unit (row, column, or $3\times 3$ block) and digit $d \in \{1,\dots,9\}$ occurs as a candidate in exactly one cell of $U$.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 47

The previous solution failed because it never engaged with the actual candidate structure of chart (32).
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 48

Let the data of chart (33) be a function $f$ assigning to each ordered pair $(r,c)$ a unique value $v$ from a finite set $V$, so that each position $(r,c)$ carries exactly one value.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 49

We work in the bipartite graph formulation of the relaxed exact cover instance for a fixed row $i_0$.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 50

Let $P$ be the 16-clue Sudoku instance (29c), and let $S$ denote its unique completed grid.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 51

The previous solution fails because it never analyzes the concrete exact cover instance $(29c)$.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 52

The previous solution failed because it never produced an actual instance.
taocp mathematics algorithms volume-4 project Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 53

We address the two errors separately and rebuild both arguments from correct foundations.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 54

Let $U$ be the 32 clues of puzzle (29a), and let $S$ be its unique completed solution.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 55

Let $S = (28s)$ be the given completed Sudoku solution grid.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 56

The previous argument fails at a structural level because it invents “local trades” that do not exist in Sudoku.
taocp mathematics algorithms volume-4 research Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 57

Let the Sudoku grid be partitioned into the usual $3\times 3$ boxes.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 58

We work from first principles and reduce the problem to a structured constraint on permutation systems.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 59

The previous solution fails at a single foundational point: it treats the omission of the instances in (34) from the prompt as mathematical information.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 60

Let the three puzzles in Figure 60 be denoted by $(a)$, $(b)$, and $(c)$.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 61

Let $S$ denote Behrens’s $5\times 5$ gerechte design from (35a).
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 62

Each nonstraight pentomino covers exactly $5$ unit squares.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 63

The previous solution failed because it introduced unsupported “affine rigidity” claims and then deduced uniqueness without ever correctly modeling Behrens’s array (35c).
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 64

The previous construction failed because it violated the defining jigsaw constraint: each region must contain every symbol exactly once.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 65

The previous solution is incorrect because it replaces the mathematical task with a meta-level claim about missing input data.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 66

Two independent instances are given.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 67

Let a _rainbow box_ denote a set of nine cells that must contain each symbol in ${1,2,3,4,5,6,7,8,9}$ exactly once.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 68

Working
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 69

The previous solution failed because it abandoned the given instance instead of extracting and using its structure.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 70

We work directly from the given $7\times 8$ array.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 71

Let the Dominosa instance consist of a $7\times 8$ grid of cells $C$, each cell $x\in C$ carrying a label $\lambda(x)\in{0,1,\dots,6}$.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 72

The previous solution fails mainly because it does not correctly define the second probability space and because it reports numerical outcomes without a valid reproducible experiment.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 73

The previous solution failed because it stopped at an irrelevant upper bound and never addressed the extremal structure of Dominosa instances.
taocp mathematics algorithms volume-4 research Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 74

The previous solution fails at the point where it replaces a mathematical existence proof with an unverified claim of computation.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 75

A grope is a set $G$ with a binary operation $\circ$ satisfying x \circ (y \circ x)=y \qquad \text{for all }x,y\in G.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 76

The key issue in the previous solution is that part (b) attempted to enforce commutativity by informally “merging choices,” without giving a valid exact-cover encoding.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 77

The original construction fails because it encodes whole mappings as single options and implicitly enumerates all embeddings.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 78

Let the 27 names be $w_1,\dots,w_{27}$, with lengths $|w_i|$, and let L=\sum_{i=1}^{27} |w_i|.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 79

Let $(48)$ denote the exact-cover representation introduced earlier in the section.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 80

The correct way to answer this exercise is to actually carry out the backtracking process defined by Algorithm C with the specific branching rule in step C3 (using Exercise 9) and the initialization g...
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 81

**Answer: False.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 82

Let primary items be indexed by $1,2,\dots,N_1$, and let items with index $x > N_1$ be secondary items.
taocp mathematics algorithms volume-4 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 83

The key mistake in the previous solution is the attempt to interpret the modification via a cumulative “$O_j \cup \{s_1,\dots,s_j\}$” expansion.
taocp mathematics algorithms volume-4 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 84

We restart the argument in a way that separates _finding the optimal bound_ from _enumerating all optimal solutions_, because mixing both in a single changing-bound traversal is what caused the failur...
taocp mathematics algorithms volume-4 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 85

The flaw in the previous solution is the attempt to force _first-found optimality_ via local ordering of option numbers.
taocp mathematics algorithms volume-4 Hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 86

Solution to TAOCP 7.2.2.1 Exercise 86.
taocp mathematics algorithms volume-4 math-hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 87

An $n \times n$ double word square is an array filled with words such that each of the $n$ rows is a word, each of the $n$ columns is a word, and all $2n$ words are pairwise distinct.
taocp mathematics algorithms volume-4 Hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 88

The flaw in the previous solution is not a minor modeling issue but a fundamental misuse of exact cover.
taocp mathematics algorithms volume-4 Hard Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 89

The original write-up fails because it never resolves the combinatorial instance: it replaces the exercise with a modeling statement and then stops.
taocp mathematics algorithms volume-4 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 90

The previous solution fails at a single fundamental point: it treats the word list from Exercise 88 as missing, and from that incorrectly concludes that the problem is not actually solvable.
taocp mathematics algorithms volume-4 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 91

Fix a positive integer $W$.
taocp mathematics algorithms volume-4 project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 92

Let a five-letter word be written as a word $w = w_1 w_2 w_3 w_4 w_5$.
taocp mathematics algorithms volume-4 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 93

Let a configuration for period $p$ consist of $3p$ words placed on a toroidal arrangement of $p$ rows and $3$ word-positions per row, with wraparound in both directions, such that each of the $3p$ wor...
taocp mathematics algorithms volume-4 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 94

We construct a binary cycle $(x_0 x_1 \ldots x_{15})$ by setting (x_0 x_1 \ldots x_{15}) = 0000100110101111.
taocp mathematics algorithms volume-4 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 95

We rebuild the solution directly in the framework of Algorithm C (exact cover with color controls), and we explicitly fix the missing connectivity argument and the running time.
taocp mathematics algorithms volume-4 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 96

Let the binary alphabet be ${0,1}$.
taocp mathematics algorithms volume-4 math-research Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 97

The condition d_{(i+3)\bmod 9,j} = (d_{ij}+1)\bmod 3 couples only rows whose indices differ by $3$, while leaving column indices unchanged.
taocp mathematics algorithms volume-4 math-medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 98

The previous reduction fails because it tries to let clause edges share vertices with variable gadgets, which is impossible under exact cover: once a vertex is covered by the variable cycle matching,...
taocp mathematics algorithms volume-4 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 99

Working
taocp mathematics algorithms volume-4 Medium Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 100

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 101

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 102

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 103

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 104

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 105

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 106

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 107

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 108

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 109

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 110

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 111

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 112

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 113

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 114

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 115

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 116

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 117

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 118

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 119

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 120

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 121

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 122

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 123

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 124

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 125

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 126

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 127

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-simple Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 128

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 129

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-simple Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 130

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 131

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 132

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 project Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 133

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 134

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 135

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 136

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 hm-research Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 137

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 138

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 139

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 140

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 141

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 142

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 143

Stopped thinking
taocp mathematics algorithms volume-4 math-medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 144

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 145

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 146

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 147

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 148

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 149

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 150

We restart from a complete and explicit formulation.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 151

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 152

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 153

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 154

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 155

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 156

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 157

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 158

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 159

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 160

Let a configuration be a placement of $n$ queens on an $n \times n$ board with one queen in each row and each column, satisfying the diagonal constraints.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 161

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 162

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 163

In (12), the variable $p$ is used to traverse exactly the vertical list of nodes that correspond to active options containing item $i$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 164

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 165

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 166

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 167

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 168

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 simple Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 169

Let the vertices of $G$ be $v_1, v_2, \dots, v_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 170

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 171

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 172

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 173

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 project Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 174

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 175

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 176

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 177

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 178

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 179

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 simple Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 180

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 181

Assume \tilde{D}(5n+r)=4^n c_r-\frac{3}{4}, \qquad n\ge 2,\quad 0\le r<5.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 182

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 183

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 184

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 185

A strict exact cover problem consists of options, each option containing exactly one primary item and any number of secondary items, such that every primary item is covered exactly once and each secon...
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 186

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 187

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 hm-project Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 188

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 189

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 hm-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 190

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 hm-research Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 191

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 hm-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 192

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 193

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 194

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 hm-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 195

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 196

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 197

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 198

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 199

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 200

We keep the algebraic setup but fix part (b) by replacing symbolic computation with a randomized polynomial identity test in a finite field.
taocp mathematics algorithms volume-4 hm-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 201

Items are the vertices $X_1,\dots,X_n$ and $Y_1,\dots,Y_n$.
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 202

The statement of the exercise depends entirely on Figure 202, which is not present in the provided context.
taocp mathematics algorithms volume-4 simple Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 203

Equation (95) defines $T \otimes T'$ as the binary operation that combines two search trees by grafting $T'$ onto the terminal structure of $T$, with identity element $\square$ (the single-node tree).
taocp mathematics algorithms volume-4 math-simple Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 204

Let d=\deg(\alpha), \qquad d'=\deg(\alpha').
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 205

A fully corrected solution cannot be produced from the information provided, because the exercise statement is incomplete.
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 206

Let the dominance order on nodes be denoted by $\preceq$, and recall that a tree is **minimally dominant** if its root is minimal in this order among all nodes of the tree, i.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 207

We correct the solution, focusing especially on part (c), which requires a precise interpretation of “exponential growth” in Algorithm X dynamics, and a justified role for both parameters.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 208

Let the exact cover instance of Fig.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 209

Let the instance of the exact cover problem consist of a set of items $I$, partitioned into two disjoint classes $I = U \cup V$, $U \cap V = \varnothing$, together with a family of options $\mathcal{O...
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 210

Let the three options be denoted $\alpha'$, $\beta'$, and $\gamma'$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 211

We analyze bipairs in the standard exact cover formulations of the Langford pair problem, the $n$ queens problem, and Sudoku.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 212

Let primary items be linearly ordered.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 213

Let the items be linearly ordered and let the restricted growth string of a partition be defined in the standard way: scanning items in increasing order, each item receives the index of the block in w...
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 214

Let a _string solution_ be a sequence of options produced by the search procedure, where the same underlying exact cover solution may appear in different orders depending on the choices made during ba...
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 215

Let $K_{2q+1}$ have vertex set $\{0,1,\dots,2q\}$.
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 216

In Exercise 215, the underlying instance is an exact cover formulation of a combinatorial structure on $K_{2q+1}$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 217

The previous solution failed because it never actually classifies bipairs; it only restates the problem in terms of abstract “delta sets” and then assumes the conclusions.
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 218

Understood.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 219

Let $p$ and $q$ be primary items in an XCC instance.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 220

Let $A$ be an exact cover problem in the sense of Section 7.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 221

Let $S$ be the stack formed in step P7 after all options that begin with items already on the search stack have been examined.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 222

Let item $i$ be the item to be deleted in step P7, and let $S$ denote the distinguished item whose occurrences determine which options are treated as exceptional in this stage.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 223

Let $S$ denote the stack of options accumulated in step P7.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 224

Let the items be $x_1, x_2, \dots, x_n$.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 225

In Algorithm P, the number of options removed during a covering step equals the number of nodes eliminated from the vertical lists of items that are deleted together with the chosen item.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 226

Let $a_1,\dots,a_{2n}$ be a Langford pairing, and define the reversed sequence by $a'_k = a_{2n+1-k}, \qquad 1 \le k \le 2n.$ For any function $f$, define $T_f = \sum_{k=1}^{2n} k\, f(a_k), \qquad T_f...
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 227

In the Langford pairing exact cover formulation for $n=4$, options are indexed lexicographically by $(k,i)$ where $k$ is the value and $i$ is the first position, with the second position $j=i+k+1$.
taocp mathematics algorithms volume-4 simple Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 228

Let $a_1\ldots a_{2n}$ be a Langford pairing, so each symbol $j \in {1,\dots,n}$ appears exactly twice among the $a_k$, and if $a_k = a_{k'} = j$ with $k<k'$, then $k'-k=j+1$.
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 229

A Langford pairing of order $n$ is a sequence $a_1,\dots,a_{2n}$ containing each symbol $k \in {1,\dots,n}$ exactly twice, with the two occurrences separated by exactly $k$ positions, so that if the f...
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 230

Let each option $O$ in the instance of Fig.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 231

Let $G$ denote the set of all cells in the grid.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 232

Let a placement of 16 queens be an option set $S$ consisting of 16 chosen cells $(i,j)$, and let its cost under Algorithm $X^8$ be $w(S)=\sum_{(i,j)\in S} 8d(i,j).$ Since multiplication by the positiv...
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 233

Let the 16-queens problem of Fig.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 234

Let the board be $n \times n$, and let the center be $\left(\frac{n+1}{2}, \frac{n+1}{2}\right).$ For a queen placed at $(i,j)$, the cost is $8d(i,j)^2,$ and in the standard geometric interpretation u...
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 235

Let the board be $16 \times 16$ with rows and columns indexed by $i,j \in {1,\dots,16}$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 236

Let the board be indexed by $1,\dots,n$ in both directions, and let the center be $c = (n+1)/2$.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 237

Let a solution of the prime square problem be an $n \times n$ array $(x_{ij})$ of primes satisfying the defining constraints of the problem in the text, and let the product of the solution be $P = \pr...
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 238

Let the array entries be constrained by digit class as follows: each entry is either a 3-digit prime or an $n$-digit prime, and all entries are distinct.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 239

A family ${S_1,\ldots,S_m}$ of subsets of ${1,\ldots,n}$ is given together with weights $(w_1,\ldots,w_m)$, where each $w_j>0$.
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 240

The original solution failed because it never used the actual USA-partition instance.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 241

Algorithm $P^s$ is a specialization of a general backtracking scheme in which a partial solution is extended step by step and each extension is later undone before exploring alternative branches.
taocp mathematics algorithms volume-4 simple Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 242

Let $G = (V,E)$ be the graph processed by the algorithm of exercise 7.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 243

Let a solution consist of exactly $d$ options, and let the weight of option $k$ be $x_k$ for $1 \le k \le d$.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 244

Let $G$ be an undirected graph on vertex set $V$.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 245

Let $G$ be the USA graph on 48 states, and let $G'$ be the augmented graph obtained by adding vertex $\mathrm{DC}$ adjacent only to $\mathrm{MD}$ and $\mathrm{VA}$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 246

Let a partition consist of options $O_1,\dots,O_7$, each induced subgraph on its vertex set having size fixed by the construction in (118).
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 247

Let each option $O$ have original cost $c(O)\ge 0$.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 248

Let $i$ be an active item, and let $f(i)$ denote the number of active options that contain $i$ and have cost strictly less than $\theta = T - C_l$ at the current level $l$ in step C3$^s$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 249

Let the costs be revealed as a sequence $x_1, x_2, \ldots, x_{dt}$, where $\{x_1,\ldots,x_{dt}\} = \{c_1,\ldots,c_{dt}\}$ and each $x_t \ge 0$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 250

Let $Z$ be a set of characters with the property that for each $\alpha \in Z$, every option contains exactly one primary item whose name begins with $\alpha$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 251

Algorithm Z operates by recursive search over partial exact covers, maintaining the invariant that the current data structure represents the residual exact cover instance induced by the choices alread...
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 252

Let (121) denote the set of options defining the exact cover instance, and let Algorithm Z construct a ZDD by recursive application of step Z3, where each node corresponds to a choice of an item $i$ a...
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 253

Let $Z$ denote Algorithm Z as in Section 7.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 254

Let Algorithm Z operate on an exact cover instance with primary items and secondary items with colors, in the sense of Section 7.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 255

Let $K_n$ denote the complete graph on vertex set ${1,2,\dots,n}$ and consider the exact cover formulation of perfect matchings where each item is a vertex and each option is an unordered pair ${i,j}$...
taocp mathematics algorithms volume-4 hm-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 256

Algorithm Z reduces the problem of finding perfect matchings of a graph to an exact cover instance in which each vertex is an item and each edge is an option covering its two endpoints, with the addit...
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 257

The items are $1,2,\dots,n$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 258

The previous solution fails because it replaces Algorithm Z’s actual backtracking dynamics with a single-pass incidence count.
taocp mathematics algorithms volume-4 hm-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 259

Each bounded permutation instance has items $X_1,\dots,X_n,Y_1,\dots,Y_n$ and options $O_{ij} = \{X_i, Y_j\} \qquad (1 \le j \le a_i).$ A solution is a set of options selecting exactly one $Y_j$ for e...
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 260

We address the reviewer’s objections by redoing the analysis from the structure of the two exact cover instances, and by separating clearly: 1.
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 261

Let $G=(V,E)$ be a directed acyclic graph, let $S \subseteq V$ be the set of sources and $T \subseteq V$ the set of sinks.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 262

The shape $S_n$ is a $16 \times n$ rectangular region with four fixed right triangles of side $7$ removed from its corners.
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 263

Let $I$ be an exact-cover instance arising from a problem in which each solution is a set of rows covering all columns exactly once.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 264

Let the items be arranged in the circular doubly linked list headed by node $0$, with the active items forming a linear order when read from $i = \mathrm{RLINK}(0)$ forward.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 267

Let the Conway pentomino names be used in their standard letter forms $F, I, L, N, P, T, U, V, W, X, Y, Z$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 268

The problem is an exact cover instance in the sense of (6)–(9): each legal placement of a pentomino on the $5\times 12$ board corresponds to one option, and a valid tiling corresponds to a set of opti...
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 269

Let a decomposable packing be one in which a vertical line between columns $k$ and $k+1$ separates the $5\times 12$ rectangle into a $5\times k$ region and a $5\times(12-k)$ region, with no pentomino...
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 270

Let the 11 nonsquare pentominoes be the free pentomino set with the $O$ pentomino removed.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 271

A pentomino tiling of a $6\times 10$ rectangle can be encoded as an exact cover problem in the sense of Algorithm X, with items representing both geometric constraints and piece constraints, and with...
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 272

In the exact cover formulation of pentomino packing, each option represents a placement of a specific pentomino, covering one item for the pentomino identity and five items for the occupied unit squar...
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 273

Let the $3\times 20$ board be fixed.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 274

We restart from first principles and remove the two unsupported assumptions in the previous solution: 1.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 275

Color the $8\times 8$ board in the standard checkerboard coloring and assign each square weight $+1$ for black and $-1$ for white.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 276

Let the five tetrominoes be denoted by $I$ (straight), $O$ (square), $T$, $L$, and $S$ (skew).
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 277

We restate the problem in a form that separates what is purely structural from what must be verified finitely and explicitly.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 278

Let $\mathcal{P}$ denote the set of all $6 \times 10$ pentomino packings obtained by Algorithm X without symmetry reduction.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 279

Let the cube have edge length $\sqrt{10}$.
taocp mathematics algorithms volume-4 project Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 280

A Möbius strip of width $4$ formed from unit squares has fundamental domain a $4 \times 15$ rectangle, since each pentomino has area $5$ and the twelve pentominoes cover $60$ unit squares, so the tota...
taocp mathematics algorithms volume-4 math-hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 281

The Aztec diamond of order $11/2$ contains $61$ cells, and the Aztec diamond of order $13/2$ with a hole of order $3/2$ contains $80$ cells.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 282

The original argument fails because it replaces the geometric constraint system with an exact-cover abstraction and then draws global invariance conclusions that do not follow.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 283

Let $P$ be a fixed pentomino.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 284

Let $\mathcal{P}={I,L,P,N,T,U,V,W,X,Y,Z,O,F}$ be the twelve pentominoes, considered up to translation, rotation, and reflection.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 285

Each one-sided pentomino is a connected 5-cell polyomino, and there are 18 distinct pieces.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 286

Let the twelve pentominoes be the standard set, with each piece used exactly once to tile the $6\times 10$ rectangle.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 287

Let each pentomino placement be an option $O$.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 288

Each one-sided pentomino is a fixed 5-cell polyomino with orientation distinguished up to rotation, but not reflection.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 289

Please provide Figure (36) and the full image for exercise 289(c), or the corresponding region coordinates.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 290

Let the board be a rectangle whose cells are colored in the usual checkerboard fashion.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 291

Solution to TAOCP 7.2.2.1 Exercise 291.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 292

Color the infinite square grid as a checkerboard, assigning the two colors according to the parity of the coordinates of a cell.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 293

Let a hexomino be represented by a finite connected set of six unit squares.
taocp mathematics algorithms volume-4 project Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 294

The missing information identified in the previous response remains a decisive obstacle.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 295

The missing figure is essential data for this exercise.
taocp mathematics algorithms volume-4 project Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 296

Exercise 7.
taocp mathematics algorithms volume-4 project Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 297

Exercise 7.
taocp mathematics algorithms volume-4 research Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 298

There are $80$ cells in the $8\times10$ rectangle.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 299

Let $R$ be the $5\times54$ rectangle.
taocp mathematics algorithms volume-4 project Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 300

The three parts have different logical status.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 301

I’m not able to produce a reliable complete solution to this exercise without risking fabricated enumeration data.
taocp mathematics algorithms volume-4 Medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 302

Solution to TAOCP 7.2.2.1 Exercise 302.
taocp mathematics algorithms volume-4 Hard Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 303

A complete corrected solution would need, in addition to the generating-function derivation, one of the following for part (d): 1.
taocp mathematics algorithms volume-4 hm-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 304

Let $\mathcal P$ denote the decision problem in the statement.
taocp mathematics algorithms volume-4 math-medium Jul 6, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 305

The previous solution failed because it never _actually constructs_ the windmill dominoes or the induced parity geometry.
taocp mathematics algorithms volume-4 Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 306

Let $G_L$ be the graph whose vertices are the $20$ large squares in the $4 \times 5$ rectangle, with edges joining orthogonally adjacent squares.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 307

Color the board by assigning to each cell $(i,j)$ the value \chi(i,j) \equiv i+j \pmod 3, with values in ${0,1,2}$.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 308

We work in the triangular lattice of Exercise 124.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 309

A _base placement_ (Exercise 266 convention) counts a placement of a polyiamond in the triangular grid together with a distinguished base cell, with translations identified but rotations and reflectio...
taocp mathematics algorithms volume-4 Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 310

The lower bound is correct and cannot be improved: since each hexiamond has area $6$, the 12 pieces cover $72$ unit triangles, and any $7 \times m$ strip must satisfy 7m \ge 72 \;\;\Rightarrow\;\; m \...
taocp mathematics algorithms volume-4 Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 311

A hexiamond is a connected set of $6$ unit triangles in the triangular grid, so each hexiamond has area $6$.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 312

The original argument fails at exactly one structural point: it assumes that all eight faces can independently host a full hexiamond, and that the remaining uncovered triangles can be paired up global...
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 313

Let the original hexiamond be denoted by $H$, consisting of six unit equilateral triangles.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 314

The core mistake in the proposed encoding is the failure to represent the two tilings as two independent exact-cover constraints.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 315

Represent each hexagon of the infinite grid by a triple $(x_1,x_2,x_3)\in\mathbb{Z}^3$ satisfying $x_1+x_2+x_3=0$, with adjacency defined by moving from $(x_1,x_2,x_3)$ to one of the six points obtain...
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 316

The previous argument failed because it tried to force a local decomposition without controlling the global constraints of embeddings of polyhexes in the radius-3 hexagon.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 317

Let $H$ denote the $28$-hex region obtained in the statement, and let $\mathcal{T}_1,\dots,\mathcal{T}_7$ be the seven distinct tetrahexes.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 318

The corrected argument must begin by constructing a single, explicit coordinate model in which both objects live.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 319

Each polyabolo is a finite connected union of congruent isosceles right triangles whose sides are either legs of length $1$ or hypotenuses of length $\sqrt{2}$.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 320

An $N$-abolo is a polyform made of $N$ unit isosceles right triangles joined edge-to-edge.
taocp mathematics algorithms volume-4 math-project Jun 29, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 321

A _one-sided tetrabolo_ is a tetromino considered up to translation and rotation, but not reflection.
taocp mathematics algorithms volume-4 project Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 322

A polystick is a connected set of unit horizontal or vertical segments in the integer grid.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 323

The reviewer’s objections identify two real issues: (i) the structural claims in (b) were not properly justified at the level of quotienting by translation, and (ii) part (c) introduced a spurious red...
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 324

We recompute the number of base placements using the orbit–stabilizer theorem under the action of the proper rotation group of the cube, which has order $24$.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 325

We start from the definition.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 326

We restart from the structural content that actually drives the proof: the W-wall is not treated abstractly, but as a product-composed exact cover instance coming from a separable geometric decomposit...
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 327

The reviewer is correct that the previous write-up never engages with the actual finite instance set, so it does not solve the exercise.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 328

Let the $3\times 3\times 2$ box be the set of lattice points $\{(x,y,z)\mid x,y\in\{1,2,3\},\ z\in\{0,1\}\},$ with unit cubes centered at these points.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 329

Solution to TAOCP 7.2.2.1 Exercise 329.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 330

The previous argument fails because it introduces irrelevant structural constraints on Soma pieces and misses the only fact that actually matters: any realizable region must coincide with the full $3\...
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 331

The error in the previous solution is that it never carries out the enumeration that the exercise demands.
taocp mathematics algorithms volume-4 math-project Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 332

A correct solution must actually perform a complete enumeration of all exact covers, not rely on informal claims about search behavior.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 333

The failure in the previous solution is that it replaces the required existence proof with an unsubstantiated claim that a solution can be found by search.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 334

The previous submission fails because it never performs the required step: it does not determine the actual Soma placements for the three façades.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 335

The previous write-up failed because it replaced the required reasoning with unverified computational claims.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 336

Let $B$ be the $3 \times 3 \times 3$ cube, partitioned into unit cells with coordinates $(x,y,z)$ where $1 \le x,y,z \le 3$.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 337

Solution to TAOCP 7.2.2.1 Exercise 337.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 338

A tetracube is a connected union of four unit cubes in $\mathbb{Z}^3$, considered up to rigid motion.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 339

Let an octomino be given, and suppose it defines a $4$-level prism that can be realized by tetracubes.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 340

Working
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 341

The problem is an exact cover instance built from the 29 pentacubes, augmented with additional geometric constraints coming from symmetry and partitioning requirements of a $7 \times 7 \times 5$ box.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 342

The problem is an exact cover instance in which each pentacube is an option and each unit cell of the target solid is an item.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 343

Let $P$ be a fixed pentomino.
taocp mathematics algorithms volume-4 simple Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 344

The packing problem is an exact cover instance in which each of the 25 solid Y pentominoes contributes an option consisting of the 5 unit cubes it occupies, and each unit cube of the $5\times 5\times...
taocp mathematics algorithms volume-4 simple Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 345

The previous construction fails because it forces each forbidden pair to be covered exactly once.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 346

The original solution fails because it replaces the geometric object with a 1-dimensional cycle decomposition.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 347

Let $\omega$ be a primitive $k$th root of unity, so $\omega^k = 1$ and $1 + \omega + \cdots + \omega^{k-1} = 0$.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 348

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-project Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 349

The previous writeup fails because it tries to force a naive grid argument that neither produces valid bricks nor supports the counting claim.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 350

The previous argument fails because it replaces the 3D packing problem with unjustified slab and projection reductions.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 351

Let $s = a+b+c+d+e$.
taocp mathematics algorithms volume-4 math-research Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 352

The previous solution is correct in its modeling but incomplete in the only place that matters: it never actually justifies the numerical value $8$.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 353

Solution to TAOCP 7.2.2.1 Exercise 353.
taocp mathematics algorithms volume-4 project Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 354

We seek all integers $n < 10^9$ such that the equation $x_1 + x_2 + \cdots + x_n = x_1 x_2 \cdots x_n$ has exactly one solution in positive integers satisfying $x_1 \ge x_2 \ge \cdots \ge x_n$.
taocp mathematics algorithms volume-4 math-hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 355

A polysphere is given as a connected set of points $\{(x_1,y_1,z_1,w_1),\ldots,(x_n,y_n,z_n,w_n)\}\subset S,$ where each point satisfies $w_k + x_k + y_k + z_k = 0$.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 356

The previous argument fails at a structural level: it replaces the actual combinatorics of tile embeddings with an unproved “rigidity” principle and never uses the classification of tetraspheres and t...
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 357

A truncated octahedron tessellates $\mathbb{R}^3$ face-to-face, so each cell has a well-defined adjacency graph in which two cells are adjacent exactly when they share a square or hexagonal face.
taocp mathematics algorithms volume-4 math-immediate Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 358

We begin by reconstructing the geometry of $S(3)$ directly from the defining condition.
taocp mathematics algorithms volume-4 hm-simple Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 359

The problem requires placing nine given pieces into a $65 \times 65$ square.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 360

The review correctly identifies the failure point: a valid solution must encode “reducedness” inside a legitimate Algorithm M (exact cover with primary and secondary items), not by introducing an inva...
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 361

We first restate the correct combinatorial bound and then give a fully valid geometric construction, avoiding the independence and “free assignment” issues in the rejected solution.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 362

We restart from the definition of the object being counted and keep the modification from Exercise 360 precise.
taocp mathematics algorithms volume-4 simple Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 363

Let the construction of Exercise 360 be interpreted in the standard way: items correspond to unit cells of the $m\times n$ grid together with the boundary-usage constraints that enforce reducedness, a...
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 366

Let $\mathcal{S}$ denote the set of all solutions produced by the construction in Exercise 365.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 367

A motley dissection of an $m\times n$ rectangle is a guillotine subdivision obtained by repeatedly cutting a rectangle into two smaller rectangles by a full horizontal or vertical cut, starting from t...
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 368

The previous argument fails because it attempts to interpret column-span quantities as independent combinatorial crossings.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 369

The flaw in the previous solution is not in the arithmetic bound t \le \binom{m+1}{2}-1, but in the missing justification that this bound is actually tight.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 370

Solution to TAOCP 7.2.2.1 Exercise 370.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 371

Let $R = [a \ldots b) \times [c \ldots d)$ be a subrectangle of $[0 \ldots n) \times [0 \ldots n)$.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 372

We work entirely from the geometric structure of a tatami floorplan.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 373

The original argument fails at the point where it replaces a global structural constraint (a guillotine partition with globally consistent segment lengths) by a local “attach a staircase” heuristic.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 374

An incomparable dissection consists of $t$ rectangles with side lengths $(h_i \times w_i)$ such that for all $i \ne j$ it is not the case that $h_i \le h_j$ and $w_i \le w_j$ simultaneously.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 375

Solution to TAOCP 7.2.2.1 Exercise 375.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 376

The earlier solution correctly reduced the problem to a horizontal-strip decomposition but failed at the key combinatorial constraint: it implicitly treated each row as independently partitioned.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 377

The previous solution fails because it assumes concatenation can generate new side lengths.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 378

We address the reviewer’s three critical issues directly and rebuild the proof in a way that is logically sound and avoids all invalid reductions.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 379

A packing of an $h \times n$ rectangle by copies of the Q pentomino is an exact cover of the set of unit cells of the rectangle by translated and rotated copies of a fixed set of 5 cells.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 380

Working
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 381

Let the given shape consist of four unit squares with no adjacency constraints between them, so that each copy is simply a multiset of four independent cells.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 382

Let $T:[0,7)^3\to[0,7)^3$ be T(x,y,z)=(7-y,\;7-z,\;7-x).
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 383

Let Exercise 382 provide a decomposition principle in the following form: there exist three ordered sequences of positive integers (a_1,\dots,a_{23}),\quad (b_1,\dots,b_{23}),\quad (c_1,\dots,c_{23}),...
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 384

An $l \times m \times n$ motley dissection consists of a family of subcuboids $[a_i,b_i) \times [c_i,d_i) \times [e_i,f_i),$ with $0 \le a_i < b_i \le l$, $0 \le c_i < d_i \le m$, $0 \le e_i < f_i \le...
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 385

A motley cuboid of size $l \times m \times n$ is a decomposition of the discrete box $[0,l) \times [0,m) \times [0,n)$ into finitely many subcuboids $(a_i,b_i)\times(c_i,d_i)\times(e_i,f_i)$ satisfyin...
taocp mathematics algorithms volume-4 math-project Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 386

Solution to TAOCP 7.2.2.1 Exercise 386.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 387

Solution to TAOCP 7.2.2.1 Exercise 387.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 388

The statement of the problem depends on the concrete futoshiki grids given in Figure 388, including the initial filled entries and the inequality relations between adjacent cells.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 389

Let the futoshiki puzzle consist of an $n\times n$ grid of variables $x_{i,j}$, each intended to take a value in ${1,\dots,n}$, with all rows and columns forming latin squares and with additional weak...
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 390

The flaw in part (a) is structural: it tries to encode a strict inequality using overlapping interval coverage, but exact cover does not express “existence of a separating threshold” unless that thres...
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 391

We restate the problem in the exact-cover framework required by Algorithm X.
taocp mathematics algorithms volume-4 Hard Jul 5, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 392

The previous solution fails because it replaces the actual futoshiki–Latin-square interaction with unjustified global claims.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 393

The core issue in the previous solution is not a minor gap but a structural failure: it replaces a constraint-satisfaction problem with a purely combinatorial relabeling argument, without first establ...
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 394

The previous solution fails because it never works on the actual solution set $S$, and instead replaces it with an artificial labeling model that does not correspond to futoshiki solutions.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 395

The previous solution fails because it artificially collapses the space of Latin squares to cyclic shifts.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 396

The review correctly identifies two fatal flaws in the proposed construction.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 397

An $n\times n$ grid is given.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 398

Working
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 399

A KenKen puzzle on an $n\times n$ grid defines variables $x_{ij}\in{1,\dots,n}$ subject to Latin constraints (all rows and columns are permutations) and cage constraints (each cage satisfies a fixed a...
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 400

Let the 11 clues be $C_1,\dots,C_{11}$.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 401

The previous argument fails because a 2-cell KenKen cage does not determine a unique unordered pair of values.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 402

The previous solution incorrectly treated cage products as if they should be analyzed via **prime factorization alone**.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 403

The previous solution fails because it incorrectly restricts KenKen clues, ignores the need for a defined ordering of clues, and introduces an irrelevant Latin-square completion argument.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 404

Solution to TAOCP 7.2.2.1 Exercise 404.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 405

Let $G=(V,E)$ be the given graph, let $v \in V$, and let $L \ge 1$.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 406

Working
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 407

The reviewer’s diagnosis is correct: the previous “solution” never engaged with the actual constraint graph of the full $4\times 8$ Hidato instance.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 408

A Hidato puzzle on a $6\times 6$ grid is a labeling of the $36$ cells by the integers $1,2,\dots,36$ such that consecutive integers occupy adjacent cells (adjacency in the king sense, including diagon...
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 409

A $10 \times 10$ Hidato puzzle assigns each cell either blank or a number from ${1,2,\dots,100}$ such that every number in this set appears exactly once in the completed grid.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 410

A slitherlink solution is a subset of grid edges such that every vertex has degree $0$ or $2$, forming a disjoint union of simple cycles, and the puzzle requires that the only valid configuration is a...
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 411

**Claim.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 412

Let the slitherlink grid have integer lattice vertices and unit edges between adjacent vertices.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 413

Let Algorithm C be the exact cover procedure derived from Algorithm X in Section 7.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 414

The previous solution fails at a basic structural level: it incorrectly treats a small forced boundary fragment as globally isolating, and from that deduces impossibility.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 415

Let the $5\times 5$ slitherlink grid be fixed.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 416

We correct the missing argument by isolating the fundamental invariant of slitherlink solutions.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 417

We address the reviewer’s objections by discarding the invalid “padding extension” idea and rebuilding the argument from a configuration where global consistency is fully controlled.
taocp mathematics algorithms volume-4 math-research Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 418

The symmetry is the involution (i,j)\mapsto (4-i,4-j).
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 419

The previous argument fails because it never engages with the actual constraint system of the grid.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 420

The previous argument fails because it tries to force a global 2-regular structure in the face graph including the outer face, which is not part of the slitherlink constraint system.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 421

The original solution fails because it replaces Masyu propagation with unverified “global forcing”.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 422

Working
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 423

Let the grid of the $m\times n$ masyu puzzle be embedded in the usual way, so that each potential edge $e$ is shared by at most two cells.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 424

The previous response fails for a simple reason: it replaces the task with a meta-description of how one would solve it, while the exercise explicitly demands the outcome of an exhaustive study on the...
taocp mathematics algorithms volume-4 project Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 425

We first address what the problem actually requires: for each $n \in \{4,5,6\}$ and each integer $k$, construct a Masyu puzzle on an $n \times n$ grid whose unique solution contains exactly $k$ occurr...
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 426

The previous solution failed because it never engaged with the given instance.
taocp mathematics algorithms volume-4 project Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 427

The original attempt failed because it never established **uniqueness of the solution loop**, and its construction of a Hamiltonian cycle was only informal.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 428

The failure in the previous solution is structural: a spiral Hamiltonian cycle has $\Theta(n^2)$ turns, so any constant-density sampling still yields $\Theta(n^2)$ clues.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 429

The previous solution fails primarily because it never engages with the actual instances in Figures 429a and 429b.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 430

A kakuro instance specifies a finite set of cells partitioned into horizontal and vertical blocks.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 431

The previous argument fails because it replaces the given Kakuro instance with a hypothetical system.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 432

The missing “solution” failed because it never instantiated the diagrams, so we restart from the underlying combinatorial model of a Kakuro region: each white run is a sequence of distinct digits from...
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 433

The previous solution fails because it replaces the actual constraint analysis of the given Kakuro instance with an unproved claim of uniqueness.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 434

Let the $9\times 9$ kakuro diagram be represented by a binary matrix $(x_{ij})$, where $x_{ij}=1$ denotes a white cell (empty cell) and $x_{ij}=0$ denotes a black cell.
taocp mathematics algorithms volume-4 project Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 435

The previous argument fails because it confuses “cell value equals clue” with Kakuro’s actual constraint system.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 436

Let $W$ be the white set of a solution and let $x$ be a seed.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 437

Let the hitori instance consist of an $m \times n$ array indexed by cells $x = (r,c)$, each containing a symbol $\sigma(x)$ from a finite alphabet.
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 438

The previous solution failed because it attempted to introduce an additional pruning condition based on an informal notion of “forced black in all completions,” which is not a valid XCC-state predicat...
taocp mathematics algorithms volume-4 Hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 439

Let $G=(V,E)$ be a graph and $U\subseteq V$.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 440

**Answer: False.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 441

Let the instance be a string $S[1],\dots,S[n]$ over an alphabet of size $d$.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 442

We first restate the definition of a hitori cover as used in Exercise 439.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 443

The previous argument fails because it attempts to extract a global lower bound from an unproven “segment endpoint” structure.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 444

A Hitori puzzle on an $n \times n$ grid assigns a symbol to each cell.
taocp mathematics algorithms volume-4 math-hard Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 445

The previous solution fails because it never reconstructs the combinatorial problem that actually depends on the five explicit $6\times 6$ solution patterns.
taocp mathematics algorithms volume-4 math-medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 446

The previous solution fails because it replaces the actual Hitori constraints with a fictitious equality-class structure.
taocp mathematics algorithms volume-4 project Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 447

We restart from the definitions.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 448

Let a _double word square_ be a $6\times 6$ arrangement of words from $\mathrm{WORDS}(3000)$ such that every row and every column is a word from the same set of six words, as in Exercise 87.
taocp mathematics algorithms volume-4 Medium Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 449

A _Hitori puzzle_ consists of an $m \times n$ array of digits together with the constraint that one may blacken a subset of cells so that in each row and each column, no digit appears more than once a...
taocp mathematics algorithms volume-4 project Jun 28, 2026
Practice › Mathematics › TAOCP › TAOCP Vol 4: Combinatorial Algorithms › TAOCP 7.2.2.1: Dancing Links ›

TAOCP 7.2.2.1 Exercise 450

The previous solution failed because it replaced the construction in Section 7.
taocp mathematics algorithms volume-4 project Jun 28, 2026