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?
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
