The eight queens puzzle is about placing eight queens on a 8x8 chess board such
that none of the queens share the same row, column, and diagonal. In fact there
are more than one ways to place eight queens on a chess board without violating
the rule. The puzzle can be generalized into a
n-queens puzzle where the player
is tasked to place
n queens on a
n chess board.
This post is about my attempt to solve the
n-queens puzzle using
Clojure. The classic approach to solve the puzzle is to
use a technique called backtracking. In backtracking, the entire solution space
for the puzzle is searched until all or some of the solutions are found. In The
Algorithm Design Manual,
Steve Skiena outlines a general form of the backtracking algorithm.
The idea behind the backtracking algorithm is to progressively generate candidates that will eventually make up a solution to the problem. In the context of eight-queens puzzle, the algorithm will place one queen at a time until all eight queens are placed. Each newly placed queen will satisfy the rule of the puzzle—no two queens share the same row, column, and diagonal.
In the above snippet, two functions are defined. The
first checks the length of the partial solution. The partial solution contains
placements of queens on the chess board. When there are placements for
we know we have a single complete solution. However, if there are less than
queens placed, the algorithm will find all the suitable placements for the next
queen while making sure the rule of the puzzle is enforced. That’s what
gen-candidates does; it returns all the valid placements in the next row for a
queen. For each of the valid placements, the
backtrack function will append
the placement to its partial solution, then it continues to find the next valid
placement for the next queen by calling itself. Put it another way, the
backtrack function places a queen in one of the placements returned by
gen-candidates, so it is one step/queen closer to finding a complete solution
n queens on a
n chess board. The crucial bit is that
gen-candidates must return proper set of candidates.
The idea of
gen-candidates is to first generate all possible placements for
the next queen, then filter out the placements that will violate the placement
rule—no two queens share the same row, column, and diagonal. The two
invalid? are used to enforce the rule of the
puzzle so no queens can attack each other.
In total there are 92 possible ways to place eights queen on a chess board. You can find all the solutions returned by calling:
Due to readability and space, I will show the solutions for a smaller chess board. Here are the solutions for the four-queens puzzle:
There are two solutions to place four queens on a 4x4 chess board. The return value is a list that contains vectors, in this case, there are two. Each vector holds the placements for the four queens. The placements are represented as tuples with the first element being the row, and the second element being the column (both start at 0).
And finally, here are the solutions for six-queens:
There you have it. My attempt at the n-queens puzzle using clojure. I must admit the performance is not that great, but I think it is a decent start.