# n Queens Problem

I work in a little shop in Monteriggioni (SI) here in Italy, we sell local products like olive oil, Chianti wines, pasta and more; it is a very nice idea but we are in a little hide place and few people can really find us, so most of the time is just myself looking the emptiness in front of me.

Finally I decided to bring my computer and use the plenty of free time I have at work to do something interesting.

Since I have never solved it before I decide to work on the n-Queens problem.

Let’s go straight to the code

Short and easy how I like it.

The chess-board is a vector of vector, nothing more classic, and it is build by the function `new-world`

.

`put-queen`

put a queen (:q) in the chess-board, nothing to add.

The function that check if the queen is in a valid position is `valid-state?`

(the help functions are not show, but they are trivial), the function instead of check if any queen in the whole chess-board attack any other queen only check if the position (x, y) is under attack by some queen (or vice-versa), we safe some little computation for interaction but considering the number of total interaction it is worthed.

Consider now just the double argument `queens`

function.

`x`

is the row we are analyzing and `y`

is the collum (just the contrary of the normal xOy plane), all the function is basically just a big cycle but in this way, instead of cycle for every single possibility in the chess board, as soon as I realize that the state is not valid I cut the research.

It is a recursive function so it may be hard to get it very quickly however just try to visualize it in a paper, draw a 4 by 4 chess board and try to follow the algorithm (note that the 4x4 chessboard has not solution, if you want to find a solution by hand try with the 5x5 board).

A problem with this function is that return a very deep nested list (you call a for inside another for up to the number of queens times), I solved it flatten all and the re-assembling (partitioning) the chessboard.

The function is lazy, even if a lot of computation to get the result n is the same that the computation necessary to get the result n+1.