Canonical Form

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

Postby JPF » Fri Feb 02, 2007 10:50 pm

coloin wrote:The approx upper limit of 7@r2c3 [416codes] is now 385+ [385*385] /2 X 2500 = 186243750 [maybe much less]

Sorry, I don't understand.

coloin wrote:Can we say there is no duplicates in 7@r2c3 min lex grids ?

No, Red Ed gave duplicate isohex grids with 7@r2c3 (index* = 70,45,69,148,...; index** = 133,068,131,225,...)

* with index416.exe
** gsf's index


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

Postby gsf » Sat Feb 03, 2007 5:52 pm

JPF wrote:
gsf wrote:I burned some background cycles overnight to generate the min and max min-lex grids for each of the 416 bands

gsf,
Am I missing something, or should your index list start with 001,002,... ?

I edited the post -- thanks

here are then band populations

001-099 ~1hr per band
200-299 ~20min per band
there's a better algorithm lurking but sometimes brute force works faster than gray matter
edit: all bands accounted for and sum to 5472730538 (phew)

001 1007170
002 25502082
003 16538087
004 8417906
005 48737791
006 96229042
007 15765443
008 5306280
009 8136013
010 47174193
011 46788396
012 46177270
013 15340394
014 45397270
015 45600758
016 1631576
017 15093541
018 45101600
019 44832423
020 88782526
021 44036568
022 85627559
023 42711122
024 85102373
025 41847039
026 41335391
027 4455504
028 41102914
029 4591391
030 4664261
031 13606209
032 40697707
033 80468663
034 79175610
035 77979783
036 38536298
037 76146967
038 74505665
039 74154564
040 72171447
041 36053455
042 70552290
043 69437575
044 67978951
045 33904021
046 66337407
047 65880161
048 64996381
049 63898062
050 62192220
051 61691475
052 60192385
053 29966384
054 29734495
055 58731513
056 57263818
057 57033275
058 55394556
059 55022930
060 54018514
061 52964870
062 52242492
063 51245000
064 50540742
065 49644127
066 49190978
067 24077300
068 47978806
069 47059527
070 46231581
071 22715795
072 44778204
073 44053469
074 43401907
075 21398806
076 42061440
077 41316125
078 40571245
079 40282447
080 39233218
081 38522319
082 37881913
083 37460193
084 18460204
085 36127803
086 35584769
087 34821531
088 34334716
089 33769162
090 33174401
091 32520037
092 31945541
093 31221072
094 30579410
095 29977732
096 29390061
097 14518368
098 14372444
099 28268021
100 27849953
101 13768854
102 26929453
103 26382806
104 4359314
105 25997296
106 25467197
107 24888528
108 24423300
109 23988326
110 23541927
111 23070530
112 22609142
113 22100458
114 10879514
115 21378062
116 20985174
117 20674972
118 20107116
119 19854606
120 9732970
121 19084488
122 9491325
123 18532281
124 9142485
125 18075269
126 17675306
127 17545752
128 16990098
129 8369473
130 16406705
131 16189996
132 15791769
133 2613345
134 15362664
135 15272476
136 14918036
137 7254450
138 14383075
139 7011714
140 13738161
141 13445152
142 6593805
143 12918117
144 6403269
145 12568136
146 12354720
147 12036469
148 5931073
149 5949060
150 11577852
151 11435633
152 11155974
153 10671486
154 10525735
155 10188634
156 10059617
157 9805813
158 9629320
159 9490222
160 9280124
161 8844112
162 8628099
163 8429593
164 8227144
165 7998287
166 7813413
167 3839149
168 7548052
169 7349287
170 7146807
171 6993422
172 6828801
173 6674911
174 6476248
175 3166465
176 6205963
177 6040631
178 5882934
179 5812748
180 5615082
181 5461387
182 5367414
183 5222068
184 5072949
185 4918277
186 4778878
187 4641003
188 4539624
189 4407284
190 2186822
191 4220821
192 4158097
193 4070158
194 3857103
195 3785628
196 3693474
197 3555681
198 3453089
199 3345667
200 3252227
201 3165254
202 3064062
203 2966309
204 2932890
205 2841380
206 2701985
207 2628788
208 2532198
209 2443960
210 1243959
211 2317171
212 2357854
213 1137589
214 1083228
215 2183311
216 2244753
217 2143677
218 2100798
219 1007465
220 1970315
221 1841722
222 1873099
223 1772301
224 347777
225 1968442
226 1677704
227 1521001
228 1498734
229 1515366
230 1457098
231 1331185
232 1279569
233 1262013
234 1218744
235 386642
236 1182963
237 570172
238 1111083
239 1076551
240 167032
241 533940
242 1048083
243 974591
244 967788
245 455310
246 915249
247 500537
248 783336
249 822496
250 377256
251 408556
252 437792
253 387029
254 140436
255 361962
256 354702
257 675674
258 661737
259 313209
260 623191
261 546083
262 524804
263 534167
264 503384
265 464985
266 461786
267 441645
268 418773
269 424148
270 378441
271 361885
272 360821
273 176161
274 172023
275 165927
276 154694
277 150664
278 309399
279 144927
280 141820
281 137601
282 287667
283 246093
284 123480
285 124070
286 116970
287 117351
288 110418
289 37988
290 109351
291 211267
292 209636
293 189161
294 188766
295 171584
296 152633
297 147806
298 70955
299 133302
300 139754
301 119226
302 20203
303 62246
304 63613
305 69669
306 58811
307 21225
308 56942
309 55120
310 49427
311 91869
312 89983
313 80765
314 43270
315 74594
316 69012
317 73627
318 62449
319 59123
320 57580
321 47910
322 44876
323 46852
324 46002
325 40108
326 37300
327 36969
328 31504
329 28919
330 27982
331 29202
332 25098
333 20652
334 10105
335 19471
336 18996
337 17212
338 14780
339 13660
340 12324
341 10597
342 9562
343 9012
344 8215
345 7261
346 3569
347 7136
348 455
349 2935
350 2990
351 4836
352 2156
353 2141
354 1959
355 4171
356 3376
357 3171
358 3150
359 647
360 1528
361 2484
362 2233
363 1930
364 1353
365 1368
366 1232
367 1667
368 925
369 872
370 928
371 808
372 560
373 757
374 451
375 245
376 333
377 156
378 193
379 161
380 23
381 163
382 154
383 111
384 124
385 87
386 49
387 66
388 125
389 27
390 59
391 19
392 41
393 2
394 16
396 11
399 10
401 1
405 4
407 19
411 3
416 1
Last edited by gsf on Tue Feb 06, 2007 7:04 pm, edited 2 times in total.
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby JPF » Sat Feb 03, 2007 6:54 pm

gsf wrote:I edited the post – thanks

for some reason the list stops at 373.

gsf wrote:here are some preliminary band population results (to be verified when all bands are done)
Code: Select all
001 1007170

Doest it mean that the band #1 is (at least once) in 1007170 min-lex grids ?

Thanks.

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

Postby gsf » Sat Feb 03, 2007 10:23 pm

JPF wrote:
gsf wrote:I edited the post – thanks

for some reason the list stops at 373.

a mouse snarf and/or post size limit
I edited the first to contain 001-199 and the next post will have 200-416
JPF wrote:
gsf wrote:here are some preliminary band population results (to be verified when all bands are done)
Code: Select all
001 1007170

Doest it mean that the band #1 is (at least once) in 1007170 min-lex grids ?

the list I posted is ordered by row-order min-lex canonical representation
they are partitioned by the row order min-lex bands 001-416
because of how min-lex grids and bands are defined there are a few assertions one can make on the list
for band 001: there are exactly 1007170 min-lex grids containing band 001
for band 002: some grids containing band 002 could be in the band 001 count, so there are 25502082 grids containing band 002 and not band 001
so entries for band B account for grids containing bands b >= B
and we end up with band 416 containing the only grid with signature 416,416,416,416,416,416 (the max min-lex grid)
Code: Select all
123456789457893612986217354274538196531964827698721435342685971715349268869172543
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby gsf » Sat Feb 03, 2007 10:25 pm

here are the min and max min-lex grids for bands 200-416

200 123456789457189263896327145214538697365791428978264351531942876649873512782615934
200 123456789457189263896327145289765431645931872731842596364218957572694318918573624
201 123456789457189263896327154214538697365791428789264315531842976642975831978613542
201 123456789457189263896327154289765431645931872731842596374618925518293647962574318
202 123456789457189263896327415214538697365791824789264531548912376631875942972643158
202 123456789457189263896327415289765341645931872731248596378612954514893627962574138
203 123456789457189263896327451214538697365791824789264135531872946642915378978643512
203 123456789457189263896327451289765314645931872731248596378612945564893127912574638
204 123456789457189263896327514214538697365791428789264135531872946648915372972643851
204 123456789457189263896327514289765431645931872731842695374218956518694327962573148
205 123456789457189263896327541214538697365791824789642135542873916638915472971264358
205 123456789457189263896327541289765314645913827731842695312674958578291436964538172
206 123456789457189263896372145214537698365298471789641352542963817638715924971824536
206 123456789457189263896372145289765431645913872731248956378521694562894317914637528
207 123456789457189263896372154214537698365891427789264315542718936631945872978623541
207 123456789457189263896372154289765431645931827731824695362547918514698372978213546
208 123456789457189263896372451214537698365894127789261534542913876638745912971628345
208 123456789457189263896372451289765314645931872731248596362517948514893627978624135
209 123456789457189263968327145214538697375691428689274351531862974742915836896743512
209 123456789457189263968327145296875431745931826831642957389514672512768394674293518
210 123456789457189263968327154214538697375691428689274315531942876792863541846715932
210 123456789457189263968327154294875631736941825815632497342518976579264318681793542
211 123456789457189263968327415214538697375691824689742531531864972796215348842973156
211 123456789457189263968327415296875341745913826831642597384591672579268134612734958
212 123456789457189263968327514214538697375691428689274135541863972732915846896742351
212 123456789457189263968327514296875431745931826831642957374518692519264378682793145
213 123456789457189263968327541214538697375691428689742135531864972742913856896275314
213 123456789457189263968327541296745318735891426841632975382564197574918632619273854
214 123456789457189263968372145214537698376298451895614327582763914631945872749821536
214 123456789457189263968372145296837514375941826814625937539268471681794352742513698
215 123456789457189263986327145214538697365791428798642351572914836649873512831265974
215 123456789457189263986327145298765431645931827731842956374618592569274318812593674
216 123456789457189263986327154214538697365791428879642531538274916642913875791865342
216 123456789457189263986327154298765431645931872731248695362894517579612348814573926
217 123456789457189263986327451214538697365791824798264135531642978649873512872915346
217 123456789457189263986327451298765314645931872731842695369218547572694138814573926
218 123456789457189326689237451214365897368791245795824163542913678836572914971648532
218 123456789457189326689237451298765143564913872731824695342571968876392514915648237
219 123456789457189326689237514214365897368791452795824163542913678836572941971648235
219 123456789457189326689237514298715643536894271714362895362971458871543962945628137
220 123456789457189326689237541214365897368791254795842163542673918831924675976518432
220 123456789457189326689237541298765413564913872731824695342571968876392154915648237
221 123456789457189326689273145214365897368791452795842631542618973836927514971534268
221 123456789457189326689273145298765431561834297734912568375628914842591673916347852
222 123456789457189326689273451214365897368791245795824163531648972876932514942517638
222 123456789457189326689273451298765143564391278731842695376928514845617932912534867
223 123456789457189326689273541214365897368791254795824163531648972876932415942517638
223 123456789457189326689273541298765413564321978731948652342617895876592134915834267
224 123456789457189326689327154214538697365792841798614235542861973836975412971243568
224 123456789457189326689327154296735841745891632831642597368274915574918263912563478
225 123456789457189326689327451214538697365791248978642135531864972742915863896273514
225 123456789457189326689327451298765143564931278731842695376298514815674932942513867
226 123456789457189326689327541214538697365792814798614235542871963836945172971263458
226 123456789457189326689327541298765413564813972731294865345671298876932154912548637
227 123456789457189326689372415214537698365891247798264531531648972876923154942715863
227 123456789457189326689372415298765143541238967736914852362891574874523691915647238
228 123456789457189326689372541214537698365891472798264135532648917876913254941725863
228 123456789457189326689372541298765413564913278731824695376298154815647932942531867
229 123456789457189326689723145214365897368297514795814263571648932836972451942531678
229 123456789457189326689723145298675431564831972731942568376598214845217693912364857
230 123456789457189326689723415214365897368297541795814263571648932836972154942531678
230 123456789457189326689723415298675143564831972731942568376518294845297631912364857
231 123456789457189326689732145214365897368297514975841263591678432742913658836524971
231 123456789457189326689732145298675431564321978731948652315897264876214593942563817
232 123456789457189326689732415214365897368297541975841632531978264742613958896524173
232 123456789457189326689732415298675143564321978731948652345297861876513294912864537
233 123456789457189326689732514214365897368947152975218463536824971742591638891673245
233 123456789457189326689732514298675431564391278731248695312964857876513942945827163
234 123456789457189326689732541214365897368297415975841632531978264742613958896524173
234 123456789457189326689732541298675413564813972731294865376928154845361297912547638
235 123456789457189326698237145214365897369718452875924613531872964742691538986543271
235 123456789457189326698237145286741593735968412941325678379612854514893267862574931
236 123456789457189326698237541214365897369718254875942163536874912742591638981623475
236 123456789457189326698237541289765413561394278734821695375948162816572934942613857
237 123456789457189326698273514214365897369748251785912463571894632842631975936527148
237 123456789457189326698273514289734651376591248514628973741962835865317492932845167
238 123456789457189326698273541214365897369718254875942613536894172742531968981627435
238 123456789457189326698273541289765413561348972734921865345617298812594637976832154
239 123456789457189326698732415214365897369847251875291634536924178742518963981673542
239 123456789457189326698732415289675143564321978731948562315864297842597631976213854
240 123456789457189326869372514214537698376298145985641237531864972698723451742915863
240 123456789457189326869372514298543671514768932736921845345617298672894153981235467
241 123456789457189623689237145214365897368792514795814236531648972876923451942571368
241 123456789457189623689237145298715364315864972746392851562971438871543296934628517
242 123456789457189623689237154214365897368792415795814236531648972876923541942571368
242 123456789457189623689237154298765431561843297734921568342618975876594312915372846
243 123456789457189623689273145214365897368792514975814236536928471742531968891647352
243 123456789457189623689273145298765431561834297734921568345618972876592314912347856
244 123456789457189623689273154214365897368792415795841236531627948872934561946518372
244 123456789457189623689273154298765431564931278731842965342618597876594312915327846
245 123456789457189623689273541214365897368791254795824136531648972876932415942517368
245 123456789457189623689273541298761354536948217714325968362894175871532496945617832
246 123456789457189623689327145214538967365792418978641532531874296742963851896215374
246 123456789457189623689327145298765431561843297734291568312974856876532914945618372
247 123456789457189623689327154214538967365794812978612435596241378742863591831975246
247 123456789457189623689327154298763541361542897574918362742635918836291475915874236
248 123456789457189623689372145214537896365891274978264351592618437746923518831745962
248 123456789457189623689372145298765431536214897741938562312647958874593216965821374
249 123456789457189623689372154214537896365891247978264315531648972742913568896725431
249 123456789457189623689372154298765431561843297734921568342618975876594312915237846
250 123456789457189623689372514214537896365298147978641352592863471746915238831724965
250 123456789457189623689372514298764351346521897715938246531297468874615932962843175
251 123456789457189623689723145214365897376894512895217436531642978768931254942578361
251 123456789457189623689723145298675314371248956546391278765832491834917562912564837
252 123456789457189623689723154214365897368947215795812436531678942872594361946231578
252 123456789457189623689723154298645371345917862761832495574261938836594217912378546
253 123456789457189623689723415214365897368917542795248361531894276872631954946572138
253 123456789457189623689723415298675134316294578574318296765832941842961357931547862
254 123456789457189623689723451214365897368947215795812364531678942872594136946231578
254 123456789457189623689723451296837514318645972574291836762918345831564297945372168
255 123456789457189623689723514214365897368947251795812346536291478871534962942678135
255 123456789457189623689723514298645137376291845541378962765832491834917256912564378
256 123456789457189623689723541214365897376891452598247136765934218831572964942618375
256 123456789457189623689723541298641357314975862765832194542318976836297415971564238
257 123456789457189623689732145214365897368947512975218436536824971742591368891673254
257 123456789457189623689732145298675431564391872731248956376514298815927364942863517
258 123456789457189623689732154214365897368947215795821436531678942872594361946213578
258 123456789457189623689732154298675431564391278731248596376824915815967342942513867
259 123456789457189623689732415214365897368917542975248136536824971742591368891673254
259 123456789457189623689732415298574361546391278731268594315927846874615932962843157
260 123456789457189623689732451214365897368947215795821364531678942872594136946213578
260 123456789457189623689732451298675314564321978731948562315864297876293145942517836
261 123456789457189623689732514214365897368971452795248361531894276872613945946527138
261 123456789457189623689732514298675431564391872731248956315864297876923145942517368
262 123456789457189623689732541214365897368974152795218436531897264872643915946521378
262 123456789457189623689732541298675314561394278734218965315827496876943152942561837
263 123456789457189623698237145214365897369748512785912364536894271842571936971623458
263 123456789457189623698237145289765431561943872734821596345672918812594367976318254
264 123456789457189623698237154214365897369874215785921436531748962846592371972613548
264 123456789457189623698237154289765431561943278734821596345692817812374965976518342
265 123456789457189623698237541214365897369874152875912436536728914742591368981643275
265 123456789457189623698237541289765314536841972714392865362974158845613297971528436
266 123456789457189623698273145214365897369817452785942361531628974842791536976534218
266 123456789457189623698273145289765431561834297734912568345691872812347956976528314
267 123456789457189623698273154214365897375918462986742531531694278762831945849527316
267 123456789457189623698273154289765431561934278734821596345692817812347965976518342
268 123456789457189623698327145214538967365792418879641352536874291742915836981263574
268 123456789457189623698327145289765431564831297731942568315694872842573916976218354
269 123456789457189623698327154214538967365791842789264315536912478842673591971845236
269 123456789457189623698327154289765431531942876746813592362574918874291365915638247
270 123456789457189623698327514214538967369271458785694231531942876846715392972863145
270 123456789457189623698327514289765431546213897731948256362571948815694372974832165
271 123456789457189623698372145214537896365891472789264351536728914842913567971645238
271 123456789457189623698372145289765431561943278734821596312594867845637912976218354
272 123456789457189623698372154214537896365891472789264315536728941842913567971645238
272 123456789457189623698372154289765431564213897731894562315948276842637915976521348
273 123456789457189623698732145214365897369874512785291364531948276846527931972613458
273 123456789457189623698732145289675314374218956516394278765823491831947562942561837
274 123456789457189623698732154214365897375918462986274531531697248762843915849521376
274 123456789457189623698732154289617435316594278745823916562978341834261597971345862
275 123456789457189623698732415214365897369874152785291364531948276846527931972613548
275 123456789457189623698732415289645371374218956516397248765823194831974562942561837
276 123456789457189623698732514214365897375948162986217345531824976762591438849673251
276 123456789457189623698732514289645137376291845514378962765823491842917356931564278
277 123456789457189623698732541214365897369874215785921364531248976846597132972613458
277 123456789457189623698732541289617435316594278745823916571948362862375194934261857
278 123456789457189623869237145214365897375892416698714352531628974782943561946571238
278 123456789457189623869237145298765431641328597735941268384572916516894372972613854
279 123456789457189623869273145214365897376894512985712436591628374638947251742531968
279 123456789457189623869273145298761534536948217741325896312597468674832951985614372
280 123456789457189623869273154214365897538947261976821435342518976691732548785694312
280 123456789457189623869273154298764315546321978731598246315947862674832591982615437
281 123456789457189623869273451214365897375892146698714235531648972782931564946527318
281 123456789457189623869273451298761534536948172741325896315697248674832915982514367
282 123456789457189623869327154214538967376291548985674312591843276638712495742965831
282 123456789457189623869327154298765431635214897741938562316842975572691348984573216
283 123456789457189623869372145214537896376298514985641237592863471631724958748915362
283 123456789457189623869372145298765431645831972731294856386517294512948367974623518
284 123456789457189623869372154214537896376891245985624317598713462631245978742968531
284 123456789457189623869372154298763541346521978715948236571894362634215897982637415
285 123456789457189623896237145214365897368972514579841236642713958781594362935628471
285 123456789457189623896237145289715364531964278674823951315678492742591836968342517
286 123456789457189623896237154214365897375891462968724531531948276649572318782613945
286 123456789457189623896237154289741365645823971731695842372964518514378296968512437
287 123456789457189623896237415214365897368972541579841236642713958781594362935628174
287 123456789457189623896237415289745361534961278671823954345678192712594836968312547
288 123456789457189623896237451214365897378941562965728134531894276649572318782613945
288 123456789457189623896237451289741536645823197731695842378964215514372968962518374
289 123456789457189623896237514214365897368792451579814362642571938785923146931648275
289 123456789457189623896237514268974135371865492945312867534691278682743951719528346
290 123456789457189623896237541214365897375892416968714352531628974649571238782943165
290 123456789457189623896237541289745136534691872671823495318572964762914358945368217
291 123456789457189623896327145214538967365792418978641532531874296689215374742963851
291 123456789457189623896327145289765431645231897731948562362574918514893276978612354
292 123456789457189623896327154214538967379642518568791432682914375745263891931875246
292 123456789457189623896327154289765431645231897731948562378612945514893276962574318
293 123456789457189623896327415214538967365791248789642531572863194648915372931274856
293 123456789457189623896327415289765341635241978741893256368574192514932867972618534
294 123456789457189623896327451214538967379642518685791234568914372742863195931275846
294 123456789457189623896327451289765314645213897731894562362571948514938276978642135
295 123456789457189623896327514214538967375691248689742351561873492742915836938264175
295 123456789457189623896327514289765431641893257735241968312574896564918372978632145
296 123456789457189623896372145214537896365891472789264351572643918648915237931728564
296 123456789457189623896372145289765431645231897731894562318947256574623918962518374
297 123456789457189623896372154214537896365891247978264315539728461681943572742615938
297 123456789457189623896372154289765431534921867671843295345618972762594318918237546
298 123456789457189623896372451214537896365894172978261534531948267682713945749625318
298 123456789457189623896372451289763514645918372731524968312647895564891237978235146
299 123456789457189623968327145214538967375694218689271534531742896792863451846915372
299 123456789457189623968327145296875431741932568835641972312794856579268314684513297
300 123456789457189623968327154214538967389761542675942831531874296746295318892613475
300 123456789457189623968327154296875431741293865835641972312968547589734216674512398
301 123456789457189623968327415214538967579642831836791254342875196685914372791263548
301 123456789457189623968327415296875341745631892831294567384512976519768234672943158
302 123456789457189623968372145214537896376894512589621437631245978742968351895713264
302 123456789457189623968372145285793461631248597749561238314825976592637814876914352
303 123456789457189623968372154214537896376891245895624317589713462631245978742968531
303 123456789457189623968372154296837541735241968841695372374518296512964837689723415
304 123456789457189623986327145214538967379642518865791234531274896648915372792863451
304 123456789457189623986327145298745361564213897731968452342691578675832914819574236
305 123456789457189623986327154214538967579642318638791542341875296795264831862913475
305 123456789457189623986327154298745361534691278671832945365978412742513896819264537
306 123456789457189623986327415214538967379264158865791342531942876642873591798615234
306 123456789457189623986327415298745361534691278671832954365214897749568132812973546
307 123456789457189623986327451214538967379642518865791234531274896648915372792863145
307 123456789457189623986327451269741538541638297738592146312864975695273814874915362
308 123456789457189623986327514214538967739612845865974231398761452572843196641295378
308 123456789457189623986327514298745361534691278671832945315274896749568132862913457
309 123456789457189623986327541214538967539674218678291435391742856745863192862915374
309 123456789457189623986327541298745136534691872671832495365978214742513968819264357
310 123456789457189632689237145214365897376892451598741263745623918831974526962518374
310 123456789457189632689237145298714563314625978765398421536972814871543296942861357
311 123456789457189632689273145214365897368794251795821463531647928876932514942518376
311 123456789457189632689273145298765314374891526561324978736548291815932467942617853
312 123456789457189632689273154214365897395827461768914325572648913831792546946531278
312 123456789457189632689273154298765413564831297731942568376594821815327946942618375
313 123456789457189632689273514214365897395718426768942351572894163831627945946531278
313 123456789457189632689273514298765143365914278741328956574632891836591427912847365
314 123456789457189632689327154214538967536794218978612543362871495745963821891245376
314 123456789457189632689327154298715463315264897764893521576931248831542976942678315
315 123456789457189632689372145214537896365891274978624513531248967746915328892763451
315 123456789457189632689372145298765314546231897731894526315947268874623951962518473
316 123456789457189632689372154214537896378964521965218473591843267742695318836721945
316 123456789457189632689372154298765413376214895514938267762591348845623971931847526
317 123456789457189632689723145214365897738914526965278314346591278592837461871642953
317 123456789457189632689723145298675413364218597571934268736591824845362971912847356
318 123456789457189632689723514214365897395847261876291345531978426748612953962534178
318 123456789457189632689723514298675143561394278734218956312947865876532491945861327
319 123456789457189632689732145214365897768941253935278461346527918571894326892613574
319 123456789457189632689732145298675413536841297741293568312967854865324971974518326
320 123456789457189632689732154214365897378914265596278413745691328831527946962843571
320 123456789457189632689732154298675413561394278734218596312947865876523941945861327
321 123456789457189632689732514214367895378594126965218473592671348746823951831945267
321 123456789457189632689732514298675143561394278734218956312947865876523491945861327
322 123456789457189632689732541214365897736894215895217463362978154571643928948521376
322 123456789457189632689732541298675413531924867746318295362897154815243976974561328
323 123456789457189632698237145214368597536972814879514263362845971745691328981723456
323 123456789457189632698237145289765314365914827741328596512643978874591263936872451
324 123456789457189632698237154214365897539874261876912543362748915745691328981523476
324 123456789457189632698237154289765413531842976746913528362574891874391265915628347
325 123456789457189632698237514214365897735891426986724351362948175579613248841572963
325 123456789457189632698237514289765143536914278741328965365872491874591326912643857
326 123456789457189632698273145214365897586917324739842516345691278862734951971528463
326 123456789457189632698273145289764513536918427741532968365891274874625391912347856
327 123456789457189632698327145214538976736291458985764321369842517572613894841975263
327 123456789457189632698327145289765314346918257571243968765832491812694573934571826
328 123456789457189632698327154214538976536974821879261345361842597745693218982715463
328 123456789457189632698327154289764315364512978571938426736845291812693547945271863
329 123456789457189632698327541214563897539718264786294153365972418842631975971845326
329 123456789457189632698327541289765413346918257571243968765832194812694375934571826
330 123456789457189632698372154214537896736891425985264317369728541571943268842615973
330 123456789457189632698372154289765413346821975571934826712693548865247391934518267
331 123456789457189632698732145214365978576891324839274516345927861761548293982613457
331 123456789457189632698732145289675413536841297741293568312967854865324971974518326
332 123456789457189632698732514214365978586917243739824165342691857865273491971548326
332 123456789457189632698732514289675143374291865516348297765914328842563971931827456
333 123456789457189632869273145214368597678945213935712864382697451591824376746531928
333 123456789457189632869273145298765314634891527715324968342917856571648293986532471
334 123456789457189632869372145214537896638294517795861324346728951572913468981645273
334 123456789457189632869372145298763514634215897715948263346521978571894326982637451
335 123456789457189632896237145214375896765948213938612574342761958579823461681594327
335 123456789457189632896237145289764513641593278735821496364972851572318964918645327
336 123456789457189632896237415214375896765918243938642571342761958579823164681594327
336 123456789457189632896237415289765341364912857715348926578623194642891573931574268
337 123456789457189632896327145214538976635974821978261453389712564561843297742695318
337 123456789457189632896327145289765314635241978741938526318594267574612893962873451
338 123456789457189632896327154214563897738291546965748213389612475572834961641975328
338 123456789457189632896327154289765413634218597715943268348671925562894371971532846
339 123456789457189632896327451214563978578942163639718524342671895781295346965834217
339 123456789457189632896327451289765314635241978741938526318594267574612893962873145
340 123456789457189632896327541214538976568792413739641258342915867685273194971864325
340 123456789457189632896327541289764315645213978731895426368571294572948163914632857
341 123456789457189632896372145214593867635718294978264513382645971561937428749821356
341 123456789457189632896372145289764513614935278735821496342597861578613924961248357
342 123456789457189632896372154214537896738964521965218473389741265571623948642895317
342 123456789457189632896372154289764315645913278731825946312648597578291463964537821
343 123456789457189632896372451214537896738964125965218347389721564572643918641895273
343 123456789457189632896372451289765314364291578715834926572948163641523897938617245
344 123456789457189632968327145214568973679243851835791264392874516581632497746915328
344 123456789457189632968327145296875314735914826841632597379261458512748963684593271
345 123456789457189632968327154214568973689732541735914268396871425571243896842695317
345 123456789457189632968327154296875413574631928831942576312794865645218397789563241
346 123456789457189632968327451214578396689243175735691824392714568571862943846935217
346 123456789457189632968327451296745318374218596581693247639874125715932864842561973
347 123456789457189632986327145214978356735264891869513274398641527571892463642735918
347 123456789457189632986327145298764513645831297731592864369278451512643978874915326
348 123456789457289163689173452231564897568397241974812635312645978745928316896731524
348 123456789457289163689173452294861537365947218718325946536794821871532694942618375
349 123456789457289163689713254231564897568197342974328516345971628716842935892635471
349 123456789457289163689713254296845317315697842874132695531978426768524931942361578
350 123456789457289163698137425231564897569718342874392651382941576745623918916875234
350 123456789457289163698137425285974631364521978971368254516892347739645812842713596
351 123456789457289163698137524231564897574892316869713452312675948786941235945328671
351 123456789457289163698137524286975431745813296931642857319728645572364918864591372
352 123456789457289163698317254231564897574928631869173425312845976785691342946732518
352 123456789457289163698317254286931547534762891719845326362574918845193672971628435
353 123456789457289163698317524231564897574928631869173452315842976782691345946735218
353 123456789457289163698317524285931647374568291916724358531892476769145832842673915
354 123456789457289163698713254231564897569871342874392516386147925745928631912635478
354 123456789457289163698713254286395471345167928971842635512978346769534812834621597
355 123456789457289163869713245231564897574892316986371452315647928642938571798125634
355 123456789457289163869713245298675431641832597735194628386527914512948376974361852
356 123456789457289163869731245231564897574892316986173452312645978648927531795318624
356 123456789457289163869731245298675431634192578715843926382514697576928314941367852
357 123456789457289163869731524231564897574892316986173452315927648642318975798645231
357 123456789457289163869731524298675431645193278731842956382514697574968312916327845
358 123456789457289163896317245231564897574928316689173452312895674745631928968742531
358 123456789457289163896317245289764531534921678671538492345692817712843956968175324
359 123456789457289163896731524231564897568397412749128356384612975615973248972845631
359 123456789457289163896731524261948375745312896938567412389675241512894637674123958
360 123456789457289613689173245231564897765891324894327561312645978576918432948732156
360 123456789457289613689173245296831457315647892748592361531768924872914536964325178
361 123456789457289613689713245231564897568971324974328156315847962746192538892635471
361 123456789457289613689713245296875134741392568835641972318527496574968321962134857
362 123456789457289613689713254231564897568971342974328561345697128716842935892135476
362 123456789457289613689713254296875341348961572715342968531628497872594136964137825
363 123456789457289613698137254231564897574918362869372541345621978716893425982745136
363 123456789457289613698137254286975341731864592945321867369718425512643978874592136
364 123456789457289613698317245231564897574928136869173524316792458742835961985641372
364 123456789457289613698317245286974351735861492941532867312645978569728134874193526
365 123456789457289613698317254231564897574928136869173425316792548742835961985641372
365 123456789457289613698317254286975341319842567574163892762594138845731926931628475
366 123456789457289613698713245231564897574892136869371524315927468742638951986145372
366 123456789457289613698713245286974351349521867715638492562897134871345926934162578
367 123456789457289613869713245231564897678391524945872361382147956594638172716925438
367 123456789457289613869713245298671534635894172741532896372145968584967321916328457
368 123456789457289613869731245231564897678193524945872361316925478584617932792348156
368 123456789457289613869731245298675134614893527735142968382917456571364892946528371
369 123456789457289613869731254231564897586973421974128536342817965698345172715692348
369 123456789457289613869731254298645371631897542745312968382574196516928437974163825
370 123456789457289613896137245231564897574928136689371524312695478745813962968742351
370 123456789457289613896137245289745361365812497741693852538924176612578934974361528
371 123456789457289613896137254231564897574928361689371425318792546742615938965843172
371 123456789457289613896137254289745361645813972731692548368971425512364897974528136
372 123456789457289613896317245231564897574938126689172534368741952742895361915623478
372 123456789457289613896317245289745136345621978761893524578164392612938457934572861
373 123456789457289613896317425231564897574928136689173542312745968748692351965831274
373 123456789457289613896317425289745136641832597735691842364528971512974368978163254
374 123456789457289613896731245231564897574928361689173524312645978748392156965817432
374 123456789457289613896731245289643571645817392731592864364175928512968437978324156
375 123456789457289613896731254231564897574928361689173542315642978748395126962817435
375 123456789457289613896731254289643175574812936631597428312968547765324891948175362
376 123456789457289613968137245231564897649871352785923461396718524574692138812345976
376 123456789457289613968137245296871534571943862834562971315628497649715328782394156
377 123456789457289613968137254231564897689371542745928361316795428574812936892643175
377 123456789457289613968137254295813476671924835834675921316748592589362147742591368
378 123456789457289613968731245231564897689173452745928361314697528576812934892345176
378 123456789457289613968731245296817534571342896834695127312564978689173452745928361
379 123456789457289613986137245231564897698371452745928361364715928579842136812693574
379 123456789457289613986137245298713564631524897745968321312645978569871432874392156
380 123456789457289631689173245231567894768914523945328167372645918596831472814792356
380 123456789457289631689173245246891573871532496935647128362914857594768312718325964
381 123456789457289631689713254231564897745928163896371425312645978578192346964837512
381 123456789457289631689713254296845317745132968831697542312574896568921473974368125
382 123456789457289631698317254231564897574928316869173425316792548745831962982645173
382 123456789457289631698317254286945173745163892931728465364892517572631948819574326
383 123456789457289631869713245231564897678391524945872163386147952514928376792635418
383 123456789457289631869713245298564317631978452745321968382695174574132896916847523
384 123456789457289631869713254231564897694378125785921463312645978578192346946837512
384 123456789457289631869713254298645173631897542745132968316978425574321896982564317
385 123456789457289631869731245231564897698173452745928163316892574582347916974615328
385 123456789457289631869731245298317456315642978674895123586174392731928564942563817
386 123456789457289631869731254231564897698173425745928163312897546576342918984615372
386 123456789457289631869731254298317465315642897674895312586174923731928546942563178
387 123456789457289631896137245231564897689371452745928163318692574562743918974815326
387 123456789457289631896137245289645173534871926761923458312594867645718392978362514
388 123456789457289631896137254231564897689371425745928163318792546572643918964815372
388 123456789457289631896137254289715346531648972674392815342861597715923468968574123
389 123456789457289631896137425231564897689371254745928163318792546572643918964815372
389 123456789457289631896137425289371546631524897745968312312645978574892163968713254
390 123456789457289631896317245231564897689173452745928163318745926562891374974632518
390 123456789457289631896317245285741963631892574749635812312978456568124397974563128
391 123456789457289631896317254231564897689173425745928163318645972572891346964732518
391 123456789457289631896317254285641973649735128731892546312978465568124397974563812
392 123456789457289631896731245231564897574928316689173524315642978748395162962817453
392 123456789457289631896731245285317964641892573739645812312968457578124396964573128
393 123456789457289631968137254245918376631574928789623415314862597576391842892745163
393 123456789457289631968137254295713468736894512841562397312975846584621973679348125
394 123456789457289631968731245231564897689317452745928163314875926596142378872693514
394 123456789457289631968731245284615397631897524795342816346978152579123468812564973
396 123456789457289631986137245231645897698713524745892316312564978574928163869371452
396 123456789457289631986137245248615973695743128731892456312978564579364812864521397
399 123456789457389612896127354231564978649718523785932146372645891568291437914873265
399 123456789457389612896127354231645978649871523785293146378564291562918437914732865
401 123456789457389612896172354285793146631524978749618523312945867568237491974861235
401 123456789457389612896172354285793146631524978749618523312945867568237491974861235
405 123456789457389612896271354281537946645928173739164528312645897568792431974813265
405 123456789457389612896271354289564173641937528735128946312645897568792431974813265
407 123456789457389612896721354231564978649178523785932146312645897568297431974813265
407 123456789457389612896721354239564178641978523785132946312645897568297431974813265
411 123456789457389621896217354268174593745938162931562847382641975574893216619725438
411 123456789457389621896217354268741593745893162931625847382164975574938216619572438
416 123456789457893612986217354274538196531964827698721435342685971715349268869172543
416 123456789457893612986217354274538196531964827698721435342685971715349268869172543
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby coloin » Tue Feb 06, 2007 9:12 pm

Fine work by gsf

I had made a few erroneous assumptoions....

In trying to estimate the upper limit of 416 codes I made an assumption that a 416 band in B1B2B3 along with another 416 band in B1B4B7 would give essentially the same number of solutions. This is infact true there are only 2865 essentially different B1B2B3B4B7 combinations - however I dont think you can also assume that that they will have the same grid solutions/respective 416 codes.

Couting the duplicates is also rubbish - we cant assume that every grid will have the same number of duplicate grids per coding.

There appears to be many different grids with initial bands 1-31 which have identical codes.
Not so many from 32-onwards - I hadnt appreciated the duplicates in the "isohex" grids...

C
coloin
 
Posts: 1638
Joined: 05 May 2005

Postby Red Ed » Tue Feb 06, 2007 9:48 pm

coloin wrote:there are only 2865 essentially different B1B2B3B4B7 combinations
No, there are a heck of a lot more than that. "Essentially" same/different is a term we've always used to describe ismorphism classes: so there are "essentially" only 416 arrangements of B123 and essentially (don't know, but lots) arrangements of B12347. The 2865 number, on the other hand, is a "gangster" count, like the 44 number: it sees minirows (in B4/7) and minicolumns (in B2/3) as unordered triples, not ordered triples, which makes it a lot easier to put two arrangements in the same class.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby gsf » Tue Feb 06, 2007 11:35 pm

the band counting finished
the program counted each of the 5472730538 grids with each one in hand
so this is a different (and much slower) verification of the number of distinct grids
I didn't have the per grid encoder done so I'll have to rerun to build a catalog of all grids
the encoder can get 9 bytes per grid partitioned into files with the same initial band
so the whole catalog would be 46Gi and allow direct indexing to each grid
the largest would be band 006 at 826Mi

generating the catalog by minlex bands is straightforward
start with a band and start filling in values in minlex order
when all values are filled in check if the grid is minlex
if it is then it is one of the 5472730538 grids up to isomorphism
otherwise it has a smaller minlex representation and would be counted either earlier in the
current band or in a smaller band

edit I forgot to mention that filling in the band in the opposite order can
be used to find the max min-lex value for a band -- this is how I posted the min and max
min-lex values for each band way before the total counts came in

this is neat because each grid is esentially compared with itself
there is no direct comparison with previous or future grids
i.e., no need to have a lookup table of all grids to check if the current grid is a dup
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Red Ed » Wed Feb 07, 2007 2:32 pm

Very nice! I've not seen the catalogue constructed directly before. That'll put you in a good position the next time a "what's the most number of X in any grid?" question comes along.

Surprised to see mebibytes and gibibytes in your message. I hope you've not been involved in any lawsuits !:D
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby gsf » Wed Feb 07, 2007 2:43 pm

Red Ed wrote:Very nice! I've not seen the catalogue constructed directly before. That'll put you in a good position the next time a "what's the most number of X in any grid?" question comes along.

when its done it would be nice to find a host for the 46Gi
I'll post the decoder code in a bit
Red Ed wrote:Surprised to see mebibytes and gibibytes in your message. I hope you've not been involved in any lawsuits !:D

no lawsuits, but bowing to lawyers of another sort (iso, posix)
it really does make sense, just takes a week or so to get used to
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby udosuk » Wed Feb 07, 2007 3:14 pm

gsf wrote:when its done it would be nice to find a host for the 46Gi

A few months ago I initiated a discussion about minimalization/compression of solution grids in this thread... I wonder if those schemes from RW etc would be helpful to trim this huge size of 46Gi down to xxx Mi's?:?: It'd be much nicer to pack the whole catalogue in less than 700MB or 4.7GB so it can be burnt into a single CD/DVD...
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gsf » Wed Feb 07, 2007 6:55 pm

udosuk wrote:
gsf wrote:when its done it would be nice to find a host for the 46Gi

A few months ago I initiated a discussion about minimalization/compression of solution grids in this thread... I wonder if those schemes from RW etc would be helpful to trim this huge size of 46Gi down to xxx Mi's?:?: It'd be much nicer to pack the whole catalogue in less than 700MB or 4.7GB so it can be burnt into a single CD/DVD...

the 46Gi is for each of the 416 bands in a separate file, 9 byte header + 9 bytes (81 bits) per grid
fixing each grid at 9 bytes allows random access given an index from 1 to 5B

if random access is dropped then it can be reduced to ~6.8 bytes (54.2 bits) per grid for a total of ~35Gi

back of the envelope: 5472730538 into 4.7Gi is < 1 byte per puzzle -- none of the discussions ever got that close
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby udosuk » Thu Feb 08, 2007 6:11 am

gsf wrote:back of the envelope: 5472730538 into 4.7Gi is < 1 byte per puzzle -- none of the discussions ever got that close

Thanks gsf... Very thoughtful calculation...:)
udosuk
 
Posts: 2698
Joined: 17 July 2005

Postby gsf » Fri Feb 09, 2007 4:48 pm

udosuk wrote:
gsf wrote:back of the envelope: 5472730538 into 4.7Gi is < 1 byte per puzzle -- none of the discussions ever got that close

Thanks gsf... Very thoughtful calculation...:)

well, it turns out we can use a smaller envelope for our calculations ...

as this deals directly with minlex grids I'll hijack the duscussion here

if we're talking about compressing a large grid catalog (and I am: all essentially different grids)
then the discussion to this point has been much too local

let each grid be a minlex record of 81 data bytes, with all records sorted in ascending order
the difference between adjacent grids, especially in the lower bands, is very small on average
coding a compressor to take advantage of the differences can be a big win
burrows-wheeler (bzip2) does this, and does better than gzip, but doesn't take advantage
of the sudoku grid domain
i.e., there are both lexical and functional similatrities between adjacent grids
and off the shelf compressors for the most part only handle lexical similarities well
some of the sudoku specific similarities are
(1) first 28 minlex digits can be represented as 416 bands
(2) the remaining digits can be specified w.r.t. the basic sudoku constraints (~singles)

(1) is a sudoku specific lexical insight
(2) is a functional insight

I set up a coder to compress into windows of 1Mi
data compressed is <band index, #automorphisms, grid> for each grid
early bands compress well just using the sudoku specific lexical similarities and functional info
but it turns out that burrow-wheeler on the sudoku specific coding can get another factor of 2 for the lower (and more populated) bands

here are the number of bytes per grid for a few bands
sudz: sudoku specific coding, sudz+bw: sudz followed by (modified) burrows wheeler
Code: Select all
bands   grids     sudz  sudz+bw
006     96229042  1.66  0.74
100     27849953  1.92  1.21
150     11577852  2.17  1.44
300-416  2097068  3.51  2.78


more info later, including the sudoku specific coder, when the bands complete
sometime next week
gsf
2014 Supporter
 
Posts: 7306
Joined: 21 September 2005
Location: NJ USA

Postby Mauricio » Mon Feb 12, 2007 9:02 pm

daj95376 wrote:I favor this (extended) Canonical Form that (I believe) was proposed by JPF somewhere in this forum. I (sometimes) use it to generate puzzles.
Code: Select all
123|4..|...
456|...|...
789|...|4..
---+---+---
.4.|...|...
...|...|.4.
...|..4|...
---+---+---
..4|...|...
...|.4.|...
...|...|..4



It is easy to see what daj95376/JPF say. It is harder to see that every sudoku grid is isomorph to a grid with the following 18 fixed cells:
Code: Select all
123|...|...
456|12.|...
789|...|1..
---+---+---
.1.|...|...
...|.1.|...
...|...|.1.
---+---+---
..1|...|...
...|..1|...
...|...|..1

The difficult part is to see that we can set r2c5=2.

Proof: First fix the 1's and relabel the numbers in the first box, so that they match the proposed solution, now we want to set r2c5=2.
We analize the possible places to put 2 and 3 in box 2:
1. If r2c5=2, good, we are done.
2. If r2c6=2, then:
2.1 If r3c8=2, then do r123456789 c123456789 -> r132465798 c123789456 and relabel accordingly so now r2c5=2.
2.2 If r3c9=2 then do r123456789 c123456789 -> r231564897 c465798132 and relabel accordingly.
3. If r2c5=3 or r2c6=3 then swap columns 2 and 3 and relabel so now that 3 is a 2, now we are in a case that has been covered in steps 2.1 and 2.2.
4. If r2c5<>2,3 and r2c6<>2,3, then we start again, but instead of fixing the 1's, we fix the 2's and we are done (after that litle work is needed here).

In daj95376/JPF example there are 17 fixed cells, I showed that we can fix 18 cell's. Can we fix more than 18 cells?
Mauricio
 
Posts: 1174
Joined: 22 March 2006

PreviousNext

Return to General