


































 thats best
 thats best































       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 file

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 






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







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 































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)



