3.3 The Explorer

The Explorer is a graphical tool of the Mozart programming environment. It can run scripts and display the explored search trees. It can also display the information in the constraint stores associated with the nodes of the search tree.

The statement

{ExploreAll Money}

tells the Explorer to run the script Money and explore the entire search tree. The Explorer will pop up a window and display the explored nodes of the search tree (see left part of Figure 3.3). Choice nodes appear as blue circles, failure nodes as red boxes, and solution nodes as green diamonds. Fully explored subtrees not containing solution nodes are collapsed into a single red triangle.

Figure 3.3: The Explorer with the search tree of Money.

You can select any node of the displayed search tree by clicking it with the left mouse button. Select the red triangle and type the command h (hide/unhide). This will replace the triangle with the actual nodes of the tree (see right part of Figure 3.3). You now see the full search tree of Money, which consists of three choice nodes, three failure nodes, and one solution node. Typing the command h once more will switch back to the compact representation of the failed subtree.

double clicking nodes

Next, double click the green solution node with the left mouse button.

This will display the unique solution

sol(d:7 e:5 m:1 n:6 o:0 r:8 s:9 y:2)

of the Money Puzzle in the Browser. You can also double click a blue choice node. This will display the information about the solution that was accumulated in the constraint store before the node was distributed. Double clicking the top node of the tree, for instance, will display

sol(d:_[2#8]  e:_[4#7]  m:1  n:_[5#8]  
    o:0       r:_[2#8]  s:9  y:_[2#8])

in the Browser. This way, the Explorer and the Browser can display the annotated search tree shown in Figure 3.2.

open and closed choice nodes

The statement

{ExploreOne Money}

tells the Explorer to run the script Money until the first solution is found. This time the Explorer will show a partial search tree that contains the solution node in the rightmost position, and also contains an open choice node. An open choice node is a choice node for which not all direct descendents have been explored yet. A closed choice node is a choice node for which all direct descendents have been explored already. While closed choice nodes are displayed in dark blue, open choice nodes are displayed in light blue. Not yet explored descendents of an open choice node are not displayed.

To check whether there are further solutions, you can resume the search process by selecting the root node and typing the command n (next). This will resume the search until either the next solution is found or all nodes of the search tree are explored.

stopping exploration

You can stop the exploring Explorer at any time by typing the command C-g.

resuming exploration

You can resume the exploration of a partial search tree by selecting any choice node and typing the command n or a. The command n (next) will resume the exploration of the selected subtree until a further solution is found or the subtree is fully explored. The command a (all) will resume the exploration of the selected subtree until it is fully explored.

resetting the Explorer

The command C-r will reset the Explorer and show only the root node of the search tree. By double clicking you can see in the Browser what is known about the solution before the first distribution step. You can request the exploration of the seach tree by typing n or a.

hand-guided exploration

You can guide the search of the Explorer by hand. Reset the Explorer by typing C-r. This will select the root node, which is an open choice node. Now type the command o (one) to compute the first descendent of the root. Select the root once more and type o again. This will compute the second and final descendent of the root. Note that the root has now changed from light blue indicating an open choice node to dark blue indicating a closed choice node.

zooming the search tree

The right vertical scroll bar of the Explorer's window zooms the size of the displayed search tree. You can zoom the tree to fit the size of the window by clicking the zoom bar with the right mouse button.

Exercise 3.1 (See solution)

With the Explorer it is easy to observe the effect of different distribution strategies. Replace the first-fail distribution strategy in Money with the naive strategy

{FD.distribute naive Root}

which distributes on the leftmost undetermined variable and its least possible value. Draw the new search tree with the Explorer and observe that it is twice as large as the tree obtained with first-fail distribution.

Exercise 3.2 (See solution)

Write a script that finds distinct digits for the letters A, B, D, E, G, L, N, O, R, and T such that the equation


holds without leading zeros. Run the script with the Explorer and study the search tree. Try both first-fail and naive distribution. Observe that first-fail distribution yields a search tree that is by one order of magnitude smaller than the search tree obtained with naive distribution.

Christian Schulte and Gert Smolka
Version 1.4.0 (20080702)