Re: [Jscheme-user] ILC 2003 Programming Contest

[Timothy J. H. <tim...@ma...>]

On Monday, August 25, 2003, at 01:38 PM, Ken Anderson wrote:

> Here's a Lisp programming contest:
> http://www.ravenbrook.com/doc/2003/05/28/contest/
> Though they want a common lisp solution, it might be fun to come up 
> with one in JScheme too.  I'm interested in any suggestions on what a 
> good strategy would be.

   Here is a logic programming inspired solution strategy.... this is 
how N-queens and similar problems are solved
using Constraint Logic Programming. We could translate it into Jscheme 
without too much trouble....

The initial approach would be to use a constrained backtracking method.

For each of the 64 spaces on the board we would keep track of which 
particular puzzle pieces could go there.
This task is simplified if we consider each orientation of the 13 
pieces as a different piece. (So there are now
13*4 = 52 different pieces, and a constraint that exactly one piece 
from each group of 4 must be used).

Similarly, we can number the cells on each (oriented) puzzle piece, so 
that we would specify that
in a particular frame position (say row=5,col=3)
   cell 3 of piece "J" with orientation "N" could be in that position.
The idea here then is that one first initializes all 64 frame positions 
to see which puzzle pieces they could contain
(loop over all 13 pieces, 4 orientations and 3-6 cells of each piece).
There would be about 13*4*5 = 260 puzzle placements possible
at each of the 64 positions of the initial board. A board state could 
be an 8x8 array of bit strings of size 260 or so.

Then one starts at the top row and col and selects one of the possible 
pieces (e.g. the first).
All other pieces are removed from that position and each removed piece 
is then used to remove
possibilities from neighboring cells. Moreover, each removal is cached 
in a list so that it can be restored on backtracking.
(On backtracking, the next choice will be made, etc until all choices 
have been made (at which point deeper backtracking
is called).

One then takes the "next" board position that contain more than one 
elements and non-deterministically chooses one repeating the
same constraint process. The "next" board position can be chosen 
arbitrarily (e.g. the position containing the fewest positions
is a good choice....)
If a frame position becomes empty (i.e. no puzzle piece could cover 
that cell) then you backtrack to
the last choice and make a new choice....

The "tabs" constraint is handled by noticing that each cell of a puzzle 
piece can be labelled with "Black" or "White" and
each position in the Chessboard can be labelled with "Black" or "White" 
in a checkerboard pattern. If this is done, then the
tabs will match iff the even/odd properties match. This is just a 
further restriction on which puzzle positions can go in which
board positions.


Implementing this will require implementing a choice point stack. a 
trail stack (to store the backtracking info),
and deciding on how to represent the current set of possible puzzle 
placements at each position in the board....

we could use an array of hashsets??? or an 8x8 array of bit strings??

Cheers,
---Tim---



> k
>
>
>
> -------------------------------------------------------
> This SF.net email is sponsored by: VM Ware
> With VMware you can run multiple operating systems on a single machine.
> WITHOUT REBOOTING! Mix Linux / Windows / Novell virtual machines
> at the same time. Free trial click 
> here:http://www.vmware.com/wl/offer/358/0
> _______________________________________________
> Jscheme-user mailing list
> Jsc...@li...
> https://lists.sourceforge.net/lists/listinfo/jscheme-user