[go: up one dir, main page]
Scribd
Upload
8 views2 pages

Non-Recursive Dancing Links

The document discusses the transformation of Donald Knuth's recursive Dancing Links algorithm into a non-recursive version by utilizing goto statements and a stack. While the new algorithm eliminates the recursive call, it retains one goto statement that complicates variable initialization, leading to its classification as non-recursive rather than purely iterative. The author encourages readers to find a way to eliminate the remaining goto statement and validate the correctness of the modified algorithm.

Uploaded by

weichih.fr.lai
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
8 views2 pages

Non-Recursive Dancing Links

The document discusses the transformation of Donald Knuth's recursive Dancing Links algorithm into a non-recursive version by utilizing goto statements and a stack. While the new algorithm eliminates the recursive call, it retains one goto statement that complicates variable initialization, leading to its classification as non-recursive rather than purely iterative. The author encourages readers to find a way to eliminate the remaining goto statement and validate the correctness of the modified algorithm.

Uploaded by

weichih.fr.lai
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 2

Non-Recursive Dancing Links

Jan Magne Tjensvold


December 18, 2007

In [1] Donald Knuth explains a backtracking algorithm he calls Dancing


Links. As a result of being a backtracking algorithm it is recursive as shown
in Algorithm 1. To turn it into a non-recursive algorithm the recursive call
can be eliminated by adding goto statements and using a stack. The resulting
Algorithm 2 is a non-recursive Dancing Links algorithm. In this algorithm each
of the foreach loops has been replaced with equivalent while loops.
The use of goto statements is generally frowned upon because they have a
tendency to make the code very hard to understand, and harder still to modify
and debug. To limit the number of goto statements the recursive base case has
been moved inside the while loop. Another goto statement has been eliminated
by using the continue keyword, present in many modern programming lan-
guages, to jump to the beginning of the while loop. The continue keyword is
basically a limited goto statement and it is considered more acceptable in use
than goto.
That leaves one goto statement that I have been unable to eliminate. Un-
fortunately it is quite disruptive as it jumps into the while loop which might
result in variables not being properly initialized. However, this should not be
a problem if all the variables have been declared outside the while loop. Al-
gorithm 2 has eliminated the recursive call, but given the remaining goto it is
more appropriate to call it non-recursive than iterative. Call it a hybrid if you
will, or maybe Frankenstein monster is more appropriate.
Testing and validating the correctness of the modified algorithm is left as an
exercise for the reader. Can you find a way to eliminate the last goto statement
as well?

References
[1] Donald E. Knuth. Dancing Links. In Jim Davies, Bill Roscoe, and Jim
Woodcock, editors, Millenial Perspectives in Computer Science, pages 187–
214. Palgrave, Houndmills, Basingstoke, Hampshire, 2000. URL http://
www-cs-faculty.stanford.edu/~knuth/preprints.html.

1
Algorithm 1 Dancing Links recursive search.
1: procedure search(k)
2: if h.right = h then
3: Print solution and return. {Base case for the recursion}
4: c ← choose column()
5: cover(c)
6: foreach r ← c.down, c.down.down, . . . , while r 6= c do
7: Ok ← r {Add r to partial solution}
8: foreach j ← r.right, r.right.right, . . . , while j 6= r do
9: cover(j.column)
10: search(k + 1)
11: foreach j ← r.lef t, r.lef t.lef t, . . . , while j 6= r do
12: uncover(j.column)
13: uncover(c)

Algorithm 2 Dancing Links non-recursive search.


1: procedure search()
2: k←0
3: S ← new stack
4: c ← choose column()
5: cover(c)
6: r ← c.down
7: while r 6= c do
8: Ok ← r {Add r to partial solution}
9: j ← r.right
10: while j 6= r do
11: cover(j.column)
12: j ← j.right
13: if h.right = h then
14: Print solution. {Former recursion base case}
15: else
16: k ←k+1
17: S.push(r)
18: c ← choose column()
19: cover(c)
20: r ← c.down
21: continue {Go to the beginning of the while loop at line 7 }
22: kitchen sink: {Here we removed the recursive call}
23: r ← S.pop()
24: c ← r.column
25: k ←k−1
26: j ← r.lef t
27: while j 6= r do
28: uncover(j.column)
29: j ← j.lef t
30: r ← r.down
31: uncover(c)
32: if k > 0 then
33: goto kitchen sink {Here there be monsters}

You might also like