The New Sudoku Players' Forum

[Mathimagics]

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]

Thanks Pat!

We are grateful for the enlightenment.

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

[Pat]

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

[denis_berthier]

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.

[Mathimagics]

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

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?

[denis_berthier]

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

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?

[Mathimagics]

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]

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]

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

[denis_berthier]

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.

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 ?

[Mathimagics]

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.

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]

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 = 82148
01:28:22 Initial LS = #69731
01: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 = 82148
02:06:02 Initial LS = #36925
02: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]

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]

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.

[Mathimagics]

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 1461 times

Irreducible (33 hints)

USolns_7_log#1_Rmax_Graph.gif (15.63 KiB) Viewed 1461 times