Contact me

Twitter  ⟐  LinkedIn
Christophe Delord


News!

Monday 18. july 2016: Updates on my new simulation framework project in Haskell.

Friday 25. march 2016: Dear backers, unfortunately, the FUN project was not successfully funded. I will now focus on FRP (Functional Reactive Programming) applied to real-time critical system specification and simulation.

CDSoft :: CV/Resume :: Free softwares Essays Haskell Handy Calc pp TPG BonaLuna Calculadoira todo pwd w Live :: AI tools in Prolog AI dialog

License

This program is free software: you can redistribute it and/or modify it under the terms of the GNU General Public License as published by the Free Software Foundation, either version 3 of the License, or (at your option) any later version.

This program is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU General Public License for more details.

You should have received a copy of the GNU General Public License along with this program. If not, see http://www.gnu.org/licenses/.

Introduction

Here is a classic problem. The N-Queens problem consists in placing N queens on a board without interfering. Two queens must be on different rows, columns and diagonals.

The problem is to find all the possible configurations.

import System.Environment
import Data.List

Board representation

There is only one queen on each row. So the board can be represented by a list of integers, each integer is a row and its value is the position of the queen in this row.

A board is [qiqj][\ldots q_i \ldots q_j \ldots]. By construction, qiq_i and qjq_j are not on the same row. We must ensure that they are not on the same column or diagonal:

Solver

nqueens takes an integer (N) and returns the list of all the solutions. Let’s notice that a solution is a permutation of [1,N][1,N] because all columns are different. If we generate all the permutations we only have to check that two queens are not on the same diagonal.

So, a solution is a permutation where (i,j)[1,N]2,ij|qiqj||ij|\forall (i,j) \in [1,N]^2, i \ne j \cdot |q_i-q_j| \ne |i-j|

nqueens :: Int -> [[Int]]
nqueens n = [qs | qs <- perm [1..n], dontFight qs]
    where
        dontFight :: [Int] -> Bool
        dontFight qs = and [ abs ((qs!!j) - (qs!!i)) /= j - i
                           | i <- [0..n-2],
                             j <- [i+1..n-1]
                           ]
        perm :: Eq a => [a] -> [[a]]
        perm [] = [[]]
        perm xs = [x:xs' | x <- xs, xs' <- perm (delete x xs)]

In fact this solution is not efficient. It takes a factorial time because all permutations are generated.

A better solution is to check that a queen does not fight with others as soon as it is put on the board instead of checking full boards only.

nqueens' :: Int -> [[Int]]
nqueens' n = solve n []
    where

solve gets the number of queens to put on the board and the partially filled board:

        solve :: Int -> [Int] -> [[Int]]
        solve 0 qs = [qs]
        solve i qs = concat [ solve (i-1) (q:qs)
                            | q <- positions,
                              dontFight q qs
                            ]
        positions = [1..n]

The new queen qq does not fight with any queens qq' if

        dontFight :: Int -> [Int] -> Bool
        dontFight q qs = and [ (dq /= 0) && (dq /= i) && (dq /= -i)
                             | (i,q') <- zip [1..] qs,
                               let dq = q' - q
                             ]

Main function

The main function takes NN as an argument and prints all the solutions.

main :: IO()
main = do
    [n] <- getArgs
    let qss = nqueens' (read n :: Int)
    putStrLn (n++"-queens problem\n")
    mapM_ putBoard qss
    putStrLn (show (length qss) ++ " solutions")

putBoard = putStrLn . showBoard

showBoard qs = dashes ++ concatMap showLine qs ++ dashes
    where
        dashes = "+" ++ replicate nqs '-' ++ "+\n"
        showLine q = "|" ++ dots (q-1) ++ "Q" ++ dots (nqs-q) ++ "|\n"
        dots k = replicate k '.'
        nqs = length qs

Execution

$ runhaskell nqueens.lhs 6
6-queens problem

+------+
|....Q.|
|..Q...|
|Q.....|
|.....Q|
|...Q..|
|.Q....|
+------+

+------+
|...Q..|
|Q.....|
|....Q.|
|.Q....|
|.....Q|
|..Q...|
+------+

+------+
|..Q...|
|.....Q|
|.Q....|
|....Q.|
|Q.....|
|...Q..|
+------+

+------+
|.Q....|
|...Q..|
|.....Q|
|Q.....|
|..Q...|
|....Q.|
+------+

4 solutions

Source

The Haskell source code is here: nqueens.lhs