
View previous topic :: View next topic 
Author 
Message 
 sztomi
 Joined: 31 Oct 2008  Posts: 5  :   Items 

Posted: Fri Oct 31, 2008 8:43 pm Post subject: Checking for uniqe solution 


Hi everyone!
I'm writing a sudoku solver/generator in java.
The solver part uses backtracking, and works fine.
However, I came across a problem I was unable to solve with the generator. I would like it to generate sudokus with a unique solution (not "fake sudokus"). I searched this forum and learned that, if I run the backtracking algorithm from the last cell of the sudoku, it will find a different solution than the one found running from the first one (in case there are multiple solutions). Is that true? I mean is there a correct proof?
Thank you for your time. 

Back to top 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

Posted: Sat Nov 01, 2008 3:09 pm Post subject: 


There have been differing opinions on whether or not this approach works. I'm not aware of any proof.
From a personal point of view, I believe it works ... if ... your backtracking algorithm is truely brute force and doesn't use the state of the grid to determine which candidate/cell is tried next; i.e., no look ahead optimization and only the direction of the cell processing is altered during the two passes. The candidates must be chosen in the same sequential order no matter which direction you use during a pass! 

Back to top 


 sztomi
 Joined: 31 Oct 2008  Posts: 5  :   Items 

Posted: Sat Nov 01, 2008 4:39 pm Post subject: 


daj95376 wrote:  There have been differing opinions on whether or not this approach works. I'm not aware of any proof.
From a personal point of view, I believe it works ... if ... your backtracking algorithm is truely brute force and doesn't use the state of the grid to determine which candidate/cell is tried next; 
Thanks for you reply. I believe that it works, too, but I would just like to make it as good as possible, so to be sure. (And yes, my solver is truly bruteforce, it always tries the candidates in the same order, 1 to 9).
My primary intention is to decide, if there are multiple solutions or just one. Are there any other methods that proven correctly? 

Back to top 


 Lunatic
 Joined: 11 Mar 2007  Posts: 166  :  Location: Ghent  Belgium  Items 

Posted: Sat Nov 01, 2008 7:19 pm Post subject: Re: Checking for uniqe solution 


sztomi wrote:  I searched this forum and learned that, if I run the backtracking algorithm from the last cell of the sudoku, it will find a different solution than the one found running from the first one (in case there are multiple solutions). Is that true? I mean is there a correct proof?

I confirm the statements of daj95376, but once you find the first solution (and hopefully the only solution), you can take note of that solution and then simply reject the last solved cell so your backtracking solver will continue the search looking for possible multiple solutions. _________________ Marc
~~~<><~~~<><~~~<><~~~<><~~~ 

Back to top 


 sztomi
 Joined: 31 Oct 2008  Posts: 5  :   Items 

Posted: Wed Nov 19, 2008 12:32 am Post subject: 


I tried the rejecting technique, but is awfully slow.
I decided to "trust" the method described above (solving backwards and comparing), but after the fifth try, I generated a nonunique puzzle* that passed the twoway check:
000001000608030004009080000805640000010020800002000050231700500000050006006803000
*: Accoriding to SudokuExplainer, it has multiple solutions.
Sorry for not formatting well, this is how my program does not perform any yet.
This is how I did it (only the important parts. The generator uses the solver):
Code: 
private static boolean internalSolve( int i, int j, int[][] grid )
{
if ( i == 9 )
{
i = 0;
if ( ++j == 9 )
{
return true;
}
}
if ( grid[i][j] != 0 )
{
return internalSolve( i + 1, j, grid );
}
for ( int val = 1; val <= 9; ++val )
{
if ( isLegal( i, j, val, grid ) )
{
grid[i][j] = val;
if ( internalSolve( i + 1, j, grid ) )
{
return true;
}
}
}
grid[i][j] = 0;
return false;
}
private static boolean internalSolveBack(int i, int j, int[][] bgrid)
{
if ( i == 1 )
{
i = 8;
if ( j == 1 )
{
return true;
}
}
if ( bgrid[i][j] != 0 )
{
return internalSolveBack( i  1, j, bgrid );
}
// Same order
for ( int val = 1; val <= 9; ++val )
{
if ( isLegal( i, j, val, bgrid ) )
{
bgrid[i][j] = val;
if ( internalSolveBack( i  1, j, bgrid ) )
{
return true;
}
}
}
bgrid[i][j] = 0;
return false;
}



Back to top 


 sztomi
 Joined: 31 Oct 2008  Posts: 5  :   Items 

Posted: Wed Nov 19, 2008 12:40 am Post subject: 


Interesting. I changed the internalSolveBack method, so that it checks the candidates in reversed order, and now it computes a different solution!
Output when the same order used:
Code: 
000001000608030004009080000805640000010020800002000050231700500000050006006803000
324971685678235914159486273895647132413529867762318459231764598987152346546893721
324971685678235914159486273895647132413529867762318459231764598987152346546893721

Output when reversed order used:
Code: 
000001000608030004009080000805640000010020800002000050231700500000050006006803000
324971685678235914159486273895647132413529867762318459231764598987152346546893721
423971685678235914159486723895647231314529867762318459231764598987152346546893172

(The 1st line is the puzzle itself, the 2nd one is the straight solution, the 3rd one is the backwards).
Am I doing something wrong or I just found an answer to my own question? (see the first post in the thread.) 

Back to top 


 daj95376
 Joined: 05 Feb 2006  Posts: 349  :   Items 

Posted: Thu Nov 20, 2008 8:11 am Post subject: 


You did everything right and I screwed up with my suggestion. My apologies
Your puzzle does have multiple solutions ... and ... the backtracking method that I proposed does not work for it.
My second suggestion is to have the second pass start at the beginning of the puzzle and apply values in descending order. 

Back to top 


 sztomi
 Joined: 31 Oct 2008  Posts: 5  :   Items 

Posted: Thu Nov 20, 2008 10:21 am Post subject: 


Yeah, thanks. I already figured the 3pass method out, hope this will be reliable. An exact proof would still be better . 

Back to top 


 briturner
 Joined: 14 Oct 2008  Posts: 75  :   Items 

Posted: Sat Nov 29, 2008 11:38 pm Post subject: 


Greetings,
Here is my understanding of using multiple passes to verify uniqueness:
First, assume you have a straight backtracking brute force program. For example, if you only had 3 cells with the numbers from 1 to 3, then you would check the following in order to determine if a solution is found:
111 112 113 121 122 123 131 132 133
211 212 213 221 222 223 231 232 233
311 312 313 321 322 323 331 332 333
lets assume we have 2 solutions, 123, and 231. If you started down the list, you would find 123 first. Starting from the end would find 231 first. So this method would work, but you must do the exact opposite when backtrackings, including both reversing the cell changed first, and the order of the numbers changing (3, 2, 1 instead of 1, 2, 3).
This should always work, but is not the best method, since it requires altering the code for each pass.
A better method is to mark a solution found, then let the normal routine continue. This allows the same code to be used, and allows you to add in optimizations since you do not have to be able to repeat the sequence in reverse.
For timing purposes, if you use no optimizations, then the timing will average the same. If it is a unique solution, then you will need to test every condition, so timing is the same. Assuming 2 solutions, then for first solution is the same either way. If there is a random distribution over the rest of the solution space, then on average, both directions will result in the same time.
If any optimizations are used then doing a pass in reverse will on average take longer.
For your code, it looks like you are reversing the direction of the cells changed, but not the order of the number changing in that call.
brit 

Back to top 


 sudokusnake
 Joined: 25 May 2009  Posts: 4  :   Items 

Posted: Sun Aug 09, 2009 12:06 am Post subject: 


just brute force ALL of the possible candidates, iterate an integer each time you find one, and if in the end the integer is 1, you have a unique solution. 

Back to top 


 PIsaacson
 Joined: 17 Jan 2006  Posts: 47  :  Location: Campbell, CA  Items 

Posted: Tue Aug 11, 2009 1:52 am Post subject: 


You might want to consider using DLX. It is capable of determining if a sudoku puzzle has 0, 1 or multiple solutions (and if required, it can actually find all possible solutions). There are numerous Java code examples available, so use Google and the forum search help. The sticky at the beginning of this forum contains links to various DLX implementations, but I code in C/C++ and use libexact, so I have no experience with the Java supplied code.
Unless you are after speed records, and that seems unlikely with Java as a language of choice, the difference in execution time between a bruteforce checker vs DLX should be insignificant. 

Back to top 


 nukefusion
 Joined: 27 Jun 2009  Posts: 22  :   Items 

Posted: Tue Aug 11, 2009 10:03 am Post subject: 


I would recommend implementing DLX as well. Can take a little time to get your head around it, but actually, even with a JIT compiled language such as Java, you may still notice a difference when compared to a standard brute force solver.
My solver is being coded using managed C# and my initial nonlogical solver (used for testing uniqueness and brute forcing any solveable puzzle) utilised a simple bruteforce backtracking mechanism. I then updated it to use DLX to check for solveability and uniqueness and although I didn't do any timed tests, the difference in speed was enough for it to be noticeable by the end user, especially during puzzle generation. 

Back to top 


 lkSudoku
 Joined: 16 May 2009  Posts: 60  :   Items 

Posted: Thu Nov 26, 2009 2:33 pm Post subject: 


I believe the following brute force method will ensure unique solution:
1. Solve using your described internalSolve function
2. Solve using a modification of internalSolve function in which you test different values in descending order instead of ascending order (although the order of the cell being tested should remain the same)
If you get the same result, there must be a unique sudoku
Now I will provide my logic for that algorithm
Suppose there are exactly two solution:
Solution A 123456789...
Solution B 124356789...
When you solve with values in ascending and descending orders, the the prefix until the 3rd cell will be the same as all other numbers will result in an error
When we get to the third cell, the ascending algorithm will find 3 and get a solution, while the descending algorithm will find 4 and get a solution
In the general case, at the first cell in which there are two different values with solutions, the two algorithms will find different numbers
However, if you solve the same puzzle backward starting from the last cell, either ascending or descending order, there is a chance, at least theoretically, that both algorithms will find the same values for all the cells
Quote: 
111 112 113 121 122 123 131 132 133
211 212 213 221 222 223 231 232 233
311 312 313 321 322 323 331 332 333
lets assume we have 2 solutions, 123, and 231. If you started down the list, you would find 123 first. Starting from the end would find 231 first. So this method would work, but you must do the exact opposite when backtrackings, including both reversing the cell changed first, and the order of the numbers changing (3, 2, 1 instead of 1, 2, 3).
This should always work,

I doubt it is so, suppose the known given value is the second value 2, and there are two solutions: 123, and 321
The first solution will guess 1 in first cell, and then find 123 as a solution
the opposite solution will guess 3 at the third cell, and again will find 123 as a solution although there is a 321 solution
However if you go with the cells in the same order of places, once with ascending values and the other with desceding values you will get 123 with ascending and 321 with descending 

Back to top 


 Lunatic
 Joined: 11 Mar 2007  Posts: 166  :  Location: Ghent  Belgium  Items 

Posted: Fri Nov 27, 2009 4:17 pm Post subject: 


lkSudoku wrote:  However if you go with the cells in the same order of places, once with ascending values and the other with desceding values you will get 123 with ascending and 321 with descending 
I confirm this as correct, but I think this is not the fastest way since, as daj95376 stated elsewhere in this thread, your brute force don't allow to use the state of the grid to determine which cell is tried next.
I suggested the "rejection method" (which I use in my generator/solver) earlier, but forgot to mention that it always takes the cell with the least candidates for the next step. There's nothing wrong in taking advantage of selecting the cell with the least candidates, it would surely be faster than going through the grid in a fixed order...
You can check the "checkuniqueness" routine within the c code from my random sudoku generator example at
http://users.telenet.be/mpq/sudoku/random_sudoku_generator.c _________________ Marc
~~~<><~~~<><~~~<><~~~<><~~~ 

Back to top 


 m_b_metcalf
 Joined: 13 Mar 2006  Posts: 210  :  Location: Berlin  Items 

Posted: Fri Nov 27, 2009 5:18 pm Post subject: 


A method I use for uniqueness is:
1) Use simple logic/brute force to find the first solution.
2) In that solution grid locate, in turn, each unavoidable 4set and each unavoidable 6set. Each time a set is located check that it is covered by a clue in the original puzzle. If it isn't, you know there are multiple solutions and can end there.
3) If this step is reached, continue counting in the brute force until a second solution, if any, is found.
The third step is entered only for grids with higher order unavoidable sets that are uncovered (and all loworder ones covered), or for those with a unique solution. The fast tests in 2) are, on balance, faster than just counting as in step 3).
Regards,
Mike Metcalf 

Back to top 




You cannot post new topics in this forum You cannot reply to topics in this forum You cannot edit your posts in this forum You cannot delete your posts in this forum You cannot vote in polls in this forum

Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron
