Guido Tack

An Integrated Oz Search Factory

IOzSef is a search factory for Mozart. It is a toolbox that can be used to build custom search engines for solving constraint problems. It features both a graphical interface very similar to that of the Oz Explorer, and a search engine library that may serve as a replacement for the Search module.

Information about the design behind IOzSeF can be found in the paper Compositional Abstractions for Search Factories by Guido Tack and Didier LeBotlan, which was presented at the 2004 International Mozart/Oz Conference.


You can obtain IOzSeF from the Mogul. It requires the TkTreeWidget to be installed. Both packages can be downloaded and installed using ozmake:

ozmake --install --package=mogul:/tack/TkTreeWidget
ozmake --install --package=mogul:/tack/iozsef


The interactive interface can be used as a replacement for the Oz Explorer. The following example shows how to solve the n-Queens puzzle using IOzSeF:

[IOZSEF] = { ['x-ozlib://tack/iozsef/iozsef.ozf']}

fun {Queens N}
   proc{$ Row}
      L1N  = {MakeTuple c N}
      LM1N = {MakeTuple c N}
      {FD.tuple queens N 1#N Row}
      {For 1 N 1 proc{$ I}
                     L1N.I=I LM1N.I=~I
      {FD.distinct Row}
      {FD.distinctOffset Row LM1N}
      {FD.distinctOffset Row L1N}
      {FD.distribute generic(value:min) Row}

{IOZSEF.exploreAll {Queens 8}}

Working with the interactive IOzSeF

The interactive IOzSeF should work quite similarly to the Oz Explorer.

The tree view

The main part of the IOzSeF window is used by the tree view that displays the current search tree. The tree consists of six different node types:

You can select nodes by clicking on them. Double-clicking invokes the currently selected inspection action, which defaults to displaying the root variable of the current node in the Oz Inspector.

You can also navigate through the tree using the arrow keys. The down-arrow moves to the leftmost child of a node. The up-arrow moves to the parent node. The left- and right-arrows move to the left and right sibling.

The IOzSeF menu

In this menu, you find the operations Halt, Reset, and Quit, which should be self-explaining.

The Node menu

This menu lets you hide or unhide the selected node, unhide all nodes in the current subtree, or unhide failed subtrees below the current subtree.

The Search menu

Using the items in this menu, you can search for the next n solutions, for the next solution, or for all remaining solutions. Search always starts at the currently selected node and only affects the subtree below that node.

Clicking the menu item One step performs a single search step. You can use this to manually explore the search tree.

The item Next phase is only active for search engines based on phases, like iterative deepening.

The Options menu

Using the items in this menu, you can control how IOzSeF searches for solutions, how they can be displayed, and how the memory of the search tree is managed.

The status line

The status line provides information about the search tree. It presents the number of nodes of each type, and the time needed for the last search.


The IOzSeF module

setOption(Key Value)Sets option Key to value . See the section on options below.
getOption(Key ?Value)Retrieves the current value of option Key.
addInformationAction(Name Type Action)Registers an information action that can be activated by double-clicking on a node. The Name is an atom describing the action, it will be used for the menu entry. The Type is one of space or root. space(root) means that the space (root variable) of the clicked node is given to the action. The action is a unary procedure that gets the space or root variable as its argument.
deleteInformationAction(Name)Unregisters the information action Name.
addPopUpAction(Name Type Action) Registers a pop-up action. Pop-up actions are invoked when the user stays with the mouse over a node for more than one second. The Name is used as for information actions. The type can be either space, or root, as for information actions.
deletePopUpAction(Name)Unregisters a pop-up action.
init(Script)Initializes IOzSeF with the Script. This opens a window showing an unexplored root node.
initBest(Script Order)Initializes IOzSeF for branch-and-bound search.
explore(Script)Explores all solutions of Script in the interactive IOzSeF.
exploreOne(Script)Explores one solution of Script in the interactive IOzSeF.
exploreBest(Script Order)Explores all solutions of Script in the interactive IOzSeF, performing branch-and-bound search. The last solution found is guaranteed to be optimal.
searchAll(Script ?Sols) Returns all solutions of Script in the list Sols.
searchOne(Script ?Sol) Returns one solution of Script in a singleton list Sol, or the empty list if Script has no solution.
searchBest(Script Order ?Sol) Return all solutions of Script performing branch-and-bound search. The last solution is guaranteed to be optimal.
cancelSearch Cancels the current non-interactive search.
cancelExploration Cancels the current interactive exploration.
getSolutions(?Sols) Returns the solutions found so far during interactive exploration.
closeCloses the exploration window.


Actions can be used to visualize information about a node in the search tree. The default inspection action just opens the Oz Inspector and displays the root variable of the node.

Information Actions

Information actions are invoked when the user double-clicks a node in the search tree. Information is not available for failed nodes.

An information action can either get the space of the clicked node or its root variable, depending on the Type parameter given on registration. If the type space is used, you must note that that is the actual space of the node, not a copy, for efficiency reasons. This means that you must not merge it or post constraints on it, as that may make subsequent exploration from that space impossible.

Pop-up Actions

Pop-up actions are invoked when the user "hoovers" over a node in the search tree, that is, when the mouse stays over the same place for more than a second.

A pop-up action must return a string that is then displayed in the pop-up window above the note. It can, just as for information actions, operate on a space or a root variable, and the same restrictions for spaces apply.

Using actions to compare two nodes

The Oz Explorer provides comparison actions that can be used to compare different nodes in the search tree. We can partly emulate this behavior using a combination of information and pop-up actions.

The main idea is to select the first node using an information action, and then use a pop-up action to compare it to a second node. Let us assume that we have a procedure CmpSpacesToString/3 that returns a string, given two root variables. Then we can implement comparison as follows:

   S = {NewCell unit}
   proc {InfoAction NewS}
      S := NewS
   fun {PopupAction R}
      {CmpSpacesToString @S R}
   {IOZSEF.addInformationAction compare root InfoAction}
   {IOZSEF.addPopUpAction compare root PopupAction}


OptionMeaningPossible values
explorationStrat Used search strategy dfs,bdfs,id,lds
noOfSols Number of solutions after which to stop search 0...
recompStrat Strategy for recomputation plain,fixed,adaptive
mrd Maximum recomputation distance (for fixed and adaptive recomputation) 0..
hideFailedSubtrees Whether to automatically hide failed subtrees during search true,false
updateEvery Redraw the tree after how many found solutions
informationAction Selected information action
popUpAction Selected pop-up action

Guido Tack
Last modified: Thu May 2 20:47:02 CEST 2002