The New Sudoku Players' Forum

[Mathimagics]

===========================================================================
RE: BumbleBeagle's 8-clue Jigsaw Sudoku puzzles
===========================================================================

The first two puzzles are 9-clue, and have different jigsaw layouts (JL's), which I call "BB1" and "BB2".

There are 2 layouts with 8-clue puzzles, 5 on JL "BB3", and two on JL "BB3".

Code: Select all

AAAAAAABCADDDDDDBCADEBBBBBCDDEBFFFCCEEEBFCCCGEFFFFCHIGEFHHHHHIGEHHIIIIIGEHIIGGGGG # BB1
AAABBCCDEABBBCCDDEABFFCDDGEABFCCDGGEABFCDDGEEABFCDHGEIAFFHHHGEIFFHHGGGEIHHHIIIIII # BB2
AAAAABBBBACCDAAAEBCCDDFFFEBCDDFFGGEBCDFFHGEEBCDFHHGEIBCDFHGGEIICDHHGIEEIHHHGGIIII # BB3
AAAAAAABCADDEEBBBCADEEBBFFCDDEBBFFCCDEEBFFCCGDEFFFHCIGDEHHHHCIGDHHIIIIIGHHIIGGGGG # BB4


[ EDIT ] layout BB3 was wrong, now fixed

I have found 14 x 8-clue puzzles on BB3, and 3 x 8-clue puzzles on BB4. So many are new. (see below for list).

These were found by a simple procedure. I first enumerated all transversals (TV's) on each JL, then set clue(r, c) = region# for the 9 cells defined for each TV, and tested the resulting puzzle. There were 45 x 9-clue puzzles found for BB3, and 26 for BB4. I then tested each 9-clue puzzle for clue-removal to find any 8-clue cases.

Back in 2005, the author (Bob H) posted here about his discoveries, and used the term "snaky" to describe the JL regions he used. (See post by me13013 a few posts down the page).

A "snaky" region might also be called linear, since its adjacency graph is a straight line. A more general definition, which I call twiggy, includes adjacency graphs that are trees (in the graph theory sense). Thus all linear regions are twiggy, but not vice-versa, as the following non-linear examples show:

Code: Select all

     X            XXXX
   XXXXXX           X         
    X X           XXXX


More formally:

• a region is linear iff each cell has only 1 or 2 neighbours in the same region

• a region is twiggy iff it contains no 2x2 square

My catalog of 3.57 milllion valid (symmetric) JL's has 7472 cases of TJL's. Only 21 of these are totally linear (ie all 9 regions are "snaky"), while most have some linear regions.

TJL example: Show

Code: Select all

+---+---+---+---+---+---+---+---+---+
|           |           |           |
+---+---+   +   +---+   +   +---+---+
|       |   |   |   |   |   |       |
+   +---+   +---+   +   +   +---+   +
|   |               |   |       |   |
+   +---+---+---+---+   +---+   +   +
|   |   |   |           |   |   |   |
+   +   +   +---+---+---+   +   +   +
|   |   |                   |   |   |
+   +   +   +---+---+---+   +   +   +
|   |   |   |           |   |   |   |
+   +   +---+   +---+---+---+---+   +
|   |       |   |               |   |
+   +---+   +   +   +---+   +---+   +
|       |   |   |   |   |   |       |
+---+---+   +   +---+   +   +---+---+
|           |           |           |
+---+---+---+---+---+---+---+---+---+


This example is symmetric, and has 6 linear regions, and 3 non-linear. The non-linear regions are the one in the center, the top-left and bottom-right.

The main objective is to investigate a suggested link between TJL's and low-clue puzzles.

Here are the 8-clue puzzle lists for BB3 and BB4. Independent confirmation of these would be appreciated!

BB3-8C: Show

Code: Select all

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


BB4-8C: Show

Code: Select all

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


[creint]

All BB3-8C puzzles have multiple solutions.

1 > SE 10 but easier than 3

Code: Select all

........9.2.......1....................4.........5.........6..........8.......7..

2 < SE 10

Code: Select all

........9.2.......1..........3...................5.........6.........7.........8.

3 > SE 10 hardest one

Code: Select all

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

Verification with miniSat was easy.

[Mathimagics]

Thanks creint!

It seems that a gremlin has been chewing on my code!

[Mathimagics]

Ok, it seems that I simply copied the wrong list.

There are now only 14 for BB3, and I have updated the list.

Would you try again?

[ EDIT ] I have now checked the list of 14 x BB3-8C puzzles (as updated in the original post) and confirm that all are valid (tested with DLX, FSSS and SAT !!!)

[Mathimagics]

.
The list of 14 puzzles for BB3-8C (as amended and checked) reveals that there are probably many, many more 8-clue puzzles on that JL.

If you look carefully at the list, the clues do occur in different rows and columns, but NOT in distinct regions!

This occurred because I was generating the puzzles using the templates for BB4 by mistake.

If I generate the intended puzzle list for layout BB3, then each clue has different rows, columns, and regions. The resulting list has 17 entries, none of which appear in the list of 14:

BB3-8C-TV: Show

Code: Select all

.2..........4.........5.........6...........91...............8............3......
.2...............9......7..................8.1............5.......4..........6...
.2...............9......7..................8....4.........5....1.............6...
..3..............9....5..........7...2.......1...........4...................6...
...4............8.........9......7...2..................3......1.............6...
...4.............91..............7.........8............3.......2............6...
...4.............9.....6..................7.........8.1............5.....2.......
...4.............9......7..................8.1............5.........6....2.......
.....6.........7.........8.1.........2.........3.........4.........5.............
.....6.........7.........8..2.......1..........3.........4.........5.............
.....6.........7.........8..2.......1..........3..........5.......4..............
.....6.........7.........8..2.........3......1...........4......................9
.....6.........7.........8..2.........3......1...........4.........5.............
......7......5....1...........4......2............6...........9.......8..........
......7......5...........8..2.......1..........3...........6....................9
......7.......6...................8....4.....1............5............9.2.......
.......8.....5....1.........2......................7.......6......4.............9

Again, these have all been verified with DLX, FSSS and SAT !!!

So that means at least 31 x 8C puzzles exist on layout BB3. And a {+1,-1} search seems likely to produce many more ...

[creint]

Those have still multiple solutions.

[Mathimagics]

.

creint, my sincere apologies!

The original BB3 I gave in the original post was some other JL that I had on the clipboard, so the 8-clue puzzle list wouldn't be valid using that JL.

The correct BB3 should be:

Code: Select all

AAAAABBBBACCDAAAEBCCDDFFFEBCDDFFGGEBCDFFHGEEBCDFHHGEIBCDFHGGEIICDHHGIEEIHHHGGIIII

Visually it should look like this:

BB3: Show

Code: Select all

+---+---+---+---+---+---+---+---+---+
|                   |               |
+   +---+---+---+   +---+---+---+   +
|   |       |   |           |   |   |
+---+   +---+   +---+---+---+   +   +
|       |       |           |   |   |
+   +---+   +---+   +---+---+   +   +
|   |       |       |       |   |   |
+   +   +---+   +---+   +---+   +   +
|   |   |       |   |   |       |   |
+   +   +   +---+   +   +   +---+   +
|   |   |   |       |   |   |   |   |
+   +   +   +   +---+   +   +   +---+
|   |   |   |   |       |   |       |
+   +   +---+   +   +---+   +---+   +
|   |   |       |   |   |       |   |
+---+---+   +---+   +   +---+---+   +
|           |       |               |
+---+---+---+---+---+---+---+---+---+


I have fixed the mistake in the original post

Hopefully the 8-clue puzzles will now be reported as valid for you ...

[urhegyi]

Finally it seems to be ok now.

Code: Select all

Analysis results 
Difficulty rating: 9,3
This Sudoku Jigsaw can be solved using the following logical methods:
66 x Hidden Single (1,0-1,5)
1 x Direct Pointing (1,7)
5 x Naked Single (2,3)
1 x Direct Hidden Triplet (2,5)
13 x Pointing (2,6)
17 x Claiming (2,8)
12 x Generalized Intersection (2,9)
1 x Naked Pair (3,0)
1 x X-Wing (3,2)
1 x Generalized X-Wing (6,5)
1 x Turbot Fish (6,6)
1 x Forcing X-Chain (6,7)
5 x Forcing Chain (7,1-7,2)
44 x Nishio Forcing Chains (7,6-8,3)
1 x Cell Forcing Chains (8,3)
1 x Region Forcing Chains (8,3)
25 x Dynamic Cell Forcing Chains (8,8-9,3)
26 x Dynamic Contradiction Forcing Chains (8,8-9,3)
12 x Dynamic Region Forcing Chains (8,8-9,1)
1 x Dynamic Double Forcing Chains (8,9)

Code: Select all

1..........3.........4.............9..............6.......5..........7.........8. 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.3/1.5/1.5

[Mathimagics]

At last!

Thanks for that.

[urhegyi]

At last!

Thanks for that.

I rated the complete list:

Hidden Text: Show

Code: Select all

1..........3.........4.............9..............6.......5..........7.........8. 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.3/1.5/1.5
.2.........3..............9......7..................8.1............5.........6... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=10.1/1.2/1.2
.2..........4.............9...............7..1...............8.....5.........6... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.7/8.3/2.6
.2..........4.............9....5......3...............1...............8......6... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.4/9.0/2.6
.2..........4.............9....5......3............7..1......................6... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=8.3/8.2/2.6
.2...............9....5..........7..................8.1.............6.....3...... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=10.4/8.3/2.6
..3..............9......7......5..............2..............8.1.............6... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=11.2/8.3/2.6
...4......2...............9....5.........6...1..............7.............3...... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.4/8.3/2.6
....5.....2...............9...4.....1.............6.........7.............3...... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.2/8.3/2.6
....5.....2...............9......7.............3.............8.1.............6... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.1/8.3/2.6
....5.....2...............9......7..................8.1.............6.....3...... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.1/8.3/2.6
....5.....2...............9......7..................8...3......1.............6... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=8.2/8.2/2.6
.....6....2...............9....5......3............7..1....................4..... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.1/8.2/2.6
........91.............6......4....................7......5...........8...3...... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=11.1/1.2/1.2
.2..........4.........5.........6...........91...............8............3...... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=10.8/8.3/2.6
.2...............9......7..................8.1............5.......4..........6... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=10.9/8.2/2.6
.2...............9......7..................8....4.........5....1.............6... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=10.9/8.2/2.6
..3..............9....5..........7...2.......1...........4...................6... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=11.2/8.0/2.6
...4............8.........9......7...2..................3......1.............6... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=10.5/8.0/2.6
...4.............91..............7.........8............3.......2............6... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=10.4/8.2/2.6
...4.............9.....6..................7.........8.1............5.....2....... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=10.9/8.3/2.6
...4.............9......7..................8.1............5.........6....2....... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.3/8.2/2.6
.....6.........7.........8.1.........2.........3.........4.........5............. 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.5/2.6/2.6
.....6.........7.........8..2.......1..........3.........4.........5............. 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.6/2.6/2.6
.....6.........7.........8..2.......1..........3..........5.......4.............. 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.3/2.6/2.6
.....6.........7.........8..2.........3......1...........4......................9 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=10.6/2.6/2.6
.....6.........7.........8..2.........3......1...........4.........5............. 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.4/2.6/2.6
......7......5....1...........4......2............6...........9.......8.......... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.2/8.0/2.6
......7......5...........8..2.......1..........3...........6....................9 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.2/8.1/2.6
......7.......6...................8....4.....1............5............9.2....... 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.3/7.9/2.6
.......8.....5....1.........2......................7.......6......4.............9 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=8.4/8.1/2.6


[Mathimagics]

Excellent!

I take it from those ratings that most of the puzzles are hard. This is to be expected, of course.

Maybe this newly found 8-clue puzzle on BB2 might be slightly easier?

Code: Select all

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

[urhegyi]

Excellent!

I take it from those ratings that most of the puzzles are hard. This is to be expected, of course.

Maybe this newly found 8-clue puzzle on BB2 might be slightly easier?

Code: Select all

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

Yes it is:

Code: Select all

.2..........4.....................8......6...........9......7....3......1........ 111223345122233445126634475126334775126344755126348759166888759668877759888999999 ED=7.8/1.2/1.2

[Mathimagics]

Excellent again!

On Bob H's webpage (linked above), BB2 is the 2nd grid in the first pair of puzzles. He identified the 9-clue puzzle on it and said it was singles-only, or close to it. So it made sense that the 8-clue puzzle that I found was possibly easier than the BB3 8C-puzzles.

BTW, I have now found 672 x 8-clue puzzles on BB3 !!

And without resorting to vicinity search ...

[urhegyi]

I now have rated your 3 very hard BB4 puzzles:

Code: Select all

........9.2.......1....................4.........5.........6..........8.......7.. 111111123144552223145522663445226633455266337456668397458888397488999997889977777 ED=10.7/1.2/1.2
........9.2.......1..........3...................5.........6.........7.........8. 111111123144552223145522663445226633455266337456668397458888397488999997889977777 ED=10.0/1.2/1.2
......7......5.............1...............8...3..............9...4......2....... 111111123144552223145522663445226633455266337456668397458888397488999997889977777 ED=12.2/12.2/2.6


[urhegyi]

This BB3 was mentioned in the link in the first post:

Code: Select all

.....6.........7.........8.1.........2.........3.........4.........5............. 111112222133411152334466652344667752346687552346887592346877599348879559888779999 ED=9.5/2.6/2.6