Not sure, but my guess would be that having one array with both values at once would be beneficial, as you will often find that you need to get the count, and then the bsr value.
--
Mats
Printable View
I have now implemented the "check if the sub-section can be solved" - however, it's now slower than before - probably due to naff implementation that takes too long to check each candidate. I have an idea of how to make it a bit better.
Edit: My idea didn't help much. I think it's time to get rid of linked lists and start using a bitmap [which in fact was my initial approach - I just had some other bugs, and didn't realize that the problems I had was completely unrelated to the storage of the candidates, but rather a logical problem in detecting the solution is finished.]
But the anon "unsolvable" is solved in "zero time" as my code is now immediately recognizing that there's no valid solution.
--
Mats
I also just implemented this idea myself.Quote:
I have now implemented the "check if the sub-section can be solved" - however, it's now slower than before - probably due to naff implementation that takes too long to check each candidate. I have an idea of how to make it a bit better.
I found that it made it faster for the cases of checking whether there are numbers that cannot appear in any row or column.
However after then adding the check for numbers that cannot appear in any 3x3 grid, most of that performance gain went away again. At first I thought that the check was just slow enough that it outweighted the bennefit, however upon debugging a few boards, I found that the return statement was actually never being hit. So although I'm sure one can craft a board that will hit this case on the first call, on the majority of boards all that extra checking is for nothing.
Whereas the row and column checks seemed to be hit frequently - go figure!
So yeah, mine's down to 1.1ms now for the hardest board, and I've updated the source file I linked to earlier on my site.
we should try something like 25*25 sudoku... that should be more of a challenge for computers :).
I solved a 25x25 Sudoku. Took me days. 25 rows, 25 columns, 25 5x5 subgrids. Instead of numbers, you fill in the letters A-Y.
I have never seen that before and I didnt even know it existed...that sounds masochistic.
why not just solve it then test is it follows the rules. hmm.... but then you would need a break if it is impossible to solve, lets say after 100 loops? you will need 81 at max for sure but 100 is a rounder number, do it like this
Code:for(int loops_run = 0; !solved && loops_run < 100; loops_run++)
{
// the code implementing your solver
}
O_o
Please don't bump old threads without an extremely good reason.
I was expecting revelations...
Soma
And that wasn't a good reason.
Closed.