A Crash into FP through ATS:
PrevNext

Chapter 17. Example: Queen Puzzle Revisited

The famous 8-queen puzzle asks the player to find ways to put eight queen pieces on a chess board such that no queen piece can attack any other ones. In other words, no two queen pieces can be put on the same row, the same column, or the same diagnal. A solution to a generalized version of this puzzle was presented in an earlier part of the book but there is a serious drawback with the solution when it is used to animate the underlying search process. For instance, if we want to deal with the case where the chess board is of the dimension 20 by 20, then no animation can actually happen as the time taken to generate all of the valid board configurations to the puzzle is prohibitively long. By making use of stream-based lazy-evaluation, I present as follows a slight variant of the previously presented solution so as to obviate the need for generating all of the valid board configurations before displaying them. Instead, each valid board configuration is generated only when it needs to be displayed.

Please recall that a node represents a board configuration where there are n queen pieces on the first n rows of the chess board such that no one piece can attack any other pieces. Given a node, another node extending it with one more queen piece is considered its child. The following declared function node_get_children is supposed to be called to obtain all of the child nodes of a given node: 

extern
fun
node_get_children(node): list0(node)
overload .children with node_get_children

With node_get_children, we can readily implement node_dfsenum as follows for enumerating in the depth-first manner all of the nodes contained in the tree rooted at a given node: 

//
extern
fun
node_dfsenum
  (nx0: node): stream(node)
//
implement
node_dfsenum(nx0) = $delay
(
stream_cons
(
nx0
,
list0_stream_concat<node>
(
list0_map<node><stream(node)>
  (nx0.children(), lam(nx) => node_dfsenum(nx))
)
)
) (* node_dfsenum *)
//

Note that the return value of node_dfsenum is a stream (in contrast to a list used in the previous version). Also note that the function list0_stream_concat is a variant of the function list0_concat (which flattens a list of lists into a list): 

//
extern
fun
{a:t@ype}
list0_stream_concat
  (xss: list0(stream(a))): stream(a)
//
implement
{a}(*tmp*)
list0_stream_concat(xss) = $delay
(
case+ xss of
| list0_nil() =>
  stream_nil()
| list0_cons(xs, xss) =>
  !(stream_append<a>(xs, list0_stream_concat<a>(xss)))
)
//

Given a list of streams, list0_stream_concat flattens it lazily into a single stream.

There is no change with respect to the implementation of node_get_children. Various minor coding details that are omitted for brevity can be found in the file QueenPuzzle.dats A demo for animating the depth-first search performed by node_dfsenum can be seen by clicking here.

Please find on-line the entirety of the code used in this chapter. The mentioned URL link(s) can be found as follows:

PrevHomeNext
Lazy Stream-Processing Linear Lazy Stream-Processing