The New Sudoku Players' Forum

[Dr. Octagon]

Is it possible to generate a standard 9x9 Sudoku puzzle with the following pattern?
Note: "!" marks squares where a number can appear.
Note: "." marks squares where a number can NOT appear.

Code: Select all


12.|34.|56.
!..|!..|!..
...|...|...
---+---+---
!!.|...|!!.
!..|...|!..
...|...|...
---+---+---
!!.|!!.|!!.
!..|!..|!..
...|...|...



If it is not possible to generate such a puzzle, I would like to know why not.
On the other hand, if it is possible, I would like to see such a puzzle.

[blue]

Here's one:

Code: Select all

+-------+-------+-------+
| 1 2 . | 3 4 . | 5 6 . |
| 7 . . | 8 . . | 9 . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| 9 1 . | . . . | 6 2 . |
| 5 . . | . . . | 8 . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| 6 3 . | 7 2 . | 4 1 . |
| 8 . . | 5 . . | 7 . . |
| . . . | . . . | . . . |
+-------+-------+-------+

And another:

Code: Select all

+-------+-------+-------+
| 1 2 . | 3 4 . | 5 6 . |
| 7 . . | 8 . . | 9 . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| 4 6 . | . . . | 7 2 . |
| 2 . . | . . . | 3 . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| 5 3 . | 9 6 . | 1 8 . |
| 9 . . | 1 . . | 4 . . |
| . . . | . . . | . . . |
+-------+-------+-------+

And one with no redundant clues:

Code: Select all

+-------+-------+-------+
| 1 2 . | 3 4 . | 5 6 . |
| 7 . . | 8 . . | 9 . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| 6 9 . | . . . | 1 5 . |
| 4 . . | . . . | 7 . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| 5 6 . | 4 1 . | 2 3 . |
| 8 . . | 7 . . | 4 . . |
| . . . | . . . | . . . |
+-------+-------+-------+

[Dr. Octagon]

Thanks Blue,

My Sudoku generator/solver has been unable to make puzzles like the ones you provided.

It may be that my program doesn't know enough solving strategies to make such a puzzle. Currently my program only knows about:

1) Singles in block
2) Singles in row/column
3) Singles in square
4) Pointing pairs/triples
5) Block line reductions
6) Hidden/Naked pairs, triples, quads
7) Xwings

Yours truly,
Will

[JasonLion]

When searching for puzzles that fit specific patterns it is best to use an extremely fast brute force solver.

[blue]

This shape was extremely difficult too.
I had to resort to unusual techniques, to find a puzzle.

[champagne]

This shape was extremely difficult too.
I had to resort to unusual techniques, to find a puzzle.

right

I tested several of my standard processes, heavily oriented toward minimal puzzles and failed.


But the remark of Jasonlion is basically true. Exploring millions of permutations, only the brute force can be used.

I am trying to adjust the parameters of my search for seeds, so I could have by to morrow more comments.

[Dr. Octagon]

When searching for puzzles that fit specific patterns it is best to use an extremely fast brute force solver.

Thanks Jason. Eventually I plan to program a Backtracking brute force solver to complement my Logic-based solver.

[champagne]

Thanks Jason. Eventually I plan to program a Backtracking brute force solver to complement my Logic-based solver.

You can find in that forum the "best known code" for a brute force. here

Back to your pattern, the more I look, the more I think that the number of different puzzles is very very small.

So far, I found a morph of the first puzzle given by blue and a new non minimal puzzle.

I cheated in my last test, running a full scan after having forced the 9 first digits of the puzzles provided by blue. In my process, this comes as last choice. The test is running and should last 2 or 3 days.
This represents a huge number of possibilities to test. Not something you can do without a performing brute force.

Congratulations to blue who produced some puzzles in a short time. This can be misleading, either he was lucky or he has a terrible weapon

[dobrichev]

Yes, this pattern has no much puzzles. I can't comment are the puzzles found by blue extremely rare, but I ran a test over ~3000 grids, searching for minimal puzzles only, and found nothing.

[champagne]

With 3 empty rows, 3 empty columns, one empty box, many "symmetries" (and only 24 clues), one could not expect millions of puzzles.

The open question is "is there tens of puzzles".

After the explorations made I have heavy doubts

[Dr. Octagon]

You can find in that forum the "best known code" for a brute force. here

Thanks!

[champagne]

I had to cancel the partial scan, but 80% of the field was covered.

I have several morphs of the puzzles published by blue, but no new minimal puzzle.

I found only 3 non minimal new puzzles

Code: Select all

98.76.54.3..2..1...........76....28.8.....6...........25.48.76.1..3..9...........
98.76.54.3..2..1...........64....38.1.....7...........75.14.62.2..5..9...........
98.76.54.3..2..1...........59....83.1.....6...........47.62.98.6..1..2...........


To test the changes in my code for a full handling of non minimal puzzles, I'll test the vicinity of theses puzzles, but I am not expecting many new puzzles


EDIT

The depth 5 vicinity search did not bring any new stuff.
I tried a depth 7 search and I got so far one new non minimal puzzle.

The entire file (output of gridchecker minlex keeping the pattern untouched) is now

Hidden Text: Show

12.34.56.3..5..7...........74....89.9.....2...........59.27.14.8..6..3...........
12.34.56.3..7..4...........85....69.7.....3...........56.23.81.9..4..7...........
12.34.56.3..7..8...........45....69.7.....3...........56.23.41.9..8..7...........
12.34.56.3..7..8...........54....92.8.....7...........75.61.24.9..8..3...........
12.34.56.4..7..8...........35....92.7.....4...........86.57.31.9..4..7...........
12.34.56.4..7..8...........81....25.7.....4...........59.67.31.2..4..7...........
12.34.56.6..2..7...........54....89.3.....1...........79.15.24.8..6..3...........

A total of about 10 ED puzzles seems a reasonable guess for that pattern.
Only one minimal puzzle has been found (by blue)

[blue]

I think this is the full list (assuming no bugs) -- 8 puzzles:

Code: Select all

12.34.56.3..5..7...........74....89.9.....2...........59.27.14.8..6..3...........
12.34.56.3..7..4...........85....69.7.....3...........56.23.81.9..4..7...........
12.34.56.3..7..8...........45....69.7.....3...........56.23.41.9..8..7........... (minimal)
12.34.56.3..7..8...........54....92.8.....7...........75.61.24.9..8..3...........
12.34.56.4..1..7...........86....47.2.....9...........75.26.38.9..5..1...........
12.34.56.4..7..8...........35....92.7.....4...........86.57.31.9..4..7...........
12.34.56.4..7..8...........81....25.7.....4...........59.67.31.2..4..7...........
12.34.56.6..2..7...........54....89.3.....1...........79.15.24.8..6..3...........

Congratulations to blue who produced some puzzles in a short time. This can be misleading, either he was lucky or he has a terrible weapon

It was mainly luck. After trying for a few hours, and not finding anything with my usual software, I decided to try to find puzzles for the shape with one extra clue. With the extra clue in the center box, the puzzles for 4 of the 6 ED clue positions, had at least one band/stack with all 9 digits in the clues. That lead me to testing a random 1/6th of the puzzles with 1-9 in the top band. Two popped up, neither one minimal. Then I did the full scan for that type, and another 4 came up, including the minimal one. The results are above, are for a full scan with no restrictions.

[Dr. Octagon]

Code: Select all

12.34.56.3..5..7...........74....89.9.....2...........59.27.14.8..6..3...........
12.34.56.3..7..4...........85....69.7.....3...........56.23.81.9..4..7...........
12.34.56.3..7..8...........45....69.7.....3...........56.23.41.9..8..7...........
12.34.56.3..7..8...........54....92.8.....7...........75.61.24.9..8..3...........
12.34.56.4..7..8...........35....92.7.....4...........86.57.31.9..4..7...........
12.34.56.4..7..8...........81....25.7.....4...........59.67.31.2..4..7...........
12.34.56.6..2..7...........54....89.3.....1...........79.15.24.8..6..3...........

Thanks for the list of puzzles. This has been quite useful to me.

[Pat]

Code: Select all


O . O O . O O . O
. . . . . . . . .
O . . O . . O . .
O . O . . . O . O
. . . . . . . . .
O . . . . . O . .
O . O O . O O . O
. . . . . . . . .
O . . O . . O . .



With 3 empty rows, 3 empty columns, one empty box,
many "symmetries"
(and only 24 clues),
one could not expect millions of puzzles.

The open question is "is there tens of puzzles".

my Layout also has those 7 empty houses
(and 24 cells given, spread evenly in the 8 non-empty boxes)

Code: Select all


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



the difference is,
i avoided those heavy lines of 6 givens
(reduced them to 5 givens per line)