Canonical Form

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

Postby 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
Last edited by JPF on Sat Jan 27, 2007 4:07 pm, edited 2 times in total.
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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
coloin
 
Posts: 1629
Joined: 05 May 2005

Postby 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)
Last edited by Red Ed on Sat Jan 27, 2007 6:48 pm, edited 1 time in total.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby 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
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

C
Last edited by coloin on Sat Jan 27, 2007 7:01 pm, edited 2 times in total.
coloin
 
Posts: 1629
Joined: 05 May 2005

Postby 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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby 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).
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby 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
Last edited by coloin on Sun Jan 28, 2007 7:28 pm, edited 3 times in total.
coloin
 
Posts: 1629
Joined: 05 May 2005

Postby 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].
daj95376
2014 Supporter
 
Posts: 2624
Joined: 15 May 2006

Postby 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
Last edited by JPF on Sun Jan 28, 2007 5:38 am, edited 2 times in total.
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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!
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby 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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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)
Red Ed
 
Posts: 633
Joined: 06 June 2005

Postby 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
coloin
 
Posts: 1629
Joined: 05 May 2005

Postby 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
JPF
2017 Supporter
 
Posts: 3752
Joined: 06 December 2005
Location: Paris, France

Postby 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.
Red Ed
 
Posts: 633
Joined: 06 June 2005

PreviousNext

Return to General