Jump to content
  • Advertisement
Sign in to follow this  
Mad_Coder

Worst Case Scenario for sudoku solving algorithm

This topic is 3470 days old which is more than the 365 day threshold we allow for new replies. Please post a new topic.

If you intended to correct an error in the post then please contact us.

Recommended Posts

A Sudoku solving program I wrote in the past uses the brute force method and I figured out:
  • The worst case scenario O() for solving the puzzle is the sum of the worst case scenario of the subsquares
    • The O() for solving a sub square is the sum of the worst case scenario for all the squares in the sub square
      • The O() for solving a square is the factorial of the number of candidates the square has
      However, what I need to figure out an equivalent way ( whether it may or may not be worst case scenario) to determine the efficiency exactly of using a single candidates solving method compared to brute forcing, but this varies in so many way such as:
      • The number of squares throughout solving the puzzle that have single candidates.
      • The number of other squares a squares that you found its number using this method will effect it's reduction of candidates.
      ..and many other factors; how would i go about determining the efficiency for any Sudoku puzzle using the single candidate solving technique? [Edited by - Mad_Coder on December 20, 2008 10:24:50 PM]

Share this post


Link to post
Share on other sites
Advertisement
I'll try and help, but your post is a little confusing.
Quote:
The worst case scenario O() for solving the puzzle is the sum of the worst case scenario
That just stated that something is the sum of itself?
Quote:
The O() for solving a sub square is the sub of the worst case scenario for all the squares in the sub square
I presume the middle "sub" is supposed to say "sum"?

Now you appear to be after the efficiency of solving a Sudoku via the single candidate solving method. Unfortunately not all Sudoku's can be solved using this technique, so I'm not sure how useful an answer is in that respect.

Assuming you've written a solver that can solve using only that technique, then I think an answer can only be given to that implementation itself because it is hard to know exactly how it is implemented. For example does the implementation recalculate all the candidates every time it finds a number, or does it track candidates and just mark off more each time? When it marks them off, does it then only examine cells that could possibly have their number of candidates affected, or does it re-examine all cells? "The devil is in the details" as they say.
As such, I think you can see that we can only get an answer that relates to an implementation, not the the problem itself.

As an aside, I've written a solver that can solve the worlds hardest Sudoku in about 1 millisecond, available on my website. I'm not even going to try and calculate the Big-Oh notation of my implementation!

Share this post


Link to post
Share on other sites
Can't help with all the complexities, but the single candidates method cannot solve puzzles alone. (However, since it won't backtrace it can't have a really bad complexity, perhaps O(m*n) for some values m and n less than 81 instead of complexities involving factorials?)

In practice (but that might probably depend completely on the representations of board and algorithms) I have used single candidates (and some other methods) before going brute-forcing. Solving even some cells, as it seems to me, in practice seemed to shorten the time it takes for brute-force solving considerably (sometimes).

Share this post


Link to post
Share on other sites
I apologize for those first three bullets being mistyped and worded, I was in a hurry to head out; but to answer your question, yes each time it finds a single candidate, it will update all the squares that could be possibly affected to save time having to check all squares, sum of which that wouldn't be affected by this. I do realize that this technique usually won't solve the entire puzzle, but I just want to know the efficiency of all the techniques i will use so i know what to make faster. I am planning on also perhaps storing all the squares not only in a class by row and column and anothe by the subsquare and its element number, but by a vector of a vector where the first element is stores the single canididates and the elements of squares with the least number of candidates go after that to the last element stores the squares with the most number of candidates and the second element the inside vector will be all the squares with this particular number of candidates; so when the squars change i will convert it from one of the other 2 ways to by how close it is to being a single candidate and they will be swapped to the appropriate position as they have less and less candidates producing quality efficiency when searching for single candidates and ones close.

Share this post


Link to post
Share on other sites
Quote:
Original post by visitor
Can't help with all the complexities, but the single candidates method cannot solve puzzles alone. (However, since it won't backtrace it can't have a really bad complexity, perhaps O(m*n) for some values m and n less than 81 instead of complexities involving factorials?)


I also did not understand what you ment "it does not backtrace" and doesn't have a " bad complexity ", and what does the m and n variables and why is this O() computation "for some valus less than 81 instead of complexities involving factorials??"

Share this post


Link to post
Share on other sites
"it does not backtrace" would refer to a technique where once you fill in a cell, that is the final answer for that cell. E.g. the single candidate solving method.
In contrast, a backtracing algorithm will spend a lot of its time filling in cells that are not the correct values for those cells (effectively guessing) and then has to undo back to the point which it guessed wrong.
Without backtracking capability, you're algorithm basically won't be able to solve more difficult Sudoku boards. As difficult as backtracking sounds though, if you're good at writing recursive functions, it's a doozie.

You mention sorting the cells by the number of candates remaining. This is a very important optimisation. It sped up my solver by a factor of about 40 when I added it. The need for backtracking comes in when the cell with the fewest number of candidates is two or more.

Share this post


Link to post
Share on other sites
So, is the reason that harder puzzles require backtracing is becuase techniques such as single canidates cannot solve harder puzzles ( or really any puzzle ) alone so you have to try every combination for every canidates of every squares via backtracing? Am I on to the right idea of backtracing - sort of similiar to brute force method?

Share this post


Link to post
Share on other sites
Logical methods when combined can solve a lot of puzzles (provided that they have one solution - otherwise guessing is inevitable, and the puzzle doesn't contain a step that needs a deduction that the program is not programmed to do), including what I think iMalc is referring to as the world's hardest sudoku ;)

This is what I have used in my Sudoku program (sorry, I don't want to reveal more code from it):


bool SudokuGenerator::solve_()
{
do {
//basic methods that actually solve cells
while (find_single_candidates_() || find_hidden_single_());

} while (found_count < 81 && (
//advanced techniques that eliminate candidates
//leading (hopefully) to more single candidate cells being found
find_locked_candidates_() ||
find_box_pair_single_() ||
find_naked_pair_() ||
find_hidden_pair_() ||
find_naked_triple_() ||
find_hidden_triple_() ||
find_xwing_() ||
find_swordfish_() ||
find_xywing_() ));
return found_count == 81;
}



Of course, the aim of my program was not simply to solve puzzles (where brute force would be enough). Having all these different techniques lets it decide a) if a puzzle is solvable without guessing, b) how hard might it be for a human to solve etc.

Edit:
I also believe all (or most) of these methods when taken separately have a O(n) complexity (multiplied by some constant). For example, find_single_candidates simply traverses the 81 cells once, more complicated methods might traverse the 81 cells 3 times etc.

However, all this is fast enough for me (solving a single puzzle takes no noticeable time and more time-consuming generation of puzzles happens in a background thread anyway), so I almost didn't worry about the performance characteristics and optimizing at all.

Share this post


Link to post
Share on other sites
I was referring to this world's hadrest Sudoku puzzle (Al Escargot).

That's a very elaborate solver visitor. It wont work on the above, but it should work on those even considered just "hard" for human players.
Quote:
Having all these different techniques lets it decide a) if a puzzle is solvable without guessing, b) how hard might it be for a human to solve etc.
That's a tricky bit eh, deciding how hard it is for a human solver. I don't think my board generator does that very well.

Interestingly, I found a way of determining if there is a single unique solution or not rather quickly, by examining the search space twice, from each end.

Oh and my solver is on the "Useful Classes" page of my site, though I didn't actually wrap it in a class yet.

Share this post


Link to post
Share on other sites
Well, the puzzle in the article is just an illustration. That's not a particularly hard one. You can find the tough ones in the linked Sudoku programming page. My solver couldn't do those using logical methods. Of course, for brute-forcing it is a piece of cake.

Share this post


Link to post
Share on other sites
Sign in to follow this  

  • Advertisement
×

Important Information

By using GameDev.net, you agree to our community Guidelines, Terms of Use, and Privacy Policy.

Participate in the game development conversation and more when you create an account on GameDev.net!

Sign me up!