Programming Praxis – N-Queens

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
About these ads

Tags: , , , , , , ,

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Follow

Get every new post delivered to your Inbox.

Join 35 other followers

%d bloggers like this: