Hm, having tried the Knight's Tour with the same program (making only
the necessary changes in the rules in "GetPosSuccessors", I can see that
this arrangement is hopelessly inefficient, or rather, becomes so as the
board size increases. Although the program finds all 304 solutions of
the 5-sided board in just under 2 minutes, it takes unacceptably long to
find even the first solution of an 8-sided board.
I can see that there will be enormous waste of computation the way I
have done it, as huge amounts of subspaces are computed then rejected.
Now, I know there exist several clever heuristics and algorithms to
"smarten" up the Knight's Tour problem - but what I'm looking for here
is the neatest declarative formulation, BEFORE any smart heuristics are
applied.
Is there a less naive, yet purely declarative way of formulating the
program, using constraints to do the pruning, and avoiding all the
duplication caused by the thread/blackboard approach I used initially?
.
.
.
==============================
The rules I used for knight's moves, otherwise no change to the previous
program, other than removing special cases, starting data and "cyclic" case.
% In _this_ case the move is any valid knight move
proc {GetPosSuccessors Index Successors}
% temp store for succesors pending filtering
% 8 possible knight moves... tll=top-left-left, etc.
CandidateRecord = {MakeRecord cands [tll ttl ttr trr brr bbr bbl bll]}
% 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
fun {NotTopRow Idx} Idx>Size end
fun {NotTop2Row Idx} Idx>Size+Size end
fun {NotBotRow Idx} SizeSq-Size>=Idx end
fun {NotBot2Row Idx} SizeSq-Size-Size>=Idx end
fun {NotLftCol Idx} (Idx+Size-1) mod Size \= 0 end
fun {NotLft2Col Idx} {And {NotLftCol Idx} (Idx+Size-2) mod Size \= 0} end
fun {NotRgtCol Idx} Idx mod Size \= 0 end
fun {NotRgt2Col Idx} {And {NotRgtCol Idx} (Idx+1) mod Size \= 0} end
in % positions clockwise
{CheckSetMove CandidateRecord.tll {And {NotTopRow Index} {NotLft2Col
Index}} Index-Size-2}
{CheckSetMove CandidateRecord.ttl {And {NotTop2Row Index} {NotLftCol
Index}} Index-Size-Size-1}
{CheckSetMove CandidateRecord.ttr {And {NotTop2Row Index} {NotRgtCol
Index}} Index-Size-Size+1}
{CheckSetMove CandidateRecord.trr {And {NotTopRow Index} {NotRgt2Col
Index}} Index-Size+2}
{CheckSetMove CandidateRecord.brr {And {NotBotRow Index} {NotRgt2Col
Index}} Index+Size+2}
{CheckSetMove CandidateRecord.bbr {And {NotBot2Row Index} {NotRgtCol
Index}} Index+Size+Size+1}
{CheckSetMove CandidateRecord.bbl {And {NotBot2Row Index} {NotLftCol
Index}} Index+Size+Size-1}
{CheckSetMove CandidateRecord.bll {And {NotBotRow Index} {NotLft2Col
Index}} Index+Size-2}
% filter temp succesor record into List for use by constraint syntax
Successors = {Record.toList {Record.filter CandidateRecord fun{$
Cand} Cand \= false end}}
end
_________________________________________________________________________________
mozart-users mailing list
[email protected]
http://www.mozart-oz.org/mailman/listinfo/mozart-users
