new challenges

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

new challenges

Postby ab » Sun Oct 24, 2010 7:41 pm

Well two old challenges and one new one. The old one is to find the puzzle with the least clues such that each clue is redundant. ie you can remove each clue and still have a valid puzzle.

The new challenge is to find a valid puzzle such that you can change every clue and still have a valid puzzle. ie if the puzzle had 25 clues then there are 25 valid puzzles which differ from the original puzzle by one clue and each one differs by a different clue. This might not be possible. Then the challenge is to find a puzzle for which you can alter the most clues and still have a valid puzzle.

Also I think we had a similar challenge before. To find a puzzle for which one clue can take on the most values. I think there was one that could take on six values.
ab
 
Posts: 451
Joined: 06 September 2005

Re: new challenges

Postby AR4793 » Mon Oct 25, 2010 4:43 am

ab wrote:Also I think we had a similar challenge before. To find a puzzle for which one clue can take on the most values. I think there was one that could take on six values.


Not sure if you're referring to exactly the same thing, but there was a thread which searched for "mega-clues." You start with a valid minimal puzzle and take away one clue. What is the maximum multiplicity that you can obtain? The pertinent post is below. Removing the clue created 11,339,281 solutions. That is a bit more than 6!
http://www.setbb.com/phpbb/viewtopic.ph ... udoku#9393

Regards,
Herb
AR4793
 
Posts: 13
Joined: 26 September 2010

Re: new challenges

Postby RW » Mon Oct 25, 2010 4:57 am

ab wrote:Also I think we had a similar challenge before. To find a puzzle for which one clue can take on the most values. I think there was one that could take on six values.

Mauricio found some 9-mutable clues.

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

Re: new challenges

Postby m_b_metcalf » Mon Oct 25, 2010 8:26 am

ab wrote: The old one is to find the puzzle with the least clues such that each clue is redundant. ie you can remove each clue and still have a valid puzzle.

If this is an old challenge, what was the old result? A quick run gave:
Code: Select all
 . . . . 4 3 . . .
 . . . 6 . . 8 . .
 . . 5 . 1 7 . 6 9
 6 . . . 5 . . . 8
 . . 3 . 6 9 . 1 7
 7 . 9 . . 8 . . .
 . . 8 2 . . . . 5
 . . 4 1 3 . 6 8 .
 2 . . . . . 4 . .

No. of givens =  30, all redundant

Regards,

Mike Metcalf
Last edited by m_b_metcalf on Mon Oct 25, 2010 8:47 am, edited 5 times in total.
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Re: new challenges

Postby RW » Mon Oct 25, 2010 8:29 am

ab wrote:The new challenge is to find a valid puzzle such that you can change every clue and still have a valid puzzle. ie if the puzzle had 25 clues then there are 25 valid puzzles which differ from the original puzzle by one clue and each one differs by a different clue. This might not be possible.

This is an old challenge that has been explored in the same thread that I mentioned above. I think the largest chameleon found was 24 clues by coloin.

[Edit: Correction, JPF found some 34-clue chameleons already on the first page of that thread. Most likely you can find larger in the current collections of high clue minimal puzzles. Mauricio found some 20-clue chameleons which I believe are the smallest.]

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

Re: new challenges

Postby gsf » Mon Oct 25, 2010 12:55 pm

ab wrote:Well two old challenges and one new one. The old one is to find the puzzle with the least clues such that each clue is redundant. ie you can remove each clue and still have a valid puzzle.

here's a 27 clue maximally superfluous puzzle
Code: Select all
. . .  4 . .  7 8 .
. . 6  . . 9  . 2 .
. . .  . 3 1  5 . 4

2 . 4  . . .  . 1 .
. . .  . . 3  . . 6
9 . .  8 . .  . . .

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

it's solution grid might look familiar
the current search is sort of dumb
I'll rework it if 27 gets bested
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: new challenges

Postby m_b_metcalf » Mon Oct 25, 2010 4:55 pm

Another 27, with a random grid:

Code: Select all
 1 . . . 2 . 3 4 .
 5 . . . 6 . . . 2
 . . 7 . . 3 . . .
 . 2 4 . 7 . . 8 .
 7 . . 2 . 6 . . .
 . . . . 4 1 . . .
 . 9 . 4 . . . 6 .
 . 3 . 5 . . 9 1 .
 . . . . 1 . 2 . .
No. of givens =  27

Regards,

Mike Metcalf
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Re: new challenges

Postby coloin » Mon Oct 25, 2010 5:47 pm

Yes..... they certainly were challenges - and remain so.

The minimal redundant puzzles thread - shows we didnyt try too hard - then [29].
There is a requirement for each unavoidable set to have at least 2 clues in the givens.

The first chameleon was found in a 34 clue puzzle ....... we thought that high clues would favour this - until that is 25,24 and 23 chameleons are plentiful in the MC grid [still not sure why - is it because it is diverse from most other grids ?] There is a 22 clue chameleon in the mcgrid - no 21 however.....

Here is an untouchable 21
Code: Select all
+---+---+---+
|...|...|...|
|12.|3..|8..|
|34.|12.|...|
+---+---+---+
|...|.6.|..7|
|..9|..7|..8|
|6..|...|5..|
+---+---+---+
|..5|..3|..4|
|.1.|...|...|
|...|8..|.9.|
+---+---+---+ [no clue is mutable - no puzzles within {-1+1]


The search for a 9-mutable - wasnt thought possible - untill mauricio stepped in.

The megaclue thread was a belter. The megaclue was found in a 17 puzzle - no one has dared to search through all the 1e9 18-puzzles for a bigger one.

Having said that - given a puzzle with 25 clues JPF found a megaclue - can you do better ?
Code: Select all
 *-----------*
 |.3.|...|...|
 |...|..3|.4.|
 |.24|..5|37.|
 |---+---+---|
 |...|..2|7..|
 |.18|..7|.6.|
 |...|1.6|.5.|
 |---+---+---|
 |.6.|..1|4.7|
 |.8.|...|.3.|
 |1..|9..|...|
 *-----------*  omitting the 9 @r9c4 gives 138142 grid solutions


And lastly - no one has risen to the present challenge of finding 9plus12s

C
coloin
 
Posts: 1632
Joined: 05 May 2005

Re: new challenges

Postby m_b_metcalf » Tue Oct 26, 2010 5:59 am

coloin wrote:Yes..... they certainly were challenges - and remain so.

The minimal redundant puzzles thread - shows we didn't try too hard - then [29].
There is a requirement for each unavoidable set to have at least 2 clues in the givens.

Using the grid you publish there, I found two more 27s (here renumbered):

Code: Select all
 . . . . . . . 1 2
 3 4 . . 5 . . . 6
 7 . . . . . 8 . .
 . 9 5 1 4 . . 2 .
 . . . . . 8 . . .
 . . 3 . . . 1 5 .
 . . 8 2 7 . . . 4
 . 7 . . . . . . .
 1 . . 4 . 9 6 3 .   

 . 1 . . . . 2 3 .
 . 4 . . 5 6 . . .
 . . 7 8 . . 1 . .
 1 . . . 4 . 9 . 2
 6 3 . . 2 . 4 . .
 . . . 7 . . . . .
 8 2 1 . 9 . . 7 .
 . . . . . . 6 1 3
 . 5 . . . . . . .   Both 27 clues, all redundant

Regards,

Mike Metcalf

[Edit: With a longer run, I've found another dozen 27s in your grid, but no 26.]
User avatar
m_b_metcalf
2017 Supporter
 
Posts: 8290
Joined: 15 May 2006
Location: Berlin

Re: new challenges

Postby gsf » Tue Oct 26, 2010 1:50 pm

here's a 26 clue minimal superfluous/redundant
alternate (non-random) search attempt was a bust
Code: Select all
. 2 .  . . .  7 . .
4 . 6  . 8 9  . . .
. 9 .  . 3 .  5 . .

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

3 . .  1 . .  . . .
5 . .  . . 7  6 . .
. 4 .  . 2 .  . 9 .
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Re: new challenges

Postby Red Ed » Sat Oct 30, 2010 5:52 pm

WIBNI there existed an "Open problems" page on Sudopedia? For each open problem (like the ones here), you describe it briefly, link to the best results so far, and give the status. Status would reflect the amount of effort thrown at the problem so far.

The tricky bit would be structuring the page to make the important questions most prominent, and to group similar problems together.

Any volunteers? (expecting deathly silence, including from me)
Red Ed
 
Posts: 633
Joined: 06 June 2005


Return to General