Checking for uniqe solution

sztomi · 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.

daj95376 · 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!

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

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

sztomi · 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 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):

sztomi · 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:

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

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.

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

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

.

briturner · 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

sudokusnake · 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.

PIsaacson · 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 brute-force checker vs DLX should be insignificant.

nukefusion · 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 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.

lkSudoku · 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

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

m_b_metcalf · 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 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