module Problem2 where -- for Haskell info visit www.haskell.org import Data.Array type Square = (Int, Int) e1 :: Square e1 = (5,1) onBoard :: Square -> Bool onBoard (x,y) = (x>=1) && (x<=8) && (y>=1) && (y<=8) boardBounds :: ((Int, Int), (Int, Int)) boardBounds = ((1,1),(8,8)) type MarkedBoard = Array Square Integer initialBoard :: MarkedBoard initialBoard = array boardBounds [(s, if s==e1 then 1 else 0) | s <- range boardBounds] type RevMoveFunc = Square -> [Square] -- function which maps a square to a list off squares from which it -- can be reached updateBoard :: RevMoveFunc -> MarkedBoard -> MarkedBoard -- given a board with every square marked with the number of paths -- which reach it after n moves yields a board with every square -- marked with the number of paths which reach it after n+1 moves updateBoard f b = b // [(s, sum [b!s' | s'<-f s]) | s <- indices b] king, lazyking, queen, lazyqueen :: RevMoveFunc king s = filter onBoard $ steps s 1 -- an ordinary chess king lazyking s = s : king s -- a king which is also allowed to not move at any given move queen s = filter onBoard $ concatMap (steps s) [1..7] lazyqueen s = s:queen s -- same for a queen steps :: Square -> Int -> [Square] steps (x,y) i = [(x-i,y-i),(x,y-i),(x+i,y-i), (x-i,y), (x+i,y), (x-i,y+i),(x,y+i),(x+i,y+i)] solve :: RevMoveFunc -> Int -> Integer -- How many paths reach the eigths row after n moves? solve f n = sum [b!(x,8) | x <- [1..8]] where b = iterate (updateBoard f) initialBoard !! n {- example session (also works well with hugs) $ ghci Problem2 ___ ___ _ / _ \ /\ /\/ __(_) / /_\// /_/ / / | | GHC Interactive, version 6.4, for Haskell 98. / /_\\/ __ / /___| | http://www.haskell.org/ghc/ \____/\/ /_/\____/|_| Type :? for help. Loading package base-1.0 ... linking ... done. Compiling Problem2 ( Problem2.hs, interpreted ) Ok, modules loaded: Problem2. *Problem2> solve king 7 1994 *Problem2> solve king 8 30280 *Problem2> solve lazyking 8 46232 *Problem2> solve queen 7 339934673 *Problem2> solve lazyqueen 7 457872199 *Problem2> solve queen 100 1148411858161688271726445791658282269648909701234982618112683105194160818962047912539842384144861118972094188981819575450334818854976969 -}