3 ms·
If you convert a sudoku to an exact cover you can usually solve it by finding colums that are a subset from another column and remove all rows that are only in
by fjfaase 1y ago
If you convert a sudoku to an exact cover you can usually solve it by finding colums that are a subset from another column and remove all rows that are only in one of them.
Sudokus that can be solved with reasoning alone, can be solved in polynomial time.
I recently discovered that solving exact covers, and probably also with SAT, using a generic strategy, does not always result in the most efficient way for finding solutions. There are problems that have 10^50 solutions, yer finding a solution can take a long time.
- eru 11mo ago> Sudokus that can be solved with reasoning alone, [...] Is 'reasoning alone' actually well defined in the context of Sudoku? Sudoku's are finite, so I can solve all of them with just a lookup table in constant time..
- muragekibicho 11mo agoI coded the paper Sinkhorn Solves Sudoku. Lol the most bizarre algorithms can solve sudoku. https://github.com/MurageKibicho/Sinkhorn-Solves-Sudoku https://github.com/MurageKibicho/Sinkhorn-Solves-Sudoku
- fjfaase 11mo agoThe link https://leetarxiv.substack.com/sinkhorn-solves-sudoku https://leetarxiv.substack.com/sinkhorn-solves-sudoku reports 'Page not found'.
- muragekibicho 11mo agoI've not yet published the writeup. Only the C code is available atm. I solo run a thing called LeetArxiv. It's a successor to Papers with Code since the latter shut down.