search

t-dillon / tdoku

A fast Sudoku solver and generator with a benchmark suite for comparing the fastest known solvers.
https://t-dillon.github.io/tdoku
BSD 2-Clause "Simplified" License
197 stars 25 forks source link

Does recursion beat a stack implementation? #4

Closed Andersama closed 3 years ago

Andersama commented 3 years ago

I've written a few sudoku solvers, but I've avoided recursion because I wanted to make sure I didn't overflow the stack if I wanted to use it on larger boards. Reading some of the listed benchmark timings I'm wondering if there's some performance benefit to having the cpu essentially handle a stack with recursion. I've got two implementations, one I think is equivalent to the basic solver you have listed, the other uses additional bitmasks to do space based eliminations (I think the term's called cross hatching). They run about 1ms and 3ms per puzzle. If I template out specifically for the board size it seems to roughly improve performance by a factor of 10, but obviously my hardware's not the same and my code's probably not ideal.

The cross hatching approach seems to shave a significant amount of branching factor from the basic algorithm by cutting the guess work by a fourth, but it doesn't seem to pay off unless the board is complex.

I'd be curious to see what the benchmarks look like.

t-dillon commented 3 years ago

I wouldn't worry about stack overflow in a recursive Sudoku solver. Whether you can be faster with a self-managed stack or queue is a good empirical question, but in practice there's no overlap between the set of large puzzles that you can solve in a feasible amount of time and the set of large puzzles that will overflow your stack.

Andersama commented 3 years ago

I was definitely more curious about the performance difference between managing your own stack vs just having a recursive function and having the hardware essentially manage one for you Reading this back to myself I don't know why I would've been worried about a stack overflow, maybe I was imagining having a cpu being really taxed for some reason, weird. I'm pretty confident a self managed one will beat a recursive function.