Logic Masters Deutschland e.V.

(I almost published this about 10 days ago. But the ID assigned to the puzzle was 000JAM, so I created a jam-themed puzzle instead: JAM)

Standard 8x8 irregular sudoku rules apply: Put a digit from 1 to 8 in each cell so that every digit occurs once in each row and column, and in each box defined by the thick black lines.

Standard killer rules apply: In each cage defined by the dotted lines, the digits sum to the number in the top left corner of the cage. Digits cannot repeat in a cage.

In addition, the "all-pairs" rule applies: There are 56 pairs of horizontally adjacent cells in the grid, 7 in each of the 8 rows. There are also 56 possibilities for the digits that can occur in such a pair: You can choose any of the 8 digits for the cell on the left and any of the other 7 digits for the one on the right. In this puzzle, each possible pair of digits occurs exactly once as a horizontally adjacent pair. Each pair of digits also occurs exactly once as a vertically adjacent pair.

For example, for the digits 3 and 5 there are exactly four places where they occur in orthogonally adjacent cells, one where 3 is to the left of 5, one where it's to the right, one where it's above, and one where it's below. (These places might overlap, sharing either the 3 or the 5.)

You can solve this in SudokuPad.

I had hoped to make an ordinary 9x9 sudoku using this constraint. Unfortunately it's impossible to fill a sudoku grid so that the all-pairs rule applies to horizontally adjacent cells, let alone in both directions. I don't have a proof of that, but I wrote a computer program to do an exhaustive search and it found nothing. An 8x8 sudoku with 2x4 boxes can satisfy the condition either horizontally or vertically, but not both.

I suspect that whenever N is an odd number larger than 1, it's impossible to satisfy the all-pairs condition horizontally in any latin square of order N. Maybe there's a simple proof of that, but I haven't thought of one. If some expert on latin squares can supply a proof or counterexample, I'd be interested to see it. (P.S.: I found a counterexample.)

For even N it is possible to satisfy the condition in both directions. One way to do so uses the addition table for the integers (mod N), with the columns and rows permuted into the order 0, N-1, 1, N-2, 2, N-3, ..., N/2-1, N/2. E.g. for N=6 this is an example:

P.S.: It turns out that I was wrong. A long-running program found that, although there are no latin squares of order 3, 5, or 7 that satisfy the all-pairs condition horizontally, there are some of order 9. Here's one:

I don't know yet if a 9x9 can satisfy the condition in both directions.