Finding figures of constant width on a chessboard
We will say a collection of squares on an nxn board is a figure of constant width w if every row, column and diagonal (both main diagonals) intersects the collection in exactly w squares or does not intersects it at all. Such a figure will contain exactly k*w squares and we will say it is of type
(n,k,w). Note that the figures of type
(n,n,1) are the solutions to the n-queens problem.
Finding figures of constant width with the computer is an interesting problem. This problem was first described here.
The following is a backtracking algorithm that enumerates all connected figures of type
I use the word connected in the following sense. Imagine each point in the figure is a teleportation unit and you are allowed to jump between any two points laying on the same row or column or any of the two main diagonals. A figure will be connected if there is a path of jumps between any two points in it.
For example, the n-queens solutions (figures of constant width 1) are totally disconnected; so this program does not find them.
We will start by defining, for every finite subset S of the infinite board, the function such that:
where p is point on the board, row(p) is the row containing p, column(p) the column containing p and so on.
This function is locally defined, meaning that it satisfies the following expression:
The algorithm assumes fS(p)=(w,w,w,w) for every p belonging to the solution S, it then attempts to recursively satisfy the above mentioned locally defined property. This process either converges to a figure of type (n,_,w) or escapes the nxn board boundary.
Here is the link to the full F# program (cwfigures.fs) and bellow is the function
find that performs the search strategy.
let find len F availables buffer = let rec search sol len (avlen,avail) (bufflen,buff) = match buff with |_ when avlen + bufflen < len -> () //not enough left to complete a solution | -> F sol //found one! |p::tail -> let (r,rows), (c,columns), (d1,diag1), (d2,diag2), remaining = collect p avail if r < state.r p || c < state.c p || d1 < state.pd p || d2 < state.nd p then () //can not satisfy local constraint else (search (p::sol) (len-1) |> (prune_before_continue remaining >> combinator diag2 (state.nd p) >> combinator diag1 (state.pd p) >> combinator columns (state.c p) >> combinator rows (state.r p) )) (bufflen - 1, tail) search  len availables buffer;;
While there are other backtracking strategies, some of them more aesthetically appealing, this was the faster combination I could come up with. To generate all figures of type (11,_, 3) it took roughly 31 days on a Windows XP virtual machine hosted on Linux running on a quad-core. The same program running on the Linux host (with Mono 2.0.1) performed about twice slower.
There are 21 solutions of type (11,11,3) and 1 solution of type (11,10,3), module the symmetries of the square. You can see them here
blog comments powered by Disqus