Investigation of one-crossing-free patterns

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

Re: Investigation of one-crossing-free patterns

Postby coloin » Mon Jul 13, 2015 11:14 pm

Short of something to do ... I have further investigated puzzles with a full row and a full box in the same band.
A continuation of the 9plus12 theme ..... except there are 15plux "x" clues
eg
Code: Select all
+-----+-----+-----+       
|. . .|. . .|. . .|
|. . .|. . .|. . .|       
|. . .|. . .|. . .|
+-----+-----+-----+ 
|. . .|. . .|. . .|
|. . .|. . .|. . .|       
|. . .|. . .|. . .|
+-----+-----+-----+     
|. . .|. . .|x x x| 
|. . .|. . .|x x x|   
|x x x|x x x|x x x|
+-----+-----+-----+ add 'x' more clues....

It seems easy [enough] to generate valid puzzles with these clues plus any 10 other clues ....
e.g
Code: Select all
+---+---+---+
|...|1.8|...|
|..4|..2|...|
|..5|...|...|
+---+---+---+
|...|...|5..|
|9..|.3.|...|
|8..|..9|...|
+---+---+---+
|...|...|123|
|...|...|456|
|123|456|789|
+---+---+---+[15plus10puzzle]

Only a very few 15plus9puzzles however [!]
There are also only 3 ED ways to have the 15 clues .....

From looking at Serg's patterns - maybe there are more rules we can apply ...
It might be that there are very few 15plus9 patterns which are valid
And perhaps we may be able to increase our invalid pattern criteria ...

C
coloin
 
Posts: 2283
Joined: 05 May 2005
Location: Devon

Re: Investigation of one-crossing-free patterns

Postby Serg » Tue Jul 28, 2015 5:08 pm

Hi, coloin!
Unfortunately, I have no ideas in what way your "15plus9puzzles" approach can help to go further in possible puzzles exploring. But I think it's better to say "nothing", than nothing to say. I encountered problems trying to expand "one-crossing-free" approach to 6 free boxes - too many variants, too much CPU time it's necessary. I'm pondering alternative approaches to exhaustive search methods.

Serg
Serg
2018 Supporter
 
Posts: 801
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby coloin » Wed Aug 19, 2015 4:57 pm

Thanks for considering it Serg
Here are the four 4 15plus9s that I found by generating more than 180,000 15plus10s !

Code: Select all
123456789456......789........8...........2..4.7.........1.....6...8........27....
123456789456......789........8...........2..4.7.........1.....6....8.......27....
123456789456......789........8....6....51...............4..9.........5........21.

123456789457......896.......8..........6........1.36........16..............89...


Since its not exhaustive, there may be more ... but there wont be many.

Of the 3 ED ways to have the 15 clues [only 3] the canonical one is by far the most common.

If these 15plus9 puzzles are the only puzzles - a possible use might be in removing patterns which cant have puzzles.

But of course it needs to be proved.

C
coloin
 
Posts: 2283
Joined: 05 May 2005
Location: Devon

Re: Investigation of one-crossing-free patterns

Postby Serg » Mon Jan 16, 2017 9:19 pm

Hi, people!
I've done exhaustive search and now can confirm blue's result - published below patterns have no valid puzzles, so one can use it for filtering out invalid patterns.

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


Serg
Serg
2018 Supporter
 
Posts: 801
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby Serg » Sun Oct 16, 2022 7:37 pm

Hi, all!
Till this moment invalid patterns only discussed in this thread. Now I've done exhaustive search for locally minimal valid patterns, having one crossing "free", i.e boxes B5, B6, B8 and B9 contain 9 clues each, boxes B1, B2, B3, B4, B7 may have arbitrary number of clues. These patterns are valid, because they have valid Sudoku puzzles, but if we remove 1 clue from "free" area (boxes B1, B2, B3, B4, B7), pattern becomes invalid. Some locally minimal patterns are well known. For example, these 2 patterns are locally minimal:
Code: Select all
       Q240                    Q242

+-----+-----+-----+     +-----+-----+-----+
|. . x|. . .|. . .|     |. . .|. . .|. . .|
|. x x|. . .|. . .|     |x x x|. . .|. . .|
|x x .|. . .|. . .|     |x x x|. . .|. . .|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+

I found 242 of one-crossing-free locally minimal valid patterns. These patterns contain at least 5 clues in the crossing, but 2 of them contain 9 clues in the crossing (it is maximal number of clues in the crossing for such patterns). Here they are:
Code: Select all
        Q32                     Q33

+-----+-----+-----+     +-----+-----+-----+
|. . .|. . .|. . .|     |. . .|. . .|. . .|
|. . .|. . x|. . x|     |. . .|. . x|. . x|
|. . .|. x x|. x .|     |. . .|. x x|. x .|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. x x|x x x|x x x|     |. x x|x x x|x x x|
|. x x|x x x|x x x|     |x . x|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
|. . .|x x x|x x x|     |. . .|x x x|x x x|
+-----+-----+-----+     +-----+-----+-----+

Full list of 242 minimal patterns is available by link https://drive.google.com/file/d/1YdPBFJI1fyYCoFLQ0qgQa4A-iUc5gxQS/view?usp=sharing.

Each crossing of every valid pattern must contain as morphed subset at least one of those 242 patterns.

Serg
Serg
2018 Supporter
 
Posts: 801
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby JPF » Sun Oct 16, 2022 10:09 pm

Hi Serg,

Interesting results.
To use more easily your patterns, could you give the list of those 242 patterns in this format:
Code: Select all
..............x..x....xx.x....xxxxxx.xxxxxxxx.xxxxxxxx...xxxxxx...xxxxxx...xxxxxx;Q32
..............x..x....xx.x....xxxxxx.xxxxxxxxx.xxxxxxx...xxxxxx...xxxxxx...xxxxxx;Q33

or
Code: Select all
..............1..1....11.1....111111.11111111.11111111...111111...111111...111111;Q32
..............1..1....11.1....111111.111111111.1111111...111111...111111...111111;Q33

JPF
JPF
2017 Supporter
 
Posts: 6017
Joined: 06 December 2005
Location: Paris, France

Re: Investigation of one-crossing-free patterns

Postby Serg » Sun Oct 16, 2022 10:43 pm

Hi, JPF!
Here is 242 patterns list in the format you defined below:
JPF wrote:
Code: Select all
..............1..1....11.1....111111.11111111.11111111...111111...111111...111111;Q32
..............1..1....11.1....111111.111111111.1111111...111111...111111...111111;Q33


Serg
Serg
2018 Supporter
 
Posts: 801
Joined: 01 June 2010
Location: Russia

Re: Investigation of one-crossing-free patterns

Postby JPF » Mon Oct 17, 2022 7:19 pm

Thanks!

JPF
JPF
2017 Supporter
 
Posts: 6017
Joined: 06 December 2005
Location: Paris, France

Previous

Return to General