3 ms·

Exact cover and applications

36 points by Labo333 4y ago

vismit2000 4y ago
Stanford Lecture: Don Knuth—"Dancing Links" (2018): https://youtu.be/_cR9zDlvP88 https://youtu.be/_cR9zDlvP88
fjfaase 4y ago
Interesting exposition about how to use Exact Cover to solve a Sudoku. But in case a sudoku has one solution, it is possible to solve it by reducing the exact cover. For example, if you have a column that is a true subset of another column (with respect to the 1-s) you can remove all the rows that have a 1 in the row with the larger number, because these rows can never be selected. Also when solving an Exact Cover there are some (rather simple) strategies that can improve the speed of finding solutions. I used Exact Covers a lot for solving all kinds of puzzles (most of them far more complicated than Sudoku's). See: https://www.iwriteiam.nl/Dpuzzle.html#EC https://www.iwriteiam.nl/Dpuzzle.html#EC for a list of blogs I wrote over the time.
PennRobotics 4y ago
I must be missing something. malib does not have solve_cover, and this specific function is used without definition in the Sudoku example. The shown solution seems to be the order in which the digits are solved and not the actual digits in their correct location, because the solution matrix has repeat digits everywhere, and the first 21 digits are the provided solution digits in order.
- PennRobotics 4y ago
  This just needed a few corrections to get running: * solve_cover should simply be solve * The solution is a list with elements in the form (digit, x location, y location), zero-indexed. So I changed the ending some: out = [['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0']] for d, x, y in solution: out[x][y] = str(d) print(''.join([a for b in out for a in b])) # Flatten 2d array There's probably a more elegant/pythonic way to do each code block, but this will get you a valid solution matrix: (Format lines were added during posting.) 842|713|695 913|652|847 675|498|213 ---+---+--- 354|267|189 189|345|726 267|189|534 ---+---+--- 521|974|368 438|526|971 796|831|452 It is a bit interesting seeing the similarities and differences between the posted article and Norvig's Sudoku solver[1]. I've always appreciated how Norvig is concise and still has intermediate representations for debugging (e.g. shows all of the possible digits for a cell that hasn't yet been solved). The article's solver is MUCH faster in non-exact cases: The "multiple solution" example from Norvig (which Norvig states takes 3 minutes to solve) is done in 10 ms using this solver (plus, it finds a different valid solution), and the "impossible solution" (which fails after 24 minutes) gives a StopIteration after 90 ms. [1] https://norvig.com/sudoku.html https://norvig.com/sudoku.html

36 points by Labo333 4y ago

vismit2000 4y ago

Stanford Lecture: Don Knuth—"Dancing Links" (2018): https://youtu.be/_cR9zDlvP88 https://youtu.be/_cR9zDlvP88

Interesting exposition about how to use Exact Cover to solve a Sudoku. But in case a sudoku has one solution, it is possible to solve it by reducing the exact cover. For example, if you have a column that is a true subset of another column (with respect to the 1-s) you can remove all the rows that have a 1 in the row with the larger number, because these rows can never be selected. Also when solving an Exact Cover there are some (rather simple) strategies that can improve the speed of finding solutions. I used Exact Covers a lot for solving all kinds of puzzles (most of them far more complicated than Sudoku's). See: https://www.iwriteiam.nl/Dpuzzle.html#EC https://www.iwriteiam.nl/Dpuzzle.html#EC for a list of blogs I wrote over the time.

PennRobotics 4y ago

I must be missing something. malib does not have solve_cover, and this specific function is used without definition in the Sudoku example. The shown solution seems to be the order in which the digits are solved and not the actual digits in their correct location, because the solution matrix has repeat digits everywhere, and the first 21 digits are the provided solution digits in order.

PennRobotics 4y ago
This just needed a few corrections to get running: * solve_cover should simply be solve * The solution is a list with elements in the form (digit, x location, y location), zero-indexed. So I changed the ending some: out = [['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0','\n'], ['0','0','0','0','0','0','0','0','0']] for d, x, y in solution: out[x][y] = str(d) print(''.join([a for b in out for a in b])) # Flatten 2d array There's probably a more elegant/pythonic way to do each code block, but this will get you a valid solution matrix: (Format lines were added during posting.) 842|713|695 913|652|847 675|498|213 ---+---+--- 354|267|189 189|345|726 267|189|534 ---+---+--- 521|974|368 438|526|971 796|831|452 It is a bit interesting seeing the similarities and differences between the posted article and Norvig's Sudoku solver[1]. I've always appreciated how Norvig is concise and still has intermediate representations for debugging (e.g. shows all of the possible digits for a cell that hasn't yet been solved). The article's solver is MUCH faster in non-exact cases: The "multiple solution" example from Norvig (which Norvig states takes 3 minutes to solve) is done in 10 ms using this solver (plus, it finds a different valid solution), and the "impossible solution" (which fails after 24 minutes) gives a StopIteration after 90 ms. [1] https://norvig.com/sudoku.html https://norvig.com/sudoku.html