While I desperately tried to solve a Sudoku at a Juggling Convention Thomas Furtner had the idea to a somewhat similar kind of puzzle with Siteswaps: In a rectangular matrix every row (from left to right) and every column (from top to bottom) must be a valid siteswap (with throws from 1 to 9).
At home I started implementing a program to generate such matrices. Here’s one example:
1 1 1 1 1 1 1 1 1
Of course it’s rather boring, so I imposed some other constraints. First, each siteswap must contain at least two different throws. Second, the puzzle must not contain the same siteswap twice. For the purposes of this puzzle I defined two siteswaps as equal if they are identical or one of their rotations is identical, i.e., 531 is the same siteswap as 531, 315, and 153.
With these additional contraints matrices like this were created:
7 4 4 4 1 7 7 1 1
This looks much better but I found out pretty quickly that square matrices are very unsuited for this type of puzzle since one can add or subtract (if possible) the period length to any element in the matrix and all siteswaps will still be valid. Hence I went to 3×4 matrices and finally got some interesting matrices:
8 1 3 8 9 1 1 5 7 4 8 5
Now the only thing left is to remove as many elements in the matrix as possible so that it still gives a unique solution:
8 3 1 4 8 5
The program to generate these puzzles is implemented in GNU Prolog using the Constraint Logic Programming extension CLP(FD). Constraint Programming allows the solution of some classes of problems just by writing down the constraints they are subject to. The constraint solver does the rest – usually very efficiently. The classic example is the “SEND+MORE=MONEY” problem, an implementation of which is given on the Wikipedia Constraint Programming Page. I’ll show you how this is applicable to siteswaps!
We need to define what a siteswap is. Mathematically speaking, the sequence t_0, t_1, …, t_n-1 is a valid siteswap if and only if the sequence (t_0 + 0) mod n, (t_1 + 1) mod n, …, (t_n-1 + n-1) mod n is a permutation of the sequence 0, 1, …, n-1. Since all elements of the modified sequence are “mod n” this is the same as saying that all elements in the modified sequence must different from each other, i.e., no two elements must be the same.
This brings us to the implementation of the siteswap constraints. I’ll use a slightly simplified notation here so as not to scare away people unfamiliar with Prolog syntax. These are the constraints for a siteswap with period 3:
is_siteswap([T0,T1,T2]) :- domain([M0,M1,M2], 0, 2), M0 = (T0+0) mod 3, M1 = (T1+1) mod 3, M2 = (T2+2) mod 3, all_different([M0,M1,M2]).
The first line is the introduction to the definition of a predicate – similar to a function in C or a procedure in Pascal. Our predicate “is_siteswap” takes one argument, namely a list of three variables T0, T1, T2, which represent the three throws in the siteswap.
The second line declares three more variables, namely for the modified sequence. The declaration tells the constraint solver that these variables will be numbers in the range from 0 to 2 (CLP(FD) can only deal with whole numbers).
The next three lines “generate” the modified sequence. It looks like simple algebra, but at this point there are no calculations involved, because this predicate must work even if one of the Ts is unknown. If it couldn’t do that, it would only be good for checking whether a siteswap is valid!
The last line is a call to a predicate built into CLP(FD) which makes sure that all Ms are different, as required for valid siteswaps.
Now that we have written it we can do several things with this predicate. The simplest of all is checking whether a siteswap is valid:
valid_test :- is_siteswap([5,3,1]), labeling().
The only thing new here is the call to the predicate “labeling” which really starts the constraint solver. It is called with a list of variables for which it is supposed to find values satisfying all the constraints. Since we are only interesting in checking the validity of a siteswap we have no variables, so we call it with an empty list. In this case it can only either succeed or fail. Not surprisingly, it will succeed, because 531 is a valid siteswap.
Another thing we can use our predicate for is completing an “unfinished” siteswap:
complete_test(X) :- domain([X],1,9), is_siteswap([5,3,X]), labeling([X]).
The second line here tells the constraint solver that X must be in the range 1 to 9. The last line orders the constraint solver to solve for X. The answers it will give are 1, 4, and 7.
We could also use the predicate to generate all siteswaps with period 3 and throws in the range from 1 to 9 (or any other range):
generate_test([T0,T1,T2]) :- domain([T0,T1,T2],1,9), is_siteswap([T0,T1,T2]), labeling([T0,T1,T2]).
My little program, which you can download here (you’ll need GNU Prolog to run it) implements several other constraints, notably the “non-triviality” constraint (making sure that a siteswap contains at least two different throws) and the “not-equal” constraints (making sure two siteswaps are different). My Prolog never was much to write home about and has degenerated noticably during the past few years, plus I’m rather lazy, so this program is certainly not an example of good Prolog style!
If you’re curious about constraint programming, the Wikipedia article probably isn’t the worst place to start.
For the puzzle freaks, here are some more:
2 4 3 1 5 2 1 6 3 3 1 1 7 5 2 1 1 1 2 6 8 2 2 2 6 2 4 2