π¨βπ» about me home CV/Resume ποΈ Contact Github LinkedIn Iβm a Haskeller π Best of Haskell abp hCalc bl todo pwd TPG

π **Sunday 24. May 2020**: Working at EasyMile for more than 3 years. Critical real-time software in C, simulation and monitoring in Haskell β‘οΈ perfect combo! Itβs efficient and funny ;-)

π And**we are recruiting!** Contact if you are interested in **Haskell** or **embedded softwares** (or both).

π And

24 May 2018

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.

```
import System.Environment
import Data.List
```

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

`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]]
0 qs = [qs]
solve = concat [ solve (i-1) (q:qs)
solve i qs | q <- positions,
dontFight q qs
]= [1..n] positions
```

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
= and [ (dq /= 0) && (dq /= i) && (dq /= -i)
dontFight q qs | (i,q') <- zip [1..] qs,
let dq = q' - q
]
```

The `main`

function takes \(N\) as an argument and prints all the solutions.

```
main :: IO()
= do
main <- getArgs
[n] let qss = nqueens' (read n :: Int)
putStrLn (n++"-queens problem\n")
mapM_ putBoard qss
putStrLn (show (length qss) ++ " solutions")
= putStrLn . showBoard
putBoard
= dashes ++ concatMap showLine qs ++ dashes
showBoard qs where
= "+" ++ replicate nqs '-' ++ "+\n"
dashes = "|" ++ dots (q-1) ++ "Q" ++ dots (nqs-q) ++ "|\n"
showLine q = replicate k '.'
dots k = length qs nqs
```

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