/
sudoku.py
714 lines (576 loc) · 30.2 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
"""An example data algebra script. Naively solve a Sudoku game using techniques a person would
likely use. This is a teaching exercise, not an attempt at writing the fastest solver possible."""
# $Id: sudoku.py 22726 2015-08-04 14:12:37Z jaustell $
# Copyright Algebraix Data Corporation 2015 - $Date: 2015-08-04 09:12:37 -0500 (Tue, 04 Aug 2015) $
#
# This file is part of algebraixlib <http://github.com/AlgebraixData/algebraixlib>.
#
# algebraixlib is free software: you can redistribute it and/or modify it under the terms of version
# 3 of the GNU Lesser General Public License as published by the Free Software Foundation.
#
# algebraixlib is distributed in the hope that it will be useful, but WITHOUT ANY WARRANTY; without
# even the implied warranty of MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
# Lesser General Public License for more details.
#
# You should have received a copy of the GNU Lesser General Public License along with algebraixlib.
# If not, see <http://www.gnu.org/licenses/>.
# --------------------------------------------------------------------------------------------------
import time
from functools import partial
import itertools
from algebraixlib.mathobjects import Atom, CacheStatus, Couplet, Set
import algebraixlib.algebras.relations as relations
import algebraixlib.algebras.clans as clans
import algebraixlib.algebras.sets as sets
import algebraixlib.extension as extension
import algebraixlib.partition as partition
from algebraixlib.undef import Undef
VERBOSE = False
# VERBOSE = True
BLOCK_SIZE = 3
GRID_SIZE = BLOCK_SIZE * BLOCK_SIZE
BLOCK_VALUES_CLAN = Set(
Set(Couplet('value', i)).cache_relation(CacheStatus.IS).cache_functional(CacheStatus.IS)
for i in range(1, GRID_SIZE + 1)).cache_clan(CacheStatus.IS).cache_functional(
CacheStatus.IS).cache_regular(CacheStatus.IS)
BANDS_STACKS = Set(
(relations.from_dict({'row': r, 'col': c, 'band': int((r - 1) / BLOCK_SIZE) + 1,
'stack': int((c - 1) / BLOCK_SIZE) + 1})
for r, c in itertools.product(list(range(1, GRID_SIZE + 1)), list(range(1, GRID_SIZE + 1))))
).cache_clan(CacheStatus.IS).cache_functional(CacheStatus.IS).cache_regular(CacheStatus.IS)
def _sorted(iterable, key=None):
return sorted(iterable, key=key)
def _unsorted(iterable, key=None):
_ = key
return iterable # sorting is for debugging...for performance don't sort
# _SORT = _sorted # To get consistent timing/debugging
_SORT = _unsorted
def make_board(_puzzle):
assert len(_puzzle) == GRID_SIZE * GRID_SIZE
board = set()
for i, value in enumerate(_puzzle):
value = 0 if value == '.' else int(value)
col = (i % GRID_SIZE) + 1
row = int(i / GRID_SIZE) + 1
band = int((row - 1) / BLOCK_SIZE) + 1
stack = int((col - 1) / BLOCK_SIZE) + 1
# cell = {'row': row, 'col': col}
cell = {'row': row, 'col': col, 'band': band, 'stack': stack}
if value != 0:
cell['value'] = value
board.add(relations.from_dict(cell))
return Set(board, direct_load=True).cache_clan(CacheStatus.IS).cache_functional(CacheStatus.IS)
def print_string(board):
if VERBOSE:
print(get_string(board))
def by_key(key, rel):
return rel(key)
def by_keys(key1, key2, rel):
val1 = rel(key1)
val2 = rel(key2)
return val1, val2
def by_clan_key(key, clan):
return sets.single(clan[key])
def by_clan_keys(key1, key2, clan):
val1 = sets.single(clan[key1])
val2 = sets.single(clan[key2])
return val1, val2
def get_string(board):
digits = []
for cell in sorted(board, key=partial(by_keys, 'row', 'col')):
value = cell('value')
digits.append(0 if value is Undef() else value.value)
assert len(digits) == GRID_SIZE * GRID_SIZE
return ''.join(str(x) for x in digits)
def get_filled_cells(board):
return clans.defined_at(board, Atom('value'), _checked=False)
def project(clan: 'PP(M x M)', *lefts) -> 'PP(M x M)':
clan = clans.project(clan, *lefts)
return clan
def get_missing_values(clan):
"""Get remaining values from passed in clan by subtracting it from from all possible values."""
values_clan = project(clan, 'value')
return sets.minus(BLOCK_VALUES_CLAN, values_clan)
def get_missing_rowcols(block_clan):
band, stack = by_clan_keys('band', 'stack', block_clan)
# Get block defined by band, stack
full_block_clan = clans.superstrict(BANDS_STACKS,
clans.from_dict({'band': band, 'stack': stack}))
# Get missing rows/cols from the block
target_rowcols = sets.minus(project(full_block_clan, 'row', 'col'),
project(block_clan, 'row', 'col'))
return target_rowcols
def get_new_board(board, new_cells):
if VERBOSE:
for cell in new_cells:
row = cell('row').value
col = cell('col').value
value = cell('value').value
print("*** value %d goes in Row %d, Col %d" % (value, row, col))
cell_filter = project(new_cells, 'row', 'col')
old_cells = clans.superstrict(board, cell_filter)
new_board = sets.minus(board, old_cells)
band = new_cells['band']
if not band:
# print("missing band")
bands_stacks = clans.superstrict(BANDS_STACKS, cell_filter)
new_cells = clans.cross_functional_union(new_cells, bands_stacks)
new_board = sets.union(new_board, new_cells)
# if VERBOSE:
# print(get_string(new_board))
assert len(new_board) == GRID_SIZE * GRID_SIZE
return new_board
def check_values(_board):
"""Look for values where only one is missing. If there is only one missing, then there is
only one cell where adding the value would not cause a duplicate in a row or column. Fill
in those cells if they exist."""
if VERBOSE:
print("* check_values")
board = get_filled_cells(_board)
new_cells = Set()
value_clans = partition.partition(board, partial(by_key, 'value'))
for value_clan in _SORT(value_clans, key=partial(by_clan_key, 'value')):
# If there is only 1 missing value..fill in the cell
if value_clan.cardinality == GRID_SIZE - 1:
# Get the set of rows and cols containing value
occupied_rows = project(value_clan, 'row')
occupied_cols = project(value_clan, 'col')
# Get the entire set of rows and cols based on the occupied rows and cols
occupied = clans.superstrict(_board, sets.union(occupied_rows, occupied_cols))
# Remove all occupied rows to get the only candidate row_col left
row_col = sets.minus(_board, occupied)
value = project(value_clan, 'value')
new_cells = sets.union(new_cells, clans.cross_union(row_col, value))
if new_cells:
return get_new_board(_board, new_cells)
return _board
def check_rows(_board, try_harder=0):
"""Look for rows where there is only one missing value. If any are found fill in the missing
value. Look for rows where there are two missing values. If either missing value is blocked
by the same value in the candidate row, col, or block then the other value can be placed in
the blocked cell. The other value can be placed in the other cell. Look for rows with more
than two missing values. Check each empty cell to see only one of the missing values can be
placed in it. Check each value to see if there is only one cell where it can be placed."""
if VERBOSE:
print("* check_rows")
board = get_filled_cells(_board)
all_rows_clans = partition.partition(board, partial(by_key, 'row'))
for row_clan in _SORT(all_rows_clans, key=partial(by_clan_key, 'row')):
row = project(row_clan, 'row')
board_row = clans.superstrict(_board, row)
values_clan = get_missing_values(row_clan)
if row_clan.cardinality == GRID_SIZE - 1:
# Row is missing only 1 value, remove row_clan from the board leaving target row_col
row_col = sets.minus(board_row, row_clan)
new_cells = clans.cross_union(row_col, values_clan)
_board = get_new_board(_board, new_cells)
try_harder = 0
continue
# Get the set of candidate col/value pairs
row_possible = clans.cross_union(values_clan,
project(sets.minus(board_row, row_clan), 'col'))
if row_clan.cardinality == GRID_SIZE - 2:
# The occupied_clan is the col/value pair that is a conflict for each col/value
occupied_clan = project(clans.superstrict(board, row_possible), 'col', 'value')
# If there are no conflicts neither value can be placed without checking entire board
if not occupied_clan.is_empty:
# ..remove occupied_clan col/value pairs from all possible
new_possible = sets.minus(row_possible, occupied_clan)
if new_possible.cardinality == 2:
# Of the 4 possibilities (2 values * 2 cols), 2 were removed, place remaining
new_cells = clans.cross_union(row, new_possible)
_board = get_new_board(_board, new_cells)
try_harder = 0
continue
# 3 of the possibilities remain...
occupied_col = project(occupied_clan, 'col')
# Remove the occupied_col choices to get the first col/value pair
col_value1 = clans.superstrict(new_possible, occupied_col)
occupied_val = project(col_value1, 'value')
# Remove the occupied_val choices to get the second col/value pair
col_value2 = sets.minus(new_possible, clans.superstrict(new_possible, occupied_val))
new_cells = clans.cross_union(row, col_value1)
new_cells = sets.union(new_cells, clans.cross_union(row, col_value2))
_board = get_new_board(_board, new_cells)
try_harder = 0
continue
# The occupied_clan is the row/col/value set that could be a conflict for values
occupied_clan = clans.superstrict(board, values_clan)
# If there are no conflicts then no cells can be placed
if occupied_clan.is_empty:
continue
# Add row to row_possible for remaining checks
all_possible = clans.cross_union(row_possible, row)
# Get the set of conflicts...conflicting row/value + col/value
conflict = sets.union(
clans.superstrict(all_possible,
project(occupied_clan, 'value', 'col')),
clans.superstrict(all_possible,
project(occupied_clan, 'value', 'row')))
# Remove the conflicts from all_possible
new_possible = sets.minus(all_possible, conflict)
if new_possible.is_empty:
continue # All possible may have been excluded due to row/col conflicts
# Otherwise...need to check for block (band+stack) conflicts too!!
# ...if value exists in same block as element of all_possible
# Add band/stack
new_targets = clans.superstrict(BANDS_STACKS, project(new_possible, 'row', 'col'))
new_possible3 = clans.cross_functional_union(new_targets, new_possible)
occupied_clan2 = occupied_clan
# Remove block (band+stack) conflicts
new_possible4a = sets.minus(project(new_possible3, 'value', 'band', 'stack'),
project(occupied_clan2, 'value', 'band', 'stack'))
new_possible4 = clans.superstrict(new_possible3, new_possible4a)
while True:
candidates_updated = False
# Partition by row/col
placed = 0
candidates = partition.partition(new_possible4, partial(by_keys, 'row', 'col'))
for candidate in _SORT(candidates, key=partial(by_clan_key, 'col')):
# If any row/col has only 1 candidate, place it
if candidate.cardinality == 1:
# Remove band/stack
_board = get_new_board(_board, candidate)
try_harder = 0
placed += 1
if placed:
break
# Partition by value
candidates = partition.partition(new_possible4, partial(by_key, 'value'))
for candidate in _SORT(candidates, key=partial(by_clan_key, 'value')):
# If any value fits in only 1 cell, place it
if candidate.cardinality == 1:
# Remove band/stack
_board = get_new_board(_board, candidate)
try_harder = 0
else: # If any value must be placed elsewhere, remove as candidate for this cell
if try_harder:
value = project(candidate, 'value')
# If this row of a sibling block must contain this value...
blocks = partition.partition(candidate, partial(by_keys, 'band', 'stack'))
if blocks.cardinality > 1:
for block_clan in _SORT(blocks,
key=partial(by_clan_keys, 'band', 'stack')):
block = project(block_clan, 'band', 'stack')
board_block = clans.superstrict(board, block)
if board_block.is_empty:
continue
new_possible, conflict = get_block_candidates(board_block, board)
new_possible_value = clans.superstrict(new_possible, value)
if new_possible_value['row'].cardinality == 1:
# Value must be placed in this block
# ...other block candidates can be removed
remove = sets.minus(candidate, block_clan)
new_possible4 = sets.minus(new_possible4, remove)
candidates_updated = True
if not candidates_updated or not try_harder:
break
return _board
def check_cols(_board, try_harder=0):
"""Check the columns the same way rows are checked"""
if VERBOSE:
print("* check_cols")
# Rotate the board by swapping row and col then call check_rows
swaps = clans.from_dict({'row': 'col', 'band': 'stack'})
rotated = extension.binary_extend(
_board, swaps, partial(relations.swap, _checked=False)).cache_clan(
CacheStatus.IS).cache_functional(CacheStatus.IS)
new_board = check_rows(rotated, try_harder)
if rotated is not new_board:
_board = extension.binary_extend(
new_board, swaps, partial(relations.swap, _checked=False)
).cache_clan(CacheStatus.IS).cache_functional(CacheStatus.IS)
return _board
def get_block_candidates(block_clan, board):
# Get the set of missing values...see if any can be placed due to row/col information
values_clan = get_missing_values(block_clan)
# Get the set of missing values...see if any can be placed due to row/col information
target_rowcols = get_missing_rowcols(block_clan)
if block_clan.cardinality == GRID_SIZE - 1:
new_cells = clans.cross_union(target_rowcols, values_clan)
return new_cells, Set()
# Need cross union values with rows
rows_clan = project(target_rowcols, 'row')
cols_clan = project(target_rowcols, 'col')
possible_rows_values = clans.cross_union(values_clan, rows_clan)
possible_cols_values = clans.cross_union(values_clan, cols_clan)
possible_rows_cols_values = sets.union(possible_rows_values, possible_cols_values)
# The occupied_clan is the row/col/value set that is a conflict for values
occupied_clan = clans.superstrict(board, possible_rows_cols_values)
# If there are no conflicts then no cells can be placed
if occupied_clan.is_empty:
return Set(), Set()
all_possible = clans.cross_union(values_clan, target_rowcols).cache_functional(CacheStatus.IS)
# Get the set of conflicts...conflicting row/value + col/value
conflict = sets.union(
clans.superstrict(all_possible, project(occupied_clan, 'value', 'col')),
clans.superstrict(all_possible, project(occupied_clan, 'value', 'row')))
# Remove the conflicts from all_possible
new_possible = sets.minus(all_possible, conflict)
return new_possible, conflict
def check_blocks(_board):
"""Check each block. If there is only one value missing..."""
if VERBOSE:
print("* check_blocks")
board = get_filled_cells(_board)
blocks = partition.partition(board, partial(by_keys, 'band', 'stack'))
for block_clan in _SORT(blocks, key=partial(by_clan_keys, 'band', 'stack')):
new_possible, conflict = get_block_candidates(block_clan, board)
if new_possible.is_empty:
continue
if new_possible.cardinality == 1:
_board = get_new_board(_board, new_possible)
continue
if block_clan.cardinality == GRID_SIZE - 2:
# Knowing that the value in conflict can't be placed in the conflict cell
# ..it must go in the other...
first_choice = clans.superstrict(new_possible, project(conflict, 'value'))
if first_choice.cardinality == 2:
# place both values
_board = get_new_board(_board, first_choice)
continue
# Remove the first choice for all_possible
remaining_possible = sets.minus(new_possible, first_choice)
# Knowing that first_choice goes in a row/col, remove other value from that cell
first_rowcol = project(first_choice, 'row', 'col')
# The remaining cell is the second choice
second_choice = sets.minus(remaining_possible,
clans.superstrict(remaining_possible, first_rowcol))
new_cells = sets.union(first_choice, second_choice)
_board = get_new_board(_board, new_cells)
continue
# Partition by value
candidates = partition.partition(new_possible, partial(by_key, 'value'))
for candidate in _SORT(candidates, key=partial(by_clan_key, 'value')):
# If any value fits in only 1 cell, place it
if candidate.cardinality == 1:
# Remove band/stack
new_cell = project(candidate, 'row', 'col', 'value')
_board = get_new_board(_board, new_cell)
return _board
def check_done(_board):
board = get_filled_cells(_board)
if board.cardinality == GRID_SIZE * GRID_SIZE:
if VERBOSE:
print("done")
return True
if VERBOSE:
print("> %d cells remaining" % (GRID_SIZE * GRID_SIZE - board.cardinality))
return False
def solve_board(board):
try_harder = 0
while not check_done(board):
board_start = board
board = check_values(board)
board = check_rows(board, try_harder)
if board_start is not board:
try_harder = 0
board = check_cols(board, try_harder)
if board_start is not board:
try_harder = 0
board = check_blocks(board)
if board_start is board:
if try_harder == 0:
if VERBOSE:
print("*** no cells placed..trying harder")
try_harder = 1
elif try_harder == 1:
if VERBOSE:
print("*** can't solve")
break
else:
if try_harder:
try_harder = 0
return board
def solve_puzzle(_puzzle, _answer):
print(_puzzle)
start = time.time()
board = solve_board(make_board(_puzzle))
result = get_string(board)
if _answer != result:
if VERBOSE:
print("*** Wrong answer\nExpected: %s\nActual : %s" % (_answer, result))
return False
end = time.time()
if VERBOSE:
print("solve_puzzle took: %d seconds" % (end - start))
return True
import unittest
class SudokuTest(unittest.TestCase):
# quick_tests = True
quick_tests = False
def _test_func(self, _puzzle, _answer, method):
board = make_board(_puzzle.replace('\n', ''))
global _SORT
sorting = _SORT
# NOTE: Tests with partial data (12...5.6) requires sorting to be enabled or tests will fail
_SORT = _sorted
actual = get_string(method(board))
_SORT = sorting
expected = _answer.replace('.', '0')
if actual != expected:
print("*** Wrong answer\nExpected: %s\nActual : %s" % (expected, actual))
self.assertEqual(actual, expected)
def test_values(self):
self._test_func(
# Missing only one 1 in row 1 col 1
'..........1.........1.........1.........1.........1.........1.........1.........1',
'1.........1.........1.........1.........1.........1.........1.........1.........1',
check_values)
def test_row(self):
self._test_func(
# Single missing value in row 1
'.23456789........................................................................',
'123456789........................................................................',
check_rows)
if self.quick_tests:
return
self._test_func(
# Two missing values..neither with conflicts..neither can be filled
'.2345678.........................................................................',
'.2345678.........................................................................',
check_rows)
self._test_func(
# Two missing values..only 1 without conflicts..both can be filled
'.2345678.1.......................................................................',
'9234567811.......................................................................',
check_rows)
self._test_func(
# Two missing values..both with conflicts..both can be filled
'.2345678.1.......9...............................................................',
'9234567811.......9...............................................................',
check_rows)
self._test_func(
# Three missing values..only 1 without conflicts..1 can be placed in col 9
'..345678.129............29.......................................................',
'..3456781129............29.......................................................',
check_rows)
self._test_func(
# 3 missing values on row 1, no conflicts with 2 in col 7
'170904065059000740000507019002000957795426183381795426926178534834059071517040090',
'170904265059000740000507019002000957795426183381795426926178534834059071517040090',
check_rows)
self._test_func(
# 6 missing values...3 only fits in col 1
'010500200900321000002008030500030007008017500600085004040100700000700006003804050',
'310500200900321000002008030500030007008017500600085004040100700000700006003804050',
check_rows)
self._test_func(
# 3 missing values, only 1 value without conflict
'..4.5678912........3........1.......2........3....................2........3.....',
'..415678912........3........1.......2........3....................2........3.....',
check_rows)
self._test_func(
# Region conflict...3 missing values, 1 without conflict
'...456789.23................1.............................................1......',
'1..456789.23................1.............................................1......',
check_rows)
self._test_func(
# Region conflict...3 missing values, only 1 value without conflict
'..4.56789123.........2........3.....3....................................3.......',
'..4156789123.........2........3.....3....................................3.......',
check_rows)
self._test_func(
# Region conflicts...3 missing values, only 1 value without conflict
# place 1 in row 1 col 4
'..4.56789123.........23..........................................................',
'..4156789123.........23..........................................................',
check_rows)
self._test_func(
# Place 3 in row 1 col 6 by eliminating block conflicts..
'1..92....524.17..9......271.5...81.2...1.2...4127...9..6...9.1...1.36945.4..71.26',
'1..923...524.17..9......271.5...81.2...1.2...4127...9..6...9.1...1.36945.4..71.26',
partial(check_rows, try_harder=1))
def test_column(self):
self._test_func(
# 1 value missing in column 1, place the 9
'1........2........3........4........5........6........7........8.................',
'1........2........3........4........5........6........7........8........9........',
check_cols)
if self.quick_tests:
return
self._test_func(
# 2 values left in col 1, 1 with conflict, place both
'.9.......2........3........4........5........6........7........8.................',
'19.......2........3........4........5........6........7........8........9........',
check_cols)
# NOTE: This block is useful for setting up a column test..from a row string
# board = make_board(
# '052900180800230009900801002000709000300020907097000420005104290000090000009502700')
# swaps = Set(Set(Couplet('row', 'col')))
# rotated = partition.binary_extend(board, swaps, relations.swap)
# print('052900180800230009900801002000709000300020907097000420005104290000090000009502700')
# print(get_string(rotated))
# rotated = partition.binary_extend(rotated, swaps, relations.swap)
# print(get_string(rotated))
self._test_func(
# 3 goes in column 1 row 9
'089030000500009000200007509928700105030020090001900402100094207800002900092070000',
'089030000500009000200007509928700105030020090001900402100094207800002900392070000',
check_cols)
def test_block(self):
self._test_func(
# Only 1 value missing in block
'.23......456......789............................................................',
'123......456......789............................................................',
check_blocks)
if self.quick_tests:
return
self._test_func(
# Only 1 place for 1 in first block..1 goes in row 3, col3
'..3.....14.5......7.........1....................................................',
'..3.....14.5......7.1.......1....................................................',
check_blocks)
self._test_func(
# Only 1 place for 8 in first block and 7 in center block
'9..321...31.5..2....2..8.3.5...3...7..8.1.5..6...85..4.4.1..7.....7....6..38.4.5.',
'98.321...31.5..2....2..8.3.5...3...7..8.175..6...85..4.4.1..7.....7....6..38.4.5.',
check_blocks)
self._test_func(
# Only 2 values left in block...1 with conflict
'.93.....14.5......678............................................................',
'293.....1415......678............................................................',
check_blocks)
self._test_func(
# Only 2 values left in block...1 with conflict
'.93.....24.5......678............................................................',
'193.....2425......678............................................................',
check_blocks)
self._test_func(
# Only 2 values left in block...both with conflict
'.93.....14.5......678.......2....................................................',
'293.....1415......678.......2....................................................',
check_blocks)
self._test_func(
# Only 2 values left in block...no conflicts..can't place either
'.93......4.5......678............................................................',
'.93......4.5......678............................................................',
check_blocks)
def test_easy_from_file(self):
# return
if self.quick_tests:
return
from itertools import islice
with open('sudoku.dat') as file:
while True:
puzzle_solution = list(islice(file, 2))
if not puzzle_solution:
break
expected = puzzle_solution[1].rstrip()
self.assertTrue(solve_puzzle(puzzle_solution[0].rstrip(), expected))
print()
def test_one(self):
"""Use this to test solving an entire puzzle..first test of e50.txt"""
self._test_func(
'003020600900305001001806400008102900700000008006708200002609500800203009005010300',
'483921657967345821251876493548132976729564138136798245372689514814253769695417382',
solve_board)
# noinspection PyPackageRequirements
import nose
if __name__ == '__main__':
ARGUMENTS = [
'-s', '--nocapture', '-v', # Don't capture stdout (show it in the console).
'--with-coverage', # Include unit test coverage
'--tests=sudoku.py',
]
nose.main(argv=ARGUMENTS)