The New Sudoku Players' Forum

by **JPF** » Sat Jan 27, 2007 7:25 pm

coloin wrote:If there can be a 2 at r2c4....why cant there be a 3 at r2c4 ?

Good question !
With 4M grids more, I didn't find any...

I will try to post an updated complete table soon.

JPF

by **coloin** » Sat Jan 27, 2007 7:52 pm

Here is a reference to the 416 page 4

kjellfp wrote:Before the counting, all 416-band groups were generated, and their symmetry group stored. I also store enough information making it possible to permute any band back to its class representative.

EDIT from page 25 on the sudoku maths kjellfp optimized the 3x3 enumeration
they also discussed automorphism - but i didnt understand it at the time !

I dont think the list has been published as such - i will look

Its here 44-gang
Of note the 44 labelling is different to Red Eds

The 416 labelling mirrors to a degree the min lex normalization, but some are ordered differently - a pity but it probably is worthwhile correcting.

It is likely , if we can correct this glitch, that we wil have a classification system for all essentially different grids.

I am awaiting kjellfp's response

Meanwhile my "bottom" grids out of a million were

Code: Select all: 378 378 414 , 405 405 416 587426193294381756631759428163294587842567319975138264726813945458972631319645872 381 408 411 , 400 402 407 264759183978431652513682749186975234395264871427813965851397426632148597749526318 386 404 404 , 390 399 402 659217438471983625238465917314798562567321849982654371825146793143579286796832154

It might be interesting to see what their min lex norm is ?

C

by **Red Ed** » Sat Jan 27, 2007 10:24 pm

I can't tell from this thread if you(*) understand how bands are grouped into 416 classes. In short: it's just a partition of the 9! x 46656 x 56 possible bands into isomorphism classes. On average, a band is isomorphic to ~6280 others, only one of which is used to represent any given class. For an alternative explanation, see section 2.2 of Bertram and Frazer's paper. Or if you knew all this already then apologies for wasting bandwidth.

There's something else I can't tell from this thread: what are you trying to do? Are you just trying to list all the cells in the whole grid whose values never change in min-lex canonicalisation? If so then a quick enumeration of the 416 band classes in min-lex form tells you that the top band must be

Code: Select all: 123|456|789 45.|...|... ...|...|...

where '.' means "value not fixed". Beyond that (that is, in the next two bands) I would be surprised if you could fix many cell values.

(* you = any contributors to this thread; I'm not directing this at coloin in particular)

by **coloin** » Sat Jan 27, 2007 10:45 pm

Thanks Ed
Except perhaps not quite....
Possibly there might be at least 5 bands of the 416 which wont appear in the first band ?

The index416 could well be used to classify our different grids - hoewever the glitch where it confuses two different [but similar grids] is caused by an over reduction in those bands with repeating minirows.

These are [probably] the bands as defined by the index416 program .... EDIT - these are differnt from the minlex list which gsf used

Hidden Text: Show

Code: Select all: 1 123456789456789123789123456 2 123456789456789123789123465 3 123456789456789123789123645 4 123456789456789123789132465 5 123456789456789123789132564 6 123456789456789123789213465 7 123456789456789123789231564 8 123456789456789123789231645 9 123456789456789123798132546 10 123456789456789123798132564 11 123456789456789123798213564 12 123456789456789123798213654 13 123456789456789123798231564 14 123456789456789123798312564 15 123456789456789123879213546 16 123456789456789123897231564 17 123456789456789123897231645 18 123456789456789132789123546 19 123456789456789132789132654 20 123456789456789132789213654 21 123456789456789132789231456 22 123456789456789132789231564 23 123456789456789132789321564 24 123456789456789132798213456 25 123456789456789132798231546 26 123456789456789132879231564 27 123456789456789231789123645 28 123456789456789231789132546 29 123456789456789231789231564 30 123456789456789231789312456 31 123456789456789231798312654 32 123456789457189236689237514 33 123456789457189236689273541 34 123456789457189236689327154 35 123456789457189236689327514 36 123456789457189236689327541 37 123456789457189236689372451 38 123456789457189236689372514 39 123456789457189236689723154 40 123456789457189236689723415 41 123456789457189236689723451 42 123456789457189236689732514 43 123456789457189236689732541 44 123456789457189236698237145 45 123456789457189236698237415 46 123456789457189236698273145 47 123456789457189236698273415 48 123456789457189236698273541 49 123456789457189236698327145 50 123456789457189236698372145 51 123456789457189236698372541 52 123456789457189236869237415 53 123456789457189236869327514 54 123456789457189236869372415 55 123456789457189236869732145 56 123456789457189236869732451 57 123456789457189236869732541 58 123456789457189236896237145 59 123456789457189236896237415 60 123456789457189236896237514 61 123456789457189236896372145 62 123456789457189236896372154 63 123456789457189236896723451 64 123456789457189236896723514 65 123456789457189236896732415 66 123456789457189236968237154 67 123456789457189236968273145 68 123456789457189236968327154 69 123456789457189236968327514 70 123456789457189236968372514 71 123456789457189236968732154 72 123456789457189236968732541 73 123456789457189236986237514 74 123456789457189236986273541 75 123456789457189236986327154 76 123456789457189236986327415 77 123456789457189236986327451 78 123456789457189236986372154 79 123456789457189236986372451 80 123456789457189236986372514 81 123456789457189263689237145 82 123456789457189263689237514 83 123456789457189263689273154 84 123456789457189263689273415 85 123456789457189263689273451 86 123456789457189263689273514 87 123456789457189263689723415 88 123456789457189263689732514 89 123456789457189263698327415 90 123456789457189263698372154 91 123456789457189263698723451 92 123456789457189263698732154 93 123456789457189263698732415 94 123456789457189263698732541 95 123456789457189263869273145 96 123456789457189263869273451 97 123456789457189263869273514 98 123456789457189263869327514 99 123456789457189263869372415 100 123456789457189263869372451 101 123456789457189263869723415 102 123456789457189263869732145 103 123456789457189263869732451 104 123456789457189263896372145 105 123456789457189263896723541 106 123456789457189263896732154 107 123456789457189263896732451 108 123456789457189263968237514 109 123456789457189263968237541 110 123456789457189263968273154 111 123456789457189263968273415 112 123456789457189263968273451 113 123456789457189263968327145 114 123456789457189263968327514 115 123456789457189263968372145 116 123456789457189263968372451 117 123456789457189263968723451 118 123456789457189263968723514 119 123456789457189263968732451 120 123456789457189263986237514 121 123456789457189263986327514 122 123456789457189263986372451 123 123456789457189263986372541 124 123456789457189263986723514 125 123456789457189263986732154 126 123456789457189263986732541 127 123456789457189326689237154 128 123456789457189326689237451 129 123456789457189326689273154 130 123456789457189326689273451 131 123456789457189326689273514 132 123456789457189326689327154 133 123456789457189326689372541 134 123456789457189326689723145 135 123456789457189326689732415 136 123456789457189326689732541 137 123456789457189326698237541 138 123456789457189326698372154 139 123456789457189326869237514 140 123456789457189326869237541 141 123456789457189326869273451 142 123456789457189326869273541 143 123456789457189326869327451 144 123456789457189326869723541 145 123456789457189326869732415 146 123456789457189326896237415 147 123456789457189326986273145 148 123456789457189326986327451 149 123456789457189362689237541 150 123456789457189362689327154 151 123456789457189362689327415 152 123456789457189362689723154 153 123456789457189362689723451 154 123456789457189362689723514 155 123456789457189362698237415 156 123456789457189362698327514 157 123456789457189362869237514 158 123456789457189362869327415 159 123456789457189362896372451 160 123456789457189362968372514 161 123456789457189362986237514 162 123456789457189362986273154 163 123456789457189623689273541 164 123456789457189623689327154 165 123456789457189623689372514 166 123456789457189623689723154 167 123456789457189623689723415 168 123456789457189623689723451 169 123456789457189623689723514 170 123456789457189623689732415 171 123456789457189623698237154 172 123456789457189623698273145 173 123456789457189623698273514 174 123456789457189623698327514 175 123456789457189623698327541 176 123456789457189623698372154 177 123456789457189623698723145 178 123456789457189623698723154 179 123456789457189623698723514 180 123456789457189623698732154 181 123456789457189623698732514 182 123456789457189623869273145 183 123456789457189623869273451 184 123456789457189623869372415 185 123456789457189623869732451 186 123456789457189623869732541 187 123456789457189623896237451 188 123456789457189623896237514 189 123456789457189623896327145 190 123456789457189623896327451 191 123456789457189623896327514 192 123456789457189623896723154 193 123456789457189623896723415 194 123456789457189623896723541 195 123456789457189623896732145 196 123456789457189623896732451 197 123456789457189623896732514 198 123456789457189623968327415 199 123456789457189623968723154 200 123456789457189623986327145 201 123456789457189623986327415 202 123456789457189623986327451 203 123456789457189623986327514 204 123456789457189623986372145 205 123456789457189623986723145 206 123456789457189623986732415 207 123456789457189632689237145 208 123456789457189632689273154 209 123456789457189632689327154 210 123456789457189632689327514 211 123456789457189632689372145 212 123456789457189632689723415 213 123456789457189632689723514 214 123456789457189632689732415 215 123456789457189632689732541 216 123456789457189632698372145 217 123456789457189632698732541 218 123456789457189632869327145 219 123456789457189632869327154 220 123456789457189632896237145 221 123456789457189632896237415 222 123456789457189632896273451 223 123456789457189632896327451 224 123456789457189632896372415 225 123456789457189632896732541 226 123456789457189632968237415 227 123456789457189632968273154 228 123456789457189632968327154 229 123456789457189632968327415 230 123456789457189632968372145 231 123456789457189632986237154 232 123456789457189632986237451 233 123456789457189632986273415 234 123456789457189632986327145 235 123456789457189632986372154 236 123456789457198236689237451 237 123456789457198236689273154 238 123456789457198236689327154 239 123456789457198236689372154 240 123456789457198236698723415 241 123456789457198236698732415 242 123456789457198236869273541 243 123456789457198236869723154 244 123456789457198236869732145 245 123456789457198236896273154 246 123456789457198236896372541 247 123456789457198236968237451 248 123456789457198236986237154 249 123456789457198236986237415 250 123456789457198236986273415 251 123456789457198236986723415 252 123456789457198236986732541 253 123456789457198263689732154 254 123456789457198263689732541 255 123456789457198263698327415 256 123456789457198263869327451 257 123456789457198263896237154 258 123456789457198263896237451 259 123456789457198263896327514 260 123456789457198263896732514 261 123456789457198263968273145 262 123456789457198263986237514 263 123456789457198263986327415 264 123456789457198263986732541 265 123456789457198326698732451 266 123456789457198326968723514 267 123456789457198326986372145 268 123456789457198362689237154 269 123456789457198362689237451 270 123456789457198362689723415 271 123456789457198362869273451 272 123456789457198362896732154 273 123456789457198623689237154 274 123456789457198623698237451 275 123456789457198623698372145 276 123456789457198623698372514 277 123456789457198623698732154 278 123456789457198623869327415 279 123456789457198623896237154 280 123456789457198623896237514 281 123456789457198623896273415 282 123456789457198623896723541 283 123456789457198623896732145 284 123456789457198623896732541 285 123456789457198623968237145 286 123456789457198623968372145 287 123456789457198623968723145 288 123456789457198623968732154 289 123456789457198623986732541 290 123456789457198632689327154 291 123456789457198632689732154 292 123456789457198632698237154 293 123456789457198632698327541 294 123456789457198632869237415 295 123456789457198632869237451 296 123456789457198632869327541 297 123456789457198632869372154 298 123456789457198632869723154 299 123456789457198632896237145 300 123456789457198632896237514 301 123456789457198632986237145 302 123456789457198632986237154 303 123456789457198632986372145 304 123456789457198632986732514 305 123456789457289136689713542 306 123456789457289136869731254 307 123456789457289136896371254 308 123456789457289136968137452 309 123456789457289136968137542 310 123456789457289163689173452 311 123456789457289163689713254 312 123456789457289163698137524 313 123456789457289163698173542 314 123456789457289163698317254 315 123456789457289163698713254 316 123456789457289163869317245 317 123456789457289163896137425 318 123456789457289163896317524 319 123456789457289163896731254 320 123456789457289163968317245 321 123456789457289163968731542 322 123456789457289316986137452 323 123456789457289316986137542 324 123456789457289361869713524 325 123456789457289361986173452 326 123456789457289613689173254 327 123456789457289613689317425 328 123456789457289613689371245 329 123456789457289613689371254 330 123456789457289613698317254 331 123456789457289613869173254 332 123456789457289613869173452 333 123456789457289613869713254 334 123456789457289613869731524 335 123456789457289613896317245 336 123456789457289613896731254 337 123456789457289613968731425 338 123456789457289613986137245 339 123456789457289613986173254 340 123456789457289613986173542 341 123456789457289613986731245 342 123456789457289631689137254 343 123456789457289631689173245 344 123456789457289631689713245 345 123456789457289631689731254 346 123456789457289631698371245 347 123456789457289631698371452 348 123456789457289631698713452 349 123456789457289631869713524 350 123456789457289631869731254 351 123456789457289631896137425 352 123456789457289631896317245 353 123456789457289631896317254 354 123456789457289631896371254 355 123456789457289631968137254 356 123456789457289631968317245 357 123456789457289631968731245 358 123456789457289631986137245 359 123456789457289631986731245 360 123456789457298136869173254 361 123456789457298136986317245 362 123456789457298316698137254 363 123456789457298361986731524 364 123456789457298613689137245 365 123456789457298613689713245 366 123456789457298613689731245 367 123456789457298613698713245 368 123456789457298613698731254 369 123456789457298613869317245 370 123456789457298613896137524 371 123456789457298613896317245 372 123456789457298613968713254 373 123456789457298613986371254 374 123456789457298631698731245 375 123456789457298631869713254 376 123456789457298631896137524 377 123456789457298631896713245 378 123456789457298631968713425 379 123456789457298631986137542 380 123456789457389126698172354 381 123456789457389126896127453 382 123456789457389126986721543 383 123456789457389162896217435 384 123456789457389162986712345 385 123456789457389162986721354 386 123456789457389216986127453 387 123456789457389261896217534 388 123456789457389261986127534 389 123456789457389261986721354 390 123456789457389612896127354 391 123456789457389612896172345 392 123456789457389612896172354 393 123456789457389612896271345 394 123456789457389612896712345 395 123456789457389612896712354 396 123456789457389612896721354 397 123456789457389612968127354 398 123456789457389612986127354 399 123456789457389621689127345 400 123456789457389621689721354 401 123456789457389621698127345 402 123456789457389621869127354 403 123456789457389621869721345 404 123456789457389621896172543 405 123456789457389621896217354 406 123456789457389621986271345 407 123456789457389621986721354 408 123456789457398216986217354 409 123456789457398612896127354 410 123456789457398612896172354 411 123456789457398612896217354 412 123456789457839612896271345 413 123456789457893612896127345 414 123456789457893612896127354 415 123456789457893612896217354 416 123456789457893612986217354

by **Red Ed** » Sat Jan 27, 2007 10:50 pm

Ah, we crossed in the post. Yes, point taken about bands possibly not appearing as rows 1-3. Hmm. Will ponder.

by **Red Ed** » Sat Jan 27, 2007 11:12 pm

OK, done some coding rather than some thinking. It seems likely that all min-lex grids have this form:

Code: Select all: 123|456|789 45.|.89|... ...|...|... ---+---+--- 2..|...|... ...|...|... ...|...|... ---+---+--- ...|...|... ...|...|... ...|...|...

Will have a think overnight about how one might prove that that is the best possible (if indeed it is).

by **coloin** » Sat Jan 27, 2007 11:27 pm

Thanks for that confirmation !

If I'm not mistaken these two grids might have a 3 at r2c4 [according to the readout of 381 and 386]
But the min lex i dont think is fully performed on the index416 representative ? EDIT - It is not unfortunatly

Code: Select all: 381 408 411 , 400 402 407 264759183978431652513682749186975234395264871427813965851397426632148597749526318 386 404 404 , 390 399 402 659217438471983625238465917314798562567321849982654371825146793143579286796832154

EDIT - they dont have a 3 at r2c4 when min lex normalized

I can confirm that r2c4 wont be an 8 [bands 412-416]
EDIT - this has been proved wrong !

C

by **daj95376** » Sun Jan 28, 2007 1:39 am

coloin wrote:Thanks for that confirmation !

If I'm not mistaken these two grids might have a 3 at r2c4 [according to the readout of 381 and 386]
But the min lex i dont think is fully performed on the index416 representative ?
Code: Select all
381 408 411 , 400 402 407 264759183978431652513682749186975234395264871427813965851397426632148597749526318 386 404 404 , 390 399 402 659217438471983625238465917314798562567321849982654371825146793143579286796832154

I can confirm that r2c4 wont be an 8 [bands 412-416]

C

According to gsf's solver, the canonical form of your grids have [r2c4]=1.

Code: Select all: 123456789457189623689723145235614978764895312891372456342561897576948231918237564 123456789457189623698273154235647891769831542841592367384915276512764938976328415

In search of your elusive [r2c4]=3 scenario, I generated 10^6 random filled grids starting with this pattern:

Code: Select all: *-----------------------* | 1 2 3 | 4 5 6 | 7 8 9 | | 4 5 7 | 3 8 9 | . . . | | . . . | . . . | . . . | |-------+-------+-------| | 2 . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | |-------+-------+-------| | . . . | . . . | . . . | | . . . | . . . | . . . | | . . . | . . . | . . . | *-----------------------*

[r2c4]=3 never survived after canonicalization! It always ended up in [c789].

by **JPF** » Sun Jan 28, 2007 4:24 am

Red Ed wrote:OK, done some coding rather than some thinking. It seems likely that all min-lex grids have this form:
Code: Select all
123|456|789 45.|.89|... ...|...|... ---+---+--- 2..|...|... ...|...|... ...|...|... ---+---+--- ...|...|... ...|...|... ...|...|...
Will have a think overnight about how one might prove that that is the best possible (if indeed it is).

It has already been proved that these 14 cells are fixed in the min-lex grids.
To prove that there are no other fixed cells, here is a list of 6 grids such that for any of the remaining 67 cells, 2 digits can be different.

Code: Select all: 123456789457189236896327514275948361314562897968713425539871642641235978782694153 123456789457189326689372415296738541348591672571264893715943268832617954964825137 123456789457189236689723514231967458578214693964835127316578942742391865895642371 123456789457189236689723154234697815761835492895214673348972561512368947976541328 123456789457189263968327145234798651619532874785641392391874526572963418846215937 123456789456789132789123546237964851845217963961835427374592618512678394698341275

[edit : shorter list]

other questions :

Can a min-lex grid have r2c4=3 ?
What are the minimal and the maximal min-lex grids ?

JPF

by **Red Ed** » Sun Jan 28, 2007 8:20 am

JPF wrote:It has already been proved that these 14 cells are fixed in the min-lex grids.

Really? I missed the proof that r2c5,6 = 8,9 ... can you point me to that please.

Can a min-lex grid have r2c4=3 ?
What are the minimal and the maximal min-lex grids ?

Interesting ... at least now I think I understand what this thread is trying to achieve!

The minimum min-lex grid is obviously the canonical grid:

Code: Select all: 123456789456789123789123456231564897564897231897231564312645978645978312978312645

The maximum min-lex grid is ... mmm, I don't know!

by **JPF** » Sun Jan 28, 2007 11:15 am

Red Ed wrote:The minimum min-lex grid is obviously the canonical grid:
Code: Select all
123456789456789123789123456231564897564897231897231564312645978645978312978312645

What about this one :

Code: Select all: 123456789456789123789123456214365897365897214897241635531672948642938571978514362

For the max, my favourite for the moment :

Code: Select all: 123456789457289631698317254245178396731964825986523417312645978574892163869731542

JPF

by **Red Ed** » Sun Jan 28, 2007 1:43 pm

JPF wrote:What about this one ...

Gaaa... how did I miss that? I'm having a bad time on this thread!

The minimum min-lex grid should be v. easy to find: it's just the global minimum grid. Is that what you've just showed above? (I've not checked)

by **coloin** » Sun Jan 28, 2007 3:03 pm

daJ95376 wrote:According to gsf's solver, the canonical form of your grids have [r2c4]=1.

thanks, that means the index416 doesnt quite give us the min lex that we require.......

I'm also having doubts if the 6 figure banding code can identify all essentially different grids - assuming the flaw in the repeating minirows can be ironed out.

I am also begining to suspect this maximum min-lex grid is going to be a tough one to prove !

C

by **JPF** » Sun Jan 28, 2007 3:15 pm

Red Ed wrote:The minimum min-lex grid should be v. easy to find: it's just the global minimum grid. Is that what you've just showed above? (I've not checked)

No, it was just a counter-example

JPF

by **Red Ed** » Sun Jan 28, 2007 4:44 pm

Right, so here is the minimum min-lex grid:

Code: Select all: 1 2 3 | 4 5 6 | 7 8 9 4 5 6 | 7 8 9 | 1 2 3 7 8 9 | 1 2 3 | 4 5 6 -------+-------+------- 2 1 4 | 3 6 5 | 8 9 7 3 6 5 | 8 9 7 | 2 1 4 8 9 7 | 2 1 4 | 3 6 5 -------+-------+------- 5 3 1 | 6 4 2 | 9 7 8 6 4 2 | 9 7 8 | 5 3 1 9 7 8 | 5 3 1 | 6 4 2

Or, in compact form:

Code: Select all: min-lex: 123456789456789123789123456214365897365897214897214365531642978642978531978531642 JPF: 123456789456789123789123456214365897365897214897241635531672948642938571978514362 ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^

You were close, JPF!

Having found this grid, I searched for it on the 'net and found an amazing short Perl program to calculate it.

The New Sudoku Players' Forum

Canonical Form