The New Sudoku Players' Forum

[Red Ed]

So please enlighten us!

My search is depth-first on the non-clue cells ...

Code: Select all

. . .|. . .|. . .
. . .|A B C|. . .
. . .|D E F|. . .
-----+-----+-----
. M P|1 2 3|S V .
. N Q|4 . 6|T W .
. O R|7 8 9|U X .
-----+-----+-----
. . .|G H I|. . .
. . .|J K L|. . .
. . .|. . .|. . .

... fixing those in B5 and then filling in the remaining non-clue cells in the order A,B,C,...,X subject to the symmetry constraints:

• A<D, G<J, A<G
• M<P, S<V, M<S

In addition to symmetry constraints, I check for unavoidables and isomorphs:

• Each time I fill in one of {C,F,I,L,O,R,U,X}, I check that the partial grid has no unavoidables.
• Each time I fill in {L}, I check that the half-way grid (of 8 fixed + 12 variable) cells is not isomorphic to any previous half-way grid.

That's it: nothing gets past the final unavoidables check at {X}, so there's not even any need to check that what's left can be completed to a full sudoku grid.

The isomorphism check shows that there are 11098 half-way grids with no unavoidables. (There's something you can check relatively easily to confirm that I'm not making all this up.)

[Havard]

wow! Quite a bit of new stuff there for me!

Starting with the symmetry constraints:

Code: Select all

. . .|A B C|. . .
. . .|D E F|. . .
-----+-----+-----
. M P|1 2 3|S V .
. N Q|4 . 6|T W .
. O R|7 8 9|U X .
-----+-----+-----
. . .|G H I|. . .
. . .|J K L|. . .
. . .|. . .|. . .

... fixing those in B5 and then filling in the remaining non-clue cells in the order A,B,C,...,X subject to the symmetry constraints:

• A<D, G<J, A<G
• M<P, S<V, M<S

So if I understand you correctly, if you did not have the symmetry contraints in place you could have this partially filled grid:

Code: Select all

. . .|. . .|. . .
. A->|2 . 1|. . .
. D->|3 . 8|. . .
-----+-----+-----
. . .|1 2 3|. . .
. . .|4 . 6|. . .
. . .|7 8 9|. . .
-----+-----+-----
. G->|5 . 4|. . .
. J->|6 . 7|. . .
. . .|. . .|. . .

and by using a "conversion table" like this:

Code: Select all

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

...and flipping it upside down(which we are allowed to do because of the symmetry), you get this grid:

Code: Select all

. . .|. . .|. . .
. A->|3 . 4|. . .
. D->|6 . 5|. . .
-----+-----+-----
. . .|1 2 3|. . .
. . .|4 . 6|. . .
. . .|7 8 9|. . .
-----+-----+-----
. G->|2 . 7|. . .
. J->|9 . 8|. . .
. . .|. . .|. . .

but since this grid violates your rule "A<G", this effectivly stops this isomorph from happening?

I guess my first question then would be if there would be any point to add a symmetry-contraint for 90 degree rotational symmetry here as well?
Would it be any point to change the symmetry-constraints to:

Code: Select all

. . .|A B C|. . .
. . .|D E F|. . .
-----+-----+-----
. M P|1 2 3|S V .
. N Q|4 . 6|T W .
. O R|7 8 9|U X .
-----+-----+-----
. . .|G H I|. . .
. . .|J K L|. . .
. . .|. . .|. . .

• A<D, G<J, A<G (flipping over X-axis)
• O<R, U<X, O<U (flipping over Y-axis)

and then add:

• A<O (rotation 90 degrees)

or I am not quite getting this?

to illustrate, it looks to me as if these two grids are isomorphic:

Code: Select all

. . .|. . .|. . .
. . .|3 . 4|. . .
. . .|5 . 7|. . .
-----+-----+-----
. 4 8|1 2 3|5 9 .
. . .|4 . 6|. . .
. 5 3|7 8 9|2 6 .
-----+-----+-----
. . .|6 . 5|. . .
. . .|8 . 1|. . .
. . .|. . .|. . .

Code: Select all

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

and rotating 45 degrees to the right you get:

Code: Select all

. . .|. . .|. . .
. . .|5 . 2|. . .
. . .|9 . 4|. . .
-----+-----+-----
. 4 8|1 2 3|5 9 .
. . .|4 . 6|. . .
. 3 5|7 8 9|1 2 .
-----+-----+-----
. . .|6 . 5|. . .
. . .|8 . 7|. . .
. . .|. . .|. . .

Both grids seem to fit your constraints, so could it be a point to add this extra one?

I am also not quite smart enough too see the use for the constraints A<D and G<J, can you keep enlightning?

What is clear to me, however, is how these constraints reduces the searchtree enormously!
In terms of using this to generate sudoku from a template, I am thinking that if a pattern can be transformed (using the rules we know: shifting rows within a chute etc) to its "most symmetrical", and then some of these constraints be applied before the search starts it could potentially make template-generating a lot faster!
...or are these constraints just usable in this special example???

phew, I'll have to get back to you about those unavoidables...
To much information for a little brain here...

(and for the record, I both trust and admire your results!!!)
Havard

[Red Ed]

Havard, you're too kind

First, the symmetry constraints. Symmetry was a bad word to use, sorry. For the A<D constraint, the argument goes like this: if there's a cross shape with no unavoidables then we can swaps rows 2 & 3 (if necessary) to ensure that A<D (this cannot introduce any new unavoidables), so we may as well assume that the constraint holds. The same sort of argument goes for the other constraints, too. I'm not sure about your extra constraint, A<O, since I don't know if it's possible to transform a grid to obey that whilst also keeping the digits of B5 unchanged.

On generating a sudoku from a template - yes, you can use the same sort of technique; but, no, you don't need to transform the grid to its "most symmetrical" form. You will win whenever the template shape is invariant under any of the usual set of transformations. In this case, the template shape is invariant under the swap row 2 <-> row 3, so we may assume "without loss of generality" that A<D, and so on. The more invariant ops, the more you can assume "w.l.o.g.".

btw, isomorphism checking at {L} uses more than just the symmetry constraints. Each time I get to {L}, I temporarily canonicalise the half-way grid and check it's not equal to any that I prepared earlier. If it's not a duplicate, I continue the search (with the original, non-canonicalised form); otherwise I backtrack. With symmetry constraints alone, I'd have 40000+ half-way grids to work with; but after isomorph checking, I'm down to 11098. So basic symmetry constraints help, but not completely.

[Havard]

On generating a sudoku from a template - yes, you can use the same sort of technique; but, no, you don't need to transform the grid to its "most symmetrical" form. You will win whenever the template shape is invariant under any of the usual set of transformations. In this case, the template shape is invariant under the swap row 2 <-> row 3, so we may assume "without loss of generality" that A<D, and so on. The more invariant ops, the more you can assume "w.l.o.g.".

I so get it!!! For every possible row / column / band / stack swap you can perform on the template without it changing shape, you can introduce one of your constraints! Genius! Can't wait to program this up! thankyouthankyouthankyou:)

btw, isomorphism checking at {L} uses more than just the symmetry constraints. Each time I get to {L}, I temporarily canonicalise the half-way grid and check it's not equal to any that I prepared earlier. If it's not a duplicate, I continue the search (with the original, non-canonicalised form); otherwise I backtrack. With symmetry constraints alone, I'd have 40000+ half-way grids to work with; but after isomorph checking, I'm down to 11098. So basic symmetry constraints help, but not completely.

So, would it be too much to ask that you perhaps maybe could try out my set of constraints to see if this would reduce the 40000 a bit? (*blink, blink*) (just would be great to hear it from you wether there is a point adding a 45 degree rotational constraint as well)

Havard

[Havard]

I'm not sure about your extra constraint, A<O, since I don't know if it's possible to transform a grid to obey that whilst also keeping the digits of B5 unchanged.

I thought that this example showed that it is possible:

to illustrate, it looks to me as if these two grids are isomorphic:

Code: Select all

 
. . .|. . .|. . .
. . .|3 . 4|. . .
. . .|5 . 7|. . .
-----+-----+-----
. 4 8|1 2 3|5 9 .
. . .|4 . 6|. . .
. 5 3|7 8 9|2 6 .
-----+-----+-----
. . .|6 . 5|. . .
. . .|8 . 1|. . .
. . .|. . .|. . .

1=3, 2=6, 3=9, 4=2, 5=5, 6=8, 7=1, 8=4, 9=7
rotating 45 degrees right

. . .|. . .|. . .
. . .|5 . 2|. . .
. . .|9 . 4|. . .
-----+-----+-----
. 4 8|1 2 3|5 9 .
. . .|4 . 6|. . .
. 3 5|7 8 9|1 2 .
-----+-----+-----
. . .|6 . 5|. . .
. . .|8 . 7|. . .
. . .|. . .|. . .


Both grids seem to fit your constraints, so could it be a point to add this extra one?

[daj95376]

[Withdrawn]

[Red Ed]

(just would be great to hear it from you wether there is a point adding a 45 degree rotational constraint as well)

No, you cannot insist on A<O for this particular template. For example, consider the following cross shape ...

Code: Select all

. . .|. . .|. . .
. . .|3 4 5|. . .
. . .|9 6 8|. . .
-----+-----+-----
. 5 9|1 2 3|6 7 .
. 7 8|4 . 6|1 9 .
. 2 6|7 8 9|3 5 .
-----+-----+-----
. . .|5 1 4|. . .
. . .|6 9 7|. . .
. . .|. . .|. . .

There are 8 ways to permute and relabel it such that B5 has the right values and my original six ?<? constraints are satisfied (this is true of any instance of the cross shape, not just the one shown). But none of those eight ways also has A<O.

You can, however, insist on the transposition constraint A<M. Unfortunately, though, this is a waste of time because A<M is implied ~96% of the time by the first six.

Well, it was worth a try

[Havard]

I see.
Thank you again for your time and effort!

Now if you could find some more time there are a still a few things I don't quite grasp:

1: Why is there still a gap between the 40000+ and the 11098 even with your brilliant constraints in place? Can we ever hope to generate only those 11098, and how could this be done? What transformations don't your constraints pick up on?

2: Does it matter that the contraints are focused around a few placement (like A G appearing twice) or would it be just as effective with say: A<D, E<K, I<L. I have extended my templategenerator to find these constraints automatically and, was wondering if there is any gain in "where" in the two invariant sectors you place the constraints.

The constraints is working even better then I could hope for, quite often not just reducing the search tree a lot, but forcing placements as well! (a<b where a=4 and b has the candidates 12347, forces b=7) As you probably understand I am thirsty for more of this stuff!

Havard

[Red Ed]

Havard, oops - sorry, I misread my own constraints - I thought I was checking O<R, U<X, O<U rather than M<P, S<V, M<S ... so my previous post had some typos in it. These are corrected now.

Now your two new q's.

1. The constraints only consider six of the nine row/col shuffling ops that are available; they don't consider the isomorphs you could get from r4<->r6, c4<->c6 or transpose (+ relabelling in each case). This doesn't matter, though, because the full isomorph check at the half-way point gives enough cut-down for the search to finish in reasonable time.

2. It does matter that the constraints are of a particular form. To take your proposal, can you think how to use row/col swaps + transpose & relabelling to force any grid to have A<D, E<K, I<L? It's not clear to me that that should be possible. On the other hand, it's easy to show that exactly one in 64 grids satisfy the six constraints that I posted. More sophisticated cut-down is undoubtedly possible, but you have to trade off the cost of constraint checking against the reduction in search tree size.

I have extended my templategenerator to find these constraints automatically

You need to be careful with this, as it's usually the case that constraints cannot be applied independently. We already saw that the constraint A<O, which is fine by itself, doesn't work in tandem with the other six. I always do this sort of pruning on a case-by-case basis rather than trust the computer to invent a strategy for me.

[RW]

Wouldn't it be possible to lock some more digits in that template? I think at least D=9 should be possible to set for all grids. Or does this interfere with your other constraints?

RW

[Havard]

The isomorphism check shows that there are 11098 half-way grids with no unavoidables. (There's something you can check relatively easily to confirm that I'm not making all this up.)

I have checked this, and my result is that there is only 8888(!) valid grids with this configuration:

Code: Select all

. . .|. . .|. . .
. . .|A B C|. . .
. . .|D E F|. . .
-----+-----+-----
. . .|1 2 3|. . .
. . .|4 5 6|. . .
. . .|7 8 9|. . .
-----+-----+-----
. . .|G H I|. . .
. . .|J K L|. . .
. . .|. . .|. . .

I will start a new thread on constraints vs. loss of generality

Havard

[Red Ed]

There's no contradiction here. I left r5c5 unset and only looked for ways of filling A-L such that no row, column or box contained a repeated digit. This gives a superset of fills that could possibly arise from a real sudoku grid. Your result would only contradict mine if it was a larger number than mine.

Would it have saved me more compute time to use your better, stricter, definition of "valid" than mine, compared to the time lost in coding it up? Probably not.

[coloin]

I have now completed an exhaustive search on the form

Code:
00X
0XX
XXX


No Sudoku exists, but there are plenty with only two solutions.

This completes the list of which empty-box sets there might be in a Sudoku. Ocean's list is complete, his assumtions were right. I.e. there are no Sudokus on any of the forms

Code:
00X
0XX
XXX

00X
0XX
XX0

00X
0X0
XXX


I don't know the minimal number of solutions for the last one.

For this "last" one

Code: Select all

00X
0X0
XXX

I generating a few I got a minimum of 15 and a maximum of 108 grid solutions

Code: Select all

 15 sol.#673..5...185......924......536948721897621453241573869......614......237......985
108 sol.#731..6...285......964......613729458842615973579843621......539......186......247

Code: Select all

+---+---+---+
|673|...|...|
|185|...|...|
|924|...|...|
+---+---+---+
|536|948|721|
|897|621|453|
|241|573|869|
+---+---+---+
|...|...|614|
|...|...|237|
|...|...|985|
+---+---+---+  15 sols , solved with 5 r1c6!

Room for improvement !

C

[JPF]

Room for improvement !

Yes...

This puzzle (B1B2B4B6=0)
...
can only have 0 or k solutions ; k=10, 11, 12,…, 176.
Note : again, I made a random search.
I got all these numbers of solutions except 12 numbers. (11,12,13,155,163,...)

Overnight, I did another exhaustive search. Apart from cases with no solutions, the full range of solutions is { 7...166, 168...170, 172, 174, 176, 178, 180, 184, 186, 188, 192, 208, 216, 224 }. Here are examples of the min and max of that range:

Code: Select all

  7 : 000314000000782000000965000000000743000000826000000915123478569456139278789256134
224 : 271000000538000000964000000000583000000721000000964000123479865456238179789156324

JPF

[coloin]

I got a 10 !

Code: Select all

10  sol.#365......497......812......573462189928315647641798523...931......657......284...

But the minimum that has been found is 7
Well done that man - again he saves us a lot of random generations

Ah.. but did he prove it was 7 ?
Quite possibly he did search all the possible equivalents for the pattern ?

Thanks