[fjfaase]

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]

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

I coded the paper Sinkhorn Solves Sudoku. Lol the most bizarre algorithms can solve sudoku. https://github.com/MurageKibicho/Sinkhorn-Solves-Sudoku

[fjfaase]

The link https://leetarxiv.substack.com/sinkhorn-solves-sudoku reports 'Page not found'.

[muragekibicho]

I'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.