## 4.1 Basic Search Engines

All these engines take a script as input and return a list of its solutions.

`base.one`

  > > `{Search.base.one` `+ScriptP``` `?Xs``}`

  returns a singleton list containing the first solution of the script `+ScriptP` (a unary procedure) obtained by depth-first search. If no solution exists, `nil` is returned.

  As an example,

  > `{Search.base.one proc {$ X}
  > choice
  > choice X=ape [] X=bear end
  > [] X=cat
  > end
  > end}`

  returns the list `[ape]`.

`base.all`

  > > `{Search.base.all` `+ScriptP``` `?Xs``}`

  returns the list of all solutions of the script `+ScriptP` (a unary procedure) obtained by depth-first serach. As an example,

  > `{Search.base.all proc {$ X}
  > choice
  > choice X=ape [] X=bear end
  > [] X=cat
  > end
  > end}`

  returns the list `[ape bear cat]`.

`Search.base.best`

  > > `{Search.base.best` `+ScriptP``` `+OrderP``` `?Xs``}`

  returns a singleton list containing the best solution with respect to the order `+OrderP` (a binary procedure) of the script `+ScriptP` (a unary procedure) obtained by branch and bound search. If no solution does exist, `nil` is returned.

  The branch and bound strategy works as follows. When a solution is found, all the remaining alternatives are constrained to be better with respect to the order `+OrderP`. The binary procedure `+OrderP` is applied with its first argument being the previous solution, and its second argument the root variable of a space for one of the remaining alternatives.

  For instance, the following script constrains its root variable to a pair of integers, such that a certain equation holds between its components.

  > `proc {Script Root}
  > X={FD.int 1#10} Y={FD.int 1#10}
  > in
  > Y =: 10 - X - 2*Y
  > Root = X#Y
  > {FD.distribute split Root}
  > end`

  With the order

  > `proc {MaxSum Old New}
  > Old.1 + Old.2 <: New.1 + New.2
  > end`

  we can search for a solution with maximal sum of `X` and `Y` by

  > `{SearchBest Script MaxSum}`

  This returns the singleton list `[7#1]`.

  Similarly, we can search for the solution with the maximal product, by using the order:

  > `proc {MaxProduct Old New}
  > Old.1 * Old.2 <: New.1 * New.2
  > end`

  in:

  > `{SearchBest Script MaxProduct}`

  This returns the singleton list `[4#2]`.