Deprecated: The each() function is deprecated. This message will be suppressed on further calls in /home/zhenxiangba/zhenxiangba.com/public_html/phproxy-improved-master/index.php on line 456
-- Knight tour with the Constrained Constructor pattern -- Sergio Antoy -- Wed Feb 9 12:55:46 PST 2005 -- revised Tue Jan 15 09:29:18 PST 2013 -- Wed Jun 28 12:55:50 PDT 2017 -- Move a knight on a chess board so that it visits all -- the positions exactly once -- Position of a knight: -- It consists of the knight's row and column on the chess board data Pos = Pos Int Int -- Constrained Constructor on positions: -- The coordinates of a knight must fall inside the board. -- valid coordinates are no less than 0 and less than the board size makePos r c | valid = Pos r c where valid = 0 <= r && r < size && 0 <= c && c < size -- make a move: -- From the current position, reach a position that is 1 off -- in a coordinate and 2 off in the other coordinate. move (Pos x y) = makePos (x+2) (y-1) ? makePos (x+2) (y+1) ? makePos (x-2) (y-1) ? makePos (x-2) (y+1) ? makePos (x-1) (y-2) ? makePos (x+1) (y+2) ? makePos (x-1) (y+2) ? makePos (x+1) (y-2) -- A path is a partial solution, e.g., a sequence of -- positions according to the puzzle's rules. type Path = [Pos] -- Constrained Constructor on Path -- In any path, any state except the initial one must be -- obtained from the preceeding state by means of a move -- and cycles are not allowed. makePath s p | valid && noCycle = s:p where valid = s =:= move (head p) noCycle = all (s /=) p -- extend the path argument till the puzzle is solved -- see the Incremental Solution pattern extend p = if (length p == size*size) then p else extend (makePath unknown p) -- solve the puzzle size = 6 main = reverse (extend [Pos 0 0])