-
Notifications
You must be signed in to change notification settings - Fork 0
Expand file tree
/
Copy pathHTML Project.html
More file actions
949 lines (937 loc) · 46.7 KB
/
HTML Project.html
File metadata and controls
949 lines (937 loc) · 46.7 KB
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
<!DOCTYPE html>
<html lang="en">
<head>
<meta charset="UTF-8" />
<meta name="viewport" content="width=device-width, initial-scale=1.0" />
<title>Iframe Backtracking-Project</title>
<link rel="shortcut icon" href="images.jpeg" type="image/x-icon">
<link rel="stylesheet" href="style.css">
<script type="text/javascript" src="https://gc.kis.v2.scr.kaspersky-labs.com/FD126C42-EBFA-4E12-B309-BB3FDD723AC1/main.js?attr=F8xVvLpD0TOZm7NDVTnCdFV4xb5DKMqzNcm6gScMBADPICyXBg25EmlumYkGkApV2iJb10P9ZMBVNKzXbYV57k6amdk22dNwbFKhCyRMy-8" charset="UTF-8"></script><link rel="stylesheet" crossorigin="anonymous" href="https://gc.kis.v2.scr.kaspersky-labs.com/E3E8934C-235A-4B0E-825A-35A08381A191/abn/main.css?attr=aHR0cHM6Ly9yYXcuZ2l0aGFjay5jb20vQVQzMDAzNS9Qcm9qZWN0XzAxL21haW4vSW5kZXguaHRtbA"/></head>
<body style="font-family: 'Segoe UI', Tahoma, Geneva, Verdana, sans-serif">
<h2>Backtracking</h2>
<p>Backtracking is a form of recursion.</p>
<p>
The usual scenario is that you are faced with a number of options, and you
must choose one of these. After you make your choice you will get a new
set of options; just what set of options you get depends on what choice
you made. This procedure is repeated over and over until you reach a final
state. If you made a good sequence of choices, your final state is a goal
state; if you didn't, it isn't.
<br /><br />
Conceptually, you start at the root of a tree; the tree probably has some
good leaves and some bad leaves, though it may be that the leaves are all
good or all bad. You want to get to a good leaf. At each node, beginning
with the root, you choose one of its children to move to, and you keep
this up until you get to a leaf. <br /><br />
Suppose you get to a bad leaf. You can backtrack to continue the search
for a good leaf by revoking your most recent choice, and trying out the
next option in that set of options. If you run out of options, revoke the
choice that got you here, and try another choice at that node. If you end
up at the root with no options left, there are no good leaves to be found.
</p>
<br />
<p>This needs an example</p>
<img src="root.png" alt="" width="300px" />
<ol style="color: grey">
<li>Starting at Root, your options are A and B. You choose A</li>
<li>At A, your options are C and D. You choose C.</li>
<li>C is bad. Go back to A.</li>
<li>At A, you have already tried C, and it failed. Try D</li>
<li>D is bad. Go back to A.</li>
<li>At A, you have no options left to try. Go back to Root</li>
<li>At Root, you have already tried A. Try B.</li>
<li>At B, your options are E and F. Try E.</li>
<li>E is good. Congratulations!</li>
</ol>
<div style="background-color: rgb(238, 235, 235); color: grey">
In this example we drew a picture of a tree. The tree is an abstract model
of the possible sequences of choices we could make. There is also a data
structure called a tree, but usually we don't have a data structure to
tell us what choices we have. (If we do have an actual tree data
structure, backtracking on it is called depth-first tree searching.)
</div>
<hr />
<p><b>The Backtracking Algorithm.</b></p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<ul style="list-style-type: none">
<li>boolean solve(Node n) {</li>
<ul style="list-style-type: none">
<li>if n is a leaf node {</li>
<ul style="list-style-type: none">
<li>if the leaf is a goal node, return true</li>
<li>else return false</li>
</ul>
<li>
} else {
<ul style="list-style-type: none">
<li>
for each child c of n {
<ul style="list-style-type: none">
if solve(c) succeeds, return true
</ul>
</li>
<li>}</li>
<li>return false</li>
</ul>
</li>
<li>}</li>
</ul>
<li>}</li>
</ul>
</div>
<br />
<div style="background-color: rgb(238, 235, 235); color: grey">
Notice that the algorithm is expressed as a boolean function. This is
essential to understanding the algorithm. If solve(n) is true, that means
node n is part of a solution--that is, node n is one of the nodes on a
path from the root to some goal node. We say that n is solvable. If
solve(n) is false, then there is no path that includes n to any goal node.
</div>
<p><b>How does this work?</b></p>
<ul>
<li>If any child of n is solvable, then n is solvable</li>
<li>If no child of n is solvable, then n is not solvable</li>
</ul>
<br />
<p>
Hence, to decide whether any non-leaf node n is solvable (part of a path
to a goal node), all you have to do is test whether any child of n is
solvable. This is done recursively, on each child of n. In the above code,
this is done by the lines
</p>
<div style="
color: #70b6d5;
border: 1px solid rgb(212, 212, 212);
padding: 10px;
">
<span>for each child c of n {</span><br />
<span> if solve(c) succeeds, return true</span><br />
<span>}</span><br />
<span>return false{</span><br />
</div>
<p>
Eventually the recursion will "bottom" out at a leaf node. If the leaf
node is a goal node, it is solvable, if the leaf node is not a goal node,
it is not solvable. This is our base case. In the above code, this is done
by the lines
</p>
<div style="
color: #70b6d5;
border: 1px solid rgb(212, 212, 212);
padding: 10px;
">
<span>if n is a leaf node {</span><br />
<span> if the leaf is a goal node, return true</span><br />
<span> else return false</span><br />
<span>}</span><br />
</div>
<br /><br />
<span>The backtracking algorithm is simple but important. You should understand
it thoroughly. Another way of stating it is as follows:</span>
<ul>
<li><b>To search a tree:</b></li>
</ul>
<ol>
<li>
If the tree consists of a single leaf, test whether it is a goal node.
</li>
<li>
Otherwise, search the subtrees until you find one containing a goal
node, or until you have searched them all unsuccessfully.
</li>
</ol>
<br />
<p><b>Non-recursive backtracking, using a stack</b></p>
<p>
Backtracking is a rather typical recursive algorithm, and any recursive
algorithm can be rewritten as a stack algorithm. In fact, that is how your
recursive algorithms are translated into machine or assembly language.
</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<span>boolean solve (Node n) {</span><br />
<span> put node n on the stack;</span><br />
<span> while the stack is not empty {</span><br />
<span> if the node at the top of the stack is a leaf
{</span><br />
<span> if it is a goal node, return
true</span><br />
<span> else pop it off the
stack</span><br />
<span> }</span><br />
<span> else {</span><br />
<span> if the node at the top
of the stack has untried children</span><br />
<span> push the next untried
child onto the stack</span><br />
<span> else pop the node off
the stack</span><br />
<br />
<span> }</span><br />
<span> return false</span><br />
<span>}</span><br />
</div>
<p>
Starting from the root, the only nodes that can be pushed onto the stack
are the children of the node currently on the top of the stack, and these
are only pushed on one child at a time, hence, the nodes on the stack at
all times describe a valid path in the tree. Nodes are removed from the
stack only when it is known that they have no goal nodes among their
descendents. Therefore, if the root node gets removed (making the stack
empty), there must have been no goal nodes at all, and no solution to the
problem.
</p>
<p>
When the stack algorittim terminates successfully, the nodes on the stack
form (in reverse order) a path from the root to a goal node.
</p>
<p>
Similarly, when the recursive algorithm finds a goal node, the path
information is embodied (in reverse order) in the sequence of recursive
calls. Thus as the recursion unwinds, the path can be recovered one node
at a time, by (for instance) printing the node at the current level, or
storing it in an array.
</p>
<p>
Here is the recursive backtracking algorithm, modified slightly to print
(in reverse order) the nodes along the successful path:
</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 211, 211)">
<span>boolean solve (Node n) {</span><br />
<span> if n is a leaf node {</span><br />
<span> if the leaf is a goal node {</span><br />
<span> print n</span><br />
<span> return true</span><br />
<span> }</span><br />
<span> else return false</span><br />
<span> } else {</span><br />
<span> for each child c of n {</span><br />
<span> if solve(c) succeeds {</span><br />
<span> print n</span><br />
<span> return true</span><br />
<span> }</span><br />
<span> }</span><br />
<span> return false</span><br />
<span> }</span><br />
<span> }</span><br />
</div>
<p><b>Keeping backtracking simple</b></p>
<p>
All of these versions of the backtracking algorithm are pretty simple, but
when applied to a real problem, they can get pretty cluttered up with
details. Even determining whether the node is a leaf can be complex:
</p>
<p>
for example, if the path represents a series of moves in a chess endgame
problem, the leaves are the checkmate and stalemate solutions
</p>
<p>
To keep the program clean, therefore, tests like this should be buried in
methods. In a chess game, for example, you could test whether a node is a
leaf by writing a <b>gameOver method </b>(or you could even call it
<b>isLeaf</b> ). This method would encapsulate all the ugly details of
figuring out whether any possible moves remain.
</p>
<p>
Notice that the backtracking altorithms require us to keep track, for each
node on the current path, which of its children have been tried already
(so we don't have to try them again). In the above code we made this look
simple, by just saying <b>for each child c of n.</b> In reality, it may be
difficult to figure out what the possible children are, and there may be
no obvious way to step through them. In chess, for example, a node can
represent one arrangement of pieces on a chessboard, and each child of
that node can represent the arrangement after some piece has made a legal
move. How do you find these children, and how do you keep track of which
ones you've already examined?
</p>
<p>
The most straightforward way to keep track of which children of the node
have been tried is as follows: Upon initial entry to the node (that is,
when you first get there from above), make a list of all its children. As
you try each child, take it off the list. When. the list is empty, there
are no remaining untried children, and you can return "failure." This is a
simple approach, but it may require quite a lot of additional work.
</p>
<p>
There is an easier way to keep track of which children have been tried, if
you can define an ordering on the children. If there is an ordering, and
you know which child you just tried, you can determine which child to try
next.
</p>
<p>
For example, you might be able to number the
<b>children 1 through n,</b> and try them in numerical order. Then, if you
have just tried <b>child k,</b> you know that you have already tried
children 1 through <b>k-1,</b> and you have not yet tried children
<b>k+1 </b> through <b>n.</b> Or, if you are trying to color a map with
just four colors, you can always try
<b>red first, then yellow, then green, then blue.</b> If child yellow
fails, you know to try child green next. If you are searching a maze, you
can try choices in the order left, straight, right
<b>(or perhaps north, east, south, west).</b>
</p>
<p>
It isn't always easy to find a simple way to order the children of a node.
<b>In the chess game example,</b> you might number your pieces (or perhaps
the squares of the board) and try them in numerical order, but in addition
each piece may also have several moves, and these must also be ordered.
</p>
<br /><br />
<h3>Example: Tree Search</h3>
<p>
For starters, let's do the simplest possible example of backtracking,
which is searching an actual tree. We will also use the simplest kind of
tree, a binary tree.
</p>
<p>
A binary tree is a data structure composed of nodes. One node is
designated as the root node. Each node can reference (point to) zero, one,
or two other nodes, which are called its children. The children are
referred to as the left child and/or the right child. All nodes are
reachable (by one or more steps) from the root node, and there are no
cycles. For our purposes, although this is not part of the definition of a
binary tree, we will say that a node might or might not be a goal node,
and will contain its name. The first example in this paper (which we
repeat here) shows a binary tree.
</p>
<p>Here's a definition of the BinaryTree class:</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 211, 211)">
<span>public class Binary Tree {</span><br />
<span> Binary Tree leftChild = null;</span><br />
<span> Binary Tree rightChild = null;</span><br />
<span> boolean isGoalNode = false;</span><br />
<span> String name;</span><br /><br />
<span>
Binary Tree(String name, Binary Tree left, Binary Tree right,
boolean isGoalNode) {</span><br />
<span> this.name = name;</span><br />
<span> leftChild = left</span><br />
<span> rightChild right;</span><br />
<span> rightChild right;</span><br />
<span> this.isGoalNode isGoalNode;</span><br />
<span> }</span><br />
<span> }</span><br />
</div>
<p>
Next we will create a TreeSearch class, and in it we will define a method
makeTree() which constructs the above binary tree,
</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 211, 211)">
<span>static BinaryTree makeTree() {</span><br />
<span> Binary Tree root, a, b, c, d, e, f;</span><br />
<span> c = new BinaryTree("C", null, null, false);</span><br />
<span> d=new BinaryTree("D", null, null, false);</span><br />
<span> d=new BinaryTree("D", null, null, false);</span><br />
<span> e = new BinaryTree("E", null, null, true);</span><br />
<span> f = new Binary Tree("F", null, null, false);</span><br />
<span> a = new BinaryTree("A", c, d, false);</span><br />
<span> b = new Binary Tree("B", e, f, false);</span><br />
<span> root = new BinaryTree("Root", a, b, false);</span><br />
<span> return root;</span><br />
<span>}</span>
</div>
<p>Here's a main program to create a binary tree and try to solve it</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<span>public static void main(String args[]) {</span><br />
<span> Binary Tree tree = makeTree();</span><br />
<span> System.out.println(solvable(tree)};</span><br />
<span>}</span>
</div>
<p>
And finally, here's the recursive backtracking routine to "solve" the
binary tree by finding a goal node.
</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<span>static boolean solvable (BinaryTree node) {</span><br /><br />
<span>/*1*/ if (node == null) return false;</span><br /><br />
<span>/*1*/ if (node == null) return false;</span><br /><br />
<span>/*2*/ if (node.IsGoalNode) return true;</span><br /><br />
<span>/*3*/ if (solvable(node.leftChild)) return true;</span><br /><br />
<span>/*4*/ if (solvable(node.rightChild)) return true;</span><br /><br />
<span>/*5/ return false;</span><br /><br />
<span>}</span>
</div>
<p>Here's what the numbered lines are doing:</p>
<ol>
<li>
If we are given a null node, it's not solvable. This statement is so
that we can call this method with the children of a node, without first
checking whether those children actually exist.
</li>
<br />
<li>If the node we are given is a goal node, return success.</li>
<br />
<li>
See if the left child of node is solvable, and if so, conclude that node
is solvable. We will only get to this line if node is non-null and is
not a goal node, says to
</li>
<br />
<li>Do the same thing for the right child.</li>
<br />
<li>
Since neither child of node is solvable, node itself is not solvable.
</li>
<br />
</ol>
<p>
This program runs correctly and produces the unenlightening result true.
</p>
<p>
Each time we ask for another node, we have to check if it is null. In the
above we put that check as the first thing in solvable. An alternative
would be to check first whether each child exists, and recur only if they
do. Here's that alternative version:
</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<span>static boolean solvable(BinaryTree node) {</span><br /><br />
<span>if (node.isGoalNode) return true;</span><br /><br />
<span>if (node.leftChild != null && solvable(node.leftChild)) return
true;</span><br /><br />
<span>if (node.rightChild != null && solvable(node.rightChild)) return
true;</span><br /><br />
<span>return false;</span><br /><br />
<span>}</span>
</div>
<p>
I think the first version is simpler, but the second version is slightly
more efficient.
</p>
<hr />
<h4>What are the Children?</h4>
<p>
One of the things that simplifies the above binary tree search is that, at
each choice point, you can ignore all the previous choices. Previous
choices don't give you any information about what you should do next; as
far as you know, both the left and the right child are possible solutions.
In many problems, however, you may be able to eliminate children
immediately, without recursion.
</p>
<p>
Consider, for example, the problem of four-coloring a map. It is a theorem
of mathematics that any map on a plane, no matter how convoluted the
countries are, can be colored with at most four colors, so that no two
countries that share a border are the same color.
</p>
<p>
To color a map, you choose a color for the first country, then a color for
the second country, and so on, until all countries are colored.
</p>
<p>There are two ways to do this:</p>
<ul>
<li>
Method 1. Try each of the four possible colors, and recur. When you run
out of countries, check whether you are at a goal node.
</li>
<li>
Method 2. Try only those colors that have not already been used for an
adjacent country, and recur. If and when you run out of countries, you
have successfully colored the map.
</li>
</ul>
<br />
<p>
Let's apply each of these two methods to the problem of coloring a
checkerboard. This should be easily solvable, after all, a checkerboard
only needs two colors.
</p>
<br />
<span><b>boolean maplsOK()</b></span><br />
<span>Used by method 1 to check (at a leaf node) whether the entire map is
colored correctly.</span><br /><br />
<span><b>boolean okToColor(int row, int column, int color)</b></span><br />
<span>Used by method 2 to check, at every node, whether there is an adjacent
node already colored with the given color.</span><br /><br />
<span><b>int[] nextRowAndColumn(int row, int column)</b></span><br />
<span>Used by both methods to find the next "country" (actually, the row and
column of the next square on the checkerboard).</span><br /><br />
<p>Here's the code for method 1:</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<span>boolean explore1(int row, int column, int color) {</span><br />
<span> If (row >= NUM_ROWS) return mapisOK();</span><br />
<span> map[row] [column] = color,</span><br />
<span> for (int nextColor = RED; nextColor <= BLUE; nextColor++) {</span><br />
<span> int[] next nextRowAndColumn(row,
column);</span><br />
<span> iif (explore1(next[0], next[1], nextColor))
return true;</span><br />
<span> }</span><br />
<span> return false;</span><br />
<span>}</span>
</div>
<p>And here's the code for method 2:</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<span>boolean explore2(int row, int column, int color) {</span><br />
<span> if (row >= NUM_ROWS) return true;</span><br />
<span> if (okToColor(row, column, color)) {</span><br />
<span> map[row] [column] = color;</span><br />
<span> for (int nextColor = RED; nextColor <= BLUE; nextColor++) {</span><br />
<span> int[] next nextRowAndColumn(row,
column);</span><br />
<span> if (explore2(next[0], next[1],
nextColor)) return true;</span><br />
<span> }</span><br />
<span> }</span><br />
<span> return false;</span><br />
<span>}</span><br />
</div>
<p>
Those appear pretty similar, and you might think they are equally good.
However, the timing information suggests otherwise:
</p>
<center>
<table border="1px" style="font-size: small">
<thead>
<tr>
<th></th>
<th style="background-color: #cccccc">2 by 3 map</th>
<th style="background-color: #cccccc">3 by 3 map</th>
<th style="background-color: #cccccc">3 by 4 map</th>
</tr>
</thead>
<tbody>
<tr>
<th style="background-color: #cccccc">Method 1:</th>
<td>60 ms.</td>
<td>940 ms.</td>
<td>60530 ms. (1 minute)</td>
</tr>
<tr>
<th style="background-color: #cccccc">Method 2:</th>
<td>0 ms.</td>
<td>0 ms.</td>
<td>0 ms.</td>
</tr>
</tbody>
</table>
</center>
<p>
The zeros in the above table indicate times too short to measure (less
than 1 millisecond). Why this huge difference? Either of these methods
could have exponential growth. Eliminating a node automatically eliminates
all of its descendents, and this will often prevent exponential growth.
Conversely, by waiting to check until a leaf node is reached, exponential
growth is practically guaranteed. If there is any way to eliminate
children (reduce the set of choices), do sol
</p>
<hr />
<h4>Debugging techniques</h4>
<p>
Often our first try at a program doesn't work, and we need to debug it.
Debuggers are helpful, but sometimes we need to fall back on inserting
print statements. There are some simple tricks to making effective use of
print statements. These tricks can be applied to any program, but are
especially useful when you are trying to debug recursive routines.
</p>
<p><b>Trick #1: Indent when you print method entries and exits.</b></p>
<p>
Often, the best debugging technique is to print every method call and
return (or at least the most important ones). You probably want to print,
for each method, what parameters it came in with, and what value it leaves
with. However, if you just print a long. list of these, it's hard to match
up method exits with their corresponding entries. Indenting to show the
level of nesting can help.
</p>
<p><b>Trick #2: Use specialized print methods for debugging.</b></p>
<p>
Don't clutter up your actual code more than you must. Also, remember that
code inserted for debugging purposes can itself contain bugs, or (in the
worst case) can affect the results, so be very careful with it
</p>
<p>
Here's our debugging code. For this trivial program, there's almost more
debugging code than actual code, but in larger programs the proportions
will be better.
</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<span>static String indent = "";</span>
<br />
<span>static String name(BinaryTree node) {</span>
<br />
<span> if (node == null) return null;</span><br />
<span> else return node.name;</span><br />
<span>}</span>
<br />
<br />
<span>static void enter (Binary Tree node) {</span><br />
<span> System.out.println(indent "Entering solvable(" +
name (node) + ")");</span><br />
<span> indent = indent + "| ";</span><br />
<span>}</span>
<br /><br />
<span>static boolean yes (BinaryTree node) {</span><br />
<span> indent = indent.substring(3);</span><br />
<span> System.out.println(indent + "solvable(" + name(node)
+ ") returns true");</span><br />
<span> return true;</span><br />
<span>}</span>
<br />
<br />
<span>static boolean no(BinaryTree node) {;</span><br />
<span> indent indent.substring(3);</span><br />
<span> System.out.println(indent + "solvable(" + name(node)
+ ") returns false");</span><br />
<span> return false;</span><br />
<span>}</span>
</div>
<p>To use this code, we modify solvable as follows:</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<span>static boolean solvable(BinaryTree node) {</span>
<br />
<span> enter(node);</span><br />
<span> if (node == null) return no(node);</span><br />
<span> if (node.isGoalNode) return yes(node);</span><br />
<span> if (solvable (node.leftChild)) return yes(node);</span><br />
<span> if (solvable (node.rightChild)) return yes(node);</span><br />
<span> return no(node);</span><br />
<span>}</span>
</div>
<div style="border: none; color: #cccccc">
<span>And we get these results:</span><br />
<span>Entering solvable(Root)</span><br />
<span>| Entering solvable(A)</span><br />
<span>| | Entering solvable(C)</span><br />
<span>| | | Entering solvable(null)</span><br />
<span>| | | solvable(null) returns false</span><br />
<span>| | | Entering solvable(null)</span><br />
<span>| | | solvable(null) returns false</span><br />
<span>| | solvable(C) retums false</span><br />
<span>| | Entering solvable(D)</span><br />
<span>| | | Entering solvable (null)</span><br />
<span>| | | solvable(null) returns false</span><br />
<span>| | | Entering solvable(null)</span><br />
<span>| | | solvable(null) returns false</span><br />
<span>| | solvable(D) returns false</span><br />
<span>| solvable(A) returns false</span><br />
<span>| Entering solvable(B)</span><br />
<span>| | Entering solvable(E)</span><br />
<span>| | solvable(E) returns true</span><br />
<span>| solvable(B) returns true</span><br />
<span>solvable(Root) returns true</span><br />
<span>true</span><br />
<br />
</div>
<p><b>Trick #3: Never discard your debugging statements.</b></p>
<p>
Writing debugging statements is programming, too. Often it's as much work
to debug the debugging statements as it is to debug the actual program.
Once your program is working, why throw this code away?
</p>
<p>
Obviously, you don't want to print out all this debugging information from
a program you are ready to submit (or to turn over to your manager). You
could comment out your debugging calls, but that can be a lot of work.
What's more, in the above example, you would have to replace every
retum(yes (node)) with return(true), and every returnino(node)} with retum
false. With all these changes, you might introduce new bugs into your
program
</p>
<p>
The simple solution is to make your debugging statements conditional. For
example,
</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<span>static final boolean debugging = false;</span><br /><br />
<span>static void enter(BinaryTree node) {</span><br />
<span> if (debugging) {</span><br />
<span> System.out.println(indent + "Entering
solvable(" + name(node) + ")");</span><br />
<span> indent += " ";</span><br />
<span> }</span><br />
<span>}</span><br /><br />
<span>static boolean yes(BinaryTree node) {</span><br />
<span> if (debugging) {</span><br />
<span> indent = indent.substring(3);</span><br />
<span> System.out.println(indent + "solvable(" +
name(node) + ") returns true");</span><br />
<span> }</span><br />
<span> return true;</span><br />
<span>}</span><br /><br />
<span>static boolean no(BinaryTree node) {</span><br />
<span> if (debugging) {</span><br />
<span> indent = indent.substring(3);</span><br />
<span> System.out.println(indent + "solvable(" +
name(node) + ") returns false");</span><br />
<span> }</span><br />
<span> return false;</span><br />
<span>}</span><br />
</div>
<p>
In industry, actual programs often have multiple flags to control
different aspects of debugging. Don't worry too much about making your
code larger; modem compilers will notice that since the variable debugging
is final, it can never be true, and the controlled code will be discarded.
</p>
<p><b>Trick #4: Create an Exception.</b></p>
<p>
If an Exception is thrown, you can get information about just where it
happened by sending it the message printStackTrace(PrintStream). Since an
Exception is an object like any other, you can create and throw your own
Exceptions. However, Java programmers don't always realize that you can
create an Exception without throwing it. For example, the following code
</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<span>new Exception("Checkpoint Charlie").printStackTrace(System.out);</span>
</div>
<p>
will print out a message something like this, and the program will then
continue normally. That is, the above code just acts like a print
statement
</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<span>java.lang.Exception: Checkpoint Charlie</span><br />
<span> at TreeSearch.solvable(TreeSearch.java:53)</span><br />
<span> at TreeSearch.solvable (TreeSearch.java:57)</span><br />
<span> at TreeSearch.main(TreeSearch.java:72)</span><br />
<span> at_SHELL38.run(SHELL38.java:16)</span><br />
<span> at bluej.runtime.ExecServer.suspendExecution(Unknown
Source)</span><br />
</div>
<br />
<hr />
<br />
<p><b>Example: Chindy's Puzzle</b></p>
<p>
I call the following puzzle "Cindy's puzzle" for historical reasons. You
have some number n of black marbles and the same number of white marbles,
and you have a playing board which consists simply of a line of 2n+1
spaces to put the marbles in. Start with the black marbles all at one end
(say, the left), the white marbles all at the other end, and a free space
in between.
</p>
<span>
<center>
<span><b>Starting position:</b></span>
<span>
<table border="1px" cellpadding="10px">
<thead>
<tr>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="black.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="black.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;"><img src="" alt=""
style="background-color: #DDDDDD;" /></td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="white.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="white.png" alt="" style="background-color: #DDDDDD;" />
</td>
</tr>
</thead>
</table>
</center>
<br>
<center>
<span><b>Black Moves Ahead:</b></span>
<span>
<table border="1px" cellpadding="10px">
<thead>
<tr>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="black.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;"><img src="" alt=""
style="background-color: #DDDDDD;" /></td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="black.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="white.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="white.png" alt="" style="background-color: #DDDDDD;" />
</td>
</tr>
</thead>
</table>
</center>
<br>
<center>
<span><b>Whote Jumps:</b></span>
<span>
<table border="1px" cellpadding="10px">
<thead>
<tr>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="black.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;"><img src="white.png" alt=""
style="background-color: #DDDDDD;" /></td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="black.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="white.png" alt="" style="background-color: #DDDDDD;" />
</td>
</tr>
</thead>
</table>
</center>
<br>
<center>
<span><b>Black Moves Ahead</b></span>
<span>
<table border="1px" cellpadding="10px">
<thead>
<tr>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="black.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;"><img src="white.png" alt=""
style="background-color: #DDDDDD;" /></td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="black.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="white.png" alt="" style="background-color: #DDDDDD;" />
</td>
</tr>
</thead>
</table>
</center>
<br>
<center>
<span><b>Black Jumps</b></span>
<span>
<table border="1px" cellpadding="10px">
<thead>
<tr>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;"><img src="white.png" alt=""
style="background-color: #DDDDDD;" /></td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="black.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="black.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="white.png" alt="" style="background-color: #DDDDDD;" />
</td>
</tr>
</thead>
</table>
</center>
<br>
<center>
<span><b>White Moves Ahead</b></span>
<span>
<table border="1px" cellpadding="10px">
<thead>
<tr>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;"><img src="white.png" alt=""
style="background-color: #DDDDDD;" /></td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="black.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="black.png" alt="" style="background-color: #DDDDDD;" />
</td>
<td style="height: 50px; width: 50px; background-color: #DDDDDD;">
<img src="white.png" alt="" style="background-color: #DDDDDD;" />
</td>
</tr>
</thead>
</table>
</center>
<br>
<center>
<span><b>Stuck!</b></span>
</center>
<br>
<p>The backtracking method is named solvable and returns a boolean. In solvable we shall need to check whether we
are at a leaf, which in this case means a position from which no further moves are possible. This isn't so easy.
</p>
<p>Now to the program. The main program will initialize the board, and call a recursive backtracking routine to
attempt to solve the puzzle. The backtracking routine will either succeed and print out a winning path, or it will
fail, and the main program will have to print out the bad news.</p>
<p>The backtracking method is named solvable and returns a boolean, in solvable we shall need to check whether we
are at a leaf, which in this case means a position from which no further moves are possible. This isn't so easy.
</p>
<p>Each possible move will result in a new board position, and these new board positions are the children of the
current board position. Hence to find the children of a node (that is, of a board position), we need only find the
possible moves from that node. Remember that it is also highly desirable to find an ordering on these possible
moves.</p>
<p>Here it is time to stop and take thought. To make progress, we must analyze the game to some extent. Probably a
number of approaches would work, and what follows is based on the way I worked it out. If you were to program this
puzzle, you might find a different but equally valid approach</p>
<p>First, notice that if a marble has a move, that move is unique: if it can move ahead one square, then it cannot
jump. If it can jump, it cannot move ahead one square. This suggests that, to find the possible moves, we might
assign numbers to the marbles, and check each marble in turn. When we have looked at all the marbles, we have
looked at all the possible moves. This would require having a table to keep track of where each marble is, or else
somehow "marking" each marble with its number and searching the board each time to find the marble we want.
Neither alternative is very attractive</p>
<p>Next, notice that for a given board position, each marble occupies a unique space. Hence, instead of talking
about moving a particular marble, we can talk about moving the marble in a particular space. If a move is possible
from a given space, then that must be the only move possible from that space, because if the marble in that space
has a move, it is unique. There is a slight complication because not every space contains a marble, but at least
the spaces (unlike the marbles) stay in one place.</p>
<p><b>Now we have a simpler ordering of moves to use in our program. Just check, in order, the 2n+1 spaces of the
board. For each space, either zero or one moves is possible. With this understanding, we can write a boolean
method canMove(int[] board, int position) which determines whether a move is possible from the given
position:</b></p>
<ul>
<li>If the position is empty, no move is possible;</li>
<li>If the position contains a black marble, the method checks for a move or jump to the right;</li>
<li>If the position contains a white marble, the method checks for a move or jump to the left.</li>
</ul>
<p>We write another method <b>int makeMove (int[] oldBoard, int position)</b> that will take a board and a position,
make a move from that position, and return as its value a new board (We could write this somewhat more efficiently
by changing the old board, rather than creating a new one, but here we are more concerned with simplicity) In
technical jargon, makeMove is "applicative" rather than "mutative."</p>
<p>Along with <b>canMove and makeMove,</b> we are using methods <b>puzzleSolved and printBoard</b> with meanings that should be obvious.</p>
<div style="color: #70b6d5; border: 1px solid rgb(212, 212, 212)">
<span>boolean solvable(int[] board) {</span><br>
<span> if (puzzleSolved(board)) {</span><br>
<span> return true;</span><br>
<span> }</span><br>
<span> for (int position = 0; position < BOARD_SIZE; position++) {</span><br>
<span> if (canMove(board, position)) {</span><br>
<span> int[] newBoard = makeMove(board, position);</span>br=
<span> if (solvable(newBoard)) {</span><br>
<span> return true;</span><br>
<span> }</span><br>
<span> }</span><br>
<span> }</span><br>
<span> return false;</span><br>
<span>}</span><br>
</div>
<p>Along with canMove and makeMove, we are using methods puzzle Solved and printBoard with meanings that should be obvious</p>
<p>Here is some output from the program:</p>
<ol reversed style="color: rgb(39, 36, 36);">
<li><b>WHITE WHITE WHITE _____ BLACK BLACK BLACK</b></li>
<li><b>WHITE WHITE WHITE BLACK _____ BLACK BLACK</b></li>
<li><b>WHITE WHITE _____ BLACK WHITE BLACK BLACK</b></li>
<li><b>WHITE _____ WHITE BLACK WHITE BLACK BLACK</b></li>
<li><b>BLACK BLACK WHITE BLACK WHITE _____ WHITE</b></li>
<li><b>WHITE BLACK WHITE _____ WHITE BLACK BLACK</b></li>
<li><b>WHITE BLACK WHITE BLACK WHITE BLACK _____ </b></li>
<li><b>WHITE BLACK _____ BLACK WHITE BLACK WHITE</b></li>
<li><b> _____ BLACK WHITE BLACK WHITE BLACK WHITE</b></li>
<li><b>BLACK _____ WHITE BLACK WHITE BLACK WHITE</b></li>
<li><b>BLACK BLACK WHITE _____ WHITE BLACK WHITE</b></li>
<li><b>BLACK BLACK WHITE BLACK WHITE _____ WHITE</b></li>
<li><b>BLACK BLACK WHITE BLACK WHITE _____ WHITE</b></li>
<li><b>BLACK BLACK WHITE BLACK _____ WHITE WHITE</b></li>
<li><b>BLACK BLACK _____ BLACK WHITE WHITE WHITE</b></li>
<li><b>BLACK BLACK BLACK _____ WHITE WHITE WHITE</b></li>
</ol>
<div style="background-color: rgb(238, 235, 235); color: grey">
Notice that the solution is given in reverse order: BLACK starts out on the left and WHITE on the right, as in the last line. I've added line numbers to the actual output in order to emphasize this point. Backtracking always produces its results (sequence of choices) in reverse order; it is up to you, the programmer, to reverse the results again to get them in the correct order.
</div>
</body>
</html>