Interview Questions And Answers 
-
Write an algorithm for Soduku puzzle
14,322 Views |
(40 votes, avg: 2.98)
Loading ...
Answers »
Our Sponsors
Our Sponsors
Write an algorithm for Soduku puzzle
14,322 Views | (40 votes, avg: 2.98)
Loading ...
SUDOKU falls into the category of NP problems, i.e it grows exponentially. It is one of the unsolved problems. There is no known solution for SUDOKU .. however, if the size is constrained, you can write an algorithm.
NP problem only means that there is no known exponential solution. Does not mean there is no solution.
you can use dynamic programming to solve Sudoku.
I can imagine a simple greedy algorithm.
And if you fix the size of the sudoku to a constant, the algorithm actually runs in O(1) time.
One possible soln could be:
Generate all nxn cominations of sudoku tables. Store them . This is one time cost.
When the input is given , try to map the input nxn square to already generated solutions.
@krishna: Have you ever decided to try this? It’s a n*n^(n*n)^2) operation to find all the legitimate answers. We’re talking several lifetimes of computational power on a normal machine. I just wrote a PERL program (not the fastest I understand) with recursion… try it. You’re better off writing a set of functions to solve each puzzle individually.
There are some basic mistakes above that I want to clear up.
>SUDOKU falls into the category of NP problems, i.e it grows exponentially.
What you should be saying is that Sudoku is NP-Complete. NP contains all sorts of trivial problems. The NP-Complete problems are the ones which researchers suspect to be computationally intractable.
>NP problem only means that there is no known exponential solution. Does not mean there is no solution.
This statement is false on many levels. Firstly, there are plenty of problems in NP which have deterministic polytime solutions. But even if we assume you were talking about NP-Complete problems, the statement that “NP-Complete problem only means that there is no known exponential solution.” is still false. All NP-Complete problems have exponential algorithms. What you probably meant to say is that NP-Complete problems have no known polynomial time algorithms.
Incidentally, if you want my 2 cent answer for the question, probably the easiest way to solve Sudoku would be to encode it as a SAT instance and feed it to a clause learning algorithm.
This is probably a good solution because
a) Programing a reduction is much easier than programming a hard-core algorithm. This will save time and it will have fewer bugs in it.
b) You get a fully debugged SAT-solving algorithm for free, which saves you lots of time and development money.
and c) The SAT solver will probably be faster than any program you could write anyways.
I agree with Alex (9).
But just in case we want to do this algorithm, then the answer will be the one below.
Because this is problem is NP complete, the only solution is to go over all the possible answers until a correct answer is found.
For each column 1 until column 9 {
For each cell 1 until 9 {
for i=1 to 9 {
check(i); // check that i doesnt exists already in this row, column or square.
if (i is legal) continue to the next cell in the column.
}
once finishing filling the column go to the next column.
if at some point the filling failed (i.e. the column couldnt find any legal values) then go back and try the next i.
This is a bit of a blur, but if you do it recuresively than it gets clearer and it is not that hard.
Good job Itay.
But before you start fill in all the squares that only have one possible choice.
Then as you proceed always choose the most constrained squares. If you chose the spot that has only two possibilities and you choose the wrong one it will have an error faster and you will prune larger portions of the tree.
I don’t understand the argument over if this can be solved. I’ve seen solvers for sodoku that finish the puzzle almost instantly. NP completeness is not too important when your search space is so small like in sodoku. When is the last time you heard of an 11 by 11 sodoku puzzle?
Sudoku is indeed NP-Complete for puzzles of size n. But probably you should ask to the interviewer if he means the general (n-sized) or the common (3-sized) (the one you can find in magazines) case. If he means the latter (which he probably does) the better solution is backtracking.
First input or get all fixed values:
Then test each box such that for (A,1-3), if (A,1-9 == n, (A-I,1) == n, (B,1-3) == n or (C,1-3) == n then A1 != n, and so on for A1-I9, replacing ABC with DEF for rows D, E and F, and with GHI for rows G, H, and I. Continue until solved.
No, no, NO!
The idea of \”NP\” is probably one of the most misunderstood concepts in computer science. It does NOT mean solutions are \”not polynomial\” or exponential or anything like that. It stands for Non-deterministic Polynomial time (meaning it could be solved in polynomial time on a non-deterministic Turing machine… which doesn\’t exist)
Roughly speaking, this means: given a proposed solution, it is easy (in polynomial time) to verify whether or not that solution is correct.
What most people mean when they say something is \”NP\” is actually that it is \”NP complete\”, which means the problem is just as difficult as thousands of other NP complete problems, of which there has never been found a polynomial time solution (and if a polynomial time solution WERE found for ANY NP problem, then ALL NP problems could be solved in polynomial time)
Sudoku is NP-complete, so there\’s no known polynomial time solution, and it seems unlikely one will ever be found, but it hasn\’t been proven.
That said, normal 9×9 Sudoku isn\’t very big, and could be easily solved using a number of approaches.
Prolog (or similar logic systems) would be a neat way to solve Sudoku.
sudoku one of the famous problems can easily be solved using Donald Knuth’s Dancing Link Algorithm..
Leave an Answer/Comment