SudokuFP

For fans of Killer Sudoku, Samurai Sudoku and other variants

Re: SudokuFP

Postby coloin » Wed Jan 09, 2019 6:55 pm

tarek wrote:Oh Coloin, you are opening a can of worms ( non consecutive worms) :D I

Cheers tarek im glad it didnt turn out to be a can of worms - but i didnt expect a min clue of 5 [or less]
Surely the number of solution grids wont be that large .... but relabelling is a problem ...
trying to do your 5-puzzle tonight !
C
coloin
 
Posts: 1746
Joined: 05 May 2005

Re: SudokuFP

Postby Mathimagics » Thu Jan 10, 2019 5:16 am

qiuyanzhe wrote:Non-Consecutive solution grid count …

Nice work! 8-)

I wonder if this is the first time that JSudoku has been used to perform a solution grid count for a Sudoku variant? :?:

I have confirmed the counts for the first 2 entries in your original table (167, 220), so I now trust my solver.

For NC+, we can count explicitly, or simply enumerate the NC solutions, testing each one for NC+ property.

Either way, I get these counts (for the case center-square = 1):
Code: Select all
               NC      NC+
25341....     167        4
2.3415...     220       44
2.341..5.    2321      359   
2.341...5     561        0   
253.1.4..    1199       93
2.3.154..     483       66
2.3.1.4.5     822        0
2.3.1..4.   11567     4444
2.3.1...4    1577       19
24..13...    8720     5139
2..413...    1434      135
2...134..   12700      883
2...13.4.   13269     6508
24..1...3   14864     6096
2.4.1...3    3177      389
--------------------------
            73081    24179
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

Re: SudokuFP

Postby qiuyanzhe » Thu Jan 10, 2019 6:02 am

It turns out that I mistook in calculating permutations, so all my data posted before should be multiplied by 2(edited). Now I think those are correct now, so
#NC=5288648.
And we're done with NC+, total count should be
#NC+=24179*8*9=1740888.
P.S. If all pairs are independent, there should be 6.67e21*(28/36)^144=1280504 NC grids and 6.67e21*(27/36)^144=6807 NC+ ones.. Interesting..
Last edited by qiuyanzhe on Thu Jan 10, 2019 7:36 am, edited 1 time in total.
qiuyanzhe
 
Posts: 72
Joined: 21 August 2017
Location: China

Re: SudokuFP

Postby Mathimagics » Thu Jan 10, 2019 7:25 am

Ok, good job!

Quick question - in your table for NC, why does that last entry have 8, not 16, isotopes?
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

Re: SudokuFP

Postby qiuyanzhe » Thu Jan 10, 2019 7:35 am

Mathimagics wrote:In your table for NC, why does that last entry have 8, not 16, isotopes?

I have to admit that this is not straightforward.. Every grid has 16 isotopes, but only in the last case, solutions are counted twice.
Code: Select all
473.5...6 --(19 28..)->
637.5...4 --(rot 180°)->
4...5.736 --(flip diag)->
4.7.53..6

Also edited minor mistakes in my previous post.
qiuyanzhe
 
Posts: 72
Joined: 21 August 2017
Location: China

Re: SudokuFP

Postby Mathimagics » Thu Jan 10, 2019 8:11 am

Ok, got it!

To count the number of ED grids for SudokuNC, then, we just need to add up the 1st column of your table, which gives us 344,774, agreed?

This is subject to independent verification, which I am currently doing …
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

Re: SudokuFP

Postby qiuyanzhe » Thu Jan 10, 2019 9:46 am

It's not.. actually I haven't counted the number of grids with self-symmetry( The only possible symmetry is (rotate 180°+ reverse digits) rxcy + r(10-x)c(10-y)=10 ). We still need to investigate on the number of symmetrical grids..
Suppose it is X, then the solution would be 344,774 - 28667 + (28667-X)/2 + X.
(I bet X would be an odd number! otherwise..there must be something wrong ;) )
qiuyanzhe
 
Posts: 72
Joined: 21 August 2017
Location: China

Re: SudokuFP

Postby Mathimagics » Thu Jan 10, 2019 12:44 pm

Ok, well that will be picked up in my process which is basically:

  • Enumerate the solution grids using your CBP list (center box patterns)
  • Canonicalise each grid (ie choose min form of 16 possible isotopes)
  • Remove duplicates

This will go much faster now that I have got my dobrichev-fsss2 solver working in NC mode …
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

Re: Isomorphic NC grids

Postby tarek » Thu Jan 10, 2019 3:41 pm

Re: Isomorphic grids

I got for Non Cyclic NC: 2 (Labelling) x 8 (symmetries) = 16 isomorphs
& for Cyclic NC: 18 (Labelling) x 8 (symmetries) = 144 isomorphs

Is that how you see it?

Here are the 144 isomorphs of a cyclic NC grid for verification
Show 144 cNC isomorphs: Show
Code: Select all
135268497862794135497531862971853624624179358358426971586942713249317586713685249
136497528852631794479258136947582613285316479613974852361749285528163947794825361
137258694852496371694173528946317285528649713371825946713582469285964137469731852
137295864864731592592468137759682413286314759413957286641573928928146375375829641
146928573573641829829375146682759314957413682314286957731864295295137468468592731
147926853629358471853174296538417962296835714471692538714269385962583147385741629
153697428796824153428351796281735964964182537537469281379246815642518379815973642
158693724472851396639274158963742815247518639815936472581369247724185963396427581
163528497749361825582947163258479316974613582316285749631852974497136258825794631
168524793425397168793861425931486257257139684684752931842975316579613842316248579
174295368592863741368147925683714259925386417741529683417952836259638174836471592
175293648648571392392846175539462817264718539817935264481357926926184753753629481
184926357357481629629753184462539718935817462718264935571648293293175846846392571
184963527369725841527148693275814936693572418841396275418639752936257184752481369
185724693369581427742963185274639518936815742518247369851472936693158274427396851
186953724359427186724681359241368597597142863863795241635279418972814635418536972
246379518973815246518642973182964735735281469469537182697153824351428697824796351
247518639963742815581369247158693724396427581724185963472851396639274158815936472
248316975975842613613579248861793524397425861524168397752684139139257486486931752
248369715963517482715284639157428396639751824482936157824693571396175248571842963
257139684684752931931486257793861425168524793425397168842975316316248579579613842
258137964731469582964285317649528173317946825582713649825371496173694258496852731
264718539817935264539462817392846175175293648648571392481357926753629481926184753
269714835583962417741385269174853926358629741926147583692471358835296174417538692
274639518851472936693158274369581427185724693427396851742963185518247369936815742
279635814536418279814972536142597368368241795795863142953186427681724953427359681
285316479613974852479258136794825361136497528852631794528163947361749285947582613
286314759759682413413957286641573928375829641928146375592468137137295864864731592
295137468468592731731864295573641829146928573829375146682759314314286957957413682
295174638471836952638259714386925147714683529952417386529741863147368295863592471
296835714471692538853174296385741629147926853629358471962583147714269385538417962
297164835461538297835792461352479618618253974974816352746381529183925746529647183
316248579579613842842975316684752931257139684931486257793861425425397168168524793
316285749582947163749361825497136258825794631163528497631852974258479316974613582
317946825582713649964285317496852731258137964731469582173694258825371496649528173
318275946572649318946813572463581729729364185185927463857492631294136857631758294
357481629184926357629753184293175846846392571571648293718264935462539718935817462
358629741174853926692471358269714835417538692835296174583962417741385269926147583
359427186186953724724681359972814635418536972635279418863795241241368597597142863
359471826174628593826395741268539417741862935593147268935714682417286359682953174
368241795795863142142597368814972536279635814536418279953186427427359681681724953
369248175842571693175396428751639284428157936693824751936482517284715369517963842
371825946694173528852496371285964137469731852137258694713582469946317285528649713
375829641928146375641573928413957286286314759759682413592468137864731592137295864
381746925647529381925183647253618479479352816816974253164297538792835164538461792
385741629962583147714269385471692538296835714538417962853174296629358471147926853
396427581724185963581369247815936472247518639963742815639274158472851396158693724
397425861861793524524168397752684139486931752139257486613579248248316975975842613
417538692835296174692471358926147583358629741174853926741385269583962417269714835
418536972972814635635279418863795241597142863241368597724681359359427186186953724
427359681681724953953186427795863142368241795142597368814972536536418279279635814
427396851693158274851472936518247369936815742274639518742963185369581427185724693
428157936693824751175396428517963842369248175842571693284715369936482517751639284
429386157683751429157924683574692831831475296296138574968513742315247968742869315
461538297297164835835792461183925746529647183746381529974816352352479618618253974
461582937285739614937416852379641528852973146614258379146825793528397461793164285
468592731295137468731864295314286957957413682682759314829375146573641829146928573
469731852285964137713582469371825946528649713946317285694173528852496371137258694
471359286953682714286417539862741395539268147714935862147593628395826471628174953
479352816816974253253618479925183647381746925647529381164297538538461792792835164
482936157715284639963517482396175248571842963248369715824693571157428396639751824
486931752139257486752684139524168397397425861861793524613579248975842613248316975
492857136758631492136294758364729581581463927927185364275318649813946275649572813
496852731173694258825371496582713649317946825649528173964285317731469582258137964
513968247869742513247315869475831692692574138138296475386429751924157386751683924
517963842284715369936482517693824751428157936751639284175396428842571693369248175
528649713946317285713582469137258694469731852285964137852496371694173528371825946
529647183183925746746381529974816352618253974352479618835792461461538297297164835
531497268794862531268135794685713942942586317317249685179624853426358179853971426
538417962714269385962583147629358471147926853385741629853174296471692538296835714
538461792792835164164297538816974253479352816253618479925183647647529381381746925
539268147714935862286417539628174953471359286953682714395826471147593628862741395
571842963396175248824693571482936157639751824157428396715284639963517482248369715
572649318318275946946813572294136857631758294857492631185927463463581729729364185
572693148396841725148527963481752639963184257725369481257936814639418572814275396
579613842316248579842975316425397168168524793793861425931486257684752931257139684
581463927927185364364729581136294758492857136758631492275318649649572813813946275
582461397164793825397528641973852416641379258825146973258614739416937582739285164
593147268826395741174628593417286359682953174359471826935714682268539417741862935
597142863241368597863795241635279418418536972972814635724681359186953724359427186
614258379937416852285739614528397461793164285461582937146825793379641528852973146
618253974352479618974816352746381529529647183183925746835792461297164835461538297
624179358971853624358426971586942713713685249249317586497531862135268497862794135
628174953395826471147593628714935862539268147862741395286417539953682714471359286
631758294294136857857492631185927463729364185463581729946813572572649318318275946
639751824157428396824693571248369715571842963396175248963517482715284639482936157
641379258825146973397528641739285164582461397164793825416937582258614739973852416
642518379815973642379246815796824153153697428428351796281735964537469281964182537
649528173825371496173694258731469582258137964496852731964285317582713649317946825
649572813813946275275318649927185364581463927364729581136294758758631492492857136
681724953427359681953186427536418279279635814814972536142597368795863142368241795
682953174417286359935714682593147268741862935268539417826395741174628593359471826
683714259417952836259638174592863741174295368836471592368147925741529683925386417
683751429429386157157924683315247968742869315968513742296138574574692831831475296
692574138138296475475831692247315869513968247869742513386429751751683924924157386
693572418275814936418639752184963527752481369936257184369725841527148693841396275
713685249249317586586942713358426971624179358971853624497531862862794135135268497
714683529386925147529741863295174638863592471147368295471836952638259714952417386
725369481148527963396841725639418572814275396572693148257936814481752639963184257
729364185463581729185927463857492631631758294294136857946813572318275946572649318
735281469182964735469537182697153824824796351351428697518642973246379518973815246
739285164416937582258614739825146973641379258973852416397528641164793825582461397
741862935268539417935714682359471826682953174417286359174628593826395741593147268
742869315315247968968513742296138574831475296574692831157924683683751429429386157
751639284936482517284715369842571693369248175517963842175396428693824751428157936
751683924924157386386429751138296475692574138475831692247315869869742513513968247
752481369936257184418639752841396275693572418275814936527148693369725841184963527
753629481926184753481357926817935264264718539539462817392846175648571392175293648
792835164538461792164297538647529381381746925925183647253618479816974253479352816
793164285528397461146825793614258379852973146379641528937416852285739614461582937
794825361528163947361749285613974852285316479947582613479258136852631794136497528
794862531531497268268135794426358179853971426179624853317249685685713942942586317
813946275649572813275318649758631492492857136136294758364729581927185364581463927
814275396639418572257936814725369481963184257481752639148527963396841725572693148
815936472639274158472851396724185963396427581158693724581369247963742815247518639
815973642642518379379246815537469281964182537281735964428351796796824153153697428
824796351351428697697153824469537182735281469182964735518642973973815246246379518
825794631497136258631852974316285749974613582258479316582947163749361825163528497
831475296574692831296138574968513742742869315315247968157924683429386157683751429
836471592259638174417952836741529683925386417683714259368147925592863741174295368
841396275527148693369725841936257184752481369184963527418639752275814936693572418
846392571293175846571648293718264935935817462462539718629753184357481629184926357
852973146379641528146825793461582937793164285528397461285739614937416852614258379
853971426426358179179624853317249685942586317685713942268135794794862531531497268
862741395147593628395826471953682714471359286628174953286417539714935862539268147
862794135135268497497531862249317586713685249586942713358426971971853624624179358
863592471147368295529741863952417386714683529386925147638259714471836952295174638
864731592137295864592468137928146375375829641641573928413957286759682413286314759
924157386751683924386429751869742513513968247247315869475831692138296475692574138
925386417741529683368147925836471592174295368592863741259638174417952836683714259
926147583741385269583962417835296174417538692269714835692471358174853926358629741
926184753753629481481357926648571392175293648392846175539462817817935264264718539
935817462462539718718264935571648293846392571293175846629753184184926357357481629
936815742518247369742963185427396851185724693369581427693158274851472936274639518
942586317685713942317249685179624853853971426426358179268135794531497268794862531
947582613361749285528163947852631794136497528794825361479258136613974852285316479
952417386638259714471836952147368295863592471295174638529741863386925147714683529
957413682314286957682759314829375146146928573573641829731864295468592731295137468
963184257481752639257936814572693148814275396639418572396841725148527963725369481
964182537537469281281735964428351796153697428796824153379246815815973642642518379
973815246246379518518642973351428697824796351697153824469537182182964735735281469
973852416258614739416937582164793825582461397739285164397528641825146973641379258
974613582258479316631852974163528497825794631497136258749361825582947163316285749
975842613248316975613579248139257486486931752752684139524168397861793524397425861


And the 16 isomorphs if the grid was a non cyclic NC for verification
non cyclic NC 16 isomorphs: Show
Code: Select all
135268497862794135497531862971853624624179358358426971586942713249317586713685249
147926853629358471853174296538417962296835714471692538714269385962583147385741629
168524793425397168793861425931486257257139684684752931842975316579613842316248579
184963527369725841527148693275814936693572418841396275418639752936257184752481369
316248579579613842842975316684752931257139684931486257793861425425397168168524793
358629741174853926692471358269714835417538692835296174583962417741385269926147583
385741629962583147714269385471692538296835714538417962853174296629358471147926853
397425861861793524524168397752684139486931752139257486613579248248316975975842613
713685249249317586586942713358426971624179358971853624497531862862794135135268497
725369481148527963396841725639418572814275396572693148257936814481752639963184257
752481369936257184418639752841396275693572418275814936527148693369725841184963527
794862531531497268268135794426358179853971426179624853317249685685713942942586317
926147583741385269583962417835296174417538692269714835692471358174853926358629741
942586317685713942317249685179624853853971426426358179268135794531497268794862531
963184257481752639257936814572693148814275396639418572396841725148527963725369481
975842613248316975613579248139257486486931752752684139524168397861793524397425861


tarek
User avatar
tarek
 
Posts: 2898
Joined: 05 January 2006

Re: Easy cNC puzzles

Postby tarek » Thu Jan 10, 2019 7:00 pm

Code: Select all
Easy Cyclic NC (8 clues not symmetric)
FP(1,9) redundant but makes solving easier
.....................1...2...8...6...2.............3...7.........2...............
+-------+-------+-------+
| . . . | . . . | . . . |
| . . . | . . . | . . . |
| . . . | 1 . . | . 2 . |
+-------+-------+-------+
| . . 8 | . . . | 6 . . |
| . 2 . | . . . | . . . |
| . . . | . . . | 3 . . |
+-------+-------+-------+
| . 7 . | . . . | . . . |
| . . 2 | . . . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+

Easy Cyclic NC (9 clues symmetric)
FP(1,9) needed
........1....2.......................3..1.58..............5........3....6........
+-------+-------+-------+
| . . . | . . . | . . 1 |
| . . . | . 2 . | . . . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . . . | . . . |
| . 3 . | . 1 . | 5 8 . |
| . . . | . . . | . . . |
+-------+-------+-------+
| . . . | . 5 . | . . . |
| . . . | . 3 . | . . . |
| 6 . . | . . . | . . . |
+-------+-------+-------+


tarek
User avatar
tarek
 
Posts: 2898
Joined: 05 January 2006

Re: Isomorphic NC grids

Postby Mathimagics » Thu Jan 10, 2019 8:17 pm

tarek wrote:I got for Non Cyclic NC: 2 (Labelling) x 8 (symmetries) = 16 isomorphs
& for Cyclic NC: 18 (Labelling) x 8 (symmetries) = 144 isomorphs

Is that how you see it?

Indeed I do!
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

Re: SudokuFP

Postby tarek » Fri Jan 11, 2019 8:47 am

Mathimagics wrote:.
Hmmm, is a one-given puzzle possible? I wonder ...

Possible with the correct set of constraints. IIRC udosuk has posted a puzzle with 1 clue (I can't recall the constraints but i'm expecting there were many). He nicely presented it as a golden egg at the bottom of the empty grid with an Ostrich (Hint) sitting on it. To make the presentation better he broke with convention and used 0 as a clue (Therefore the golden egg) :D :D

tarek
User avatar
tarek
 
Posts: 2898
Joined: 05 January 2006

Re: SudokuFP

Postby Mathimagics » Fri Jan 11, 2019 10:49 am

Ok, then, we'll have to see what can be done with FP's alone …

Meanwhile, back at the ranch ostrich farm, I haven't been able to post ED counts yet because my fast solver deceived me! It solved a test case correctly, so I trusted it. But when I tested the first of those 9-cell center-box patterns to verify the count, expecting 167, I got 371 (ouch!).

My first Sudoku-variant Solver failure ... :(


[EDIT] Some consolation, at least it did find all of the 167 valid solutions. And about 500 times faster than my VB6 solver did, so progress of some sort, and perhaps enough to enable a complete enumeration, from which we can produce an ED figure ...
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

Re: SudokuFP

Postby Mathimagics » Fri Jan 11, 2019 1:27 pm

Ok, by my reckoning

  • there are 330,845 ED SudokuNC grids
  • there are 12,263 ED SudokuNC+ grids


Despite the dodgy solver, it did produce all the valid solutions, just some unwanted rubbish as well. Once we tossed out the trash, and verified the counts, then generated the CF (Canonical Form) for each valid grid, then removed the duplicates, only the ED grids were left.

Full ED grid listings available on request (PM me with an email address).

ED counts are of course provisional, subject to the normal requirement of some independent verification. 8-)

[EDIT] Oh dear, made a hash of it. All my CF functions to date have normalised the grid isomorphisms before determining which is smallest lexically, but of course we can't do that here, it totally kills the NC property. Revised figures updated above. (Thanks blue! :oops: )

[EDIT #2] Owing to a bug in my NC+ CF function, the NC+ figure above was wrong, the count above now agrees with that reported by blue
Last edited by Mathimagics on Sun Jan 13, 2019 8:59 am, edited 1 time in total.
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

Re: SudokuFP

Postby Mathimagics » Sat Jan 12, 2019 7:49 am

qiuyanzhe wrote:... on the number of symmetrical grids ...
Suppose it is X, then the solution would be 344,774 - 28667 + (28667-X)/2 + X.
(I bet X would be an odd number! otherwise..there must be something wrong ;) )


X = 809 seems to be the answer, oddly enough :lol:
User avatar
Mathimagics
2017 Supporter
 
Posts: 1095
Joined: 27 May 2015

PreviousNext

Return to Sudoku variants