Looking for really hard sudoku puzzles

[jkmyoung]

^ ==> XOR
Others are right. With the modifications, have been able to solve puzzle 3.
3 iterations of previous code + 5 iterations of added code.

Am still stuck on puzzle 2. Final output:

51--263--
7264-35-8
93-5-76--
395278461
86--54--9
47--698-5
-59-41-83
-43--2-5-
-87-35-4-

Am going to post a miscellaneous question for solving this sudoku.

[NeoPa]

What? You think EOR is just a donkey noise (I can't say "ass" as our US cousins may find it too amusing) :D EOR ==> XOR ==> eXclusive OR. Just a notation difference ;)

Reminder: Can you let me know what type of data is held in the array C[][] (at an element level if possible).

[jkmyoung]

Each cell has an integer associated with it, representing the possible combinations for that square. Each cell uses 10 bits.
1<<0 Lowest order bit, determines if the value is finalized.
1<<1 bit determines if 1 is possible,
1<<2 bit determines if 2 is possible,
etc..

[NeoPa]

Thanks :)

I realised while going through the three puzzles that Nepo posted, that I had got the fundamental algorithm a little wrong in my post #26. In point #4 it says :

Start with a depth level (DLvl) of 2. This means that pairs of cells are being checked first time through the loop. The depth level only needs to go to 4. Once you are checking more than half of the available cells you can only find a result if there is also a result for the remaining cells. Clearly this should already have been found as they must, of necessity, have a depth of 9-DLvl ==> must be less than DLvl when DLvl > 9/2.

This is only true if you also check for items that occur only in a limited number of cells. If X items occur only in X cells (of the section), then they can be considered to exclude any other potential answers for any cells within that group.

Consider the following column section of data where the possibilities worked out so far are :

1 - 2;4;5;6;7;8;9
2 - all
3 - 2;4;5;6;7;8;9
4 - 2;4;5;6;7;8;9
5 - 2;4;5;6;7;8;9
6 - 2;4;5;6;7;8;9
7 - all
8 - 2;4;5;6;7;8;9
9 - 2;4;5;6;7;8;9

In this case it is clear that only entries 2 & 7 may contain the values 1 & 3. Only 2 possible cells with those 2 values. Thus neither can possibly contain any other value.

2 - 1;3
7 - 1;3

[JosAH]

In this case it is clear that only entries 2 & 7 may contain the values 1 & 3. Only 2 possible cells with those 2 values. Thus neither can possibly contain any other value.

Congrats; you've tried to find a Gomory cut. The problem is that those cuts in the search space aren't 'deep', i.e. the cut doesn't just leave one unique optimal solution to the problem. You always have to back track in the search space unless you find something ingenious; let me know then ;-)

kind regards,

Jos

[NeoPa]

And without even knowing it :D

I did appreciate that I wasn't necessarily finding unique results with this particular process, but simply refining the process of elimination outlined earlier, which should ultimately lead to a unique solution, if there is one.

If I happen to fall over a mathematical theorem while I'm doing that, then all the better. Shows I'm maybe not too far off in my thinking.

[JosAH]

And without even knowing it :D

I did appreciate that I wasn't necessarily finding unique results with this particular process, but simply refining the process of elimination outlined earlier, which should ultimately lead to a unique solution, if there is one.

If I happen to fall over a mathematical theorem while I'm doing that, then all the better. Shows I'm maybe not too far off in my thinking.

Yup, but your phrase "if there is one" tells it all: a partially filled Sudoku matrix may not have one single solution, i.e. more than one completion of the puzzle can be available, leading to all the solutions of that particular puzzle. If that is the case you do have to back track and see where your initial assumption(s) failed or succeeded. For an example see a completely empty Sudoku matrix. There definitely is a solution, but which one to select?

kind regards,

Jos

[NeoPa]

I would only be looking to see what must be, rather then any random solution.

If there are multiple solutions I would list in each cell the possible values allowed for that cell (For display purposes I leave it blank if all values are possible).

In practice, I would only be interested in a puzzle with a single correct solution anyway, but the code I have works (to the extent that it DOES work) regardless of how many potential solutions there are.

[JosAH]

I would only be looking to see what must be, rather then any random solution.

Ok, but realize there's an essential difference between trying to find one single solution (if there is only one) given a partial solution and searching for any or all solutions given any partial solution.

Just because solutions aren't 'quantified', i.e. no cost factor is given to a solution and we can't say solution A is better than solution B those Gomory cuts aren't much help either: those cuts try to minimize the solution space given a cost function of every point in that space.

Maybe solving an 'N-tower' problem N times could be of help here but then again we need that back tracking stuff again.

kind regards,

Jos

[NeoPa]

Not having followed the full explanation of the Gomory Cuts, and perceiving how you seem to be referring to it, I suspect that what I have is possibly not one of them at all.

I am looking to find the values that must be in cells, or a list of possible values if the information is not available to determine which individual value it should be.

Every iteration of the algorithm (process) has the potential for allowing other aspects of the process to yield more information still, as the result of one iteration is the starting data for the next.

I'm not aware of any sudoku puzzle (with a unique solution) that does not eventually yield up the solution on following the processes listed. Admittedly, as my software doesn't apply the whole algorithm as listed, I've often applied these steps manually (should that be cranially?), but the algorithm is the same in either case.

Where multiple solutions are possible, I've never even looked for a way to itemise the various possible solutions. I don't see that as part of this question, though I'm sure that would be possible with a little work if someone had the interest.

[JosAH]

Where multiple solutions are possible, I've never even looked for a way to itemise the various possible solutions. I don't see that as part of this question, though I'm sure that would be possible with a little work if someone had the interest.

Well, read my article in the Java Howtos section: that brute force solver finds solution(s) given a partial solution no matter whether or not more than one (or zero) solutions are possible.

Those Gomory cuts are algebraic cuts, e.g. if x != 1 all it can do is add two more constraints: x >= 2 and x <= 0 which doesn't help much because you already knew that and now you're stuck with two sub problems.

kind regards,

Jos

[NeoPa]

Those Gomory cuts are algebraic cuts, e.g. if x != 1 all it can do is add two more constraints: x >= 2 and x <= 0 which doesn't help much because you already knew that and now you're stuck with two sub problems.

From post #34 however, you'll see a before and after image that are clearly different. Whether this is a Gomory Cut I couldn't tell you, but it certainly leads to progress towards a solution.

How you use this (to provide multiple solutions or a statement of what can be determined) is surely irrelevant. I don't see how the eventual results (IE. How this information is later used) has any bearing on the matter. It either progresses the understanding of the problem or it doesn't. I'm pretty sure what I was suggesting does (It's fundamental to how I solve the puzzles myself when I do).

[JosAH]

All I was saying is this:

        Puzzle #1:
+-------+-------+-------+
| 5   4 | 8 2 6 | 3 9 7 | 
| 7 2 6 | 4 9 3 | 5   8 | 
| 9 3 8 | 5   7 | 6 2 4 | 
+-------+-------+-------+
| 3 9 5 | 2 7 8 | 4 6   | 
| 8 6   | 3 5 4 | 2 7 9 | 
| 4 7 2 |   6 9 | 8 3 5 | 
+-------+-------+-------+
| 2 5 9 | 6 4   | 7 8 3 | 
|   4 3 | 7 8 2 | 9 5 6 | 
| 6 8 7 | 9 3 5 |   4 2 | 
+-------+-------+-------+

        Puzzle #2:
+-------+-------+-------+
|       |       |       | 
|       |       |       | 
|       |       |       | 
+-------+-------+-------+
|       |       |       | 
|       |       |       | 
|       |       |       | 
+-------+-------+-------+
|       |       |       | 
|       |       |       | 
|       |       |       | 
+-------+-------+-------+

For puzzle #1 your method can find a (the) solution very quickly but it'll fail miserably for puzzle #2. Both are Sudoku puzzles though; the difference is that puzzle #1 has one and only one solution while puzzle #2 has many solutions. In order to solve all Sudokus you have to deal with two different problems.

kind regards,

Jos

[jkmyoung]

From post #2, puzzles 1 and 3 have definite solutions. puzzle 2 has multiple solutions.

Using the 54 triplets which share a nonet and either a row or column has solved puzzle #3 and limited the solutions of #2.
====
With above post (#43) perhaps a more interesting task is to determine if a given puzzle has multiple solutions?

[JosAH]

With above post (#43) perhaps a more interesting task is to determine if a given puzzle has multiple solutions?

Maybe you like this link and a specialization of it then.

kind regards,

Jos