-
Book Overview & Buying
-
Table Of Contents
Mastering Julia - Second Edition
By :
In 1972, Edsger Dijkstra used this problem to illustrate the power of what he called structured programming and published a highly detailed description of a depth-first backtracking algorithm.
The problem was originally to place eight queens on a chessboard so that no queen could take any other, although this was later generated to N queens on an N by N board. An analysis of the problem is given in Wikipedia. The solution to the case N=1 is trivial and there are no solutions for N = 2 or 3. For a standard chess board, there are 92 solutions out of a possible 4.4 billion combinations of placing the queens randomly on the board, so an exhaustive solution is out of the question.
The Julia implementation of the solution uses quite a few of the constructs we have discussed:
struct Queen x::Integer y::Integer end qhorz(qa, qb) = qa.x == qb.x; qvert(qa, qb) = qa.y == qb.y; qdiag(qa, qb) = abs(qa.x - qb.x) == abs(qa.y - qb.y); qhvd(qa, qb...