Futoshiki Generation, properties

For fans of Killer Sudoku, Samurai Sudoku and other variants

Futoshiki Properties

Postby Mathimagics » Tue Jun 09, 2015 2:29 am

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.
Last edited by Mathimagics on Sun Jun 14, 2015 9:11 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: An unusual 9x9 Latin square

Postby denis_berthier » Tue Jun 09, 2015 3:32 am

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?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Futoshiki P(U)

Postby Mathimagics » Tue Jun 09, 2015 6:45 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Futoshiki

Postby Mathimagics » Tue Jun 09, 2015 6:59 am

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?
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Futoshiki

Postby denis_berthier » Tue Jun 09, 2015 7:46 am

Mathimagics wrote: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.)
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Futoshiki

Postby Mathimagics » Tue Jun 09, 2015 9:12 am

Ok, I get it! We're on the same page, I was temporarily distracted and lost the plot ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Futoshiki properties experiment

Postby Mathimagics » Wed Jun 10, 2015 2:44 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Futoshiki properties experiment

Postby denis_berthier » Wed Jun 10, 2015 4:24 am

Mathimagics wrote: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".

Mathimagics wrote: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.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Re: Futoshiki properties experiment

Postby Mathimagics » Wed Jun 10, 2015 4:29 am

denis_berthier wrote: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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Futoshiki properties experiment

Postby denis_berthier » Wed Jun 10, 2015 5:25 am

Mathimagics wrote:
denis_berthier wrote: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.
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Futoshiki - example

Postby Mathimagics » Fri Jun 12, 2015 5:32 am

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!
Last edited by Mathimagics on Sat Jun 13, 2015 3:35 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Futoshiki solver

Postby Mathimagics » Fri Jun 12, 2015 5:37 am

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.
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Futoshiki - example

Postby denis_berthier » Fri Jun 12, 2015 6:39 am

Mathimagics wrote: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 ?
denis_berthier
2010 Supporter
 
Posts: 1253
Joined: 19 June 2007
Location: Paris

Dodgy stats?

Postby Mathimagics » Sat Jun 13, 2015 7:52 am

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
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Re: Futoshiki - example

Postby Mathimagics » Sat Jun 13, 2015 7:54 am

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


That was the very first one it tested!
User avatar
Mathimagics
2017 Supporter
 
Posts: 335
Joined: 27 May 2015

Next

Return to Sudoku variants