# Day 5 - Sudo Sudoku - misc, sudoku
> Santa's little helpers are notoriously good at solving Sudoku puzzles, so they made a special variant...
Download: [2a3fad4ea8987eb63b5abdea1c8bdc75d4f2e6b087388c5e33cec99136b4257a-sudosudoku.tar.xz](https://advent2019.s3.amazonaws.com/2a3fad4ea8987eb63b5abdea1c8bdc75d4f2e6b087388c5e33cec99136b4257a-sudosudoku.tar.xz)
## Initial Analysis
The problem's `challenge.txt` files reads as follows:
```Santa's little helpers are notoriously good at solving Sudoku puzzles.Because regular Sudoku puzzles are too trivial, they have invented a variant.
    1 2 3   4 5 6   7 8 9  +-------+-------+-------+A | . . . | . . . | . . 1 |B | . 1 2 | . . . | . . . |C | . . . | . . . | 2 . . |  +-------+-------+-------+D | . . . | . . . | . . 2 |E | . 2 . | . . . | . . . |F | . . . | . . . | . . . |  +-------+-------+-------+G | . . . | . . . | 1 2 . |H | 1 . . | . . 2 | . . . |I | . . . | 1 . . | . . . |  +-------+-------+-------+
In addition to the standard Sudoku puzzle above,the following equations must also hold:
B9 + B8 + C1 + H4 + H4 = 23A5 + D7 + I5 + G8 + B3 + A5 = 19I2 + I3 + F2 + E9 = 15I7 + H8 + C2 + D9 = 26I6 + A5 + I3 + B8 + C3 = 20I7 + D9 + B6 + A8 + A3 + C4 = 27C7 + H9 + I7 + B2 + H8 + G3 = 31D3 + I8 + A4 + I6 = 27F5 + B8 + F8 + I7 + F1 = 33A2 + A8 + D7 + E4 = 21C1 + I4 + C2 + I1 + A4 = 20F8 + C1 + F6 + D3 + B6 = 25
If you then read the numbers clockwise starting from A1 to A9, to I9, to I1 andback to A1, you end up with a number with 32 digits.  Enclose that in AOTW{...}to get the flag.
```
As the challenge describes, the objective is to solve the Sudoku puzzle with the additional constraints. Rather than do the math for this puzzle manually, I wrote a [short script](./solutions/day5_solver.py) to brute force the problem for me. Roughly speaking, this script reads all of the constraints, sets up a loop to brute force them all, and once all of the constraints are met it calls a [SAT solver](https://github.com/taufanardi/sudoku-sat-solver/blob/38d601547b04bf22591c14e1746cbe70cb777be7/Sudoku.py) to solve the remainder of the Sudoku puzzle. If a solution is found, then it outputs it and breaks, otherwise it continues on. Each sudoku solve takes less than a second, so the main computational bottleneck is the brute force of the constraints up front. The final output of the script gives the answer and the flag:
```$ time ./solutions/day5_solver.py 32 [(1, 8), (1, 7), (2, 0), (7, 3), (0, 4), (3, 6), (8, 4), (8, 1), (8, 2), (5, 1), (4, 8), (8, 6), (7, 7), (2, 1), (8, 5), (2, 2), (1, 5), (0, 7), (0, 2), (2, 3), (7, 8), (6, 2), (3, 2), (8, 7), (0, 3), (5, 4), (5, 7), (5, 0), (0, 1), (4, 3), (8, 0), (5, 5)]
<snip>
complete[[0, 6, 4, 7, 2, 0, 0, 3, 1], [0, 1, 2, 0, 0, 3, 0, 6, 8], [3, 7, 5, 6, 0, 0, 2, 0, 0], [0, 0, 9, 0, 0, 0, 3, 0, 2], [0, 2, 0, 9, 0, 0, 0, 0, 4], [5, 3, 0, 0, 4, 1, 0, 9, 0], [0, 0, 6, 0, 0, 0, 1, 2, 0], [1, 0, 0, 3, 0, 2, 0, 8, 5], [2, 5, 3, 1, 8, 4, 9, 7, 0]]Problem:[[0, 6, 4, 7, 2, 0, 0, 3, 1], [0, 1, 2, 0, 0, 3, 0, 6, 8], [3, 7, 5, 6, 0, 0, 2, 0, 0], [0, 0, 9, 0, 0, 0, 3, 0, 2], [0, 2, 0, 9, 0, 0, 0, 0, 4], [5, 3, 0, 0, 4, 1, 0, 9, 0], [0, 0, 6, 0, 0, 0, 1, 2, 0], [1, 0, 0, 3, 0, 2, 0, 8, 5], [2, 5, 3, 1, 8, 4, 9, 7, 0]]P CNF 11788(number of clauses)Time: 0.003549814224243164Answer:[[8, 6, 4, 7, 2, 9, 5, 3, 1], [9, 1, 2, 4, 5, 3, 7, 6, 8], [3, 7, 5, 6, 1, 8, 2, 4, 9], [6, 4, 9, 8, 7, 5, 3, 1, 2], [7, 2, 1, 9, 3, 6, 8, 5, 4], [5, 3, 8, 2, 4, 1, 6, 9, 7], [4, 8, 6, 5, 9, 7, 1, 2, 3], [1, 9, 7, 3, 6, 2, 4, 8, 5], [2, 5, 3, 1, 8, 4, 9, 7, 6]]
real	1m4.114suser	1m3.817ssys	0m0.181s```
With this output, the flag is: `AOTW{86472953189247356794813521457639}`