Interview Questions And Answers 
-
Write an algorithm for Soduku puzzle
20,851 Views |
(47 votes, avg: 3.04)
Loading ...
Answers »
Our Sponsors
Our Sponsors
Write an algorithm for Soduku puzzle
20,851 Views | (47 votes, avg: 3.04)
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..
If you’re using simple backtracking, randomisation of the order of slot choice will help. Considering the minimum constrained slot first seems to be a good optimization, but I’ve no idea how it’s done efficiently.
Using constraint programming in Prolog:
:- use_module(library(clpfd)).
solve(sudoko_board):-
sudoko_board =
[
[A1,A2,A3,A4,A5,A6,A7,A8,A9],
[B1,B2,B3,B4,B5,B6,B7,B8,B9],
[C1,C2,C3,C4,C5,C6,C7,C8,C9],
[D1,D2,D3,D4,D5,D6,D7,D8,D9],
[E1,E2,E3,E4,E5,E6,E7,E8,E9],
[F1,F2,F3,F4,F5,F6,F7,F8,F9],
[G1,G2,G3,G4,G5,G6,G7,G8,G9],
[H1,H2,H3,H4,H5,H6,H7,H8,H9],
[I1,I2,I3,I4,I5,I6,I7,I8,I9]
],
% Unique values per row
all_different([A1,A2,A3,A4,A5,A6,A7,A8,A9]),
all_different([B1,B2,B3,B4,B5,B6,B7,B8,B9]),
all_different([C1,C2,C3,C4,C5,C6,C7,C8,C9]),
all_different([D1,D2,D3,D4,D5,D6,D7,D8,D9]),
all_different([E1,E2,E3,E4,E5,E6,E7,E8,E9]),
all_different([F1,F2,F3,F4,F5,F6,F7,F8,F9]),
all_different([G1,G2,G3,G4,G5,G6,G7,G8,G9]),
all_different([H1,H2,H3,H4,H5,H6,H7,H8,H9]),
all_different([I1,I2,I3,I4,I5,I6,I7,I8,I9]),
% Unique values per column
all_different([A1,B1,C1,D1,E1,F1,G1,H1,I1]),
all_different([A2,B2,C2,D2,E2,F2,G2,H2,I2]),
all_different([A3,B3,C3,D3,E3,F3,G3,H3,I3]),
all_different([A4,B4,C4,D4,E4,F4,G4,H4,I4]),
all_different([A5,B5,C5,D5,E5,F5,G5,H5,I5]),
all_different([A6,B6,C6,D6,E6,F6,G6,H6,I6]),
all_different([A7,B7,C7,D7,E7,F7,G7,H7,I7]),
all_different([A8,B8,C8,D8,E8,F8,G8,H8,I8]),
all_different([A9,B9,C9,D9,E9,F9,G9,H9,I9]),
% Unique values per square
all_different([A1,A2,A3,B1,B2,B3,C1,C2,C3]),
all_different([A4,A5,A6,B4,B5,B6,C4,C5,C6]),
all_different([A7,A8,A9,B7,B8,B9,C7,C8,C9]),
.
.
% and so on, you get it!
labeling([],sudoko_board).
The vertices can be labelled with the ordered pairs x,y where x and y are integers between 1 and 9. In this case, two distinct vertices labelled by x,y and x`,y` are joined by an edge if and only if:
x=x` or y=y` or,
x/3=x`/3 or,
y/3=y`/3
The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them.
A valid Sudoku solution grid is also a Latin square. There are significantly fewer valid Sudoku solution grids than Latin squares because Sudoku imposes the additional regional constraint. Nonetheless, the number of valid Sudoku solution grids for the standard 9×9 grid was calculated by Bertram Felgenhauer in 2005 to be 6,670,903,752,021,072,936,960, which is roughly the number of micrometers to the nearest star. This number is equal to 9! × 722 × 27 × 27,704,267,971, the last factor of which is prime. The result was derived through logic and brute force computation. The derivation of this result was considerably simplified by analysis provided by Frazer Jarvis and the figure has been confirmed independently by Ed Russell. Russell and Jarvis also showed that when symmetries were taken into account, there were 5,472,730,538 solutions. The number of valid Sudoku solution grids for the 16×16 derivation is not known.
The maximum number of givens that can be provided while still not rendering the solution unique, regardless of variation, is four short of a full grid; if two instances of two numbers each are missing and the cells they are to occupy are the corners of an orthogonal rectangle, and exactly two of these cells are within one region, there are two ways the numbers can be added. The inverse of this — the fewest givens that render a solution unique — is an unsolved problem, although the lowest number yet found for the standard variation without a symmetry constraint is 17, a number of which have been found by Japanese puzzle enthusiasts, and 18 with the givens in rotationally symmetric cells.
then why dont you write a program for the constrained one.
Leave an Answer/Comment