The New Sudoku Players' Forum

by **JPF** » Tue Jun 27, 2023 9:39 pm

It is true that, in general, proving that a pattern is invalid is not an easy task!
But in the specific case of 17-clue patterns, it is relatively easy, as I mentioned and as Coloin pointed out.
That being said, the search for maximal invalid 17-clue patterns seems reasonably easy. Here's another example:

Code: Select all: +-------+-------+-------+ | . . . | . . . | . . . | | . . . | . . . | . x x | | . . x | . x x | . . . | +-------+-------+-------+ | . . . | . . x | x . x | | . . x | . . . | x . . | | . x . | . . . | . . . | +-------+-------+-------+ | . . . | x . . | . . . | | . . . | x x . | . x . | | x . x | . . . | . . . | +-------+-------+-------+

64 valid puzzles

Hidden Text: Show

Code: Select all: 1...............23..4.56........46.7..8...1...2..........7........32..5.5.6...... .1..............23..4.56........78.4..1...6...2..........7........32..5.7.6...... ..1.............23..4.56........76.8..5...7...2..........8........32..9.4.7...... ...1............23..4.56........71.8..7...5...2..........8........32..9.4.6...... ....1...........23..4.56........13.6..7...5...8..........3........97..3.6.2...... .....1..........23..1.45........45.6..7...4...3..........7........23..8.5.6...... ......1.........23..4.56........78.4..8...6...2..........5........32..9.9.6...... .......1........23..4.56........37.4..8...5...2..........9........12..6.4.7...... ........1.......23..4.56........35.4..6...7...2..........8........12..9.6.5...... .........1......23..4.56........74.1..8...6...2..........3........92..7.5.6...... ..........1.....23..4.56........78.4..5...6...2..........9........12..3.4.6...... ...........1....23..4.56........45.7..5...6...2..........1........82..9.6.7...... ............1...23..4.56........56.7..6...4...2..........3........27..8.6.9...... .............1..23..4.56........71.8..1...5...2..........8........32..9.5.6...... ..............1.23..4.56........74.8..7...1...2..........3........82..9.1.5...... ...............123..4.56........78.9..5...4...2..........9........32..1.5.6...... ................123.4.56........34.5..1...6...7..........8........27..9.4.6...... ................12.34.56........46.5..7...4...1..........8........13..2.7.6...... ................12..3456........78.4..5...6...1..........3........21..7.6.8...... ................12..3.456.......37.4..8...5...1..........8........21..9.3.6...... ................12..3.45.6......17.8..7...5...6..........2........16..9.8.5...... ................12..3.45..6.....67.8..6...5...1..........8........21..9.5.4...... ................12..3.45...5....43.6..7...5...1..........2........16..8.7.5...... ................12..3.45....6...47.3..7...5...1..........2........61..4.8.5...... ................12..3.45.....2..63.7..4...5...1..........2........61..8.5.9...... ................12..3.45......6.47.3..7...5...1..........2........18..6.3.5...... ................12..3.45.......675.8..4...7...1..........8........21..9.3.7...... ................12..3.45........6738..5...6...1..........8........21..4.6.9...... ................12..3.45........43.67.4...5...1..........2........61..8.5.9...... ................12..3.45........67.5.84...3...1..........8........21..9.7.5...... ................12..3.45........65.7..83..6...1..........7........21..9.4.6...... ................12..3.45........67.8..4.5.6...1..........4........21..9.4.6...... ................12..3.45........65.7..4..86...7..........2........19..2.3.6...... ................12..3.45........67.8..5...34..1..........8........21..9.6.4...... ................12..3.45........45.6..1...4.7.2..........1........28..9.5.6...... ................12..3.45........65.7..8...4..19..........8........19..5.6.2...... ................12..3.45........63.5..4...6...17.........8........21..3.8.5...... ................12..3.45........36.7..4...8...1.2........7........81..9.7.5...... ................12..3.45........36.7..5...8...1..6.......7........21..4.3.9...... ................12..3.45........65.3..4...7...1...8......9........21..9.7.5...... ................12..3.45........62.7..7...4...1....3.....8........91..8.4.2...... ................12..3.45........65.7..8...3...1.....6....1........27..8.5.4...... ................12..3.45........36.7..5...8...1......9...7........21..8.3.6...... ................12..3.45........67.8..4...6...1.......7..1........28..3.4.6...... ................12..3.45........63.5..7...8...1........9.6........21..4.5.8...... ................12..3.45........64.5..7...8...3.........82........19..2.5.4...... ................12..3.45........63.7..8...5...1..........97.......21..6.9.4...... ................12..3.45........67.8..5...3...1..........2.7......81..9.7.9...... ................12..3.45........67.8..4...5...1..........2..4.....81..9.7.5...... ................12..3.45........64.7..8...6...1..........7...4....21..9.4.5...... ................12..3.45........67.8..4...6...1..........8....6...21..9.4.5...... ................12..3.45........64.7..8...5...1..........1.....9..27..8.5.4...... ................12..3.45........63.7..8...5...1..........9......9.21..6.5.4...... ................12..3.45........65.3..4...6...1..........2.......671..8.9.5...... ................12..3.45........63.7..4...5...1..........6........213.8.5.7...... ................12..3.45........65.3..7...8...1..........9........21.94.8.5...... ................12..3.45........35.6..5...4...1..........2........71..848.4...... ................12..3.45........65.3..7...8...1..........9........21..4.598...... ................12..3.45........35.6..7...4...1..........2........81..9.6.59..... ................12..3.45........65.7..6...3...1..........2........17..8.5.4.8.... ................12..3.45........65.3..4...7...1..........8........21..8.4.5..3... ................12..3.45........65.3..7...8...4..........1........42..6.8.5...9.. ................12..3.45........67.8..6...9...1..........8........71..2.9.4....3. ................12..3.45........36.7..8...9...1..........6........21..4.5.7.....8

JPF

by **Serg** » Wed Jun 28, 2023 3:57 pm

Hi, JPF!
Congratulations with finding the second 17-clue maximal invalid pattern!

I've done exhaustive search for your first 17-clue maximal invalid pattern though. To be more sure my code runs properly, I searched through this pattern with 1 added clue in r9c9 cell (your proved that this "extended" pattern is valid):

Code: Select all: 18-clue extended pattern +-----+-----+-----+ |. . .|. . .|. . .| |. . .|. . .|. x x| |. . x|. x x|. . .| +-----+-----+-----+ |. . .|. . x|x . .| |. x .|. . .|. . .| |x x .|. . .|. . x| +-----+-----+-----+ |. . .|x . .|. . .| |. . .|x x .|x . .| |. . x|. . .|x . x| +-----+-----+-----+

It turns out the pattern has 739 valid puzzles, 735 of them are minimal 18-clue puzzles, 4 puzzles are not minimal, after subtraction redundant clues we'll get 4 known 17-clue puzzles. In all cases redundant clue occupies r6c9 cell. So, the cell r9c9 is not redundant, hence your first published 17-clue pattern is really invalid.

Serg

P.S. I got understand your method of 17-clue maximal invalid patterns generation - you modify -1/+1 clue cells from/to known 17-clue valid patterns.

by **JPF** » Wed Jun 28, 2023 6:29 pm

Hi Serg!

Thank you for your analysis and comments.

Serg wrote:I got understand your method of 17-clue maximal invalid patterns generation - you modify -1/+1 clue cells from/to known 17-clue valid patterns.

That's not the method I used, but perhaps it achieves the same result.

One last example for the road, and then I'll stop: I believe there are many other candidates. Moreover, my process is quite time-consuming.

Code: Select all: +-------+-------+-------+ | . . . | . . . | . . . | | . . . | . . . | . x x | | . . x | . x x | . . . | +-------+-------+-------+ | . . . | . . . | . . . | | . . x | . . . | x . . | | . x . | x . . | . . x | +-------+-------+-------+ | . . . | . . x | x x . | | . x . | . . . | . . . | | x x . | x . . | . . . | +-------+-------+-------+

Hidden Text: Show

Code: Select all: 1...............23..4.56..............5...4...3.7....1.....864..9.......72.9..... .1..............12..3.45..............4...3...2.6....1.....745..6.......18.2..... ..1.............23..4.56..............5...7...4.2....8.....365..7.......28.9..... ...1............23..4.56..............5...7...8.3....9.....765..3.......19.2..... ....1...........23..4.56..............5...7...4.2....8.....365..2.......89.4..... .....1..........23..1.45..............5...6...3.7....8.....845..7.......36.2..... ......1.........23..4.56..............1...4...7.2....8.....764..5.......12.3..... .......1........23..4.56..............5...6...7.2....8.....416..5.......29.3..... ........1.......23..4.56..............6...7...1.2....8.....749..2.......89.3..... .........1......23..4.51..............5...1...6.2....7.....847..9.......23.6..... ..........1.....23..4.51..............6...4...7.2....8.....854..9.......23.7..... ...........1....23..4.56..............5...6...3.2....7.....486..9.......72.8..... ............1...23..4.56..............5...7...8.2....9.....765..9.......27.3..... .............1..23..4.56..............7...4...3.2....8.....465..9.......82.7..... ..............1.23..4.56..............6...5...1.3....7.....548..9.......73.2..... ...............123..4.56..............6...2...3.7....4.....156..7.......38.4..... ................123.4.56..............1...3...7.8....9.....346..5.......92.7..... ................12.34.56..............3...5...7.2....8.....546..1.......82.7..... ................12..3456..............5...7...4.1....8.....765..1.......98.2..... ................12..3.456.............5...4...2.7....6.....859..7.......21.6..... ................12..3.45.6............4...7...2.1....8.....754..1.......58.6..... ................12..1.34..5...........4...6...7.2....8.....534..8.......72.1..... ................12..3.45...5..........6...3...2.7....1.....348..7.......21.9..... ................12..3.45....5.........6...4...2.7....1.....438..7.......21.9..... ................12..3.45.....5........4...3...2.6....7.....846..1.......27.9..... ................12..3.45......2.......6...4...3.7....8.....954..7.......62.1..... ................12..3.45.......2......4...6...7.8....9.....854..9.......12.7..... ................12..3.45........4.....6...7...8.1....9.....734..9.......17.2..... ................12..3.45.........3....5...4...4.2....6.....783..6.......29.1..... ................12..3.45..........6...1...3...7.2....8.....643..9.......82.5..... ................12..3.45...........3..5...6...7.2....8.....645..9.......28.1..... ................12..3.45............6.7...3...2.1....8.....453..9.......81.6..... ................12..3.45.............14...6...7.2....8.....954..6.......28.7..... ................12..3.45..............51..3...6.2....7.....389..4.......72.8..... ................12..3.45..............4.3.5...6.1....7.....846..1.......29.6..... ................12..3.41..............1..34...2.5....6.....763..5.......28.9..... ................12..2.34..............3...56..6.2....1.....543..7.......12.8..... ................12..3.45..............5...6.3.3.2....7.....845..2.......76.1..... ................12..3.45..............4...3..61.2....7.....846..9.......27.1..... ................12..3.45..............4...6...678....1.....654..8.......12.7..... ................12..3.45..............5...4...1.62...7.....158..6.......12.7..... ................12..3.45..............4...6...7.2.8..9.....654..8.......92.1..... ................12..3.45..............4...5...1.2..6.7.....846..9.......27.1..... ................12..3.45..............4...5...6.2...78.....465..8.......29.1..... ................12..3.45..............4...5...6.2....75....849..1.......62.7..... ................12..3.45..............4...5...6.7....1.2...846..7.......91.2..... ................12..3.45..............4...6...7.2....8..1..654..9.......28.1..... ................12..3.45..............4...6...2.1....7...8.954..6.......87.2..... ................12..3.45..............4...6...1.7....8....9654..7.......62.8..... ................12..3.45..............5...6...6.1....7.....7456.7.......18.2..... ................12..3.45..............6...4...3.1....7.....458.58.......21.6..... ................12..3.45..............4...6...7.1....8.....654..87......16.2..... ................12..3.45..............5...3...6.2....7.....456..8.1.....27.9..... ................12..3.45..............6...3...7.1....5.....347..8..7....12.9..... ................12..3.45..............4...5...2.1....6.....748..6...3...19.8..... ................12..3.45..............5...3...1.2....6.....743..2....7..68.9..... ................12..3.45..............5...6...4.2....7.....638..7.....5.92.1..... ................12..3.45..............5...6...3.1....7.....845..1......697.2..... ................12..3.45..............6...4...3.1....7.....458..8.......1296..... ................12..3.45..............4...6...7.1....3.....654..8.......91.82.... ................12..3.45..............6...3...7.1....4.....347..6.......12.8.6... ................12..3.45..............4...3...6.1....7.....386..9.......21.6..5.. ................12..3.45..............4...6...7.2....3.....654..1.......28.7...9. ................12..3.45..............5...4...6.2....7.....834..1.......72.6....9

JPF

by **Serg** » Sat Jul 08, 2023 2:17 pm

Hi, all!
I've done exhaustive search and can confirm that both Blue's 18-clue patterns, published in this thread, are invalid. JPF's 18-clue pattern ("parallelogram") is invalid too.

I did checks - do 16-clue maximal invalid patterns exist? So, I generated all 16-clue patterns produced by 1 clue removal from known 33884 17-clue valid patterns. There are 576028 such 16-clue ED patterns. Then I checked every pattern - are all its 1-clue extensions known 17-clue valid patterns? If I could find 16-clue pattern that can be extended to known 17-clue valid patterns only, it would be an example of 16-clue maximal invalid pattern. But such examples don't exist. Thus, the fewest number of clues for maximal invalid patterns is 17, provided that 49158 17-clue valid puzzles list is full.

Serg

by **JPF** » Sat Jul 08, 2023 9:58 pm

We can also refer to the results of afmob here, which presumably provide the exhaustive list of valid 18-clue dd symmetric patterns. The first pattern of Blue and the parallelogram pattern, which are both 18-clue dd symmetric, are not included in afmob's list.

JPF

The New Sudoku Players' Forum

Maximal invalid patterns with the fewest number of clues.

Re: Maximal invalid patterns with the fewest number of clues

Re: Maximal invalid patterns with the fewest number of clues

Re: Maximal invalid patterns with the fewest number of clues

Re: Maximal invalid patterns with the fewest number of clues

Re: Maximal invalid patterns with the fewest number of clues