# 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 `(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

blog comments powered by Disqus