Anonymous user
Knight's tour: Difference between revisions
Added a back tracking tie breaker
(Code crunch) |
(Added a back tracking tie breaker) |
||
Line 3,542:
=={{header|zkl}}==
// linear time.
<lang zkl>class Board{▼
// See Pohl, Ira (July 1967),
// "A method for finding Hamilton paths and Knight's tours"
// http://portal.acm.org/citation.cfm?id=363463
// Uses back tracking as a tie breaker (for the few cases in a 8x8 tour)
[[(dx,dy); T(-1,1); T(-2,2); _]]);
fcn init{
var
(0).pump(64,board.append.fpM("1-",Void)); // fill board with Void
}
fcn idx(x,y){x*8+y}
fcn isMoveOK(x,y
}▼
fcn gyrate(x,y,f){ // walk all legal moves from (a,b)
▲ ds:=[[(dx,dy); T(-2,2); T(-1,1),isMoveOK.fp(x,y); _]].extend(
▲ ds.pump(List,'wrap([(dx,dy)]){f(x+dx,y+dy)});
}
fcn count(x,y){ n:=Ref(0); gyrate(x,y,n.inc); n.value }
fcn moves(x,y){ gyrate(x,y,fcn(x,y){ T(x,y,count(x,y)) })
fcn knightsTour(x=0,y=0,n=1){ // using Warnsdorff's rule
m=m.filter('wrap([(_,_,c)]){c==min}); // moves with same min moves
board[idx(x,y)] = n;▼
if(m.len()>1){ // tie breaker time, may need to backtrack
x,y = m; n+=1;▼
if (64 == m.pump(Void,'wrap([(a,b)]){
board▼
n2:=knightsTour(a,b,n+1);
if (n2==64) return(Void.Stop,n2); // found a solution
board=bs.copy();
})) return(64);
return(0);
else{
board[idx(x,y)]=n;
} //while
return(n);
}
fcn toString{ board.pump(String,T.fp(Void.Read,7),
fcn(ns){vm.arglist.apply("%
}
}</lang>
Line 3,577 ⟶ 3,594:
{{out}}
<pre>
</pre>
Check that a solution for all squares is found:
<lang zkl>[[(x,y); [0..7]; [0..7];
{b:=Board(); n:=b.knightsTour(x,y); if(n!=64) b.println(">>>",x,",",y)} ]];</lang>
{{out}}Nada
{{omit from|GUISS}}
| |||