-2
$\begingroup$

I'm creating a sudoku solver, and I'm wondering at what point, with a simple backtracking sudoku solving algorithm, does the result take way too long to compute? I'm thinking like more than 30 minutes? I'll probably try to implement some heuristics, but I want to know at what point should I not expect a solution within 30 minutes?

$\endgroup$

closed as unclear what you're asking by D.W., Wandering Logic, Nicholas Mancuso, FrankW, Vor Apr 18 '14 at 22:10

Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question.

  • 2
    $\begingroup$ This is not an answerable question in its current form, as the answer depends too much on the specific solver. Moreover, you are the right one to answer this: you have your code, you can get test cases, so why haven't you just tried it and see? Why are you asking here? On this site, we expect you to make a serious effort to answer your question on your own before asking here; in this case, that would include trying it experimentally. See the help center (upper-right part of the page) for more explanation of this site format and our expectations. $\endgroup$ – D.W. Apr 18 '14 at 19:45
3
$\begingroup$

The best way to find out is for you to implementing it and do some experiments.

The difficulty level of Sudoku puzzles varies widely. Moreover, there are many ways to implement a Sudoku solver, and some will be more effective than others on hard Sudoku puzzles (e.g., SAT solvers may be more effective than simple backtracking engines). Therefore, there is no one answer that will be applicable to all Sudoku solvers and all puzzles.

Fortunately, test cases are easy to find. It's easy to find many examples Sudoku puzzles at different levels of difficulty. So, give it a try. On this site, we expect you to do serious research on your own before asking, so before asking here, you should try it on your own. The best way to find out is to try it -- that's something you'll need to do, as we can't do it for you.

$\endgroup$
2
$\begingroup$

Some sudoku puzzles of arbitrary size are easy to solve, for example if every number is given except for $1$ number (that's an extreme example, but the point is that different sudoku puzzles will take different amounts of time to be solved by a given solver). So it sounds like you want to know the worst-case running time for you solver, i.e. find the hardest puzzle for your solver. But we don't know how your solver works, and even if we did, figuring out the hardest puzzle for your solver for each $n$ would be an almost certainly impossible task. There are examples of "hard" sudoku puzzles on the web, but you shouldn't expect them to necessarily be the absolute hardest for your solver. Your question is basically impossible to answer unless you enumerate all sudoku puzzles for each $n$ that have a unique solution and try them all out, in increasing order of $n$ until you finally find a worst-case puzzle that takes more than $30$ minutes to run or whatever your time limit is for your solver.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.