Greater-Than Sudoku

(I apologize if this post is giving you trouble when you read it; for some reason Blogger doesn't seem to like the large numbers of inequality signs in this post.)

A sort of puzzle that I find incredibly frustrating is the "Greater-Than Sudoku".

This is like Sudoku, except that none of the numbers are given. But greater-than or less-than sign indicate which of any two adjacent squares contains the greater number. (The adjacencies are only within the 3-by-3 squares that make up the larger 9-by-9 square, so there's no possiblity that these could be equal.)

An example can be found about halfway down at Ed Pegg Jr's column, "Sudoku Variations", which appears to be part of his approximately monthly column Math Games at MAA Online. Not surprisingly, this gives a wide variety of Sudoku variations. Personally I prefer the variant called "Sums Sudoku", in which the 9-by-9 grid is broken up into regions containing a few cells and the sum of the numbers in each of these is given. I went through a whole book of those last summer. They were fun.

There's a greater-than sudoku in the July 26 issue of the Philadelphia City Paper, by Matt Jones, the author of "Psycho Sudoku", who believe it or not is not the guy behind Jonesin' crosswords, which that paper also includes. (Jonesin' crosswords are by Matt Gaffney.) You can find a whole bunch of Jones' variant Sudokus at the Boston Phoenix. These include Greater-Than Sudoku, Sum Sudoku, Stepping-Stone Sudoku, and Kaidoku, which really has nothing to do with Sudoku (it's a word puzzle) but has a similar-sounding name. The reason I like the first three of these is because they require more mathematical thinking than the standard Sudoku, which is exactly the reason that most people probably like them less. I have often found things explaining Sudoku to people who haven't seen it yet that say "it doesn't involve any math, just logic" -- and that's true, at least with the common understanding of those words.

The problem with not being given any numbers, as in the Greater-Than Sudoku, is that there's nowhere, really, to start. The way I've usually started these puzzles is as follows: the number 9 must be in a square that contains a number greater than that in each of the adjacent squares. That allows one to rule out most squares from containing 9; if you're lucky, it rules out enough squares that, combining this with the rule that there is exactly one 9 in each row, column, and 3-by-3 square, you know where all the 9's are. Replacing "greater than" with "less than", you can determine where the 1's go. Next, the 8's can be placed -- they must be in squares that are greater than everything adajcent to them, except they could be less than an adjacent 9. This seems to lead to more possible places where 8's can go, in general, than 9's, so the "ruling out" is harder. By symmetry, one can do the same thing with the 2's. My theory is that if I could follow this far enough, I would have enough numbers that I could solve basically like a regular Sudoku puzzle; unfortunately this doesn't seem to work. (And even when it does seem to be working, it requires scratch paper -- it gets too messy to fit all the notes I want to make in the squares -- which just feels wrong for a newspaper puzzle.)

Another method that has occurred to me is to try to determine what range the number in each square falls in. For example, consider the bottom-left 3-by-3 square in the Greater-Than Sudoku in Ed Pegg's article. It has

A > B < C
v   ^   v
D < E < F
v   v   v 
G < H > I

where v and ^ are meant to be downward-pointing and upward-pointing analogs of < and >, and A, B, ..., I are 1, 2, ..., 9 in some order. We have, of course, the twelve inequalities that are given explicitly: B<A, B<C, D<A, B<E, F<C, D<E, E<F, G<D, H<E, I<F, G<H, I<H. These specify a partial order of A, ..., I (for those who don't know what this means: it just means that we know some of them are larger than others, and that if x is larger than y and y is larger than z, then x is larger than z); what we want to do is extend this to a total order. If we knew, for example, that G<D<E<F<C<B<H<I<A (incidentally, this isn't true), then we'd have G = 1, D = 2, E = 3, ..., A = 9.

Since the relation "less than" is transitive, we end up with various "chains" of inequalities, the longest of which is G<D<E<F<C. We also know that G<A (since G<D and D<A). Finally, G is less than H, and we can't compare G with B or I. So there are six numbers greater than G; thus G is at most 3. I suspect that doing this sort of reasoning for each square would help.

However, the twelve comparison signs in any 3-by-3 square are not themselves enough to specify how the numbers 1, ..., 9 are arranged. There are only 2¹² = 4096 ways we can set them up, and 9! = 362880 ways to arrange the integers 1, ..., 9 in those boxes; on average, if we arrange the < and > signs randomly, there will be 9!/2¹² = 88.59375 ways to fill in the numbers 1 through 9 in that square which are consistent with that choice of inequality signs. And it is clearly possible for there to be many less. For example, we can never have a square with

A > B
^   v
D < E

(the rest being irrelevant), since we have A<D<E<B<A and thus A<A. Thus, to offset this, in some cases there will be many more; we need the Sudoku constraints to help fit things together. The total number of Sudoku puzzles is widely reported to be 6,670,903,752,021,072,936,960 (see Russell and Jarvis, which also gives a nice heuristic that gets very close); this is about 2⁷², so it's at least plausible that the 108 comparison signs in a 9-by-9 Greater-Than Sudoku give enough information to specify a unique solution.