Finding figures of constant width on a chessboard

Constant width figure of type (11,11,3)

p.. 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 @(n,_,w)@.

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:

where :

The algorithm assumes f_S(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