Knights' Tours, Walks etc. in Oz-Mozart

[Alex Gian]

Hi

I have never seen an implementation of the famous "Knight's Tour" in 
Mozart, and I wonder - is there any textbook approach to the problem?  
Any links would be appreciated.

I recently decided to have a stab at a similar problem:
I used Enigma #1468 from "New Scientist", included at the bottom of this 
post (NS "Enigma" is a great source of example programs, by the way, 
since they almost always concern constraints).

This puzzle is isomorphic to having a piece which behaves like a chess 
castle - but only one square at a time - which has to do a cyclic tour 
of a 6x6 board obeying certain constraints (starting position, certain 
given directions, etc)

I would be grateful to anyone who would look over my approach and offer 
comments/feedback.  I am not an academic, not even a student, just a 
hobbyist - so there may well be something basic that I am not aware of.

My script's approach was to create a thread for every move sequence of 
the solution and then to specify that for the move to be valid it must 
be a member of the possible successors of the previous position. 

   for I in 1..SizeSq-1 do
      thread TourOrder.(I+1) :: PosSuccs.(TourOrder.I) end
   end

This allows it to be quite generic; for instance it would only require a 
change of the "move rules" to make it just as applicable to "Knight's 
Tour" or any other similar problem.

What I am wondering about is efficiency.
My understanding of my program is that it works a bit as a "blackboard", 
with the generated subspaces eventually providing the solution.  The 
fact that each move is a thread allows the dataflow variables not to 
block until the solution is found. 
(Hope that explanation makes a bit sense. I said I'm not an academic :) )

I am wondering whether generating so many subspaces will be too expensive.
Would there be a better approach?
Perhaps something closer to the classic Prolog approaches, or is my 
solution acceptable?

The Explorer indicates a solution found after about 150k nodes, with a 
total of 250k being explored if I use "ExploreAll"
A search on a 900MhZ Duron takes about 30 seconds to find the solution, 
which seems about right to me... though there might be a better way.

All comments welcome

Here is the working oz program:

===

declare

% Create board for experimenting, mainly "tours", "magic squares", etc.
Size = 6
SizeSq = Size*Size

% Set up the board:  Costruct individual cells (positions)
% for the board containing var. info (pos successor moves, in this 
case)           
proc {ConstructCell Index Cell}
   Cell = {MakeRecord cell [successors anythingelse]}
   Cell.successors = {GetPosSuccessors Index}
end

% Establish the possible successors from each board position+
% This procedure would vary for different pieces / types of move
% In _this_ case the move is only one square, up, dpwn, left or right
proc {GetPosSuccessors Index Successors}
   % temp store for succesors pending filtering
   CandidateRecord = {MakeRecord cands [up dn lt rt]}
   % procedure to test whether there is a successor move in candidate 
direction
   proc {CheckSetMove CandDirection Test SuccessorCalculation}
      CandDirection = if Test then SuccessorCalculation else false end
   end
in
   {CheckSetMove CandidateRecord.up Index>Size Index-Size}
   {CheckSetMove CandidateRecord.dn Index<(SizeSq-Size+1) Index+Size}
   {CheckSetMove CandidateRecord.lt ((Index-1) mod Size \= 0) Index-1}
   {CheckSetMove CandidateRecord.rt (Index mod Size \=0) Index+1}
   % filter temp succesor record into List for use by constraint systax
   Successors = {Record.toList {Record.filter CandidateRecord fun{$ 
Cand} Cand \= false end}}
end

% Create and Initialse BoardCells
Board = {MakeTuple board SizeSq}
{Record.forAllInd Board ConstructCell}

%%% SCRIPT
proc {Tour TourOrder}
   % Temp Array holds successors modified by given data
   PosSuccs = {MakeTuple idxsuccessors SizeSq}
in
   TourOrder = {FD.tuple tourorder SizeSq 1#SizeSq}
   {FD.distinct TourOrder}

% pull in specific constraints / start
   TourOrder.1 =: 11

% Array of successors of index positions - modified by given data
   for I in 1..SizeSq do
      PosSuccs.I = case I
           of 9 then [3]
           [] 16 then [22]
           [] 27 then [33]
           [] 30 then [29]
           else Board.I.successors
           end
   end
   
   % successors linked
   for I in 1..SizeSq-1 do
      thread TourOrder.(I+1) :: PosSuccs.(TourOrder.I) end
   end
   % if tour is cyclic:
   thread TourOrder.1 :: PosSuccs.(TourOrder.SizeSq) end

   {FD.distribute ff TourOrder}
end

%{ExploreOne Tour}
{Browse {SearchOne Tour}}

========
And here is the puzzle


Enigma 1468 - Paving the way
New Scientist magazine, 10 November 2007.
by Bob Walker.

This is a view of the 36 flagstones of Joe's patio.  (Sorry, needs fixed 
font)
+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+
|   |   | ^ |   | 1 |   |
+---+---+---+---+---+---+
|   |   |   | v |   |   |
+---+---+---+---+---+---+
| E | N | I | G | M | A |
+---+---+---+---+---+---+
|   |   | v |   |   | < |
+---+---+---+---+---+---+
|   |   |   |   |   |   |
+---+---+---+---+---+---+

Joe has numbered them, so that starting on flagstone 1 (shown) and 
stepping from one flagstone (not diagonally) to an adjacent one in 
order, one will finish back on flagstone 1 after stepping on all the other
35.
The arrows indicate in which direction to step from certain flagstones 
[^=up, v=down, <=left].
What are the numbers of the flagstones E, N, I, G, M and A?