## Futoshiki Generation, properties

For fans of Killer Sudoku, Samurai Sudoku and other variants

### Order-preserving cycles

I've further improved the OPC detector. It now picks up pathological cases like this:

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

This is an order-preserving compound cycle - it's 2 x symbol-swap-cycles (in Jacobson & Matthews terminology) that have been stitched together at a pivot cell, in a way that preserves LS integrity (ie. it's a "proper move").

I'll leave identification of the pivot cell as an exercise for the reader!

A smaller change in the observed stats this time:

Code: Select all
`15:09:37 Begin LS generation (Futoshiki proper)15:17:51 Gen = 64878, Proper = 1564, p(P) = 2.411%, n(V=>U) = 644, p(V=>U) = 41.176%`

A problem is now evident, how to get a big enough sample of Proper LS's - here's another, longer batch, that suggests the estimates are reasonable:
Code: Select all
`17:04:42 Begin LS generation (Futoshiki proper)17:58:47 Gen = 320550, Proper = 7832, p(P) = 2.443%, n(V=>U) = 3378, p(V=>U) = 43.131%`

Mathimagics
2017 Supporter

Posts: 682
Joined: 27 May 2015

### Origins of Fish

Thanks Pat!

We are grateful for the enlightenment.

Any idea why they then turned to fish varieties for hidden triples, etc?

Mathimagics
2017 Supporter

Posts: 682
Joined: 27 May 2015

### re: Origins of Fish

Mathimagics wrote:Thanks Pat!

We are grateful for the enlightenment.

Any idea why they then turned to fish varieties for hidden triples, etc?

a friendly Moderator has kindly split that,
see here

Pat

Posts: 3595
Joined: 18 July 2005

### Re: Order-preserving cycles

Mathimagics wrote:I've further improved the OPC detector.
[...]
A problem is now evident, how to get a big enough sample of Proper LS's - here's another, longer batch, that suggests the estimates are reasonable:
Code: Select all
`17:04:42 Begin LS generation (Futoshiki proper)17:58:47 Gen = 320550, Proper = 7832, p(P) = 2.443%, n(V=>U) = 3378, p(V=>U) = 43.131%`

I've been away for a few days. Nice to see you're progressing fast.
Even if there are only ~ 1.5% well-formed Futoshiki puzzles among all the complete LS, I can't see any real problem here.

Using then a classical top-down generator or a controlled-bias one, the generation of minimal puzzles seems to raise questions different from Sudoku. Here, considering the small percentage of complete grids that lead to uniqueness, it is likely that this part of generation will find that some of them are already minimal puzzles. I'm curious to see the percentage.
denis_berthier
2010 Supporter

Posts: 1258
Joined: 19 June 2007
Location: Paris

### Futoshiki Minimality

I agree that this issue of minimality is a whole different ball-game to Sudoku, and how fascinating it is!

denis_berthier wrote:Considering the small percentage of complete grids that lead to uniqueness, it is likely that this part of generation will find that some of them are already minimal puzzles. I'm curious to see the percentage.

Not sure what you mean. Percentage of what exactly?

Mathimagics
2017 Supporter

Posts: 682
Joined: 27 May 2015

### Re: Futoshiki Minimality

Mathimagics wrote:I agree that this issue of minimality is a whole different ball-game to Sudoku, and how fascinating it is!
denis_berthier wrote:Considering the small percentage of complete grids that lead to uniqueness, it is likely that this part of generation will find that some of them are already minimal puzzles. I'm curious to see the percentage.

Not sure what you mean. Percentage of what exactly?

Take a complete LS, add all the < signs, delete all the digits. Discard the result if it is not a well-formed Futoshiki puzzle.
In this way, one gets all the "saturated" Futoshiki puzzles. (If you have a better name for them ...)
Among these "saturated" Futoshiki puzzles, what is the percentage of those that are already minimal before you delete any clue?
denis_berthier
2010 Supporter

Posts: 1258
Joined: 19 June 2007
Location: Paris

### Futoshiki Uniqueness Testing

What I've done with OPC's is of both theoretical interest and practical use. I referred previously to the problem of uniqueness testing, how we needed to be sure that a puzzle was unique, so had to let the solver/tester pursue a second solution, just to be sure that it didn't exist.

So my OPC detector is perhaps of some value - perhaps for larger grids it will have some advantages over DFS.

Meanwhile, I will return to the question of Futoshiki minimality - the reduction process (and at some stage I will get back to Kakuro!!!)

Mathimagics
2017 Supporter

Posts: 682
Joined: 27 May 2015

### Re: Futoshiki Generation, properties

denis_berthier wrote:In this way, one gets all the "saturated" Futoshiki puzzles. (If you have a better name for them ...)
Among these "saturated" Futoshiki puzzles, what is the percentage of those that are already minimal before you delete any clue?

Oh, I like saturated - I used that very term (well, I used poly-unsaturated) to describe the 9x9 Latin square I discovered with no 3x3 sub-matrix containing all the values 1...9 over at StackExchange.

Anyway, that's what I thought you meant, and my prediction is that percentage will be zero. They will all be reducible.

Although I definitely wouldn't mind being proved wrong in this case!

Mathimagics
2017 Supporter

Posts: 682
Joined: 27 May 2015

### Reducibility vs Saturation

My conjecture is looking good!

My first thought when you suggested that some saturated cases might also be irreducible, was what about the "1"s and "9"s in a saturated puzzle. I couldn't imagine how none of them would be redundant.

So my test function is ploughing through a batch of 15,000 unique solutions I have recenly generated and has yet to find one exception. I take the "9"'s in each row and inevitably get one (usually more) whose ">"'s I can remove entirely without upsetting uniqueness.

My new batch of U's is from a successful experiment in "direct" generation (well not really!). I just perturb one unique solution to find another - it's just the Pittenger random LS generator modified to only follow perturbations that maintain U-ness. It's very interesting that it works at all!

The batch has just finished:
Code: Select all
`05:24:42 Testing reducibility ("9" hint removal)06:22:52 There were 15524 tests, 0 exceptions`

Mathimagics
2017 Supporter

Posts: 682
Joined: 27 May 2015

### Re: Reducibility vs Saturation

Mathimagics wrote:So my test function is ploughing through a batch of 15,000 unique solutions I have recenly generated and has yet to find one exception. I take the "9"'s in each row and inevitably get one (usually more) whose ">"'s I can remove entirely without upsetting uniqueness.

Starting from a complete LS, adding all the < signs, then starting to delete digits and < signs so as to produce an "impure" Futoshiki (with both <'s and digits as clues):
- your first results proved that one cannot delete all the digits and preserve U
- your new ones tend to show that, when U is preserved, one can still remove some of the <'s

I think it gives some theoretical interest to the notion of an "impure" Futoshiki (for which there's no problem of pre-filtering the LS's). But there are at least two possible notions of minimality, defined by the following generators:
G1, with two steps:
- randomly delete as many digits as possible (preserving U)
- randomly delete as many <'s as possible (preserving U)
G2, with 1 step:
- randomly delete as many digits and <'s as possible (preserving U)
G2 would occasionally generate LS.
I think the "good" view is G1. Considering how few digits its puzzles have, I think it's what the Tatham generator does, but I can't read its archaic undocumented way of programming.

Mathimagics wrote:My new batch of U's is from a successful experiment in "direct" generation (well not really!). I just perturb one unique solution to find another - it's just the Pittenger random LS generator modified to only follow perturbations that maintain U-ness. It's very interesting that it works at all!

Are you sure they maintain U? Or do they only keep away from the no-U patterns you've mentioned previously?
Does the process preserve connectedness and uniformity of the asymptotic distribution on the U subspace ?
denis_berthier
2010 Supporter

Posts: 1258
Joined: 19 June 2007
Location: Paris

### Markov chain for Unique Solutions?

denis_berthier wrote:Are you sure they maintain U? Or do they only keep away from the no-U patterns you've mentioned previously?

They are guaranteed to be U because I explicitly test them during the process. My method was basically this:

Do {
New LS = Perturb (Current LS)
if IsU(NewLS) set Current LS = New LS
} while true

Where Perturb is a single Pittenger perturbation, and IsU is the standard test involving turning the LS into a saturated set of hints and invoking the DFS solver to test uniqueness. We start, of course, with CurrentLS set to a known U.

denis_berthier wrote:Does the process preserve connectedness and uniformity of the asymptotic distribution on the U subspace ?

Early days, but I was surprised to learn that I didn't need a bailout condition (ie. some limit on the number of perturbation tests). So every U could be transformed into another U with a single perturbation. That's very encouraging, suggestion strong connectedness, and perhaps the possibility of uniformity.

I'll run some tests on smaller grids to try and learn more.

Mathimagics
2017 Supporter

Posts: 682
Joined: 27 May 2015

### Markov chain for Unique Solutions

I ran the model on N=5, for which we have 82148 unique solutions:

Code: Select all
`01:28:22 Begin US5 connectedness test, NU5 = 8214801:28:22 Initial LS = #6973101:28:45 NU =   25600, Npert =   37623, avgP = 1.47, hit = 20694 (25.19%)01:29:20 NU =   62464, Npert =   92164, avgP = 1.48, hit = 41359 (50.35%)01:30:17 NU =  125952, Npert =  185875, avgP = 1.48, hit = 61807 (75.24%)01:50:58 NU = 1434563, Npert = 2128082, avgP = 1.48, hit = 82148`

These figures seem satisfactory. Every U was hit (eventually), ergo the space is connected. In the time it took to get to 25% of U's hit, the success rate was 80% (ie. the chances of getting a new U). For 50% coverage, the average success rate was 66%, and 75% coverage was achieved with a 50% success rate.

This suggests the essential stability of the distribution, I think.

I seem to recall that, back in 2009? when blue and I were testing a similar model for a random CGD generator (Contiguous Gerechte Designs), we got similar results.

I altered the base model so that it kept going at each generation step until the new LS was at least 50% different to the previous one, this is the sort of model I'd use in "production" mode. This gave the following results:
Code: Select all
`02:06:02 Begin US5 connectedness test, NU5 = 8214802:06:02 Initial LS = #3692502:07:13 NU =   24576, Npert =  111462, avgP = 4.54, hit = 20805 (25.33%)02:08:52 NU =   59392, Npert =  269076, avgP = 4.53, hit = 41111 (50.05%)02:11:55 NU =  122880, Npert =  557778, avgP = 4.54, hit = 61697 (75.10%)03:16:42 NU = 1478656, Npert = 6701633, avgP = 4.53, hit = 82148 (100.00%)`

These are essentially the same figures, except for the # of perturbations required at each step.

Mathimagics
2017 Supporter

Posts: 682
Joined: 27 May 2015

### Markov chain for Unique Solutions?

I'm tring to locate all Unique solns for N=6. This will help to demonstrate connectivity of the perturbation model when N > 5. Since 50% of N=5 cases are unique, the test above doesn't prove much. But confirming it for N=6 where pU = 25% will be a positive step (I hope!)

I've got a file containing all LS's of size 6 with fixed row 1 = "123456". There are 1,128,960 of these, each of which gives 6! = 720 distinct LS's for a total of 812,851,200 LS's all up.

We can expect 200 million unique soln cases, and this reduces to 25 million if we eliminate isotopies. I base this figure on the fact that there are 3 isotopies for each LS (HReflect, VReflect, DReflect) and these 4 LS's also have symbol reflections (SR).

I've got reasonably efficient routines for isotopy detection, linked list handling, etc, but what's really taking time is doing the uniqueness checking. In 24 hours it has registered nearly 4 million U's, which is 50/sec, quite reasonable, but I expect it will take a week to finish the job!

Mathimagics
2017 Supporter

Posts: 682
Joined: 27 May 2015

### Futoshiki Uniquness, Graph Theory

It occurred to me that the saturated puzzle specs for unique solutions correspond to a directed acyclic graph (see example image attached) with a lattice format.

Solving a puzzle is thus a vertex-labelling (coloring) problem but with a twist, no label can appear twice in a row or column, and the labels themselves are ordered, and must satisfy the label ordering specified by the arrows.

Does this provide an alternative form of uniqueness testing? I'm not sure, I've been looking at the manual for iGraph, but can't see anything useful.
Attachments
Unique soln (size 7) as a DAG
USolns_ log#8_Graph.gif (16.43 KiB) Viewed 262 times

Mathimagics
2017 Supporter

Posts: 682
Joined: 27 May 2015

### Futoshiki - Irreducible forms

It just keeps on getting interesting! (3 weeks since I looked at Kakuro )

I took a randomly generated U (size 7 in this experiment), then generated 10,100 reduced forms. The reduction method uses a "coarse shave" to remove random hints, then a "fine shave" to systematically reduce the result to a minimum (this routine is also random in its hint selection, since the result varies according to the order in which hints are removed).

Indeed, in the 10,100 reductions all but 2 were different. Also intriguing was the variety of hint counts. The smallest was 20, and the largest 35.

The original saturated form was:
Code: Select all
`7>><><>>><><><>>><<<>><<>><<>><><><>><<><><>>><<><<<><><<>><<>>><><>><<<><><>>>><><><`

The reduced spec with just 20 hints is:
Code: Select all
` 7 ------>>----->-------<---<-->------><--<------<---<--><->>--------->---><-->---->---`

And the reduced spec with 35 hints is:
Code: Select all
` 7 >---<>--<----->-<----<->-<->><><--->--><---->---<<<--><<->-->->--<>--<-><---->-<-<--`

The DAG images for both reductions are given below ( sorry about the scroll bars!)

Irreducible (20 hints)
USolns_7_log#1_Rmin_Graph.gif (15.3 KiB) Viewed 257 times

Irreducible (33 hints)
USolns_7_log#1_Rmax_Graph.gif (15.63 KiB) Viewed 257 times
Last edited by Mathimagics on Mon Jun 29, 2015 5:18 am, edited 1 time in total.

Mathimagics
2017 Supporter

Posts: 682
Joined: 27 May 2015

PreviousNext