Twitter ⟐ LinkedIn

Christophe Delord

**Wednesday 22. november 2017**: Working at EasyMile for 10 month. Critical real-time software in C, simulation and monitoring in Haskell → perfect combo! It’s efficient and funny ;-)

**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

25 Jun 2016

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/.

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.

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 $[\ldots q_i \ldots q_j \ldots]$. By construction, $q_i$ and $q_j$ are not on the same row. We must ensure that they are not on the same column or diagonal:

- $q_i$ and $q_j$ on the same column iif $q_i = q_j$
- $q_i$ and $q_j$ on the same diagonal iif $|q_i-q_j| = |i-j|$

`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]$ 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 $\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.

`solve`

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

- if all the queens have already been put, a solution has been found
- otherwise we try all the possible values:
- a position is in $[1,n]$
- and must not interfere with the current queens ($qs$)

```
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 $q$ does not fight with any queens $q'$ if

- $\forall q' \in qs$
- let $i$ be the index of $q'$, $0$ being the index of $q$
- $q$ and $q'$ are not in the same column if $q'-q \ne 0$
- $q$ and $q'$ are not in the same diagonal if $q'-q \ne i \land q'-q \ne -i$

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

The `main`

function takes $N$ 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
```

```
$ 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
```

The Haskell source code is here: nqueens.lhs