-
Notifications
You must be signed in to change notification settings - Fork 0
/
sudoku.py
5100 lines (4979 loc) · 288 KB
/
sudoku.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
436
437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
463
464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
487
488
489
490
491
492
493
494
495
496
497
498
499
500
501
502
503
504
505
506
507
508
509
510
511
512
513
514
515
516
517
518
519
520
521
522
523
524
525
526
527
528
529
530
531
532
533
534
535
536
537
538
539
540
541
542
543
544
545
546
547
548
549
550
551
552
553
554
555
556
557
558
559
560
561
562
563
564
565
566
567
568
569
570
571
572
573
574
575
576
577
578
579
580
581
582
583
584
585
586
587
588
589
590
591
592
593
594
595
596
597
598
599
600
601
602
603
604
605
606
607
608
609
610
611
612
613
614
615
616
617
618
619
620
621
622
623
624
625
626
627
628
629
630
631
632
633
634
635
636
637
638
639
640
641
642
643
644
645
646
647
648
649
650
651
652
653
654
655
656
657
658
659
660
661
662
663
664
665
666
667
668
669
670
671
672
673
674
675
676
677
678
679
680
681
682
683
684
685
686
687
688
689
690
691
692
693
694
695
696
697
698
699
700
701
702
703
704
705
706
707
708
709
710
711
712
713
714
715
716
717
718
719
720
721
722
723
724
725
726
727
728
729
730
731
732
733
734
735
736
737
738
739
740
741
742
743
744
745
746
747
748
749
750
751
752
753
754
755
756
757
758
759
760
761
762
763
764
765
766
767
768
769
770
771
772
773
774
775
776
777
778
779
780
781
782
783
784
785
786
787
788
789
790
791
792
793
794
795
796
797
798
799
800
801
802
803
804
805
806
807
808
809
810
811
812
813
814
815
816
817
818
819
820
821
822
823
824
825
826
827
828
829
830
831
832
833
834
835
836
837
838
839
840
841
842
843
844
845
846
847
848
849
850
851
852
853
854
855
856
857
858
859
860
861
862
863
864
865
866
867
868
869
870
871
872
873
874
875
876
877
878
879
880
881
882
883
884
885
886
887
888
889
890
891
892
893
894
895
896
897
898
899
900
901
902
903
904
905
906
907
908
909
910
911
912
913
914
915
916
917
918
919
920
921
922
923
924
925
926
927
928
929
930
931
932
933
934
935
936
937
938
939
940
941
942
943
944
945
946
947
948
949
950
951
952
953
954
955
956
957
958
959
960
961
962
963
964
965
966
967
968
969
970
971
972
973
974
975
976
977
978
979
980
981
982
983
984
985
986
987
988
989
990
991
992
993
994
995
996
997
998
999
1000
#import os; exec(open(os.path.join('D:', 'Source', 'Repos', 'sudoku', 'sudoku.py')).read())
#CD /D D:\Source\Repos\sudoku
#set PATH=%PATH%;C:\Users\Gregory\Desktop\Apps\ffmpeg-20200315-c467328-win64-static\bin;C:\program files\MiKTeX 2.9\miktex\bin\x64
#"%ProgramFiles%\Python37\scripts\manim" sudoku.py Sudoku -pl
#"%ProgramFiles%\Python37\scripts\manim" sudoku.py Sudoku -pp
#https://www.sudokuwiki.org/sudoku.htm
#http://hodoku.sourceforge.net/en/techniques.php
#https://staffhome.ecm.uwa.edu.au/~00013890/sudokumin.php
#http://www.afjarvis.staff.shef.ac.uk/sudoku/bertram.html
#https://en.wikipedia.org/wiki/Mathematics_of_Sudoku
#https://theartofmachinery.com/2017/08/14/monte_carlo_counting_sudoku_grids.html
#http://www.afjarvis.staff.shef.ac.uk/sudoku/sud23gp.html
#https://nickp.svbtle.com/sudoku-satsolver
#http://forum.enjoysudoku.com/
#import cProfile
#cProfile.run('check_puzzle(get_ctc_puzzles()[0])')
import itertools
def uprod(*seqs):
def inner(i):
if i == n:
yield tuple(result)
return
for elt in sets[i] - seen:
seen.add(elt)
result[i] = elt
for t in inner(i+1):
yield t
seen.remove(elt)
sets = [set(seq) for seq in seqs]
n = len(sets)
seen = set()
result = [None] * n
for t in inner(0):
yield t
def mirror_sudoku(sudoku, axis): #axis=0 for x-axis, 1 for y-axis
if axis == 0: return tuple(tuple(reversed(x)) for x in sudoku)
elif axis == 1: return tuple(reversed(sudoku))
def rotate_sudoku(sudoku, degree): #degree=0 for 90 degrees, 1 for 180 degrees, 2 for 270 degrees
l = len(sudoku)
if degree == 0: return tuple(tuple(sudoku[l-1-j][i] for j in range(len(sudoku[i]))) for i in range(l))
elif degree == 1: return tuple(tuple(sudoku[l-1-i][l-1-j] for j in range(len(sudoku[i]))) for i in range(l))
elif degree == 2: return tuple(tuple(sudoku[j][l-1-i] for j in range(len(sudoku[i]))) for i in range(l))
def transpose_sudoku(sudoku): #x=y diagonal
return tuple(tuple(sudoku[j][i] for j in range(len(sudoku[i]))) for i in range(len(sudoku)))
def get_val_points(sudoku, value_set):
valdict = {c:set() for c in value_set}
for i, r in enumerate(sudoku):
for j, c in enumerate(r):
valdict[c].add((i, j))
return frozenset(frozenset(x) for x in valdict.values())
#https://www.sciencedirect.com/science/article/pii/S0012365X14001824
def is_isotopic_latin_square(square, uniquevals, value_set):
l, newvals = len(square), set()
for rperm in itertools.permutations(square):
for cperm in itertools.permutations(range(l)):
valset = get_val_points([[x[cperm[i]] for i in range(len(cperm))] for x in rperm], value_set)
if valset in uniquevals: return False
newvals.add(valset)
uniquevals |= newvals
return True
def swap_row_value(square):
rem = [[None for _ in range(len(x))] for x in square]
for i, x in enumerate(square):
for j in range(len(x)):
rem[x[j]-1][j] = i + 1
return rem
def swap_col_value(square):
rem = [[None for _ in range(len(x))] for x in square]
for i, x in enumerate(square):
for j, y in enumerate(x):
rem[i][y - 1] = j + 1
return rem
def is_mainclass_latin_square(square, uniquevals, value_set): #main class must consider diagonal transposition and values for rows/columns with transpositions for 6 possible additions
transpose = transpose_sudoku(square)
#if not is_isotopic_latin_square(square, newvals, value_set): return False
if not is_isotopic_latin_square(transpose, uniquevals.copy(), value_set): return False
#swap row/values, transpose it
if not is_isotopic_latin_square(swap_row_value(square), uniquevals.copy(), value_set): return False
if not is_isotopic_latin_square(swap_row_value(transpose), uniquevals.copy(), value_set): return False
#swap column/values, transpose it
if not is_isotopic_latin_square(swap_col_value(square), uniquevals.copy(), value_set): return False
if not is_isotopic_latin_square(swap_col_value(transpose), uniquevals.copy(), value_set): return False
return True
def is_essentially_unique_sudoku(sudoku, uniquevals, value_set, bandstack):
l, newvals = len(sudoku), set()
for r in (sudoku, transpose_sudoku(sudoku)) if bandstack[0] == bandstack[1] else (sudoku,):
for bandperm in itertools.permutations(range(bandstack[0])):
for stackperm in itertools.permutations(range(bandstack[1])):
for rperm in itertools.product(*([tuple(itertools.permutations(range(bandstack[2])))] * bandstack[0])):
for cperm in itertools.product(*([tuple(itertools.permutations(range(bandstack[3])))] * bandstack[1])):
valset = get_val_points([[r[bandperm[i // bandstack[2]] * bandstack[2] + rperm[bandperm[i // bandstack[2]]][i % bandstack[2]]][stackperm[j // bandstack[3]] * bandstack[3] + cperm[stackperm[j // bandstack[3]]][j % bandstack[3]]] for j in range(len(sudoku[i]))] for i in range(l)], value_set)
if valset in uniquevals: return False
newvals.add(valset)
uniquevals |= newvals
return True
#https://en.wikipedia.org/wiki/Latin_square
#http://pi.math.cornell.edu/~mec/Summer2009/Mahmood/Four.html
#http://www.afjarvis.staff.shef.ac.uk/sudoku/
#latin_squares(1): 1 {0: 1, 1: 0} 1 1 1 1
#latin_squares(2): 2 {0: 0, 1: 0, 2: 0} 1 1 1 0
#latin_squares(3): 12 {0: 0, 1: 0, 2: 0, 3: 0} 1 1 1 0
#latin_squares(4): 576 {0: 288, 1: 0, 2: 0, 3: 0, 4: 288} 4 2 2 2
#latin_squares(5): 161280 {0: 0, 1: 0, 2: 0, 3: 0, 4: 0, 5: 0} 56 2 2 0
#latin_squares(6): 812851200 {0: 28200960, 1: 0, 2: 0, 3: 0, 4: 253808640, 5: 0, 6: 530841600} 9408 22 12 49
def latin_squares(l): #4x4 sudoku has only 0 and 4 bad house combinations, 9x9 theoretically has only 0, 4, 6, 7, 8, 9 where 1-7 are not yet confirmed
count, found = 0, set()
housedict = {x:0 for x in range(l+1)}
uniquesudoku, uqsudoku, uqls, uniquels, mainclassls = set(), set(), set(), set(), set()
reducedls = 0
if l == 6: houses, bandstack = get_rects(l // 2, l // 3, l), (l // 2, l // 3, 2, 3)
elif l == isqrt(l) * isqrt(l): houses, bandstack = tuple(get_sub_square_points(i, l) for i in range(l)), (isqrt(l), isqrt(l), isqrt(l), isqrt(l))
else: houses, bandstack = None, None
def gen_latin_squares(rows, sets):
nonlocal count, reducedls
if len(rows) == l:
#valid_ls = all(len(set(c)) == l for c in zip(*rows))
#if not valid_ls: raise ValueError
count += 1
valset = get_val_points(rows, value_set)
if all(rows[0][i] < rows[0][i+1] and rows[i][0] < rows[i+1][0] for i in range(len(rows)-1)): reducedls += 1
#latin squares have only row/column permutations to consider
#while sudoku has band/stack permutations and row/column permutations within a band/stack
#mirrorrows = mirror_sudoku(rows, 0) #not necessary if doing row/column permutations
#rotations are transpositions + reflections so also not necessary
#transposerows = transpose_sudoku(rows) #only this is necessary
#for r in (rotate_sudoku(rows, 0), rotate_sudoku(rows, 1), rotate_sudoku(rows, 2), mirrorrows, rotate_sudoku(mirrorrows, 0), rotate_sudoku(mirrorrows, 1), rotate_sudoku(mirrorrows, 2), transposerows, rotate_sudoku(transposerows, 0), rotate_sudoku(transposerows, 1), rotate_sudoku(transposerows, 2)):
#if get_val_points(r, value_set) in uniquevals: return 1
if not valset in uqls and is_isotopic_latin_square(rows, uqls, value_set):
uniquels.add(valset)
if is_mainclass_latin_square(rows, mainclassls, value_set):
mainclassls.add(valset)
print(count, housedict, reducedls, len(uniquels), len(mainclassls), len(uniquesudoku), len(uqls))
if count % 1000000 == 0: print(count, housedict, reducedls, len(uniquels), len(mainclassls), len(uniquesudoku))
if not houses is None:
badhouse = sum(1 for i in range(l) if len(set(rows[x][y] for x, y in houses[i])) != l)
housedict[badhouse] += 1
if housedict[badhouse] == 1:
print(badhouse)
if l == isqrt(l) * isqrt(l): print_sudoku(rows)
else: print(rows)
if badhouse == 0:
if not valset in uqsudoku and is_essentially_unique_sudoku(rows, uqsudoku, value_set, bandstack):
uniquesudoku.add(valset)
if l == isqrt(l) * isqrt(l): print_sudoku(rows)
else: print(rows)
return 1 #[rows] #if valid_ls else []
squarecount = 0 #squares = []
for row in uprod(*sets):
squarecount += gen_latin_squares(rows + [row], tuple(sets[i] - frozenset((row[i],)) for i in range(l)))
#squares.extend(gen_latin_squares(rows + [row], tuple(sets[i] - frozenset((row[i],)) for i in range(l))))
return squarecount #squares
value_set = frozenset(range(1, l+1))
res = gen_latin_squares([], tuple(value_set for _ in range(l)))
print(res, housedict, reducedls, len(uniquels), len(mainclassls), len(uniquesudoku))
def omino_valid_ls(houses, l):
housemap = {i:[{pt for pt in h if pt[0] < i} for h in houses] for i in range(2, l)}
def has_latin_square(rows, sets):
if len(rows) == l:
badhouse = sum(1 for i in range(l) if len(set(rows[x][y] for x, y in houses[i])) != l)
return badhouse == 0
elif len(rows) >= 2 and sum(1 for i in range(l) if len(set(rows[x][y] for x, y in housemap[len(rows)][i])) != len(housemap[len(rows)][i])) != 0: return False
for row in (tuple(value_set),) if len(rows) == 0 else uprod(*sets):
if has_latin_square(rows + [row], tuple(sets[i] - frozenset((row[i],)) for i in range(l))): return True
return False
value_set = frozenset(range(1, l+1))
return has_latin_square([], tuple(value_set for _ in range(l)))
def origin_omino(o):
mnr = min(o, key=lambda x: x[0])[0]
mnc = min(o, key=lambda x: x[1])[1]
return frozenset((x - mnr, y - mnc) for (x, y) in o)
def transpose_omino(o):
return origin_omino(frozenset((y, x) for (x, y) in o))
def match_omino(ominos, omino): #convert arbitrary omino to its representative free omino
o = origin_omino(omino)
if o in ominos: return o
r = rotate_omino(o, 0)
if r in ominos: return r
r = rotate_omino(o, 1)
if r in ominos: return r
r = rotate_omino(o, 2)
if r in ominos: return r
m = mirror_omino(o, 0) #can be either axis 0/1 here...
if m in ominos: return m
r = rotate_omino(m, 0)
if r in ominos: return r
r = rotate_omino(m, 1)
if r in ominos: return r
r = rotate_omino(m, 2)
if r in ominos: return r
def omino_to_svg(omino, curdir):
#pip install https://download.lfd.uci.edu/pythonlibs/w3jqiv8s/pycairo-1.19.1-cp38-cp38-win_amd64.whl
mxr = max(omino, key=lambda x: x[0])[0] + 1
mxc = max(omino, key=lambda x: x[1])[1] + 1
scale = 21
from cairo import SVGSurface, Context, Matrix
fname = os.path.join(curdir, str(hash(omino)) + '.svg')
s = SVGSurface(fname, mxc * scale+1+1, mxr * scale+1+1)
c = Context(s)
m = Matrix(yy=-1, y0=mxr * scale+1+1)
c.transform(m)
for pt in omino:
c.move_to(1+pt[1] * scale, 1+pt[0] * scale)
c.line_to(1+pt[1] * scale, (pt[0] + 1) * scale)
c.line_to((pt[1] + 1) * scale, (pt[0] + 1) * scale)
c.line_to((pt[1] + 1) * scale, 1+pt[0] * scale)
c.close_path()
c.save()
c.set_line_width(1.0)
c.stroke_preserve()
c.set_source_rgb(0.7, 0.7, 0.7)
c.fill()
c.restore()
s.finish()
return fname
#essentially unique: 1,1,2,21,507,54588
#omino_placements(1): (1, 1, 1, 1)
#omino_placements(2): (2, 2, 1, 1)
#omino_placements(3): (10, 10, 2, 2)
#omino_placements(4): (117, 109, 22, 21)
#omino_placements(5): (4006, 3942, 515, 507)
#omino_placements(6): (451206, 434050, 56734, 54588)
def omino_placements(l): #https://oeis.org/A172477, https://oeis.org/A328020, https://oeis.org/A172478
#place ominos in opposite corners and then brute force search
base_ominos = free_ominos_no_hole(l)
ominoall = {b:0 for b in base_ominos}
ominols = {b:0 for b in base_ominos}
unique_place = set()
has_valid_ls = set()
totls = 0
value_set = set(range(1, l+1))
def get_mirror_rotates(board):
yield rotate_sudoku(board, 0)
yield rotate_sudoku(board, 1)
yield rotate_sudoku(board, 2)
mirrorboard = mirror_sudoku(board, 0)
yield mirrorboard
yield rotate_sudoku(mirrorboard, 0)
yield rotate_sudoku(mirrorboard, 1)
yield rotate_sudoku(mirrorboard, 2)
transposeboard = transpose_sudoku(board)
yield transposeboard
yield rotate_sudoku(transposeboard, 0)
yield rotate_sudoku(transposeboard, 1)
yield rotate_sudoku(transposeboard, 2)
def brute_omino_rcrse(ominos, board):
nonlocal totls
if len(ominos) == l:
o = frozenset(ominos)
match = list(itertools.takewhile(lambda x: not x in unique_place, map(lambda x: get_val_points(x, value_set), get_mirror_rotates(board))))
if not o in unique_place and len(match) == 3 + 4 + 4:
unique_place.add(o)
baseoms = [match_omino(base_ominos, om) for om in ominos]
for om in baseoms: ominoall[om] += 1
#solvable = True
#for omino in ominos:
#ominodict = {(i, j):k+1 for k, (i, j) in enumerate(omino)}
#sudoku = [[None if not (i, j) in ominodict else ominodict[(i, j)] for j in range(l)] for i in range(l)]
#mutex_rules = (*standard_sudoku_singoverlap_regions(l), tuple(frozenset(x) for x in jigsaw_to_coords(board).values()))
#rem, solve_path, _ = solve_sudoku(sudoku, mutex_rules, (), (), value_set, None)
#if rem is None:
# solvable = False; print(logical_solve_string(solve_path, mutex_rules)); print_border(sudoku, exc_from_border(board, ())); break
#if solvable != omino_valid_ls(ominos, l): raise ValueError(solvable, omino_valid_ls(ominos, l))
#if solvable:
count = len(set((o, *match)))
if omino_valid_ls(ominos, l):
has_valid_ls.add(o); totls += count
for om in baseoms: ominols[om] += 1
else: print_border([[None] * l for _ in range(l)], exc_from_border(board, ())); print(len(unique_place), len(has_valid_ls))
return count
#elif o in has_valid_ls or any(get_val_points(x, value_set) in has_valid_ls for x in get_mirror_rotates(board)):
# totls += 1
return 0
count, u = 0, frozenset.union(*ominos)
for omino in region_ominos(next((x, y) for x in range(l) for y in range(l) if board[x][y] is None), board, ()):
#if not check_path_combo(omino, u): continue
nextboard = add_region([x.copy() for x in board], omino, len(ominos)+1)
count += brute_omino_rcrse(ominos + [omino], nextboard)
return count
def check_path_combo(path, combo):
u = path.union(combo)
if len(u) != len(path) + len(combo): return False
not_hole = set()
for (x, y) in get_path_boundary(u, l):
if (x, y) in not_hole: continue
cur_hole = get_hole_path(u, (), l, set(), x, y)
if len(cur_hole) % l != 0: return False
not_hole = not_hole.union(cur_hole)
return True
if l <= 1: return l, l, l, l
board = [[None] * l for _ in range(l)]
count, ominos = 0, []
mainominosused = set()
for mainomino in region_ominos((0, 0), board, ()):
if transpose_omino(mainomino) in mainominosused: continue
mainominosused.add(mainomino) #already on origin
mainboard = add_region([x.copy() for x in board], mainomino, 1)
for lastomino in region_ominos((l-1, l-1), mainboard, ()):
if not check_path_combo(lastomino, mainomino): continue
lastboard = add_region([x.copy() for x in mainboard], lastomino, 2)
count += brute_omino_rcrse([mainomino, lastomino], lastboard)
lines = ["<!DOCTYPE html>"]
lines.append("<html>")
lines.append("<head><style>table, th, td { border: 1px solid black; }</style></head>")
lines.append("<body>")
omino_names = ["monomino", "domino", "tromino", "tetromino", "pentomino", "hexomino", "heptomino", "octomino", "nonomino", "decomino", "undecomino", "dodecomino"]
tromino_names = {"I":frozenset({(0, 1), (0, 2), (0, 0)}), "L":frozenset({(0, 1), (1, 0), (1, 1)})} #https://en.wikipedia.org/wiki/Tromino
#https://tetris.wiki/Tetromino
tetromino_names = {"Straight":frozenset({(0, 1), (0, 2), (0, 3), (0, 0)}), "Square":frozenset({(0, 1), (1, 0), (1, 1), (0, 0)}),
"T":frozenset({(1, 0), (1, 1), (2, 0), (0, 0)}), "L":frozenset({(0, 1), (0, 2), (1, 2), (0, 0)}), "Skew":frozenset({(0, 1), (1, 0), (1, 1), (0, 2)})} #https://en.wikipedia.org/wiki/Tetromino
#for i in free_ominos(5): print(i); print(omino_string(i) + '\n')
pentomino_names = {"F":frozenset({(0, 1), (1, 2), (2, 1), (1, 1), (2, 0)}), "I":frozenset({(0, 1), (0, 4), (0, 0), (0, 3), (0, 2)}),
"L": frozenset({(0, 1), (0, 0), (0, 3), (0, 2), (1, 0)}), "N": frozenset({(2, 1), (0, 0), (3, 1), (2, 0), (1, 0)}),
"P": frozenset({(2, 1), (0, 0), (1, 1), (2, 0), (1, 0)}), "T": frozenset({(1, 2), (0, 0), (1, 1), (2, 0), (1, 0)}),
"U": frozenset({(0, 1), (2, 1), (0, 0), (2, 0), (1, 0)}), "V": frozenset({(0, 1), (0, 0), (2, 0), (0, 2), (1, 0)}),
"W": frozenset({(2, 1), (0, 0), (1, 1), (2, 2), (1, 0)}), "X": frozenset({(0, 1), (1, 2), (2, 1), (1, 1), (1, 0)}),
"Y": frozenset({(0, 1), (2, 1), (3, 1), (1, 1), (2, 0)}), "Z": frozenset({(0, 1), (2, 1), (1, 1), (2, 0), (0, 2)})} #https://en.wikipedia.org/wiki/Pentomino
#http://www.gamepuzzles.com/sxnames.htm Short N and Short S are duplicates
hexomino_names = {"A": frozenset({(1, 2), (2, 1), (1, 1), (2, 0), (0, 2), (2, 2)}), "C": frozenset({(0, 1), (0, 0), (0, 3), (0, 2), (1, 0), (1, 3)}),
"D": frozenset({(0, 1), (1, 2), (0, 0), (1, 1), (0, 3), (0, 2)}), "E": frozenset({(0, 1), (1, 2), (1, 1), (2, 0), (2, 2), (1, 0)}),
"High F": frozenset({(1, 2), (2, 1), (0, 0), (1, 1), (1, 0), (1, 3)}), "Low F": frozenset({(0, 1), (1, 2), (2, 1), (3, 1), (1, 1), (3, 0)}),
"G": frozenset({(2, 1), (0, 0), (3, 1), (1, 1), (3, 0), (1, 0)}), "H": frozenset({(1, 2), (0, 0), (1, 1), (2, 0), (2, 2), (1, 0)}),
"I": frozenset({(4, 0), (0, 0), (2, 0), (3, 0), (5, 0), (1, 0)}), "J": frozenset({(0, 1), (2, 1), (0, 0), (2, 0), (0, 2), (1, 0)}),
"K": frozenset({(0, 1), (1, 2), (2, 1), (1, 1), (2, 0), (1, 0)}), "L": frozenset({(0, 1), (2, 1), (0, 0), (3, 1), (1, 1), (4, 1)}),
"M": frozenset({(0, 1), (1, 2), (0, 0), (1, 1), (2, 3), (1, 3)}), "Long N": frozenset({(0, 1), (0, 0), (0, 3), (1, 4), (0, 2), (1, 3)}),
"O": frozenset({(0, 1), (1, 2), (0, 0), (1, 1), (0, 2), (1, 0)}), "P": frozenset({(0, 1), (0, 0), (1, 1), (0, 3), (0, 2), (1, 0)}),
"Q": frozenset({(0, 1), (2, 1), (1, 1), (2, 0), (0, 2), (1, 0)}), "R": frozenset({(0, 1), (1, 2), (2, 1), (0, 0), (1, 1), (0, 2)}),
"Long S": frozenset({(0, 1), (4, 0), (2, 1), (1, 1), (2, 0), (3, 0)}), "Short S": frozenset({(0, 1), (2, 1), (1, 1), (2, 0), (3, 0), (1, 0)}),
"Tall T": frozenset({(1, 2), (0, 0), (1, 1), (2, 0), (1, 0), (1, 3)}), "Short T": frozenset({(1, 2), (0, 0), (1, 1), (2, 0), (3, 0), (1, 0)}),
"U": frozenset({(0, 1), (1, 2), (1, 1), (0, 3), (1, 0), (1, 3)}), "V": frozenset({(0, 1), (1, 2), (0, 0), (0, 2), (2, 2), (3, 2)}),
"Wa": frozenset({(0, 1), (1, 1), (0, 3), (2, 0), (0, 2), (1, 0)}), "Wb": frozenset({(0, 1), (1, 2), (0, 0), (1, 1), (2, 3), (2, 2)}),
"Wc": frozenset({(0, 1), (2, 1), (1, 1), (2, 2), (1, 0), (3, 2)}), "X": frozenset({(0, 1), (2, 1), (3, 1), (1, 1), (2, 0), (2, 2)}),
"Italic X": frozenset({(0, 1), (1, 2), (2, 1), (3, 1), (1, 1), (2, 0)}), "High Y": frozenset({(4, 0), (0, 0), (3, 1), (2, 0), (3, 0), (1, 0)}),
"Low Y": frozenset({(0, 1), (1, 2), (0, 4), (0, 0), (0, 3), (0, 2)}), "Short Z": frozenset({(1, 2), (2, 1), (0, 3), (2, 0), (0, 2), (2, 2)}),
"Tall Z": frozenset({(1, 2), (0, 0), (1, 1), (2, 3), (1, 0), (1, 3)}), "High 4": frozenset({(1, 2), (1, 1), (2, 3), (0, 2), (2, 2), (1, 0)}),
"Low 4": frozenset({(0, 1), (1, 2), (1, 1), (2, 0), (3, 0), (1, 0)})}
lines.append("<p>Total {0} ({1}-size polyomino) placements into a {1}x{1} square: {2}</p>".format(omino_names[l-1], l, count))
lines.append("<p>Total {0} placements into a {1}x{1} valid sudoku: {2}</p>".format(omino_names[l-1], l, totls))
lines.append("<p>Total {0} essentially unique placements into a {1}x{1} square: {2}</p>".format(omino_names[l-1], l, len(unique_place)))
lines.append("<p>Total {0} essentially unique placements into a {1}x{1} valid sudoku: {2}</p>".format(omino_names[l-1], l, len(has_valid_ls)))
lines.append("<table>")
curdir = os.path.join('D:', 'Source', 'Repos', 'sudoku', 'images')
ominotbl, ominoallct, ominolsct = ["" for _ in range(1+(len(base_ominos) - 5 + 6) // 7)], ["" for _ in range(1+(len(base_ominos) - 5 + 6) // 7)], ["" for _ in range(1+(len(base_ominos) - 5 + 6) // 7)]
bominos = [x[0] for x in sorted(ominoall.items(), key=lambda o: o[1], reverse=True)]
for i, o in enumerate(bominos):
print(ominoall[o], ominols[o]); print(omino_string(o))
fname = omino_to_svg(o, curdir)
ominotbl[1+(i - 5) // 7 if i >= 5 else 0] += "<td><img src='" + fname + "'/></td>"
ominoallct[1+(i - 5) // 7 if i >= 5 else 0] += "<td><p>" + str(ominoall[o]) + "</p></td>"
ominolsct[1+(i - 5) // 7 if i >= 5 else 0] += "<td><p>" + str(ominols[o]) + "</p></td>"
lines.append("<tr><td><b>" + omino_names[l-1].capitalize() + "</b></td>" + ominotbl[0] + "</tr>")
lines.append("<tr><td><b>Total in essentially<br/> unique squares</b></td>" + ominoallct[0] + "</tr>")
lines.append("<tr><td><b>Total in essentially<br/> unique valid sudoku</b></td>" + ominolsct[0] + "</tr>")
lines.append("</table>")
for i in range(1, len(ominotbl)):
lines.append("<table>")
lines.append("<tr>" + ominotbl[i] + "</tr>")
lines.append("<tr>" + ominoallct[i] + "</tr>")
lines.append("<tr>" + ominolsct[i] + "</tr>")
lines.append("</table>")
lines.append("</body>")
lines.append("</html>")
with open(os.path.join(curdir, "omino" + str(l) + ".html"), "w") as f:
f.writelines(lines)
return count, totls, len(unique_place), len(has_valid_ls), ominoall, ominols
def min_kropki(l): #l=4, min/min unique=12, max=18 l=6, min=10, min unique=11, max=48
if l == 6: houses = get_rects(l // 2, l // 3, l)
else: houses = tuple(get_sub_square_points(i, l) for i in range(l))
housemap = {i:[{pt for pt in h if pt[0] < i} for h in houses] for i in range(1, l)}
pthouse = {pt:i for i in range(l) for pt in houses[i]}
count, mn, res = 0, l * (l - 1) * 2, None
kropkidict = dict()
edgemap = dict()
for i in range(l - 1):
for j in range(l):
edgemap[((i, j), (i+1, j))] = len(edgemap)
edgemap[((j, i), (j, i+1))] = len(edgemap)
value_set = frozenset(range(1, l+1))
permdict, revperm = dict(), []
for perm in itertools.permutations(value_set):
permdict[perm] = len(permdict)
revperm.append(perm)
def check_latin_square(rows, sets):
nonlocal count, mn, res
if len(rows) == l:
#badhouse = sum(1 for i in range(l) if len(set(rows[x][y] for x, y in houses[i])) != l)
#if badhouse != 0: return -1, None
count += 1
kropkiwhite, kropkiblack = set(), set()
for i in range(l - 1):
for j in range(l):
if rows[i][j] + 1 == rows[i+1][j] or rows[i][j] == rows[i+1][j] + 1: kropkiwhite.add(edgemap[((i, j), (i+1, j))])
elif rows[i][j] << 1 == rows[i+1][j] or rows[i][j] == rows[i+1][j] << 1: kropkiblack.add(edgemap[((i, j), (i+1, j))])
if rows[j][i] + 1 == rows[j][i+1] or rows[j][i] == rows[j][i+1] + 1: kropkiwhite.add(edgemap[((j, i), (j, i+1))])
elif rows[j][i] << 1 == rows[j][i+1] or rows[j][i] == rows[j][i+1] << 1: kropkiblack.add(edgemap[((j, i), (j, i+1))])
kropkinum = sum(1 << k for k in kropkiwhite) + sum(1 << (k + len(edgemap)) for k in kropkiblack)
if kropkinum in kropkidict: kropkidict[kropkinum] = (kropkidict[kropkinum][0] + 1, len(kropkiwhite | kropkiblack), None)
else: kropkidict[kropkinum] = (1, len(kropkiwhite | kropkiblack), [revperm[permdict[r]] for r in rows]) #rows
if count % 500000 == 0:
ka = tuple(filter(lambda k: kropkidict[k][0] == 1, kropkidict))
kd = kropkidict[min(ka, key=lambda k: kropkidict[k][1])] if len(ka) != 0 else None
print(count, mn, res, len(ka), len(kropkidict), (kd[1], kd[2]) if not kd is None else None)
return len(kropkiwhite | kropkiblack), rows
#elif len(rows) >= 2 and sum(1 for i in range(l) if len(set(rows[x][y] for x, y in housemap[len(rows)][i])) != len(housemap[len(rows)][i])) != 0: return -1, None
lr = len(rows)
housesets = [s - {rows[pt[0]][pt[1]] for pt in housemap[lr][pthouse[(lr, i)]]} for i, s in enumerate(sets)] if lr >= 1 else sets
for row in uprod(*housesets): #(tuple(value_set),) if len(rows) == 0 else uprod(*sets):
v, r = check_latin_square(rows + [row], tuple(sets[i] - frozenset((row[i],)) for i in range(l)))
if v != -1 and v < mn: mn, res = v, r
return mn, res
mn, res = check_latin_square([], tuple(value_set for _ in range(l)))
ka = tuple(filter(lambda k: kropkidict[k][0] == 1, kropkidict))
kd = kropkidict[min(ka, key=lambda k: kropkidict[k][1])] if len(ka) != 0 else None
return mn, res, len(ka), len(kropkidict), count, (kd[1], kd[2]) if not kd is None else None, kropkidict[max(kropkidict, key=lambda k: kropkidict[k][1])]
def orthagonal_pts(i, j): return ((i, j-1), (i-1, j), (i+1, j), (i, j+1))
def filter_bounds_points(l, points):
return filter(lambda x: x[0] >= 0 and x[0] <= l-1 and x[1] >= 0 and x[1] <= l-1, points)
def orthagonal_points(i, j, l):
return (frozenset(filter_bounds_points(l, orthagonal_pts(i, j))),)
def diagonal_pts(i, j): return ((i-1, j-1), (i+1, j-1), (i-1, j+1), (i+1, j+1))
def diagonal_points_filter(i, j, l):
return (frozenset(filter_bounds_points(l, diagonal_pts(i, j))),)
def king_rule_pts(i, j): return ((i-1, j-1), (i, j-1), (i+1, j-1), (i-1, j), (i+1, j), (i-1, j+1), (i, j+1), (i+1, j+1))
def king_rule_points(i, j, l):
return (frozenset(filter_bounds_points(l, king_rule_pts(i, j))),)
"""
def exclude_king_rule(rem, cell_visibility_rules, cell_sudoku_remove):
l, count = len(rem), 0
for i in range(l):
for j in range(l):
if len(rem[i][j]) != 1:
points = set(king_rule_points(i, j, l))
for z in rem[i][j].copy():
#need to look above, below, left and right to exclude based on column and row rules combined with king rule
#and combine sub square rule with kings rule
if (i != 0 and all(not z in rem[i-1][y] or (i-1, y) in points for y in range(l)) or
i != l-1 and all(not z in rem[i+1][y] or (i+1, y) in points for y in range(l)) or
j != 0 and all(not z in rem[y][j - 1] or (y, j - 1) in points for y in range(l)) or
j != l-1 and all(not z in rem[y][j + 1] or (y, j + 1) in points for y in range(l)) or
i != 0 and sub_square_from_point(i - 1, j) != sub_square_from_point(i, j) and all(not z in rem[y[0]][y[1]] or y[1] == j or y[0] == i - 1 and (y[0], y[1]) in points for y in get_sub_square_points(sub_square_from_point(i - 1, j))) or
i != l-1 and sub_square_from_point(i + 1, j) != sub_square_from_point(i, j) and all(not z in rem[y[0]][y[1]] or y[1] == j or y[0] == i + 1 and (y[0], y[1]) in points for y in get_sub_square_points(sub_square_from_point(i + 1, j))) or
j != 0 and sub_square_from_point(i, j - 1) != sub_square_from_point(i, j) and all(not z in rem[y[0]][y[1]] or y[0] == i or y[1] == j - 1 and (y[0], y[1]) in points for y in get_sub_square_points(sub_square_from_point(i, j - 1))) or
j != l-1 and sub_square_from_point(i, j + 1) != sub_square_from_point(i, j) and all(not z in rem[y[0]][y[1]] or y[0] == i or y[1] == j + 1 and (y[0], y[1]) in points for y in get_sub_square_points(sub_square_from_point(i, j + 1)))):
#print("King's Rule Locked Candidates %d in (%d, %d)" % (z, i, j))
rem, c = cell_sudoku_remove(rem, i, j, z)
count += 1 + c
continue
rem, c = exclude_sudoku_by_group(rem, cell_visibility_rules, cell_sudoku_remove)
return rem, count + c
"""
def knight_rule_points(i, j, l):
return (frozenset(filter_bounds_points(l, ((i-2, j-1), (i-2, j+1), (i-1, j-2), (i-1, j+2), (i+1, j-2), (i+1, j+2), (i+2, j-1), (i+2, j+1)))),)
def row_points(i, j, l): return frozenset((i, x) for x in range(l))
def column_points(i, j, l): return frozenset((x, j) for x in range(l))
def subsquare_points(i, j, l): return frozenset(get_sub_square_points(sub_square_from_point(i, j, l), l))
def diagonal_points(i, j, l):
return frozenset.union(frozenset((x, x) for x in range(l)) if i == j else frozenset(),
frozenset((x, l-1-x) for x in range(l)) if i == l - 1 - j else frozenset())
def bishop_rule_pts(i, j, l):
return frozenset.union(frozenset((i + x, j + x) for x in range(-l+1, l) if x != 0),
frozenset((i + x, j - x) for x in range(-l+1, l) if x != 0))
def bishop_rule_points(i, j, l):
return (frozenset(filter_bounds_points(l, bishop_rule_pts(i, j, l))),)
def row_col_points(i, j, l):
return (row_points(i, j, l), column_points(i, j, l))
#def standard_sudoku_points(i, j, l):
# return (row_points(i, j, l), column_points(i, j, l), subsquare_points(i, j, l))
#def standard_sudoku_points(i, j, l):
# return tuple(c(i, j, l) for c in mutex_regions_to_visibility(standard_sudoku_mutex_regions(l)))
def standard_sudoku_singoverlap_regions(l):
return (tuple(row_points(x, 0, l) for x in range(l)), tuple(column_points(0, x, l) for x in range(l)))
def standard_sudoku_mutex_regions(l):
return (*standard_sudoku_singoverlap_regions(l), tuple(get_sub_square_points(x, l) for x in range(l)))
def mutex_regions_to_visibility(regions):
def points_func_gen(region):
def points_func(i, j, l):
for r in region:
if (i, j) in r: return (r,)
return ()
return points_func
return tuple(points_func_gen(r) for r in regions)
#def standard_sudoku_regions(l):
# return (*(row_points(x, 0, l) for x in range(l)), *(column_points(0, x, l) for x in range(l)), *(get_sub_square_points(x, l) for x in range(l)))
def diagonal_sudoku_regions(l):
return tuple((diagonal_points(0, 0, l), diagonal_points(0, l-1, l)))
def cell_visibility(i, j, l, cell_visibility_rules):
def frozenset_union(val):
return frozenset() if len(val) == 0 else frozenset.union(*val)
return frozenset.union(*(frozenset_union(c(i, j, l)) for c in cell_visibility_rules)) - frozenset(((i, j),))
def cell_mutex_visibility(i, j, mutex_rules):
return (y for x in mutex_rules for y in x if (i, j) in y)
#return (x - frozenset(((i, j),)) for c in cell_visibility_rules for x in c(i, j, l))
def cell_sudoku_rule(rem, i, j, y, cell_visibility_rules):
#print("Initialization via Full House/Naked Single %d to (%d, %d)" % (y, i, j))
l = len(rem)
for (p, q) in cell_visibility(i, j, l, cell_visibility_rules):
if y in rem[p][q]: rem[p][q].remove(y)
for z in rem[i][j].copy():
if z != y: rem[i][j].remove(z)
#for x in range(l):
# if x != i and y in rem[x][j]: rem[x][j].remove(y)
# if x != j and y in rem[i][x]: rem[i][x].remove(y)
#for x in get_sub_square_points(sub_square_from_point(i, j)):
# if (x[0] != i or x[1] != j) and y in rem[x[0]][x[1]]: rem[x[0]][x[1]].remove(y)
return rem
def isqrt(n):
x = n
y = (x + 1) >> 1
while y < x:
x = y
y = (x + n // x) >> 1
return x
def sub_square_from_point(i, j, l):
s = isqrt(l)
if s * s != l: return -1
return i // s * s + j // s
def get_sub_square_points(x, l):
s = isqrt(l)
if s * s != l: return ()
i, j = x // s * s, x % s * s
return frozenset((i + p, j + q) for p in range(s) for q in range(s))
#return ((i, j), (i, j+1), (i, j+2), (i+1, j), (i+1, j+1), (i+1, j+2), (i+2, j), (i+2, j+1), (i+2, j+2))
def get_rects(width, height, l):
if l % width != 0 or l % height != 0: return None
rects = []
for i in range(0, l, l // width):
for j in range(0, l, l // height):
rects.append([(i + k // width, j + k % width) for k in range(l)])
return rects
def get_jigsaw_rects(rects, l):
rem = [[0 for _ in range(l)] for _ in range(l)]
for i, r in enumerate(rects):
for x in r:
rem[x[0]][x[1]] = i
return rem
def check_bad_sudoku(rem):
if any(any(len(y) == 0 for y in x) for x in rem): return True
return False
LAST_DIGIT,FULL_HOUSE,NAKED_SINGLE,HIDDEN_SINGLE,LOCKED_CANDIDATES,NAKED_MULTIPLES,HIDDEN_MULTIPLES,BASIC_FISH,FINNED_FISH,X_CHAIN,XY_CHAIN,BIFURCATION=0,1,2,3,4,5,6,7,8,9,10,11
X_CHAIN_SKYSCRAPER,X_CHAIN_TWOSTRINGKITE,X_CHAIN_TURBOT_FISH=0,1,2
KILLER_CAGE_RULE,THERMO_RULE,INEQUALITY_RULE,HIDDEN_CAGE_TUPLE,MIRROR_CAGE_CELL,ORTHAGONAL_NEIGHBOR,MAGIC_SQUARE,SANDWICH_RULE,ARROW_RULE,EVEN_ODD,MIRROR_RULE,SYMMETRY_RULE,BATTLEFIELD_RULE,RENBAN_RULE,IN_ORDER_RULE,JOUSTING_KNIGHTS,FIBONACCI_RULE,DOUBLE_RULE,MANHATTAN_RULE,SMALL_BIG,SNAKE_EGG_RULE=12,13,14,15,16,17,18,19,20,21,22,23,24,25,26,27,28,29,30,31,32
STRING_RULES = ("Last Digit", "Full House", "Naked Single", "Hidden Single", "Locked Candidates", "Naked %s", "Hidden %s", "Basic %s", "Finned %s", "X-Chain", "XY-Chain", "Bifurcation",
"Killer Cage Rule", "Thermometer Rule", "Inequality Rule", "Hidden Cage Tuple", "Mirror Cage Cell", "Orthagonal Neighbor", "Magic Square", "Sandwich Rule", "Arrow Rule", "Even or Odd Rule", "Mirror Rule", "Symmetry Rule", "Battlefield Rule", "Renban Rule", "In Order Rule", "Jousting Knights", "Fibonacci Rule", "Double Rule", "Manhattan Rule", "Small or Big Rule", "Snake Egg Rule")
def naked_single(rem, mutex_rules, cell_visibility_rules, value_set, dynamic_visibility=None):
l, possible = len(rem), []
#should find the full houses before naked singles followed by hidden singles
for i in range(l):
for j in range(l):
if len(rem[i][j]) != 1: continue
y = next(iter(rem[i][j]))
t = tuple(x for x in cell_visibility(i, j, l, cell_visibility_rules) if y in rem[x[0]][x[1]])
if not dynamic_visibility is None:
t = frozenset((*t, *(x for x in dynamic_visibility(i, j, rem, y) if y in rem[x[0]][x[1]])))
if len(t) != 0: #[(i, j, y) for y in rem[i][j].intersection(vals)]
classify = NAKED_SINGLE
for region in cell_mutex_visibility(i, j, mutex_rules):
tr = tuple(rem[x[0]][x[1]] for x in region if len(rem[x[0]][x[1]]) == 1)
if len(tr) != 0 and len(set.union(*tr)) == len(value_set) - 1:
if all(len(rem[x[0]][x[1]]) == 1 for x in frozenset((p, q) for p in range(l) for q in range(l)) - cell_visibility(i, j, l, cell_visibility_rules)) and (
all(len(rem[x[0]][x[1]]) == 1 or len(rem[x[0]][x[1]]) == 2 and y in rem[x[0]][x[1]] for x in cell_visibility(i, j, l, cell_visibility_rules))):
classify = LAST_DIGIT
else:
classify = FULL_HOUSE
break
possible.append(([(x[0], x[1], y) for x in t], classify, ((i,j),))) #or a last digit...
return possible
def hidden_single(rem, mutex_rules, cell_visibility_rules, value_set, dynamic_mutex_rules=None):
l, possible = len(rem), []
regions = tuple(r for regs in mutex_rules for r in regs)
if not dynamic_mutex_rules is None:
regions = (*regions, *dynamic_mutex_rules(l))
for y in value_set:
for points in regions:
exclusive = tuple(z for z in points if y in rem[z[0]][z[1]])
if len(exclusive) == 1:
if rem[exclusive[0][0]][exclusive[0][1]] == set((y,)): continue
possible.append(([(exclusive[0][0], exclusive[0][1], z) for z in rem[exclusive[0][0]][exclusive[0][1]] - set((y,))], HIDDEN_SINGLE, (points,)))
return possible
def locked_candidates(rem, mutex_rules, cell_visibility_rules, value_set, dynamic_visibility=None, dynamic_mutex_rules=None):
l, possible = len(rem), []
regions = tuple(r for regs in mutex_rules for r in regs)
if not dynamic_mutex_rules is None:
regions = (*regions, *dynamic_mutex_rules(l))
for points in regions:
for y in value_set:
pts = tuple(z for z in points if y in rem[z[0]][z[1]])
a = tuple(frozenset.union(cell_visibility(z[0], z[1], l, cell_visibility_rules), dynamic_visibility(z[0], z[1], rem, y) if not dynamic_visibility is None else frozenset()) for z in pts)
s = frozenset.intersection(*a) if len(a) != 0 else frozenset()
exclude = []
diff = s.difference(points)
for o, z in diff:
if y in rem[o][z]:
#if points is a row/column then it is claiming, otherwise it is pointing and pointing either on row/column depending on if o or z matches up with any row/column in points
exclude.append((o, z, y))
if len(exclude) != 0: possible.append((exclude, LOCKED_CANDIDATES, (points,diff,pts)))
return possible
def mutex_multiples(rem, mutex_rules, cell_visibility_rules, value_set):
l, possible = len(rem), []
for points in (r for regs in mutex_rules for r in regs):
for p in range(2, len(points)): #naked pairs/triples/quadruples/etc along rows/columns/sub-regions
for y in itertools.combinations(points, p):
y_exc = frozenset(points).difference(y)
s = frozenset.union(*(frozenset(rem[i][j]) for i, j in y))
if len(s) == p: #s = value_set.difference(s)
exclude = []
for i, j in y_exc:
for q in s.intersection(frozenset(rem[i][j])):
#print("Naked pairs/triples/quadruples")
exclude.append((i, j, q))
if len(exclude) != 0: possible.append((exclude, NAKED_MULTIPLES, (y, s, points)))
s = s.difference(frozenset.union(*(frozenset(rem[i][j]) for i, j in y_exc)))
if len(s) == p:
exclude = []
for i, j in y:
for q in frozenset(rem[i][j]).difference(s):
#print("Hidden pairs/triples/quadruples")
exclude.append((i, j, q))
if len(exclude) != 0: possible.append((exclude, HIDDEN_MULTIPLES, (y, s, points)))
return possible
def basic_fish(rem, mutex_rules, cell_visibility_rules, value_set):
l, possible = len(rem), []
regions = tuple(tuple(x) for x in standard_sudoku_singoverlap_regions(l)) #must be completely not visible from each other, but must each be exactly once intersecting another region twice
for mutex in range(len(regions)):
m = regions[mutex]
for y in value_set:
pre = tuple(frozenset(x for x in n if y in rem[x[0]][x[1]]) for n in m)
for p in range(2, l >> 1): #complementary fish will always exist for larger ones so only X-Wing, Swordfish and Jellyfish needed, Squirmbag, Whale and Leviathan are not strictly necessary
for region in itertools.combinations(range(len(m)), p):
s = tuple(pre[n] for n in region)
if any(not (1 < len(q) <= p) for q in s): continue
su = frozenset.union(*s)
opp = tuple(filter(lambda x: len(su.intersection(x)) != 0, regions[1-mutex]))
if len(opp) <= p:
exclude = []
unn = frozenset.union(*opp).difference(su)
for r in unn:
if y in rem[r[0]][r[1]]:
exclude.append((r[0], r[1], y))
if len(exclude) != 0: possible.append((exclude, BASIC_FISH, ([m[r] for r in region], s, unn)))
return possible
def finned_fish(rem, mutex_rules, cell_visibility_rules, value_set):
l, possible = len(rem), []
regions = tuple(tuple(x) for x in standard_sudoku_singoverlap_regions(l)) #must be completely not visible from each other, but must each be exactly once intersecting another region twice
for mutex in range(len(regions)):
m = regions[mutex]
for y in value_set:
pre = tuple(frozenset(x for x in n if y in rem[x[0]][x[1]]) for n in m)
for p in range(2, l >> 1): #complementary fish always will exist like for basic fish for larger ones
for region in itertools.combinations(range(len(m)), p):
s = tuple(pre[n] for n in region)
if any(len(q) <= 1 for q in s): continue #rule out impossible finned fish
for j in range(p):
if any(i != j and len(q) > p for i, q in enumerate(s)): continue
for z in s[j]:
subs = frozenset(get_sub_square_points(sub_square_from_point(z[0], z[1], l), l))
if not (0 < len(s[j].difference(subs)) <= p - 1): continue #perhaps this logic needs more detail for really compact subsquare cases?
su = frozenset.union(*(x.difference(subs) if i == j else x for i, x in enumerate(s)))
opp = tuple(filter(lambda x: len(su.intersection(x)) != 0, regions[1-mutex]))
if len(opp) <= p:
exclude = []
intsct = subs.intersection(frozenset.union(*opp).difference(su).difference(s[j]))
for r in intsct:
if y in rem[r[0]][r[1]]:
exclude.append((r[0], r[1], y))
if len(exclude) != 0: possible.append((exclude, FINNED_FISH, ([m[r] for r in region], s, intsct)))
return possible
def x_chain(rem, mutex_rules, cell_visibility_rules, value_set, max_depth, dynamic_visibility=None): #solves skyscrapers, empty rectangles (with or without 2 candidates), turbot fish, 2-string kites
#dual 2-kite strings and dual empty rectangles would not be explicitly identified and are the combination of 2 X-chains
l, possible = len(rem), []
def x_chain_rcrse(rem, max_depth, chain, search, exclusions):
possible = []
x, y = chain[-1]
if max_depth == len(chain) - 1: return possible
for points in cell_mutex_visibility(x, y, mutex_rules):
s = [p for p in points if search in rem[p[0]][p[1]] and p != (x, y)] #still need to fix by considering all chain values
if len(s) == 1 and len(exclusions.intersection(s)) == 0: #strong link
if len(chain) != 1:
exclude = []
for p, q in frozenset.intersection(frozenset(cell_visibility(s[0][0], s[0][1], l, cell_visibility_rules)), frozenset(cell_visibility(chain[0][0], chain[0][1], l, cell_visibility_rules))):
if not (p, q) in chain and (p, q) != s[0] and search in rem[p][q]:
#4-length X chain can be a skyscraper or empty rectangle
#print("X-Chain %d in (%d, %d) of length %d" % (search, p, q, len(chain)+1) + " " + str(chain))
exclude.append((p, q, search))
if len(exclude) != 0:
type, fullchain = -1, chain + [s[0]]
if len(fullchain) == 4:
ptsx, ptsy = frozenset(x[0] for x in fullchain), frozenset(x[1] for x in fullchain)
if len(ptsx) == 2 and len(ptsy) == 3 or len(ptsy) == 2 and len(ptsx) == 3:
type = X_CHAIN_SKYSCRAPER
elif len(ptsx) == 3 and len(ptsy) == 3 and sub_square_from_point(*fullchain[1], l) == sub_square_from_point(*fullchain[2], l):
type = X_CHAIN_TWOSTRINGKITE
else: type = X_CHAIN_TURBOT_FISH
possible.append((exclude, X_CHAIN, (fullchain,type)))
cv = cell_visibility(s[0][0], s[0][1], l, cell_visibility_rules)
if not dynamic_visibility is None:
cv |= dynamic_visibility(s[0][0], s[0][1], rem, search)
for point in cv:
if point in chain or not search in rem[point[0]][point[1]]: continue
possible.extend(x_chain_rcrse(rem, max_depth, chain + [s[0], point], search, exclusions.union(cv) | frozenset((s[0],))))
return possible
for x in range(l):
for y in range(l):
if len(rem[x][y]) != 1:
for z in rem[x][y]:
possible.extend(x_chain_rcrse(rem, max_depth, [(x, y)], z, frozenset()))
return possible
def xy_chain(rem, mutex_rules, cell_visibility_rules, value_set, max_depth): #solves XY-Wing/Y-wing, W-Wing and broken triples
#some bug exists in this code
l, possible = len(rem), []
def xy_chain_rcrse(rem, max_depth, chain, search, final):
possible = []
x, y = chain[-1]
if max_depth == len(chain): return possible
for point in cell_visibility(x, y, l, cell_visibility_rules): #weak link
nxt = search.intersection(rem[point[0]][point[1]])
if point in chain or len(rem[point[0]][point[1]]) != 2 or len(nxt) != 1: continue
#if next(iter(nxt)) == final:
if next(iter(rem[point[0]][point[1]] - search)) == final:
exclude = []
for p, q in frozenset.intersection(frozenset(cell_visibility(point[0], point[1], l, cell_visibility_rules)), frozenset(cell_visibility(chain[0][0], chain[0][1], l, cell_visibility_rules))):
if (p, q) != chain[0] and (p, q) != chain[-1] and final in rem[p][q]:
#3-length XY chain is a broken triple or XY-Wing/Y-Wing with pivot as center value
#4-length XY chain with the outer 2 in the chain and inner 2 in the chain with the same values is a W-Wing
#print("XY-Chain %d in (%d, %d) of length %d" % (final, p, q, len(chain)+1))
exclude.append((p, q, final))
if len(exclude) != 0: possible.append((exclude, XY_CHAIN, (chain + [point], final)))
possible.extend(xy_chain_rcrse(rem, max_depth, chain + [point], rem[point[0]][point[1]].difference(search), next(iter(search.difference(rem[point[0]][point[1]]))) if final is None else final))
return possible
for x in range(l):
for y in range(l):
if len(rem[x][y]) == 2:
possible.extend(xy_chain_rcrse(rem, max_depth, [(x, y)], rem[x][y], None))
"""
for x in range(l):
points = get_sub_square_points(x) #because rows/columns have 0 interaction with rows/columns, rows and columns interact at 1 point, subsquares and rows/columns have 3 interactions
for y in itertools.combinations(range(l), 2): #XY-Wing/Y-Wing/broken triples
s1, s2 = rem[points[y[0]][0]][points[y[0]][1]], rem[points[y[1]][0]][points[y[1]][1]]
if len(s1) != 2 or len(s2) != 2 or len(set(s1).intersection(s2)) != 1: continue
for z in range(l):
if sub_square_from_point(z, points[y[0]][1]) != sub_square_from_point(x, points[y[0]][1]) and points[y[0]][1] != points[y[1]][1]:
s3 = rem[z][points[y[0]][1]]
si = set(s2).intersection(s3)
if len(s3) == 2 and len(si) == 1 and len(set(s1).intersection(s3)) == 1 and si != set(s1).intersection(s3):
for q in set(p[0] for p in get_sub_square_points(sub_square_from_point(z, points[y[1]][1]))): #range(z // 3 * 3, z // 3 * 3 + 3):
if q != points[y[1]][0] and next(iter(si)) in rem[q][points[y[1]][1]]:
print("Broken Triple %d in (%d, %d) from (%d, %d), (%d, %d), (%d, %d)" % (next(iter(si)), q, points[y[1]][1], points[y[0]][0], points[y[0]][1], points[y[1]][0], points[y[1]][1], z, points[y[0]][1]))
rem, c = cell_sudoku_remove(rem, q, points[y[1]][1], next(iter(si)))
count += 1 + c
s3 = rem[z][points[y[1]][1]]
si = set(s1).intersection(s3)
if len(s3) == 2 and len(si) == 1 and len(set(s2).intersection(s3)) == 1 and si != set(s2).intersection(s3):
for q in set(p[0] for p in get_sub_square_points(sub_square_from_point(z, points[y[0]][1]))): #range(z // 3 * 3, z // 3 * 3 + 3):
if q != points[y[0]][0] and next(iter(si)) in rem[q][points[y[0]][1]]:
print("Broken Triple %d in (%d, %d) from (%d, %d), (%d, %d), (%d, %d)" % (next(iter(si)), q, points[y[0]][1], points[y[0]][0], points[y[0]][1], points[y[1]][0], points[y[1]][1], z, points[y[1]][1]))
rem, c = cell_sudoku_remove(rem, q, points[y[0]][1], next(iter(si)))
count += 1 + c
if sub_square_from_point(points[y[0]][0], z) != sub_square_from_point(points[y[0]][0], x) and points[y[0]][0] != points[y[1]][0]:
s3 = rem[points[y[0]][0]][z]
si = set(s2).intersection(s3)
if len(s3) == 2 and len(si) == 1 and len(set(s1).intersection(s3)) == 1 and si != set(s1).intersection(s3):
for q in set(p[1] for p in get_sub_square_points(sub_square_from_point(points[y[1]][0], z))): #range(z // 3 * 3, z // 3 * 3 + 3):
if q != points[y[1]][1] and next(iter(si)) in rem[points[y[1]][0]][q]:
print("Broken Triple %d in (%d, %d) from (%d, %d), (%d, %d), (%d, %d)" % (next(iter(si)), points[y[1]][0], q, points[y[0]][0], points[y[0]][1], points[y[1]][0], points[y[1]][1], points[y[0]][0], z))
print_candidate_format(rem)
rem, c = cell_sudoku_remove(rem, points[y[1]][0], q, next(iter(si)))
count += 1 + c
s3 = rem[points[y[1]][0]][z]
si = set(s1).intersection(s3)
if len(s3) == 2 and len(si) == 1 and len(set(s2).intersection(s3)) == 1 and si != set(s2).intersection(s3):
for q in set(p[1] for p in get_sub_square_points(sub_square_from_point(points[y[0]][0], z))): #range(z // 3 * 3, z // 3 * 3 + 3):
if q != points[y[0]][1] and next(iter(si)) in rem[points[y[0]][0]][q]:
print("Broken Triple %d in (%d, %d) from (%d, %d), (%d, %d), (%d, %d)" % (next(iter(si)), points[y[0]][0], q, points[y[0]][0], points[y[0]][1], points[y[1]][0], points[y[1]][1], points[y[1]][0], z))
rem, c = cell_sudoku_remove(rem, points[y[0]][0], q, next(iter(si)))
count += 1 + c
"""
return possible
"""
def skyscraper(rem, cell_visibility_rules, value_set):
l, possible = len(rem), []
for x in range(l):
for y in value_set: #skyscraper
matches = set([j for j in range(l) if y in rem[x][j]])
if len(matches) == 2:
for z in range(x+1, l):
subt = set([j for j in range(l) if y in rem[z][j]])
if len(subt) == 2 and len(matches.intersection(subt)) == 1:
exclude = []
for (p, q) in cell_visibility(x, list(matches.difference(subt))[0], l, cell_visibility_rules).intersection(cell_visibility(z, list(subt.difference(matches))[0], l, cell_visibility_rules)):
if y in rem[p][q]:
print("Skyscraper %d in (%d, %d)" % (y, p, q))
exclude.append((p, q, y))
if len(exclude) != 0: possible.append((exclude, X_CHAIN, (0)))
matches = set([j for j in range(l) if y in rem[j][x]])
if len(matches) == 2:
for z in range(x+1, l):
subt = set([j for j in range(l) if y in rem[j][z]])
if len(subt) == 2 and len(matches.intersection(subt)) == 1:
exclude = []
for (p, q) in cell_visibility(list(matches.difference(subt))[0], x, l, cell_visibility_rules).intersection(cell_visibility(list(subt.difference(matches))[0], z, l, cell_visibility_rules)):
if y in rem[p][q]:
print("Skyscraper %d in (%d, %d)" % (y, p, q))
exclude.append((p, q, y))
if len(exclude) != 0: possible.append((exclude, X_CHAIN, (1)))
return possible
def empty_rectangle(rem, cell_visibility_rules, value_set):
l, possible = len(rem), []
for x in range(l):
points = get_sub_square_points(x) #because rows/columns have 0 interaction with rows/columns, rows and columns interact at 1 point, subsquares and rows/columns have 3 interactions
for y in value_set:
total = sum(1 for z in points if y in rem[z[0]][z[1]])
if total == 1: continue
for p in set(z[0] for z in points):
for q in set(z[1] for z in points):
sc, sr = sum(1 for z in points if z[0] == p and y in rem[z[0]][z[1]]), sum(1 for z in points if z[1] == q and y in rem[z[0]][z[1]])
if sc != 1 and sr != 1 and total == sum(1 for z in points if (z[0] == p or z[1] == q) and y in rem[z[0]][z[1]]):
excluder, excludec = [], []
for r in range(l):
if not (p, r) in points and y in rem[p][r]:
s = [z for z in range(l) if z != p and not (z, r) in points and y in rem[z][r]]
if len(s) == 1:
if not (s[0], q) in points and y in rem[s[0]][q]:
print("Row Empty Rectangle %d in (%d, %d) along (%d, %d)" % (y, s[0], q, p, r))
excluder.append((s[0], q, y))
if not (r, q) in points and y in rem[r][q]:
s = [z for z in range(l) if z != q and not (r, z) in points and y in rem[r][z]]
if len(s) == 1:
if not (p, s[0]) in points and y in rem[p][s[0]]:
print("Column Empty Rectangle %d in (%d, %d) along (%d, %d)" % (y, p, s[0], r, q))
excludec.append((p, s[0], y))
if len(excluder) != 0: possible.append((excluder, X_CHAIN, (0)))
if len(excludec) != 0: possible.append((excludec, X_CHAIN, (1)))
return possible
"""
def best_bifurcate(sudoku, mutex_rules, cell_visibility_rules, value_set):
def bifurcate_inner(sudoku): #to make a proof, must not bifurcate repeatedly without trying all candidates in a cell
if check_sudoku(sudoku, mutex_rules, value_set)[1]: return False
if any(any(len(y) == 0 for y in x) for x in sudoku): return True
for i in range(l):
for j in range(l):
if len(sudoku[i][j]) != 1:
for z in sudoku[i][j]: #all must not have a solve path
rem = cell_sudoku_rule([[y.copy() for y in x] for x in sudoku], i, j, z, cell_visibility_rules)
if any(any(len(y) == 0 for y in x) for x in rem): continue
rem, _ = sudoku_loop(rem, mutex_rules, cell_visibility_rules, (), value_set)
if rem is None: continue
if not bifurcate_inner(rem): return False
return True
def bifurcate_depth(sudoku, depth, maxdepth=None):
if depth == maxdepth: return float("inf")
if check_sudoku(sudoku, mutex_rules, value_set)[1]: return None
if any(any(len(y) == 0 for y in x) for x in sudoku): return 0
mindepth = None
for i in range(l):
for j in range(l):
if len(sudoku[i][j]) != 1:
depths = []
for z in sudoku[i][j]:
rem = cell_sudoku_rule([[y.copy() for y in x] for x in sudoku], i, j, z, cell_visibility_rules)
if any(any(len(y) == 0 for y in x) for x in rem): depths.append(1); continue
rem, solve_path = sudoku_loop(rem, mutex_rules, cell_visibility_rules, (), value_set)
if rem is None: depths.append(1); continue
res = bifurcate_depth(rem, depth+1, maxdepth if mindepth is None else min(mindepth+1, maxdepth))
if res is None: return None
depths.append(1 + res)
mindepth = max(depths) if mindepth is None else min(mindepth, max(depths))
#if depth == 0: print(depths)
return mindepth
l = len(sudoku)
depth = [[{} for _ in range(l)] for _ in range(l)]
print(sum([len(sudoku[i][j]) for i in range(l) for j in range(l) if len(sudoku[i][j]) != 1]))
for i in range(l):
for j in range(l):
if len(sudoku[i][j]) != 1:
for z in sudoku[i][j]:
rem = cell_sudoku_rule([[y.copy() for y in x] for x in sudoku], i, j, z, cell_visibility_rules)
if any(any(len(y) == 0 for y in x) for x in rem): depth[i][j][z] = 1; continue
rem, solve_path = sudoku_loop(rem, mutex_rules, cell_visibility_rules, (), value_set)
if rem is None: depth[i][j][z] = 1; print(i, j, z, logical_solve_string(solve_path, mutex_rules)); continue
if not bifurcate_inner(rem): continue #first need to make sure its a solution e.g. infinite depth
curdepth = 1
while True:
res = bifurcate_depth(rem, 0, curdepth)
if res != float("inf"):
if not res is None: depth[i][j][z] = 1 + res
break
curdepth += 1
print(i, j, depth[i][j])
print(depth)
return depth
def bifurcate(sudoku, mutex_rules, cell_visibility_rules, value_set): #exclusion so not assuming uniqueness
best_bifurcate(sudoku, mutex_rules, cell_visibility_rules, value_set)
def bifurcate_inner(sudoku): #to make a proof, must not bifurcate repeatedly without trying all candidates in a cell
if check_sudoku(sudoku, mutex_rules, value_set)[1]: return False
if any(any(len(y) == 0 for y in x) for x in sudoku): return True
for i in range(l):
for j in range(l):
if len(sudoku[i][j]) != 1:
for z in sudoku[i][j]: #all must not have a solve path
rem = cell_sudoku_rule([[y.copy() for y in x] for x in sudoku], i, j, z, cell_visibility_rules)
if any(any(len(y) == 0 for y in x) for x in rem): continue
rem, _ = sudoku_loop(rem, mutex_rules, cell_visibility_rules, (), value_set)
if rem is None: continue
if not bifurcate_inner(rem): return False
return True
l = len(sudoku)
for i in range(l):
for j in range(l):
if len(sudoku[i][j]) != 1:
for z in sudoku[i][j]:
rem = cell_sudoku_rule([[y.copy() for y in x] for x in sudoku], i, j, z, cell_visibility_rules)
if any(any(len(y) == 0 for y in x) for x in rem): return ((((i, j, z),), BIFURCATION, ()),)
rem, _ = sudoku_loop(rem, mutex_rules, cell_visibility_rules, (), value_set)
if rem is None: return ((((i, j, z),), BIFURCATION, ()),)
if bifurcate_inner(rem): return ((((i, j, z),), BIFURCATION, ()),)
return []
def lookup_mutex(points, mutex_rules):
for i, regions in enumerate(mutex_rules):
for j, r in enumerate(regions):
if points.issubset(r): #if points == r:
return i, j
return None
def get_mutex_string(points, mutex_rules):
region_names = ("Row", "Column", "Subsquare", "Region")
x = lookup_mutex(points, mutex_rules)
if not x is None:
i, j = x
subsquare_names = ("Northwest", "Northern", "Northeastern", "Western", "Central", "Eastern", "Southwestern", "Southern", "Southeastern")
if mutex_rules[i][j] == subsquare_points(next(iter(points))[0], next(iter(points))[1], len(mutex_rules[i][j])):
return subsquare_names[j] + " " + region_names[i]
else:
return region_names[i] + " " + str(j + 1)
else:
return "Area" + " " + get_cells_string(points, False)
def get_cell_string(point):
return "r" + str(point[0] + 1) + "c" + str(point[1] + 1)
def get_cells_string(cells, for_latex):
if for_latex: return r",\\".join(", ".join(get_cell_string(x) for x in cells[i:i+2]) for i in range(0, len(cells), 2))
else: return ", ".join(get_cell_string(x) for x in cells)
def get_cell_vals_string(cellvals, for_latex):
if for_latex: return r",\\".join(", ".join("%d in %s" % (z, get_cell_string((x, y))) for (x, y, z) in cellvals[i:i+2]) for i in range(0, len(cellvals), 2))
else: return ", ".join("%d in %s" % (z, get_cell_string((x, y))) for (x, y, z) in cellvals)
def logic_step_string(step, mutex_rules, for_latex=False):
multiples = ("Pairs", "Triples", "Quadruples", "Quintuples", "Sextuples", "Septuples", "Octuples", "Nonuples", "Decuple")
fish = ("X-Wing", "Swordfish", "Jellyfish", "Squirmbag", "Whale", "Leviathan")
x_chain_specific = ("Skyscraper", "2-String Kite", "Turbot Fish", "Empty Rectangle")
name = STRING_RULES[step[1]]
if step[1] in (LAST_DIGIT, FULL_HOUSE, NAKED_SINGLE):
logic = "in " + get_cell_string(step[2][0])
elif step[1] == HIDDEN_SINGLE:
logic = "along " + get_mutex_string(step[2][0], mutex_rules)
elif step[1] == LOCKED_CANDIDATES:
i, _ = lookup_mutex(step[2][0], mutex_rules)
logic = "in " + get_mutex_string(step[2][0], mutex_rules) + (r"\\" if for_latex else " ") + "cells " + get_cells_string(step[2][2], for_latex) + (r"\\" if for_latex else " ") + ("pointing at" if i != 0 and i != 1 else "claiming from") + (r"\\" if for_latex else " ") + get_mutex_string(step[2][1], mutex_rules)
elif step[1] == HIDDEN_MULTIPLES or step[1] == NAKED_MULTIPLES:
name = name % multiples[len(step[2][0])-1-1]
logic = "in " + get_mutex_string(step[2][2], mutex_rules) + (r"\\" if for_latex else " ") + "cells " + get_cells_string(step[2][0], for_latex) + (r"\\" if for_latex else " ") + "with values" + (r"\\" if for_latex else " ") + ", ".join(str(x) for x in sorted(step[2][1]))
elif step[1] == BASIC_FISH or step[1] == FINNED_FISH:
name = name % fish[len(step[2][0])-2]
logic = "in " + ", ".join(get_mutex_string(x, mutex_rules) for x in step[2][0]) + (r"\\" if for_latex else " ") + "cells " + get_cells_string(tuple(frozenset.union(*step[2][1])), for_latex) + (r"\\" if for_latex else " ") + "for value " + str(step[0][0][2])
elif step[1] == X_CHAIN:
if step[2][1] != -1: name = x_chain_specific[step[2][1]]
logic = "along " + get_cells_string(step[2][0], for_latex) + " with value " + str(step[0][0][2])
else: logic = str(step[2])
return name + (r"\\" if for_latex else " ") + logic + (r"\\" if for_latex else " ") + "excludes" + (r"\\" if for_latex else " ") + get_cell_vals_string(step[0], for_latex)
def logical_solve_string(steps, mutex_rules):
return '\n'.join(logic_step_string(x, mutex_rules) for x in steps)
def exclude_sudoku_by_group(rem, mutex_rules, cell_visibility_rules, exclude_rule, value_set): #combine rule for row/column with sub regions
if check_bad_sudoku(rem): return rem, False
for func in exclude_rule + (naked_single, hidden_single, locked_candidates, mutex_multiples, basic_fish, #skyscraper, empty_rectangle,
lambda rm, mr, cv, vs: x_chain(rm, mr, cv, vs, 4), finned_fish,
lambda rm, mr, cv, vs: xy_chain(rm, mr, cv, vs, 3),
lambda rm, mr, cv, vs: x_chain(rm, mr, cv, vs, 6), lambda rm, mr, cv, vs: xy_chain(rm, mr, cv, vs, None),
#bifurcate
):
possible = func(rem, mutex_rules, cell_visibility_rules, value_set)
if len(possible) != 0:
#print(logic_step_string(possible[0], mutex_rules))
for (x, y, z) in possible[0][0]:
#sol = str_to_sudoku("174835269695472138832169475381294756946753821527618394259381647713946582468527913")
#sol = str_to_sudoku("179524863285316947634978251826143795497852316513769482958231674361497528742685139")
#sol = str_to_sudoku("178469523463275981592381674357894162216753498849612357634927815921538746785146239")
#sol = str_to_sudoku("1527346427365157364127364125361257421457636451237")
#if z == sol[x][y]:
#print_candidate_format(rem)
#print(possible[0], STRING_RULES[possible[0][1]])
#raise ValueError
if not z in rem[x][y]:
print(x, y, z, possible)
raise ValueError