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