Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Checking for uniqe solution
Goto page 1, 2  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku
View previous topic :: View next topic  
Author Message
sztomi

Joined: 31 Oct 2008
Posts: 5
:

Items
PostPosted: Fri Oct 31, 2008 8:43 pm    Post subject: Checking for uniqe solution Reply with quote

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
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Sat Nov 01, 2008 3:09 pm    Post subject: Reply with quote

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
View user's profile Send private message
sztomi

Joined: 31 Oct 2008
Posts: 5
:

Items
PostPosted: Sat Nov 01, 2008 4:39 pm    Post subject: Reply with quote

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
View user's profile Send private message
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Sat Nov 01, 2008 7:19 pm    Post subject: Re: Checking for uniqe solution Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
sztomi

Joined: 31 Oct 2008
Posts: 5
:

Items
PostPosted: Wed Nov 19, 2008 12:32 am    Post subject: Reply with quote

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 non-unique puzzle* that passed the two-way 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
View user's profile Send private message
sztomi

Joined: 31 Oct 2008
Posts: 5
:

Items
PostPosted: Wed Nov 19, 2008 12:40 am    Post subject: Reply with quote

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
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 349
:

Items
PostPosted: Thu Nov 20, 2008 8:11 am    Post subject: Reply with quote

You did everything right and I screwed up with my suggestion. My apologies Exclamation

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
View user's profile Send private message
sztomi

Joined: 31 Oct 2008
Posts: 5
:

Items
PostPosted: Thu Nov 20, 2008 10:21 am    Post subject: Reply with quote

Yeah, thanks. I already figured the 3-pass method out, hope this will be reliable. An exact proof would still be better Smile.
Back to top
View user's profile Send private message
briturner

Joined: 14 Oct 2008
Posts: 75
:

Items
PostPosted: Sat Nov 29, 2008 11:38 pm    Post subject: Reply with quote

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
View user's profile Send private message
sudokusnake

Joined: 25 May 2009
Posts: 4
:

Items
PostPosted: Sun Aug 09, 2009 12:06 am    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
PIsaacson

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

Items
PostPosted: Tue Aug 11, 2009 1:52 am    Post subject: Reply with quote

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 brute-force checker vs DLX should be insignificant.
Back to top
View user's profile Send private message
nukefusion

Joined: 27 Jun 2009
Posts: 22
:

Items
PostPosted: Tue Aug 11, 2009 10:03 am    Post subject: Reply with quote

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 non-logical solver (used for testing uniqueness and brute forcing any solveable puzzle) utilised a simple brute-force 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
View user's profile Send private message
lkSudoku

Joined: 16 May 2009
Posts: 60
:

Items
PostPosted: Thu Nov 26, 2009 2:33 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail
Lunatic

Joined: 11 Mar 2007
Posts: 166
:
Location: Ghent - Belgium

Items
PostPosted: Fri Nov 27, 2009 4:17 pm    Post subject: Reply with quote

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
View user's profile Send private message Send e-mail Visit poster's website
m_b_metcalf

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

Items
PostPosted: Fri Nov 27, 2009 5:18 pm    Post subject: Reply with quote

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 4-set and each unavoidable 6-set. 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 low-order 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
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Setting sudoku All times are GMT
Goto page 1, 2  Next
Page 1 of 2

 
Jump to:  
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
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron