Fully symmetrical puzzles

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

Postby JPF » Thu Sep 27, 2007 10:20 pm

I was actually waiting for a reaction.

A subgrid with n solutions is minimal if removing one clue gives a subgrid with m solutions and m>n.

Just a generalization of the minimality of a valid puzzle (n=1 solution).

This puzzle (3 solutions) is not minimal,
Code: Select all
 1 . . | . . . | . . 2
 . 3 . | 1 . 4 | . 5 .
 . . . | . . . | . . .
-------+-------+-------
 . 5 . | 6 . 3 | . 4 .
 . . . | . 5  .|  . . .
 . 6 . | 4 . 7 | . 3 .
-------+-------+-------
 . . . | . . . | . . .
 . 4 . | 3 . 5 | . 6 .
 8 . . | . . . | . . 9


You can remove r5c5

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby TTHsieh » Fri Sep 28, 2007 4:29 am

    a, b, c, d, e, f, g, h, i, j, k, l must keep blank or you can't get any minimal puzzle.
    because any of them will lead box 5 can have another hidden single.
Code: Select all
 x . . | . a . | . . x
 . x . | x b x | . x .
 . . . | . c . | . . .
 - - - + - - - + - - -
 . x . | x x x | . x .
 d e f | x . x | g h i
 . x . | x x x | . x .
 - - - + - - - + - - -
 . . . | . j . | . . .
 . x . | x k x | . x .
 x . . | . l . | . . x


    so this pattern has no minimal puzzle.
Code: Select all
 x . . | . . . | . . x
 . x . | x x x | . x .
 . . . | . . . | . . .
 - - - + - - - + - - -
 . x . | x x x | . x .
 . x . | x . x | . x .
 . x . | x x x | . x .
 - - - + - - - + - - -
 . . . | . . . | . . .
 . x . | x x x | . x .
 x . . | . . . | . . x


TTHsieh
TTHsieh
 
Posts: 1390
Joined: 13 July 2007

Postby coloin » Fri Sep 28, 2007 7:24 am

JPF wrote:I was actually waiting for a reaction.
A subgrid with n solutions.....................
This puzzle (3 solutions) is not minimal,

I agree.....except for the use of the "subgrid" term.

A puzzle with 2 solutions has been termed a pseudopuzzle, and these incomplete puzzles are better termed subpuzzles [2 or more grid solutions]. It acknowledges that the puzzle is incomplete.

A grid IMO is the full grid solution with 81 clues and a subgrid therefore has less than this....but it is not a helpful term.

Puzzles have one solution and can be minimal or non-minimal. [maximal when solved !]
Subpuzzles can be minimal, non-minimal or maximal.
The classic example of a minimal pseudopuzzle is gordons 16 clue pseudopuzzle with 2 solutions. [from the SF grid] When expanded maximally to 63 clues [still 2 solutions] it leaves the 18 clues of the unavoidable set.

The 8 clues in a box has been discussed before......but I cant find it !

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby JPF » Fri Sep 28, 2007 10:56 am

About semantic...:(

Subgrid is the word used by Red Ed to refer to a subset of a full sudoku grid.
A subgrid has therefore at least one solution...
In my post, I used subgrid instead of puzzle for that reason.

coloin wrote:A puzzle with 2 solutions has been termed a pseudopuzzle,
I know that "pseudopuzzle" has been used in a thread for subgrids with 2 solutions .
Do we need to use a different word for 3 solutions, an other for 4 solutions, etc..

coloin wrote:and these incomplete puzzles are better termed subpuzzles [2 or more grid solutions]. It acknowledges that the puzzle is incomplete.
I don't understand why.

coloin wrote:A grid IMO is the full grid solution with 81 clues
right
coloin wrote:and a subgrid therefore has less than this....but it is not a helpful term.
why ?

coloin wrote:Puzzles have one solution and can be minimal or non-minimal. [maximal when solved !]
Subpuzzles can be minimal, non-minimal or maximal.
so what ?

Anyway, let's avoid this Eureka's type of discussion.

The key point of my post was that the concept of minimality is not specific to valid puzzles.

JPF
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby coloin » Fri Sep 28, 2007 3:48 pm

Ok....paternalism and semantics aside......:(

I think your use of the word "puzzle" to prompt a reaction was confusing and inaccurate.

The use of the word "subpuzzle" to describe a combination of clues which dont quite make a complete solvable puzzle makes for clarity.

The use of a word "subgrid" to describe a combination of clues which may be 16 clues or 77 clues and does not distinquish if it is a not a valid puzzle is inferior.

The point of my post was also to highlight the concept of maximality in subgrids with more than 1 grid solution.....sorry - subpuzzles.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby Red Ed » Fri Sep 28, 2007 6:18 pm

I spent a few weeks on the Eureka board a while back and so I am now incapable of simply walking away from tedious arguments such as this.

Still, FWIW ...

I never formally defined "subgrid", but it appears that I have consistently used it to mean a grid (i.e. full valid solution grid) with some (>0) values blanked out. This term is perhaps most meaningful in estimating the total number of sudoku puzzles: then the algorithm is: repeat { pick a random grid; from that, pick a random subgrid; check if the subgrid has a unique solution }. A subgrid always has 1 or more solutions.

By extension, "subpuzzle" seems a reasonable term for a puzzle that has had some (>0) values blanked out. A subpuzzle may have 1 solution or 2+ solutions. A minimal puzzle is one that has no proper/valid/uniquely-solvable (pick your favourite jargon) subpuzzles.

So there.

I hereby award JPF 6.67e21 points for popularising a term that I used way back when. Meanwhile, I sentence coloin to a beating by the dreaded Gang of 44. Ha!:)
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby ravel » Fri Sep 28, 2007 6:54 pm

TTHsieh wrote:
    a, b, c, d, e, f, g, h, i, j, k, l must keep blank or you can't get any minimal puzzle.
    because any of them will lead box 5 can have another hidden single.
Code: Select all
 x . . | . a . | . . x
 . x . | x b x | . x .
 . . . | . c . | . . .
 - - - + - - - + - - -
 . x . | x x x | . x .
 d e f | x . x | g h i
 . x . | x x x | . x .
 - - - + - - - + - - -
 . . . | . j . | . . .
 . x . | x k x | . x .
 x . . | . l . | . . x


    so this pattern has no minimal puzzle.
Code: Select all
 x . . | . . . | . . x
 . x . | x x x | . x .
 . . . | . . . | . . .
 - - - + - - - + - - -
 . x . | x x x | . x .
 . x . | x . x | . x .
 . x . | x x x | . x .
 - - - + - - - + - - -
 . . . | . . . | . . .
 . x . | x x x | . x .
 x . . | . . . | . . x


TTHsieh
I did not understand. Please, TTHsieh or someone else, could you reformulate the argumentation ?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby coloin » Fri Sep 28, 2007 7:37 pm

Thanks Ref....it is terminology and I dont think JPF or myself are as serious as your "friends" in Eureka !

Although beat me with another stick if you will but if a subpuzzle has 1 solution.....that makes it a puzzle [minimal or non-minimal]

Regarding the 8 clues in a box, I think myself and JPF looked at this before, I recall surprize at finding this feature in a minimal puzzle , subsequently and quickly a puzzle with 2 boxes with this feature was found....and I think a puzzle with 3 boxes with this feature was found.....I cant find it though.

TTHsieh is saying is that,in his pattern, to have a minimal puzzle with 8 clues in a box there cant be clues in the [a,b,c,d,e,f,g,h,i,j,k,l] positions.

For there to be 8 clues in a box each one has to have an uniquely associated unavoidable set.

With the other clues in the pattern the use if the [a-l] clues maybe prevents this.......if there isnt a minimal puzzle with that pattern then this looks likely.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby TTHsieh » Fri Sep 28, 2007 7:44 pm

Code: Select all
 x . . | . . . | . . x
 . x . | x a x | . x .
 . . . | . . . | . . .
 - - - + - - - + - - -
 . x . | 1 2 3 | . x .
 . . . | 4 . 6 | . . .
 . x . | 7 8 9 | . x .
 - - - + - - - + - - -
 . . . | . . . | . . .
 . x . | x . x | . x .
 x . . | . . . | . . x

    a <> 2, 5, 8
    a = 1, 4, 7, 3, 6, 9

    if a = 1 then you can remove 1 from box 5
    if a = 4 then you can remove 4 from box 5
    ...
Mauricio wrote:The best I could do is this minimal 27:
Code: Select all
+-------+-------+-------+
| 1 . . | . . . | . . 2 |
| . 2 . | 1 3 4 | . 5 . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . 1 . | . 2 6 | . 7 . |
| . 4 . | 5 . 1 | . 3 . |
| . 5 . | 4 8 7 | . 6 . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . 3 . | 7 6 2 | . 1 . |
| 7 . . | . . . | . . 4 |
+-------+-------+-------+

All minimal puzzles that I found with 27 clues, have the same pattern, and I was not looking for that.

TTHsieh
TTHsieh
 
Posts: 1390
Joined: 13 July 2007

Postby coloin » Fri Sep 28, 2007 8:01 pm

Yep this is correct........and well shown.

I still cant find the puzzles we found before with 8-clues-in-a-box.

C
coloin
 
Posts: 1637
Joined: 05 May 2005

Postby ravel » Fri Sep 28, 2007 8:24 pm

Ah, thanks,

so each clue in a-l makes one in the center box redundant. This gives a big class of patterns, that cannot have minmals.
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Red Ed » Fri Sep 28, 2007 8:35 pm

coloin wrote:Although beat me with another stick if you will but if a subpuzzle has 1 solution.....that makes it a puzzle [minimal or non-minimal]
Yeah, it does. Like a subset still being a set (sort of). So what? Where's that stick?
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby RW » Fri Sep 28, 2007 8:45 pm

coloin wrote:I still cant find the puzzles we found before with 8-clues-in-a-box.

Here.

RW
RW
2010 Supporter
 
Posts: 1000
Joined: 16 March 2006

Postby ravel » Fri Sep 28, 2007 8:50 pm

When i eat a peace of an apple, there remains a subapple, and an apple is a subapple too. But i should not call this uncomplete apple an apple. Is this correct ?
ravel
 
Posts: 998
Joined: 21 February 2006

Postby Red Ed » Fri Sep 28, 2007 9:08 pm

No, no, no! Aren't you paying attention? Pears, not apples. Do try to keep up.
Red Ed
 
Posts: 633
Joined: 06 June 2005

PreviousNext

Return to General