1
$\begingroup$

Suppose, I got a hypothetical fixed list of all possible general Sudoku puzzles. I then create the pseudo-code to demonstrate the algorithm.

  • The algorithm does a search to compare the indexes of elements in the puzzle that are not listed as zero.

  • In other words, all the possible listed Sudoku
    grids are compared until a solution is found matching solution sharing the elements with the
    same index.

--

tuple=[.......]

tuple=[.......]

all possible Sudoku grids.

Here's our solver.

solver = input('enter the puzzle like this 10000030004000...)

if Element with Same Index solver == tuple1, tuple2,...

print (solution containing exact elements that share the indexes in
       both the solution and puzzle)

Will this algorithm solve all Sudoku Puzzles in O log n time?

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
4
$\begingroup$

Such an algorithm can solve Sudoku, but it will be very slow in practice.

By definition, Sudoku is on a 9x9 grid, so there are only a fixed (finite) number of possible puzzles. Your algorithm encodes all of them. Therefore, your algorithm takes constant time, i.e., $O(1)$ time.

What this is telling you is that asymptotic analysis is not a useful tool for analyzing the running time of a Sudoku solver, as asymptotic running time focuses on how the running time grows as you increase the size of the input. With Sudoku, you can't increase the size of the input; the size of the input is fixed. Thus it doesn't even make sense to talk about asymptotic running time for solving Sudoku puzzles.

Some people do analyze a generalization of Sudoku, where instead of a 9x9 grid, we have a $k^2 \times k^2$ grid, where $k$ can be any integer. Then one can consider asymptotic running time. However, your algorithm can't be applied to this generalization of Sudoku, as there are infinitely many puzzles for this generalization, so you can't hardcode them all in the code of your algorithm -- every algorithm must be of finite length. Thus, in that setting, while asymptotic analysis does apply, your algorithmic approach no longer works.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Well, it seems algorithmic approaches to NP problems is impossible. If this is the closest they can get. $\endgroup$
    – The T
    Commented Apr 22, 2019 at 3:22
  • $\begingroup$ @TravisWells The sudoku problem isn't NP-hard: it can be solved in $O(1)$, as you have. The NP-hard problem is generalizing it to an $n^2 \times n^2$ grid with $n$ digits. This can be solved in exponential time with respect to $n$, and verified in polynomial time; the big question is whether it can be solved in polynomial time too. $\endgroup$
    – Draconis
    Commented Apr 22, 2019 at 3:34
  • $\begingroup$ @Dracoins n2xn2 as in what? 9x9 grids. all of them can be solved. All this time, I was misled that it was a np-hard problem. Now, I can create more constraint algorithms. Now, comes mario. $\endgroup$
    – The T
    Commented Apr 22, 2019 at 5:16
  • $\begingroup$ @TravisWells You can obviously create a Sudoku with 16 rows, 16 columns, 16 boxes with numbers 1 to 16, 25 rows, 25 columns, 25 boxes with numbers 1 to 25 and so on. $\endgroup$
    – gnasher729
    Commented Apr 22, 2019 at 19:07
  • $\begingroup$ Up to Infinity actually. But, showing it in concrete form is impossible. $\endgroup$
    – The T
    Commented Apr 22, 2019 at 19:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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