SudokuP: Max Clues for Puzzle

For fans of Killer Sudoku, Samurai Sudoku and other variants

SudokuP: Max Clues for Puzzle

Postby Mathimagics » Tue Jul 24, 2018 1:35 pm

.
Prompted by coloin, I have (among other things) been looking at the "Max Clue Count" problem for SudokuP.

We are of course, referring to clue counts for minimal puzzles, ie: puzzles in which the removal of any single clue results in multiple solutions.

After looking at dobrichev's & blue's (et al) posts on the equivalent problem in regular Sudoku, I looked at various grids that were most likely to have high-clue puzzles, and quickly found exemplars for 30-clues, then 31 etc until it began to get quite hard to go beyond 33 clues.

I then focused on the MC grid (Grid #866802 in the CF catalog) as being the "most likely candidate" of all, and pretty quickly found this 36-clue set:

Code: Select all
  +-------+-------+-------+
  | . . . | . . . | . . . |
  | 4 5 6 | . . . | . . . |
  | 7 8 9 | . . . | 4 5 6 |
  +-------+-------+-------+
  | . 3 . | . 6 . | . 9 . |
  | 5 . 4 | . 9 . | . 3 . |
  | 8 . 7 | . 3 . | 5 . 4 |
  +-------+-------+-------+
  | 3 1 . | 6 4 . | 9 7 . |
  | . . 5 | 9 7 . | 3 1 . |
  | . . 8 | 3 1 . | . . 5 |
  +-------+-------+-------+


I am continuing the search on this grid, using what is basically a DFS search based on {+2, -1} and {+3, -2} morphing, starting with puzzles of size 30 or more found by a random search process.
User avatar
Mathimagics
2017 Supporter
 
Posts: 681
Joined: 27 May 2015

Re: SudokuP: Max Clues for Puzzle

Postby coloin » Thu Jul 26, 2018 11:04 am

Well ... that's more than very good
Jumping from 33 to 36 is quite a jump ! It might be the limit ....
Its also a minimal normal Sudoku puzzle .... i seem to remember I found the first minimal 36 [in the mc grid] but the 37s came without it.
Code: Select all
*-----------*
 |..3|..6|78.|
 |..6|78.|12.|
 |78.|12.|45.|
 |---+---+---|
 |.31|.64|8..|
 |.64|8..|2..|
 |8..|2..|5..|
 |---+---+---|
 |312|645|...|
 |645|...|...|
 |...|...|...|
 *-----------*

maybe this is sudokuP minimal ? - but unlikely

here is the ref for the 36 and subsequent 37 and 38 and 39s

Going up a level requires finding more puzzles at that level ..... and is challenging ...

ultimately two 40s were found and to dobrichevs credit ...... i doubt in another universe anyone else would find them.... :roll:
coloin
 
Posts: 1725
Joined: 05 May 2005

Re: SudokuP: Max Clues for Puzzle

Postby Mathimagics » Thu Jul 26, 2018 12:01 pm

.
It's a minimal SudokUP puzzle, so it seems you had a best case (36) all along! :)
User avatar
Mathimagics
2017 Supporter
 
Posts: 681
Joined: 27 May 2015

Re: SudokuP: Max Clues for Puzzle

Postby coloin » Thu Jul 26, 2018 2:02 pm

Well it was fortuitous ...

EDIT ..... it is the same puzzle as yours ! :D

here is some sudokup valid non-minimal 38C puzzles [valid minimal normal sudoku 38C]
ive tried to remove clues .... but no minimal 37s were found ? but maybe a 36 for you to work on ?
Code: Select all
..............1.23.2345.6.1..6.4..72..71..3...3276.1.4.6851..37.7...65.83.587.2.6
.............12.34.345.6712...8.1..3..362...8.78.5312..451.82...6..4..8..8.265.41
.............12.34135....62.2175..8375.8.....8.3.21..7.6..7...837.16..455.824..76
.............12.34135....62.2175..8375.8.....8.3.21..7.7..6...836.14..755.827..46
.............12.34135....62.2175..8375.8.....8.3.21..7.7..6...836.17..455.824..76
...........1..2.34..3.41.52.24.6..7.17..2..633.617..2843..15.8651..8634.6.......5
...........1..2.34..356.1.7..4.5.8...85.274.323648.7.5.18.....634..16..86.2.4.3.1
...........1..2.34.32154.6..17.6548..6..1...72.54.7..6.73.2..4.1.67.3..552...1.73
...........1..2.34.35674.21..4.2...8..84.5.7.75..68.42.46.872.5.8......75.72.6.83
...........1..2.34.52.63..7..75...8..1..8745..8..24.71.682.5.43123.48.655....6..8
...........1..2345..31456.....72.8.4.7..5823.8..4.15.7..8.......17.864233.62147..
...........1..2345..31456.....72.8.4.7..5823.8..4.15.7..8.....6.17.8642.3.62147..
...........1.23.45.2..46.73....31.84.8..7453.4...857.1..7..2..825..1836781..6..5.
...........1.23.45.2..46.73..7..2..825..1836781..6..5..7..31.84.8..7453.4...85..1
...........1.23.45.23.4.16...7.....8..8.72614.14..875..32.84576.8.....3.47..36.81
...........1.23.45.23.4516...6.37..4..72.465.2..5...17.7.....8.18..725.66.2.58.71
...........1.23.45.24.5.63...2.7518...83...72.47.825.3.1...6.5..8653..1.4...183.6
...........1.23.45.24.5.63...2.7518...83...72.47.82563.1...6.5..8653..1.4...183..
...........1.23.45.24.6..31...2...78.7.83....8.2.753....634..87..8.5746..4768.153
...........1.23.45.24.6..31...2...78.8.73....7.2.853....634..87..7.5846..4867.153
...........1.23.45.245.1.63...7.......721..38215.38.7..58..7.2.1...8..5434215..87
...........1.23.45.245.1367.....85....237..86..62.5.73...8.76...1..3..586.815273.
...........1.23.45.45..1623..3..2.76..73..41.4.67...32.381.7254.7.......154..8.67
...........1.23.45.456.1723..6.7..84..84.65.2.5.2.8.76.32..7.58.8.3.....5..8.2.37
...........1.23.4524..15673.......8.416.8..3782..314.6.5...87.41643....878..5..6.
...........1.23.4524..15673.......8.416.8..5782..514.6.3...87.41645....878..3..6.
...........1.23.4524..516.3.....5.7.1.4.7.3567..31.8.4....8..32..25.74.84.8.3256.
...........1.23.4524..51673.......8.416.8..5782..154.6.3...87.41645....878..3..6.
...........1.23.4524.5...36....7....7.23.845.8.41.2.73.867...1.1.72.65844....1.67
...........1.23.452435...61..7.8.....3...4.574253.7.86.147.2..838.....7.7.283..14
...........1.23456.4275.8.1..3.......87.35.1441..78..3..856..4..6...2..8124.87.65
..........12.34.56.347.5182..1...6.5.2.6...7..7..5..21..3.7..68..75.82.32.834..17
..........12.34.56.347.5182..1..76.5.2.6...7..7..5..21..3....68..75.82.32.834..17
Last edited by coloin on Thu Jul 26, 2018 6:04 pm, edited 1 time in total.
coloin
 
Posts: 1725
Joined: 05 May 2005

Re: SudokuP: Max Clues for Puzzle

Postby Mathimagics » Thu Jul 26, 2018 5:54 pm

Hi coloin,

I tested all pair-removals on those 38-clue puzzles without any luck. No 36-clue's there ...

I am using them, however, to test a DFS search method based on removing clues, rather than adding them. That might be an easier way to find maximal puzzles on a given grid.
User avatar
Mathimagics
2017 Supporter
 
Posts: 681
Joined: 27 May 2015

Re: SudokuP: Max Clues for Puzzle

Postby coloin » Thu Jul 26, 2018 6:10 pm

Yes removing clues and keeping to the same grid works ...
but ultimately moving between grids was the way we made the 37s
I think dobrichev scanned all his 37 puzzles for a puzzle from the MC grid - but i believe he didn't find one.

maybe there is a minimal 34 or 35 within those 38s ...
coloin
 
Posts: 1725
Joined: 05 May 2005


Return to Sudoku variants