1
2 3
4
5
4 16
71
5 2
8 4
3 91
(edited) 1
2 3
4
5
4 16
71
5 2
8 4
3 91
(edited)- - - - - - - 1 -
- - - - - 2 - - 3
- - - 4 - - - - -
- - - - - - 5 - -
4 - 1 6 - - - - -
- - 7 1 - - - - -
- 5 - - - - 2 - -
- - - - 8 - - 4 -
- 3 - 9 1 - - - -
$ python solve.py
1
2 3
4
5
4 16
71
5 2
8 4
3 91
426937815
938615724
751824936
693581472
514792683
872463591
389256147
167349258
245178369
Solved in 0.958s
- - - - - - - 1 -
- - - - - 2 - - 3
- - - 4 - - - - -
- - - - - - 5 - -
4 - 1 6 - - - - -
- - 7 1 - - - - -
- 5 - - - - 2 - -
- - - - 8 - - 4 -
- 3 - 9 1 - - - -
import time
import z3
def exactly_one_of(l):
return z3.Or([z3.And([z3.Not(l[i]) if i != j else l[i] for i in range(len(l))]) for j in range(len(l))])
def only(l):
if len(l) != 1:
if len(l) > 1:
raise ValueError("list has more than one element")
else:
raise ValueError("list is empty")
return l[0]
def pretty(sudoku):
return "\n".join("".join(f"{d}" if d != 0 else " " for d in row) for row in sudoku)
def solve(sudoku):
cells = [[[z3.Bool(f'cell_{y}_{x}_{digit}') for digit in range(1, 10)] for x in range(9)] for y in range(9)]
one_digit_per_cell = [exactly_one_of([cells[y][x][d-1] for d in range(1, 10)]) for y in range(9) for x in range(9)]
digit_unique_per_row = [exactly_one_of([cells[y][x][d-1] for x in range(9)]) for y in range(9) for d in range(1, 10)]
digit_unique_per_col = [exactly_one_of([cells[y][x][d-1] for y in range(9)]) for x in range(9) for d in range(1, 10)]
digit_unique_per_blk = [exactly_one_of([cells[y+dy][x+dx][d-1] for dx in range(3) for dy in range(3)]) for y in range(0, 9, 3) for x in range(0, 9, 3) for d in range(1, 10)]
known_digits = [cells[y][x][d-1] for y, row in enumerate(sudoku) for x, d in enumerate(row) if d != 0]
solver = z3.Solver()
solver.add(
*one_digit_per_cell,
*digit_unique_per_row,
*digit_unique_per_col,
*digit_unique_per_blk,
*known_digits,
)
solver.check()
model = solver.model()
return [[only([d for d in range(1, 10) if model.eval(cells[y][x][d-1])]) for x in range(9)] for y in range(9)]
def main():
def sudoku_line(line):
if len(line) != 9:
raise ValueError("sudokus rows must be 9 in length")
return [int(d) if d != ' ' else 0 for d in line]
sudoku = [sudoku_line(input()) for y in range(9)]
print(pretty(solve(sudoku)))
if __name__ == "__main__":
main()
(edited)$ python solve.py
1
2 3
4
5
4 16
71
5 2
8 4
3 91
745368912
819572463
362491857
693824571
421657398
587139624
158746239
976283145
234915786
Solved in 0.887s
7 4 5 3 6 8 9 1 2
8 1 9 5 7 2 4 6 3
3 6 2 4 9 1 8 5 7
6 9 3 8 2 4 5 7 1
4 2 1 6 5 7 3 9 8
5 8 7 1 3 9 6 2 4
1 5 8 7 4 6 2 3 9
9 7 6 2 8 3 1 4 5
2 3 4 9 1 5 7 8 6
learath2@l2gentoo ~/C/tdoku $ hyperfine --warmup 10 -N ./solve 1 < puzzl
Benchmark 1: ./solve
Time (mean ± σ): 826.6 µs ± 57.6 µs [User: 479.3 µs, System: 251.7 µs]
Range (min … max): 741.4 µs … 1295.3 µs 3562 runs
learath2@l2gentoo ~/C/tdoku $ hyperfine --warmup 10 -N ./solve 1 < puzzl
Benchmark 1: ./solve
Time (mean ± σ): 826.6 µs ± 57.6 µs [User: 479.3 µs, System: 251.7 µs]
Range (min … max): 741.4 µs … 1295.3 µs 3562 runs
./solve 1 < puzzl
my program reads a filelearath2@l2gentoo ~/C/tdoku $ hyperfine --warmup 10 -N ./solve 1 < puzzl
Benchmark 1: ./solve
Time (mean ± σ): 826.6 µs ± 57.6 µs [User: 479.3 µs, System: 251.7 µs]
Range (min … max): 741.4 µs … 1295.3 µs 3562 runs
- - - - - - - - -
- - - - - 3 - 8 5
- - 1 - 2 - - - -
- - - 5 - 7 - - -
- - 4 - - - 1 - -
- 9 - - - - - - -
5 - - - - - - 7 3
- - 2 - 1 - - - -
- - - - 4 - - - 9
Here's a simple proof by contradiction:
Assume the opposite: Let's assume that x + 1 ≤ x.
Subtract x from both sides: If we subtract x from both sides of the inequality, we get:
(x + 1) - x ≤ x - x
1 ≤ 0
Contradiction: This statement, 1 ≤ 0, is clearly false.
Since our assumption led to a contradiction, the original statement x + 1 > x must be true.
Therefore, for any real number x, x + 1 is always greater than x.
1 > 0
which is trivially true1 > 0
for natural numbers using ZF axioms, but real numbers would be tough$
$
1 > 0
for natural numbers using ZF axioms, but real numbers would be tough 1 > 0
for natural numbers using ZF axioms, but real numbers would be tough x + 1 > x
<-> x < x + 1 (3)
<-> x + (-x) < x + 1 + (-x) (2)
<-> x + (-x) < x + (-x) + 1 (6)
<-> 0 < 1 (5)
Thus our initial problem is equivalent to proving 0 < 1
Either 0 = 1, 0 < 1 or 1 < 0 must hold (1), we must eliminate 0 = 1 and 1 < 0
0 = 1 is false because of (7)
1 < 0 is false:
- Assume 1 < 0
- 1 + (-1) < 0 + (-1) using (2)
- 0 < -1
- 0 * (-1) < (-1) * (-1) using (8), this should be allowed since supposedly 0 < -1
- 0 < 1 which contradicts our initial assumption
Thus we must conclude that 0 < 1 QED
(edited)