## Posts Tagged ‘chess’

### Programming Praxis – Knight Moves

March 8, 2013

In today’s Programming Praxis exercise, our goal is to list all the potential ways a knight on a chess board can get from one position to another. Let’s get started, shall we?

`import Data.Ix`

A knight can move to 8 positions, assuming they fit on the board. Each move is a combination of moving one square in one direction and two in the other.

```moves :: (Int, Int) -> [(Int, Int)]
moves (x,y) = [(x+dx,y+dy) | [dx,dy] <- combos [[-1,1],[-2,2]]
, inRange (1,8) (x+dx), inRange (1,8) (y+dy)]
where combos xs = sequence xs ++ sequence (reverse xs)```

To find the possible paths to the target square we simply generate all possible sequences of n moves and take the ones that end in the desired position.

```paths :: (Int, Int) -> (Int, Int) -> Int -> [[(Int, Int)]]
paths from to n = map reverse . filter (\(x:_) -> x == to) \$
iterate (>>= \(x:xs) -> map (:x:xs) \$ moves x) [[from]] !! n```

A test to see of everything is working properly:

```main :: IO ()
main = mapM_ print \$ paths (8,8) (1,1) 6```

### Programming Praxis – N-Queens

June 11, 2010

In today’s Programming Praxis we have to solve the classic n-queens problem. The provided Scheme solution has 13 lines. Let’s see if we can do any better.

A quick import:

`import Data.List`

The wikipedia page for the algorithm mentions a simple algorithm where you take the permutations of 1 through n as the column positions for the n consecutive rows and removing the illegal ones. So let’s see if that works.

```queens :: Int -> [[Int]]
queens n = filter (safe . zip [1..]) \$ permutations [1..n]
```

Since the algorithm guarantees that no two queens will be on the same row or column, we only need to check the diagonals.

```safe :: [(Int, Int)] -> Bool
safe []     = True
safe (x:xs) = all (safe' x) xs && safe xs where
safe' (x1,y1) (x2,y2) = x1+y1 /= x2+y2 && x1-y1 /= x2-y2
```

A quick test produces the same results as the Scheme solution, and the correct amount according to Wikipedia. At four lines, that will do nicely (you can make it 3 by expressing safe as safe xs = and . zipWith (all . safe’) xs . tail \$ tails xs, but I find that version to be less clear than the current one).

```main :: IO ()
main = mapM_ print \$ queens 5
```