Is this pattern valid?

Programs which generate, solve, and analyze Sudoku puzzles

Is this pattern valid?

Postby Dr. Octagon » Wed Apr 02, 2014 10:31 pm

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.
Dr. Octagon
 
Posts: 8
Joined: 30 March 2014

Re: Is this pattern valid?

Postby blue » Thu Apr 03, 2014 7:26 am

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 . . |
| . . . | . . . | . . . |
+-------+-------+-------+
blue
 
Posts: 573
Joined: 11 March 2013

Re: Is this pattern valid?

Postby Dr. Octagon » Thu Apr 03, 2014 8:50 pm

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
Dr. Octagon
 
Posts: 8
Joined: 30 March 2014

Re: Is this pattern valid?

Postby JasonLion » Fri Apr 04, 2014 2:36 am

When searching for puzzles that fit specific patterns it is best to use an extremely fast brute force solver.
User avatar
JasonLion
2017 Supporter
 
Posts: 621
Joined: 25 October 2007
Location: Silver Spring, MD, USA

Re: Is this pattern valid?

Postby blue » Fri Apr 04, 2014 5:09 pm

This shape was extremely difficult too.
I had to resort to unusual techniques, to find a puzzle.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Is this pattern valid?

Postby champagne » Fri Apr 04, 2014 7:17 pm

blue wrote: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.
champagne
2017 Supporter
 
Posts: 5613
Joined: 02 August 2007
Location: France Brittany

Re: Is this pattern valid?

Postby Dr. Octagon » Fri Apr 04, 2014 9:12 pm

JasonLion wrote: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.
Dr. Octagon
 
Posts: 8
Joined: 30 March 2014

Re: Is this pattern valid?

Postby champagne » Sat Apr 05, 2014 2:45 pm

Dr. Octagon wrote: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
champagne
2017 Supporter
 
Posts: 5613
Joined: 02 August 2007
Location: France Brittany

Re: Is this pattern valid?

Postby dobrichev » Sat Apr 05, 2014 3:55 pm

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.
dobrichev
2016 Supporter
 
Posts: 1311
Joined: 24 May 2010

Re: Is this pattern valid?

Postby champagne » Sat Apr 05, 2014 4:50 pm

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
champagne
2017 Supporter
 
Posts: 5613
Joined: 02 August 2007
Location: France Brittany

Re: Is this pattern valid?

Postby Dr. Octagon » Sat Apr 05, 2014 5:09 pm

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


Thanks!
Dr. Octagon
 
Posts: 8
Joined: 30 March 2014

Re: Is this pattern valid?

Postby champagne » Sun Apr 06, 2014 7:49 am

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)
champagne
2017 Supporter
 
Posts: 5613
Joined: 02 August 2007
Location: France Brittany

Re: Is this pattern valid?

Postby blue » Sun Apr 06, 2014 7:10 pm

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...........


champagne wrote: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.
blue
 
Posts: 573
Joined: 11 March 2013

Re: Is this pattern valid?

Postby Dr. Octagon » Sun Apr 06, 2014 8:18 pm

champagne wrote:
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.
Dr. Octagon
 
Posts: 8
Joined: 30 March 2014

Postby Pat » Wed Apr 09, 2014 4:11 pm

Dr. Octagon wrote:
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 . .


champagne wrote:
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)
Last edited by Pat on Thu Apr 10, 2014 6:46 am, edited 1 time in total.
User avatar
Pat
 
Posts: 3423
Joined: 18 July 2005

Next

Return to Software

cron