Max number of clues

Everything about Sudoku that doesn't fit in one of the other sections

Postby Red Ed » Mon Feb 27, 2006 7:48 pm

Ocean wrote:1. A permutable set is an alternative name for an unavoidable set.
The original terminology was exchangeable set.

Ocean wrote:2. A k-permutable set (for k>=2) is a permutable set that has k valid permutations.
3. A minimal k-permutable set is a k-permutable set that does not contain any other k-permutable set.

:idea: Conjecture 1. A minimal unavoidable set is a minimal 2-permutable set.
Nope, false. I offered up the same conjecture in the pseudo-puzzles thread, which was then disproved by this minimal unavoidable with 3 valid permutations from sf-big.txt :
Code: Select all
639|2.1|78.
28.|.65|1.3
5.7|..3|624
---+---+---
.23|8..|94.
.9.|..2|..1
..8|61.|.3.
---+---+---
.42|.7.|..9
...|...|...
97.|.2.|418
Ocean wrote::idea: Conjecture 2. A k-permutable set contains between 1 and k-1 minimal 2-permutable sets as subsets.
Nope - as above.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Ocean » Mon Feb 27, 2006 11:18 pm

Red Ed wrote:
Ocean wrote:1. A permutable set is an alternative name for an unavoidable set.
The original terminology was exchangeable set.

Thanks for pointing to the history! (Those days I had not yet dicovered sudoku). The point was to give a short name to unavoidable sets that have k permutations - therefore the k-permutable set (and minimal k-permutable set).

Red Ed wrote:
Ocean wrote:...:idea: Conjecture 1. A minimal unavoidable set is a minimal 2-permutable set.
Nope, false. I offered up the same conjecture in the pseudo-puzzles thread, which was then disproved by this minimal unavoidable with 3 valid permutations from sf-big.txt :
Thanks again! I ought to remember this. Sorry. But the general idea does not really suffer. Have updated the post, hopefully getting it right this time.
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Red Ed » Mon Feb 27, 2006 11:59 pm

Ocean wrote::idea: Conjecture 1. A minimal unavoidable set is a minimal k-permutable set.
All minimal unavoidables are minimal k-permutables, but not vice-versa. If I understood your definition, a minimal k-permutable is allowed to contain some lesser m-permutable (m<k); in which case, take any full grid (a non-minimal unavoidable) as a minimal 6.67e21-permutable ...
Ocean wrote::idea: Conjecture 2. A k-permutable set contains between 1 and k-1 minimal unavoidable sets as subsets.
... in which case this conjecture is disproved, too.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Ocean » Tue Feb 28, 2006 10:21 am

Red Ed wrote:
Ocean wrote::idea: Conjecture 1. A minimal unavoidable set is a minimal k-permutable set.
All minimal unavoidables are minimal k-permutables, but not vice-versa.

Thanks again for the comment. This is exactly what was meant. Maybe my formulation was a bit unclear, and can be misunderstood, so I agree your formulation is better.
If I understood your definition, a minimal k-permutable is allowed to contain some lesser m-permutable (m<k); in which case, take any full grid (a non-minimal unavoidable) as a minimal 6.67e21-permutable ...
Ocean wrote::idea: Conjecture 2. A k-permutable set contains between 1 and k-1 minimal unavoidable sets as subsets.
... in which case this conjecture is disproved, too.

But this I don't quite understand. That a 6.67e21-permutable set contains somewhere between 1 and 6.67e21 minimal unavoidable sets as subsets does not seem unreasonable to me. So I can not see how the conjecture is disproved.
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby Red Ed » Tue Feb 28, 2006 7:30 pm

Ocean wrote:That a 6.67e21-permutable set contains somewhere between 1 and 6.67e21 minimal unavoidable sets as subsets does not seem unreasonable to me. So I can not see how the conjecture is disproved.
You're right, I wasn't paying attention; I take it back.

Here's a proof of your conjecture 2. We'll prove the contrapositive, that having k minimal unavoidables makes you m-permutable for some m>k. Suppose I've got a set S containing k minimal unavoidables, U(1),...,U(k). For each i = 1,...,k, let S(i) be S with U(i) replaced by one of its (non-trivial) valid permutations. Note that S(i)=S(j) only when i=j, since otherwise we could permute the intersection of S(i) and S(j) whilst keeping their other parts fixed -- in contradiction to the minimality of U(i) and U(j). So all the S(i) are distinct which, along with S, makes for k+1 valid permutations.

Similar reasoning applies when proving your conjecture X:
Ocean wrote::idea: Conjecture X. If removing one clue C from a minimal sudoku S results in a puzzle with n solutions, then there is exactly one minimal n-permutable set X where C is the only clue contained in that set. All minimal k-permutable sets in S which do not contain other clues than C are subsets of X.
We need the fact that a *-permutable is minimal iff it has no cell of constant value in its list of valid permutations. Now write down the n solutions to your sudoku sans C and let X be the set of cell positions that are not constant in that list. This is clearly minimal n-permutable and, practically by definition, the union of all minimal *-permutables on C but no other clues.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby Ocean » Tue Feb 28, 2006 10:47 pm

Red Ed wrote:Here's a proof of your conjecture 2. We'll prove the contrapositive, that having k minimal unavoidables makes you m-permutable for some m>k. ...

Great! Thank you for a solid proof of conjecture 2!

Red Ed wrote:Similar reasoning applies when proving your conjecture X:
Ocean wrote::idea: Conjecture X. If removing one clue C from a minimal sudoku S results in a puzzle with n solutions, then there is exactly one minimal n-permutable set X where C is the only clue contained in that set. All minimal k-permutable sets in S which do not contain other clues than C are subsets of X.
We need the fact that a *-permutable is minimal iff it has no cell of constant value in its list of valid permutations. Now write down the n solutions to your sudoku sans C and let X be the set of cell positions that are not constant in that list. This is clearly minimal n-permutable and, practically by definition, the union of all minimal *-permutables on C but no other clues.

... and for conjecture X!
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby sg » Thu Mar 02, 2006 2:03 pm

I posted elsewhere some results of an enumeration in the 2X2 toy model, which you might find interesting since it has some relevance to this thread.
sg
 
Posts: 22
Joined: 14 February 2006

Postby coloin » Tue Mar 07, 2006 9:58 pm

Ok

In a mamimum puzzle [e.g 33 clues]
Every unavoidable set is covered [very easy]
Each clue uniquely /on its own covers one or few unavoidable sets [very difficult]

Conversely in a minimum puzzle [e.g 17 clues]
Every unavoidable set is covered [very difficult]
Each clue uniquely covers many unavoidable sets [easy]

I have just got my program [from dukuso] sorted to print out minimal sudokus :

We have the canonical grid which can be solved with 32 clues.

Code: Select all
+---+---+---+
|123|456|789|
|789|123|456|
|456|789|123|
+---+---+---+
|231|564|897|
|564|897|231|
|897|231|564|
+---+---+---+
|312|645|978|
|645|978|312|
|978|312|645|
+---+---+---+


Dukuso found a 32 with difficult by randomly deleting clues many ways

Here are 25 minimal 32 clue sudoku with 28 common clues.
Code: Select all
123..67..78.12.45.4.......3.3..6489.....9...18..2.....3.2..5...64.97.3.......2.4.
12.4.67..78.12.45.4.......3.3..6489.....9..318..2.....3.2..5...64.97.........2.4.
12.4.67..78.12.45.4.......3.3..6489.....9...18..2.....3.2..5...64.97.3.......2.4.
12.4.67..78.12.45.4.......3....6489.....9..318..2.....3.2..5...64.97.3.......2.4.
12...67..78.12.45.4.......3.3..6489.....9..318..2.....3.2.45...64.97.........2.4.
12...67..78.12.45.4.......3.3..6489.....9...18..2.....3.2.45...64.97.3.......2.4.
12...67..78.12.45.4.......3....6489.....9..318..2.....3.2.45...64.97.3.......2.4.
.23..678.78.12.45.4.......3.3..6489.....9...18..2.....3.2..5...64.97.3.......2.4.
.23..67..78.12.45.4.......3.31.6489.....9...18..2.....3.2..5...64.97.3.......2.4.
.2.4.678.78.12.45.4.......3.3..6489.....9..318..2.....3.2..5...64.97.........2.4.
.2.4.678.78.12.45.4.......3.3..6489.....9...18..2.....3.2..5...64.97.3.......2.4.
.2.4.678.78.12.45.4.......3....6489.....9..318..2.....3.2..5...64.97.3.......2.4.
.2.4.67.978.12.45.4.......3.3..6489.....9..318..2.....3.2..5...64.97.........2.4.
.2.4.67.978.12.45.4.......3....6489.....9..318..2.....3.2..5...64.97.3.......2.4.
.2.4.67..78.12.45.4.......3.3..6489.....9..318..2.....312..5...64.97.........2.4.
.2.4.67..78.12.45.4.......3....6489.....9..318..2.....312..5...64.97.3.......2.4.
.2.4.67..78.12.45.4.......3....6489.....9..318..2.....3.2..59..64.97.3.......2.4.
.2...678.78.12.45.4.......3.3..6489.....9..318..2.....3.2.45...64.97.........2.4.
.2...678.78.12.45.4.......3.3..6489.....9...18..2.....3.2.45...64.97.3.......2.4.
.2...678.78.12.45.4.......3....6489.....9..318..2.....3.2.45...64.97.3.......2.4.
.2...67.978.12.45.4.......3.3..6489.....9..318..2.....3.2.45...64.97.........2.4.
.2...67.978.12.45.4.......3....6489.....9..318..2.....3.2.45...64.97.3.......2.4.
.2...67..78.12.45.4.......3.3..6489.....9..318..2.....312.45...64.97.........2.4.
.2...67..78.12.45.4.......3....6489.....9..318..2.....312.45...64.97.3.......2.4.
.2...67..78.12.45.4.......3....6489.....9..318..2.....3.2.459..64.97.3.......2.4.
There may well be more - depending how far you go back with the search.

In the 33 clue puzzles from Ocean

there are two grids each with 12 minimal 33 sudokus, 29 common clues.

Code: Select all
.2..48.6.4683.1.7....7.....9148.....2861..3.9.........83.6..59..7.......6.928.73.
.2..48.6.4683.1.7....7.....9148.....2861..3.9.........83.6..59..7.......6..28573.
.2..48.6.4683.1.7....7.....9148.....2861..3.9.........8..6..59..7.......64928.73.
.2..48.6.4683.1.7....7.....9148.....2861..3.9.........8..6..59..7.......64.28573.
.2..48.6.4683.1..5...7.....9148..6..2861....9.........83.6..59..7.......6.928.73.
.2..48.6.4683.1..5...7.....9148..6..2861....9.........83.6..59..7.......6..28573.
.2..48.6.4683.1..5...7.....9148..6..2861....9.........8..6..59..7.......64928.73.
.2..48.6.4683.1..5...7.....9148..6..2861....9.........8..6..59..7.......64.28573.
.2..48.6.4683.1..5...7.....9148.....2861..3.9.........83.6..59..7.......6.928.73.
.2..48.6.4683.1..5...7.....9148.....2861..3.9.........83.6..59..7.......6..28573.
.2..48.6.4683.1..5...7.....9148.....2861..3.9.........8..6..59..7.......64928.73.
.2..48.6.4683.1..5...7.....9148.....2861..3.9.........8..6..59..7.......64.28573.

.2..48.6.4683.1.7....7.....9841.....2168..3.9.........83.6..59..7.......6.928.73.
.2..48.6.4683.1.7....7.....9841.....2168..3.9.........83.6..59..7.......6..28573.
.2..48.6.4683.1.7....7.....9841.....2168..3.9.........8..6..59..7.......64928.73.
.2..48.6.4683.1.7....7.....9841.....2168..3.9.........8..6..59..7.......64.28573.
.2..48.6.4683.1..5...7.....9841..6..2168....9.........83.6..59..7.......6.928.73.
.2..48.6.4683.1..5...7.....9841..6..2168....9.........83.6..59..7.......6..28573.
.2..48.6.4683.1..5...7.....9841..6..2168....9.........8..6..59..7.......64928.73.
.2..48.6.4683.1..5...7.....9841..6..2168....9.........8..6..59..7.......64.28573.
.2..48.6.4683.1..5...7.....9841.....2168..3.9.........83.6..59..7.......6.928.73.
.2..48.6.4683.1..5...7.....9841.....2168..3.9.........83.6..59..7.......6..28573.
.2..48.6.4683.1..5...7.....9841.....2168..3.9.........8..6..59..7.......64928.73.
.2..48.6.4683.1..5...7.....9841.....2168..3.9.........8..6..59..7.......64.28573.


I think the problem is similar to the minimum one in that the number of grids with 33 clues probably is rare.....[only 1 in 100,000 [?]grids had a 17]

I am analysing the 152 grid solutions of the 28 clues in the canonical 28/32 and the 724 grid solutions in the 29/33 clues in one of the Oceanmax grids. Initial analysis did not show any similar sized maximums in any of these grids.
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby Ocean » Wed Mar 08, 2006 1:58 am

(deleted)
Last edited by Ocean on Wed Mar 08, 2006 7:30 am, edited 1 time in total.
Ocean
 
Posts: 442
Joined: 29 August 2005

Postby coloin » Wed Mar 08, 2006 3:51 am

coloin wrote:There may well be more - depending how far you go back with the search.
Well....

Taking the bottom 32 in the canonical grid series
Code: Select all
.2...67..78.12.45.4.......3....6489.....9..318..2.....3.2.459..64.97.3.......2.4.
Here are two more 32s:
Code: Select all
1..4.678.78.12.45.4..7....3....6489.....9..318..2.....3.2..5...64.97.........2.4.
12.4.6.8.78.12.45.4.......3.3..6489.....9...18..2.....3.2..5...64.97.3.......2.4

......making me think there should be 33s ....and indeed there are :

Code: Select all
1..4.678.78.12.45.4..7....3....6489.....9..318..2..5..312..5...64.97.........2...
1....678.78.12.45.4..7....3..1.6489.....9..318..2..5..3.2.45...64.97.........2...
1....678.78.12.45.4..7....3....6489.....9..318..2..5..312.45...64.97.........2...
...4.678.78.12.45.4..7....3..1.6489.....9..318..2..5..312..5...64.97.........2...
...4.678.78.12.45.4..7....3..1.6489.....9..318..2.....312..5...64.97.........2.4.
...4.678.78.12.45.4.......3..1.6489.....9..318..2.....312..5.7.64.97.........2.4.
...4.678.78.12.45.4.......3..1.6489.....9..318..2.....312..5...64.97.3.......2.4.
...4.678.78.12.45.4.......3..1.6489.....9..318..2.....3.2..59..64.97.3.......2.4.
.....678.78.12.45.4..7....3..1.6489.....9..318..2..5..312.45...64.97.........2...
.....678.78.12.45.4..7....3..1.6489.....9..318..2..5..3.2..597.64.97.........2...
.....678.78.12.45.4..7....3..1.6489.....9..318..2.....312.45...64.97.........2.4.
.....678.78.12.45.4.......3..1.6489.....9..318..2.....312.45.7.64.97.........2.4.
.....678.78.12.45.4.......3..1.6489.....9..318..2.....312.45...64.97.3.......2.4.
.....678.78.12.45.4.......3..1.6489.....9..318..2.....3.2.459..64.97.3.......2.4.


EDIT
I now have over 117 33 clue minimal sudokus with the canonical grid.
No 34 though.
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby coloin » Mon Mar 13, 2006 1:05 pm

I dont think this "maximum clues >33" problem is an easy one

There are 10^60 ways of putting 33 clues from a valid grid - and not many are going to be without a chance

EDIT
35 clues will have 81!/35!46! = 1.01*10^23


Most will have 8 clue numbers
Most will have less than 3 empty boxes
and most will have no "two rows or two columns" without a clue.

so

I was surprized by the plethora of 33s in the canonical grid...but we have no way of knowing iof this is the best region in the grid - it is rumoured to have 18-fold symmetry !

Here are the grids

Code: Select all
33s
1..4.678978.12.45.4.......3.....489.....97.318..2.....312..5...64.9..3.......2.4.
1..4.678978.12.45.4.......3.....489.....97.318..2......12..59..64.9..3.......2.4.
1..4.678.78.12.45.4..7....3.3...489.....9..318..2..5..312..5...64.97.........2...
1..4.678.78.12.45.4..7....3.3...489.....9..318..2..5..312..5...64..7.3.......2...
1..4.678.78.12.45.4..7....3.3...489.....9..318..2..5..3.2..5.7.64.97.........2...
1..4.678.78.12.45.4..7....3.3...489.....9..318..2..5..3.2..5.7.64..7.3.......2...
1..4.678.78.12.45.4..7....3..1..489.....9..318..2.....3.2..5..864..7.3.......2.4.
1..4.678.78.12.45.4..7....3....6489.....9..318..2..5..312..5...64.97.........2...
1..4.678.78.12.45.4..7....3....6489.....9..318..2..5..312..5...64..7.3.......2...
1..4.678.78.12.45.4..7....3.....489.....9..318..2..5..3.2..5.7864.97.........2...
1..4.678.78.12.45.4..7....3.....489.....9..318..2..5..3.2..5.7864..7.3.......2...
1..4.678.78.12.45.4..7....3.....489.....9..318..2.....3.2..5.7864..7.3.......2.4.
1..4.678.78.12.45.4.....1.3.....489.....9..318..2..5..3.2..5.7864.97.........2...
1..4.678.78.12.45.4.....1.3.....489.....9..318..2..5....2..597864.97.........2...
1....678978.12.45.4.......3.....489.....97.318..2.....312.45...64.9..3.......2.4.
1....678978.12.45.4.......3.....489.....97.318..2......12.459..64.9..3.......2.4.
1....678.78.12.45.4..7....3..1.6489.....9..318..2..5..3.2.45...64.97.........2...
1....678.78.12.45.4..7....3..1.6489.....9..318..2..5..3.2.45...64..7.3.......2...
1....678.78.12.45.4..7....3..1..489.....9..318..2..5..3.2.45..864.97.........2...
1....678.78.12.45.4..7....3..1..489.....9..318..2..5..3.2.45..864..7.3.......2...
1....678.78.12.45.4..7....3..1..489.....9..318..2.....3.2.45..864..7.3.......2.4.
1....678.78.12.45.4..7....3....6489.....9..318..2..5..312.45...64.97.........2...
1....678.78.12.45.4..7....3....6489.....9..318..2..5..312.45...64..7.3.......2...
1....678.78.12.45.4..7....3.....489.....9..318..2..5..3.2.45.7864.97.........2...
1....678.78.12.45.4..7....3.....489.....9..318..2..5..3.2.45.7864..7.3.......2...
1....678.78.12.45.4..7....3.....489.....9..318..2.....3.2.45.7864..7.3.......2.4.
..34.678.78.12.45.45.7....3.....489.....9.231...2..5..3.2..5...64..7.3...7...2...
..34.678.78.12.45.45.7....3.....489.....9..31...2..5..312..5.7.64....3...7...2...
..34.678.78.12.45.45.7....3.....489.....9..31...2..5..312..5...64..7.3...7...2...
..34.678.78.12.45.45......3.....489.....97231...2..5..3.2..5...64..7.3...7...2...
..34.678.78.12.45.4..7....3.3...489.....9..318..2..5..312..5...64..7.3.......2...
..34.678.78.12.45.4..7....3.3...489.....9..318..2..5..3.2..5.7.64..7.3.......2...
..34.678.78.12.45.4..7....3....6489.....9..318..2..5..3.2..597.64..7.........2...
..34.678.78.12.45.4.......3.3...489.....97.31...2.....3.2..5.7.64..7.3...7...2.4.
..3..678.78.12.45.4.......3.3...489.....97.31...2.....3.2.45.7.64..7.3...7...2.4.
...4.678.78.12.45.4..7....3..1.6489.....9..318..2..5..312..5...64.97.........2...
...4.678.78.12.45.4..7....3..1.6489.....9..318..2..5..312..5...64..7.3.......2...
...4.678.78.12.45.4..7....3..1.6489.....9..318..2..5..3.2..597.64..7.........2...
...4.678.78.12.45.4..7....3..1.6489.....9..318..2.....312..5...64.97.........2.4.
...4.678.78.12.45.4..7....3..1.6489.....9..318..2.....312..5...64..7.3.......2.4.
...4.678.78.12.45.4.......3..1.6489.....9..318..2.....312..5.7.64.97.........2.4.
...4.678.78.12.45.4.......3..1.6489.....9..318..2.....312..5...64.97.3.......2.4.
...4.678.78.12.45.4.......3..1.6489.....9..318..2.....3.2..59..64.97.3.......2.4.
...4.678.78.12.45.4.......3..1.6489.....9..318..2......12..59..64.97.3.......2.4.
.....678.78.12.45.4..7....3..1.6489.....9..318..2..5..312.45...64.97.........2...
.....678.78.12.45.4..7....3..1.6489.....9..318..2..5..312.45...64..7.3.......2...
.....678.78.12.45.4..7....3..1.6489.....9..318..2..5..3.2..597.64.97.........2...
.....678.78.12.45.4..7....3..1.6489.....9..318..2.....312.45...64.97.........2.4.
.....678.78.12.45.4..7....3..1.6489.....9..318..2.....312.45...64..7.3.......2.4.
.....678.78.12.45.4.......3..1.6489.....9..318..2.....312.45.7.64.97.........2.4.
.....678.78.12.45.4.......3..1.6489.....9..318..2.....312.45...64.97.3.......2.4.
.....678.78.12.45.4.......3..1.6489.....9..318..2.....3.2.459..64.97.3.......2.4.
.....678.78.12.45.4.......3..1.6489.....9..318..2......12.459..64.97.3.......2.4.

......X..........................................................................
1..4.6.8.78.12.45.4..7....3.3..6489.....9..318..2..5..312..5...64..7.3.......2...
..34.6.8.78.12.45.45.7....3.....489.....9.231...2..5..312..5...64..7.3...7...2...
..34.6.8.78.12.45.4.......3.3...489.....97231...2.....3.2..5.7.64..7.3...7...2.4.
..34.6.8.78.12.45.4.......3.3...489.....97231...2.....3.2..5..864..7.3...7...2.4.
..3..6.8.78.12.45.4.......3.3...489.....97231...2.....3.2.45.7.64..7.3...7...2.4.
..3..6.8.78.12.45.4.......3.3...489.....97231...2.....3.2.45..864..7.3...7...2.4.

.............X....................................................................
..34.678.78.1.345.4..7....3....6489.....9..318..2..5..3.2..597.64..7.........2...
...4.678.78.1.345.4..7....3..1.6489.....9..318..2..5..3.2..597.64..7.........2...

.................................X................................................
..34.678.78.12.45.45.7....3.....4.9.....9.231...2..5..312..5...64..7.3...7...2...
..34.678.78.12.45.45......3.....4.9.....97231...2..5..312..5...64..7.3...7...2...
..34.678.78.12.45.4..7....3.31..4.9.....9.231...2..5..3.2..5...64..7.3...7...2...

..................................X...............................................
1.34.678.78.12.45.4..7..1.3.3...48......9..318..2.....3.2..5...64..7.3.......2.4.
1.3..678.78.12.45.4..7..1.3.3...48......9..318..2.....3.2.45...64..7.3.......2.4.
1..4.678.78.12.45.4..7....3.3...48......9..318..2.....3.2..5.7864..7.3.......2.4.
1....678.78.12.45.4..7....3.3..648......9..318..2..5..312.45...64..7.3.......2...
1....678.78.12.45.4..7....3.3...48......9..318..2.....3.2.45.7864..7.3.......2.4.
..34.678.78.12.45.4..7....3.31..48......9..318..2..5..312..5...64..7.3.......2...
...4.678.78.12.45.4..7....3..1.648......9..318..2..5..312..5.7.64.97.........2...
...4.678.78.12.45.4..7....3..1.648......9..318..2..5..312..5.7.64..7.3.......2...
...4.678.78.12.45.4..7....3..1.648......9..318..2..5..3.2..597.64.97.........2...
...4.678.78.12.45.4..7....3..1.648......9..318..2.....312..5.7.64.97.........2.4.
...4.678.78.12.45.4..7....3..1.648......9..318..2.....312..5.7.64..7.3.......2.4.
...4.678.78.12.45.4.......3..1.648......9..318..2.....312..5.7.64.97.3.......2.4.
.....678.78.12.45.4..7....3..1.648......9..318..2..5..312.45.7.64.97.........2...
.....678.78.12.45.4..7....3..1.648......9..318..2..5..312.45.7.64..7.3.......2...
.....678.78.12.45.4..7....3..1.648......9..318..2..5..3.2.4597.64.97.........2...
.....678.78.12.45.4..7....3..1.648......9..318..2.....312.45.7.64.97.........2.4.
.....678.78.12.45.4..7....3..1.648......9..318..2.....312.45.7.64..7.3.......2.4.
.....678.78.12.45.4.......3..1.648......9..318..2.....312.45.7.64.97.3.......2.4.

...........................................X.....................................
1....678.78.12.45.4..7..1.3..1.6489.....9...18..2..5..3.2.45...64.97.........2...
..34.678.78.12.45.4..7..1.3....6489.....9...18..2..5..3.2..597.64..7.........2...
..3..678.78.12.45.4..7..1.3....6489.....9...18..2..5..3.2.4597.64..7.........2...
..3..678.78.12.45.4..7..1.3....6489.....9...18..2..5..3.2..597864..7.........2...
...4.678.78.12.45.4..7..1.3..1.6489.....9...18..2..5..3.2..597.64..7.........2...
.....678.78.12.45.4..7..1.3..1.6489.....9...18..2..5..3.2.4597.64..7.........2...

................................................X................................
1..4.678.78.12.45.4..7..1.3.....489.....9..318.....5..3.2..5.7864.97.........2...
1..4.678.78.12.45.4..7..1.3.....489.....9..318.....5..3.2..5.7864..7.3.......2...
1..4.678.78.12.45.4..7....3..1..489.....9..318.....5..3.2..5..864..7.3.......2.4.
1..4.678.78.12.45.4..7....3.....489.....9..318.....5..3.2..5.7864..7.3.......2.4.
1..4.678.78.12.45.4.....1.3.....489.....9..318.....5..3.2..5.7864.97.3.......2...
1....678.78.12.45.4..7....3..1..489.....9..318.....5..3.2.45..864..7.3.......2.4.
1....678.78.12.45.4..7....3.....489.....9..318.....5..3.2.45.7864..7.3.......2.4.
...4.678.78.12.45.4..7....3..1.6489.....9..318.....5..312..5...64..7.3.......2.4.
.....678.78.12.45.4..7....3..1.6489.....9..318.....5..312.45...64..7.3.......2.4.

......................................................X..........................
1..4.678.78.12.45.4.....1.3.....489.....9..318..2..5....2..597864.97.........2...
...4.678.78.12.45.4.......3..1.6489.....9..318..2......12..59..64.97.3.......2.4.
.....678.78.12.45.4.......3..1.6489.....9..318..2......12.459..64.97.3.......2.4.

........................................................X........................
1..4.678.78.12.45.4..7....3.3...489.....9..318..2..5..3....5.7864..7.3.......2...
1..4.678.78.12.45.4..7....3..1.6489.....9..318..2.....3....5..864..7.3.......2.4.
1..4.678.78.12.45.4..7....3..1..489.....9..318..2..5..3....5.7864.97.........2...
1..4.678.78.12.45.4..7....3..1..489.....9..318..2..5..3....5.7864..7.3.......2...
1..4.678.78.12.45.4..7....3..1..489.....9..318..2.....3....5.7864..7.3.......2.4.
1....678.78.12.45.4..7....3.3...489.....9..318..2..5..3...45.7864..7.3.......2...
1....678.78.12.45.4..7....3..1.6489.....9..318..2..5..3....5.7864.97.........2...
1....678.78.12.45.4..7....3..1.6489.....9..318..2..5..3....5.7864..7.3.......2...
1....678.78.12.45.4..7....3..1.6489.....9..318..2.....3...45..864..7.3.......2.4.
1....678.78.12.45.4..7....3..1.6489.....9..318..2.....3....5.7864..7.3.......2.4.
1....678.78.12.45.4..7....3..1..489.....9..318..2..5..3...45.7864.97.........2...
1....678.78.12.45.4..7....3..1..489.....9..318..2..5..3...45.7864..7.3.......2...
1....678.78.12.45.4..7....3..1..489.....9..318..2.....3...45.7864..7.3.......2.4.

...............................................................X.................
..34.678.78.12.45.45.7....3.....489.....9..318..2..5..312..59...4..7.3.......2...

...................................................................X.............
1..4.678978.12.45.4.......3.....489.....97.318..2.....312..5...64.9..3.......2.4.
1....678978.12.45.4.......3.....489.....97.318..2.....312.45...64.9..3.......2.4.
..34.678.78.12.45.45.7....3.....489.....9..31...2..5..312..5.7.64....3...7...2...



The 15 Clues in all the 33s are
Code: Select all
+---+---+---+
|...|..6|.8.|
|78.|1..|45.|
|4..|...|..3|
+---+---+---+
|...|..4|...|
|...|.9.|..1|
|...|...|...|
+---+---+---+
|...|..5|...|
|.4.|...|...|
|...|..2|...|
+---+---+---+


What I would like to do is analyse which of these 33s has the most pseudopuzzles...ie has the most clues which give 2 grid solutions.

If a 34 exists - does it have all clues this way ?
Last edited by coloin on Tue May 09, 2006 10:49 am, edited 1 time in total.
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby sg » Mon Mar 13, 2006 1:13 pm

coloin wrote:I dont think this "maximum clues >33" problem is an easy one

There are 10^60 ways of putting 33 clues from a valid grid - and not many are going to be without a chance
Most will have 8 clue numbers
Most will have less than 3 empty boxes
and most will have no "two rows or two columns" without a clue.


That's a lot of work Coloin!

The point that you make about there being too many possibilities to enumerate is valid. Elsewhere I wrote about the notion of skeletons. This is a tool that I've used to simplify enumeration. It could help with the kind of work that you are doing.
sg
 
Posts: 22
Joined: 14 February 2006

Postby coloin » Mon Mar 13, 2006 1:20 pm

Code: Select all
..34.678.78.12.45.45.7....3.....489.....9..318..2..5..312..59...4..7.3.......2...

This 33 has grid solutions for each clue
Code: Select all
2 sol.2 sol.2 sol.5 sol.2 sol.2 sol.2 sol.2 sol.18 sol.2 sol.2 sol.16 sol.7 sol.2 sol.19 sol.4 sol.2 sol.8 sol.15 sol.7 sol.29 sol.2 sol.2 sol.3 sol.2 sol.2 sol.7 sol.2 sol.2 sol.2 sol.2 sol.2 sol.2 sol.
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby Red Ed » Mon Mar 13, 2006 10:34 pm

Of your 117 above, 111 are non-isomorphic.

The solution grid is fixed by a group of 648 different cell permutations (plus relabelling). None of these cell perms (with relabelling) fixes any of your minimal grids; so you could easily extend your list of 117 to 648*111 = 71928 distinct minimal puzzles!

For example, here's the lexicographically smallest of the ones you missed by not using symmetries:
Code: Select all
...........9.2.4..4...89123.3...4.9.5.4.9.2.1.97..15.4..26.5..86.....31..7..126..

Were you deliberately trying to avoid creating isomorphic puzzles?
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby coloin » Tue Mar 14, 2006 2:29 am

sg - Ihave followed your post and looked at your website on all the different puzzle combinations for the 2X2........I would be amazed if this can be extended to the 3X3.....I cant give even a sensible estimate as to the number of minimal puzzles with 24 clues.

The large number of combinations of 33/34 clues makes me think that a 34 is possible.

Red Ed - The "evil" [most] canonical grid that I have used here would be the logical grid to look for a large maximum - It had the highest value for random minimal generation - was thought to be one of the worst grids to have a small minimum [it turned out to have many 19s] - although as you know Mosch has shown several grids which only have a 20.

Since dukuso found a 32 it seemed a good choice - it did surprize me with the 33s. I am glad that you have come in to confirm the symetrical isomorphs in this grid - I had remembered that it had "18 fold " symmetry when dukoso analysed it for the lack of 18s.

dukuso wrote:123456789
456789123
789123456
231564897
564897231
897231564
312645978
645978312
978312645

uses gangsters 1,1,1 - 1,1,1 so I think it's the most canonical.
It could also be the one requiring the most clues, since gangster1 stands for 1728 bands, the most of all gangsters.

So now I tested whether there is a 18-clues sudoku whith that grid as unique solution.
18 clues are required at least, as we have seen before and these must be arranged such that 2 clues solve each of the 18 3*3 latin subsquares.
This gives only 1296 possible configurations of the 18 clues and none of them give a sudoku with unique solution.
We have :
18 configurations with 413108 solutions
108 configurations with 141917 solutions
36 configurations with 47479 solutions
18 configurations with 44148 solutions
162 configurations with 41224 solutions
162 configurations with 22245 solutions
18 configurations with 16740 solutions
324 configurations with 15156 solutions
162 configurations with 9258 solutions
108 configurations with 4914 solutions
162 configurations with 411 solutions
18 configurations with 96 solutions

it seems that we have 18-fold symmetry here.

With 19 clues however there are uniquely solvable sudokus over this grid.
Code: Select all
.........
..6.8.1..
7....3.52
..1.6.8..
.....7.3.
...2.....
3....5.7.
.4.......
..8...6..


648 = ? 18*6*6 ....[could you explain these?] It was quoted to have have many 19s - might this be 648 isomorphic 19s ?

RedEd wrote:Were you deliberately trying to avoid creating isomorphic puzzles?

Not knowingly....Are you saying that there should be more isomorphs in my list of 117 ? ......I cant explain that. My methods dont distinguish between isomorphs.

C
coloin
 
Posts: 1638
Joined: 05 May 2005

PreviousNext

Return to General