The New Sudoku Players' Forum

[Mathimagics]

Consider this 9x9 Latin square:

Code: Select all

  1  2  3  4  5  6  7  8  9
  2  1  4  3  6  8  9  7  5
  3  4  2  1  7  9  6  5  8
  4  3  1  2  8  7  5  9  6
  5  6  8  7  9  1  3  2  4
  6  8  7  9  4  5  2  1  3
  7  9  5  6  2  3  8  4  1
  8  7  9  5  3  4  1  6  2
  9  5  6  8  1  2  4  3  7


No matter how you permute the rows and columns, you will never find a Sudoku-square therein, that is, you will never get 1...9 in a 3x3 region.

I call them poly-unsaturated Latin squares. See A question about Sudoku squares over at Stack Exchange for more details.

These are rare beasties, and extremely hard to track down. Unless we learn some more about why they exist, searching for them is virtually impossible for anything greater than 9 = 3 x 3.

Their very existence was (apparently) only a conjecture till now.

[denis_berthier]

Interesting example.
That reminds me of a question for which I couldn't find any answer. Indeed I couldn't find any reference to such a question.
Take a complete Latin Square, fill in all the inequalities between adjacent cells, delete all the digits. What are the chances of getting a valid Futoshiki puzzle?

[Mathimagics]

That's been on my list for some time too. One suspects that it would be reasonably good, but we'll see.

There was a magazine, SudokuXtra, which had a wide variety of puzzle types, including Sudoku Inequality, which was Futoshiki on a 9x9 grid with Sudoku regions. I was hooked on them.

[Mathimagics]

I think having every adjacency specified would completely specify the row/order content. That would surely guarantee uniqueness.

Or are we allowing more symbols than the grid size? Kind of like Kakuro?

[denis_berthier]

I think having every adjacency specified would completely specify the row/order content. That would surely guarantee uniqueness.
Or are we allowing more symbols than the grid size? Kind of like Kakuro?

I was thinking of 9x9 Futoshiki - but, for any k, we can ask the same of k*k Futoshiki with k different digits (1 2 3 4 5 6 7 8 9 A B C D ...}.

One has to find k*k unknowns and one has 2*(k-1)*k (non-independent) inequalities. So it isn't absurd to suppose that it is "often" enough to guarantee uniqueness. But I couldn't prove that it is always enough, even for k = 9. (As it was not essential to my purposes, I didn't try hard.)

[Mathimagics]

Ok, I get it! We're on the same page, I was temporarily distracted and lost the plot ...

[Mathimagics]

I'm nearly ready to test your conjecture on uniqeness in completely specified Futoshiki grids.

I've got a solver and a random Latin Square generator, just have to bolt them together.

I hadn't used my LS generator for some time - are you familiar with an elegant method by Pittenger? It's done by simple perturbations on an existing LS. It has genuine Markov chain properties, very close to truly random LS's.

[denis_berthier]

I'm nearly ready to test your conjecture on uniqeness in completely specified Futoshiki grids.

It was only a question. I don't have enough data to give it the status of a conjecture.
I still have doubts about the "always" - which is not in itself a big problem if one gets uniqueness "often enough".

I've got a solver and a random Latin Square generator, just have to bolt them together.
I hadn't used my LS generator for some time - are you familiar with an elegant method by Pittenger? It's done by simple perturbations on an existing LS. It has genuine Markov chain properties, very close to truly random LS's.

I didn't work on Latin Squares per se (as many people here, I was more interested in Sudoku). Of course, SudoRules can solve LS by switching off all mentions of blocks, but I tried only a few examples. The main reason is, I didn't have a LS generator.

AFAIK, what Pittenger leads to is a random (unbiased) generator of full grids. You still have to generate puzzles by a top-down process of clue elimination, which introduces some strong bias (wrt the number of clues), as in Sudoku.
For Sudoku, it's very hard to generate unbiased collections of minimal puzzles. Actually, as of now, we can't; we can only generate collections with (strong) known bias (see chapter 6 of my last book), starting from a list of all the non-equivalent complete grids (provided by gsf).
For Futoshiki, if uniqueness holds (often enough), one could try to combine a LS generator with the same "controlled-bias" techniques.

[Mathimagics]

It was only a question. I don't have enough data to give it the status of a conjecture.

I should have said your hypothetical conjectured conjecture.

[denis_berthier]

It was only a question. I don't have enough data to give it the status of a conjecture.

I should have said your hypothetical conjectured conjecture.

Yep
But it remains worth to try.
I think I mixed up two different problems in my previous post. The bias problem appears in Futoshiki only when one wants minimal puzzles. It has no impact on the original hypothetical conjectured conjecture.

[Mathimagics]

A random rank 6 Latin square was generated and to my surprise, the very first one I tried did not have a unique solution.

Early indicators are that the uniqueness probability decreases rapidly with grid size (all tests involved thousands of random LS's):

• grid size 4: pU ~= 57%
• grid size 5: pU ~= 57%
• grid size 6: pU ~= 24%
• grid size 7: pU ~= 4.5%
• grid size 8: pU ~= 0.25%

The trend seems to be clear!

[Mathimagics]

I through away my first attempt at hacking a recusive Solver based on my Kakuro model, a process which was giving me much grief.

I built a non-recursive model, using chains ( ie Cell[x] < Cell[y] .... < Cell[x]). I still have to see whether it can cope with a 9x9 grid.

[denis_berthier]

hey, I finally got the bugs out of my test rig, and my first run was very interesting. A random rank 6 Latin square was generated and to my surprise, out popped this report:

Code: Select all

Board is full! oops, nms = 3

  R:  2 3 4 4 3 3 4 4 4 5 5 5 6 6 3 2 3 2 1 1 1 2 1 2 1 3 4 5 5 6 6 1 5 6 2 6
  C:  1 1 1 2 2 3 3 5 4 3 4 5 5 4 4 4 5 5 4 5 6 3 2 2 3 6 6 2 6 6 3 1 1 2 6 1
-----------------------------------------------------------------------------
 S1:  2 3 4 5 6 1 3 1 2 4 3 5 6 5 4 6 2 4 1 3 4 5 2 3 6 5 6 1 2 3 2 5 6 4 1 1
 S2:  2 3 4 5 6 1 3 1 2 5 3 4 6 5 4 6 2 5 1 3 4 4 2 3 6 5 6 1 2 3 2 5 6 4 1 1
 S3:  2 3 4 5 6 1 3 1 2 6 3 4 6 5 4 6 2 5 1 3 4 4 2 3 5 5 6 1 2 3 2 6 5 4 1 1

S1 (verified)
  5  2  6  1  3  4
  2  3  5  6  4  1
  3  6  1  4  2  5
  4  5  3  2  1  6
  6  1  4  3  5  2
  1  4  2  5  6  3

S2 (verified)
  5  2  6  1  3  4
  2  3  4  6  5  1
  3  6  1  4  2  5
  4  5  3  2  1  6
  6  1  5  3  4  2
  1  4  2  5  6  3

S3 (verified)
  6  2  5  1  3  4
  2  3  4  6  5  1
  3  6  1  4  2  5
  4  5  3  2  1  6
  5  1  6  3  4  2
  1  4  2  5  6  3


Excellent. How many 6x6 puzzles did you have to test before finding it ?

[Mathimagics]

Hmmm ... I just found that after a little tidying up, my results seem to have changed.

Until I have resolved this issue, the probabilities above must be considered dodgy!

Apologies

[Mathimagics]

Excellent. How many 6x6 puzzles did you have to test before finding it ?

That was the very first one it tested!