JSolve - yet another really fast brute force Sudoku solver

dobrichev · Posted: Sat Jan 30, 2010 4:39 am Post subject:

Thank you for the effort. I found and fixed the infinite looping in the Tarek Pearly 6000 collection in fsss_v8.4. No other changes. It was nightmare debugging on 64-bit MAC OS virtual machine hosted by 32 bit Windows.

About the exotic functions usage I agree that there is a risk. My logic is that each return from a function actually restores the CPU context and makes a branch. Immediately after that a check for error is made followed by a second branch. When the latest puzzle digit is fixed, the call depth is about 10 - 20 and it is reasonable to see wheter the famous longjmp behave better than the classic code. On x86 after replacing the return with longjmp the timings remain the same, but after removing the error checking after the calls the things ran faster for about 4-5%. The whole logic is wrong if there are enough registers for compiler to perform interprocedural optimizations but this is not the case on x86 platform.

JasonLion · Posted: Sat Jan 30, 2010 11:21 pm Post subject:

I would say that the problem with your logic can be seen rather clearly in the following chart:

dobrichev · Posted: Mon Feb 01, 2010 2:42 pm Post subject:

Thank you for the timings.
There is faster fsss_8.6 with longjmps removed.