Exact cover and applications | Hacker News Reader

Exact cover and applications

louisabraham.github.io

36 pointsLabo3334 comments

Stanford Lecture: Don Knuth—"Dancing Links" (2018): 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 for a list of blogs I wrote over the time.

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.

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

Reply on news.ycombinator.com