Jigsaw Layouts (Generate / Test)

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: Jigsaw Layouts (Generate / Test)

Postby tarek » Mon Dec 16, 2019 10:23 pm

coloin wrote:from a post way back bumblebeagle - it seems that the minimum clues is 8

Hatman posted several 8 clue puzzles that have the "Hands" Jigsaw regions arrangement. One of the regions, however, doesn't have contiguous cells.
http://www.rcbroughton.co.uk/sudoku/forum/viewtopic.php?f=13&t=753 is where he posted them but the images links are unfortunately broken. According to Hatman it was introduced first by Nikoli_Freak. I had at the time some experiments with the layout and found the Jigsaw regions force the formation of X diagonals and Old Lace group too.

tarek

[Edit: Found the image: this is one my puzzles ]
Image
Last edited by tarek on Thu Dec 19, 2019 6:50 pm, edited 1 time in total.
User avatar
tarek
 
Posts: 3748
Joined: 05 January 2006

Re: Jigsaw Layouts (Generate / Test)

Postby Mathimagics » Tue Dec 17, 2019 4:35 am

@creint: You're right, of course - SAT is probably the fastest way to test a JL for validity ("has any solution"). I didn't realise this back then.

@tarek: Gareth Moore published (in his "SudokuXtra" magazine) several puzzles with toroidal jigsaw layouts.

coloin wrote:So there are 5,279,342 valid ED continuous JLs
[ and 13,638 invalid] :?: to clarify !
.... and each of these valid layouts may have 0,1 or more ED solutions


"Valid" means a layout has solutions, the invalid ones do not have solutions. See the hidden image in the very first post for a couple of innocent-looking, but invalid, layouts.

The counts I gave (13,638 invalid, 5,279,342 valid) refer to a restricted class of JL's. These are what I considered "nice" layouts - they are all symmetric, and have no partitions (no subset of regions forms a 9 x X rectangle).

Also, my actual catalog of valid "nice" JL's has only 3.5 million. I can't remember now - was this the result of a culling operation, ie removing duplicates (reflections/rotations)? Hmmm ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1602
Joined: 27 May 2015
Location: Canberra

Re: Jigsaw Layouts (Generate / Test)

Postby Hajime » Thu Jan 07, 2021 3:46 pm

Busy with jigsaw layouts....
The next jigsaw layout is valid (a solution can be found) for JS without boxes,
but no solution is possible for JSB with boxes, all jigsaw pieces touch 3 or more rows/columns
Code: Select all
#1//B4,JSB
123456789........................................................................
111152222144152552144355552114353922444333999664373988677773998677678998666678888

Is there a list of valid Jigsaw layouts with/without boxes available, say length<2500 and (point)symmetrical?
User avatar
Hajime
 
Posts: 277
Joined: 20 April 2018
Location: Netherlands

Re: Jigsaw Layouts (Generate / Test)

Postby urhegyi » Thu Jan 07, 2021 6:07 pm

[quote="Hajime"]Busy with jigsaw layouts....
The next jigsaw layout is valid (a solution can be found) for JS without boxes,
but no solution is possible for JSB with boxes, all jigsaw pieces touch 3 or more rows/columns
A valid JS starting with the numbers 1 to 9 in order at the first row:
Code: Select all
1....67.....5..............9.1.....4....6.......3.4......1...7...5.........8...5. 111152222144152552144355552114353922444333999664373988677773998677678998666678888

solution:
Code: Select all
123456789837542961648917325971285634259761843596374218364198572485623197712839456
Last edited by urhegyi on Thu Jan 07, 2021 7:00 pm, edited 1 time in total.
urhegyi
 
Posts: 227
Joined: 13 April 2020

Re: Jigsaw Layouts (Generate / Test)

Postby urhegyi » Thu Jan 07, 2021 6:14 pm

2021-01-07 (1).png
2021-01-07 (1).png (130.4 KiB) Viewed 137 times
urhegyi
 
Posts: 227
Joined: 13 April 2020

Re: Jigsaw Layouts (Generate / Test)

Postby Hajime » Thu Jan 07, 2021 9:10 pm

Great urhegyi that you can make a puzzle out of the JS layout.
But my intention is larger. I am interested in a list of about 2500 valid JS- and/or JSB layouts.
Can you generate or provide this? I like to publish this also on my SiSeSuSo website.
User avatar
Hajime
 
Posts: 277
Joined: 20 April 2018
Location: Netherlands

Re: Jigsaw Layouts (Generate / Test)

Postby urhegyi » Sat Jan 09, 2021 11:02 pm

Hajime wrote:Great urhegyi that you can make a puzzle out of the JS layout.
But my intention is larger. I am interested in a list of about 2500 valid JS- and/or JSB layouts.
Can you generate or provide this? I like to publish this also on my SiSeSuSo website.

I did some research to find a shape that can be used to generate both JS and JSB.
Here a valid pattern:
Code: Select all
111132222113333222115363342155563442556666644755864449758868499777888899777789999

Proof: 1 solution for JSB:
Hidden Text: Show
Code: Select all
123456789564879231789123645951632874836745192472981563645298317298317456317564928 111132222113333222115363342155563442556666644755864449758868499777888899777789999

JS examples:
Code: Select all
......2.........358.....34.1....6.........8.6......9....5.69....53....1.......... 111132222113333222115363342155563442556666644755864449758868499777888899777789999
.....1.....4...362.2............6.....9......54683...1............2.4....1..9.... 111132222113333222115363342155563442556666644755864449758868499777888899777789999

JSB examples:
Code: Select all
........9......8.....1.......9.8.6....4.5.......7.....21......6.6................ 111132222113333222115363342155563442556666644755864449758868499777888899777789999
5.......6..4......6...82154.42............4.......4983....6...2.9.2.3...3........ 111132222113333222115363342155563442556666644755864449758868499777888899777789999
......6..........2645....8..1.6......9....4..8...........5.2............4..1..8.3 111132222113333222115363342155563442556666644755864449758868499777888899777789999

Last two have ER 6.6
Last edited by urhegyi on Sun Jan 10, 2021 12:56 am, edited 2 times in total.
urhegyi
 
Posts: 227
Joined: 13 April 2020

Re: Jigsaw Layouts (Generate / Test)

Postby urhegyi » Sat Jan 09, 2021 11:46 pm

I tested this with SiSeSuSo 9 jan version: ER7.3 takes some time to solve but succeeded.
Code: Select all
#1//B4,JSB
.2......5.....8...56..2......1....................7........5.....8....3....97....
111132222113333222115363342155563442556666644755864449758868499777888899777789999

Hidden Text: Show
Code: Select all
Eliminated candidates per SER and per Sudoku

Method    \ Sudoku |   SER |     1
                   |-------|------
Not counted elims  |     0 |    99
Naked Singles      |   0.1 |    24
Hidden Singles     |   0.2 |    91
Naked Single  [1]  |   2.5 |     6
Naked Pair    [2]  |     3 |    23
Naked Triple  [3]  |   3.6 |     5
Naked Quad    [4]  |     5 |    18
Hidden Quad   [5]  |   5.4 |    22
Locked singles[2]  |   2.8 |    57
Locked singles[3]  |   2.9 |    14
Locked singles[4]  |     3 |     3
WXYZ Wing     [4]  |   5.5 |     1
VWXYZ Wing    [5]  |   6.3 |     1
X-chain/cycle [4]  |   6.7 |     3
XY-chain      [4]  |     7 |     3
XY-chain      [5]  |  7.05 |     1
XY-chain      [9]  |  7.25 |     2
XY-chain      [10]  |   7.3 |     5
                   |-------|------
Eliminated Cand's  |   378 |   378
Sum(SER * Cand's)  |651.55 |651.55

Initial Candidates :   378
Maximum SER rating :   7.3
Labour rating      :651.55


Very nice example of the new techniques
urhegyi
 
Posts: 227
Joined: 13 April 2020

Re: Jigsaw Layouts (Generate / Test)

Postby Hajime » Sun Jan 10, 2021 9:42 am

urhegyi wrote:I tested this with SiSeSuSo 9 jan version: ER7.3 takes some time to solve but succeeded.
Code: Select all
#1//B4,JSB
.2......5.....8...56..2......1....................7........5.....8....3....97....
111132222113333222115363342155563442556666644755864449758868499777888899777789999


Very nice example of the new techniques

Indeed, very nice puzzle.
I see that most elapsed time is in the X-chain procedure... 19 seconds of the 33.5 seconds total.
User avatar
Hajime
 
Posts: 277
Joined: 20 April 2018
Location: Netherlands

Re: Jigsaw Layouts (Generate / Test)

Postby 1to9only » Mon Jan 11, 2021 9:01 am

urhegyi wrote:I did some research to find a shape that can be used to generate both JS and JSB.

These JS layouts will generate both JSs and JSBs: j01, j08, j09, j11, j16, j17, j23, j30, j31, j34.
It's quite rare to find a JS that can be solved as JSB (the numbers have to be in the right places to form 3x3 blocks).
Some JSBs can also be solved as JSs, e.g this one (j09 Moonlotus):
Code: Select all
..4.1...8..97......1.....6.5....3.....7...43.6..1....9.....8.......2.........7... 112222233111222333411123335441666355444666555447666855477798885777999888779999988 JSB ED=6.6/1.2/1.2

..4.1...8..97......1.....6.5....3.....7...43.6..1....9.....8.......2.........7... 112222233111222333411123335441666355444666555447666855477798885777999888779999988 JS ED=8.5/1.5/1.5

1to9only
 
Posts: 2263
Joined: 04 April 2018

Re: Jigsaw Layouts (Generate / Test)

Postby Mathimagics » Mon Jan 11, 2021 12:45 pm

When I have some free time soon, I will look into the problem of generating valid JSB layouts, if Hajime is still seeking them?

The general approach, off the top of my head, would be to take a regular Sudoku solution grid, then look for possible jigsaw region assignments that fit the grid ... preferably "nice" ones, with some symmetry ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1602
Joined: 27 May 2015
Location: Canberra

Re: Jigsaw Layouts (Generate / Test)

Postby Hajime » Mon Jan 11, 2021 4:22 pm

Mathimagics wrote:When I have some free time soon, I will look into the problem of generating valid JSB layouts, if Hajime is still seeking them?

The general approach, off the top of my head, would be to take a regular Sudoku solution grid, then look for possible jigsaw region assignments that fit the grid ... preferably "nice" ones, with some symmetry ...

Yes, I am still interested and with intention to publish "your" sets of JS (not B) and JSB, if you agree.
Another possibility is that I can implement some nice algorithm to generate a JS or JSB from scratch in SiSeSuSo, but not yet figgered out how-to :o
User avatar
Hajime
 
Posts: 277
Joined: 20 April 2018
Location: Netherlands

Re: Jigsaw Layouts (Generate / Test)

Postby Mathimagics » Tue Jan 12, 2021 6:41 am

.
I am happy to share my catalog of jigsaw layouts, especially if anyone can create nice puzzles from them ...

That catalog has 3.5 million valid+nice jigsaw layouts (valid meaning they have JS solutions, "nice" as defined above).

There is a simple SAT-based method that can test these layouts to see which ones are also valid for JSB. That's what I intend to do next ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1602
Joined: 27 May 2015
Location: Canberra

Re: Jigsaw Layouts (Generate / Test)

Postby Mathimagics » Tue Jan 12, 2021 10:14 am

My first sampling of the "nice jigsaw layout" catalog suggests that as many as 30% are valid JSB layouts.

Here is a sample of 20. My SAT testing looks ok, and I am confident that they are indeed valid, but could someone confirm this?

JSB layouts: Show
Code: Select all
111112222333311222333451122364455555366444557666664457889964777888997777888899999
111111222131333422133335442666355422766555442776558444766588889776888989777999999
111111223411122233444442233544462233566666663557768883557788888557779998577999999
111123333111222223411225333444425366445555566447586666777588996788888999777789999
111123333111122333142222235444426635446666655476685555478888859777889999777789999
111111122333312222333312422355566444556666644555664447885897777888897777889999999
111112222134444422133442225134466555136666657333668857399988557998888857999977777
111111222311442222331455226344445766334555766334577776388557966888877996888999999
111111222333141252663142255633442255633347775668844775668849755868949777888999999
111111122131322222433335552436633552446666655744886685744488885777778989779999999
111122223411123323415222333415556363444456666747455586777999586797798886799998888
111112333114412333144452223446455223746555283766558288766658889777698899777699999
111112222314444422311145222334445566333555666335577766888579996887777796888899999
111111222113331222333344242356664442356564647855566647858557777888977799888999999
111111112333341222333344422356664422755666442775566648775558888777958888799999999
111111222113132222333334452663344552666645555766448855764488888777789899777999999
111111122333312222344412562333455562344456667845556777845896667888897777889999999
111111112331222222433556772443556772443356677844355677844355667888888966899999999
111111222133112242333332244556336244556666644557688644557788888757799889777999999
111111222131344442133334522334444522365555527665888877665877779688887979666999999
User avatar
Mathimagics
2017 Supporter
 
Posts: 1602
Joined: 27 May 2015
Location: Canberra

Re: Jigsaw Layouts (Generate / Test)

Postby Hajime » Tue Jan 12, 2021 1:18 pm

Mathimagics wrote:Here is a sample of 20. My SAT testing looks ok, and I am confident that they are indeed valid, but could someone confirm this?

I can confirm that all 20 JSB layouts have a solution :D
User avatar
Hajime
 
Posts: 277
Joined: 20 April 2018
Location: Netherlands

PreviousNext

Return to Sudoku variants

cron