Looking for really hard sudoku puzzles

[NeoPa]

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

I'd be interested to see your multiple solutions to #2.

I found only the one. I may have slipped up of course, but found only one valid solution.
Grid #2

|x1x|x2x|3xx|       |514|826|397|
|x2x|4xx|xxx|       |726|493|518|
|x3x|5xx|6xx|       |938|517|624|

|3xx|x7x|xx1|       |395|278|461|
|8xx|xxx|xx9|       |861|354|279|
|4xx|x6x|xx5|       |472|169|835|

|xx9|xx1|x8x|       |259|641|783|
|xxx|xx2|x5x|       |143|782|956|
|xx7|x3x|x4x|       |687|935|142|

[JosAH]

I'd be interested to see your multiple solutions to #2.

According to my stupid brute force solver there's only one solution.

kind regards,

Jos

[jkmyoung]

I get 2 more solutions corresponding to the following:

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

Relied on another online sudoku solver to find it, so hopefully it validates.

[JosAH]

I get 2 more solutions corresponding to the following:

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

Relied on another online sudoku solver to find it, so hopefully it validates.

That is an infeasible partial solution:

8,7: 1
9,9: 6

kind regards,

Jos

[NeoPa]

Relied on another online sudoku solver to find it, so hopefully it validates.

That's why I was after a solution. So that I could check it out :S

[JosAH]

That's why I was after a solution. So that I could check it out :S

That thing is incorrect (see my reply #49); no need to think about it any further.

kind regards,

Jos

[NeoPa]

I did read it Jos, but I'm afraid I couldn't follow what you were saying :
8,7: 1
9,9: 6
Probably being a little dim, but there you are.

Also, it's nice to follow something through for oneself - hence the request for a separate (complete) solution for me to check through. From that I could highlight the exact spot where a value MUST be wrong.

[JosAH]

I did read it Jos, but I'm afraid I couldn't follow what you were saying :
8,7: 1
9,9: 6
Probably being a little dim, but there you are.

Also, it's nice to follow something through for oneself - hence the request for a separate (complete) solution for me to check through. From that I could highlight the exact spot where a value MUST be wrong.

That's what my little program did for me ;-) at the 8th row, 7th column, the value 1 already exists in the same row (or column or sub-square); same with the value 6 in the bottom right corner.

kind regards,

Jos

[jkmyoung]

...I shall have to find a better sudoku solver, which isn't blocked at work.

[JosAH]

...I shall have to find a better sudoku solver, which isn't blocked at work.

Why don't you use my solver (see the article section)? You can do with it what you want (except selling it ;-)

kind regards,

Jos

[jkmyoung]

Perhaps. Was simply using the online solver as a quick reference. Am still stuck on what piece of logic to use and implement to solve puzzle 2.

[NeoPa]

Good point JK. What I did with this puzzle was to take it to the limit using the algorithm already laid out in the earlier posts (I arrived at the same point as you in post #31 btw).

From there I took a trial-and-error approach. In fact I found that C1 could only be 4 or 8. I tried 8 and found that it couldn't produce a valid solution. Conversely, when I tried 4, it presented me with a unique solution.

[JosAH]

From there I took a trial-and-error approach. In fact I found that C1 could only be 4 or 8. I tried 8 and found that it couldn't produce a valid solution. Conversely, when I tried 4, it presented me with a unique solution.

So there you took a (manual) back tracking brute force approach, trying to find a solution. You could've used that approach from the start. Humans aren't very good at that but computers are ...

You're trying to solve that puzzle like everyone does: try to find as much of the puzzle by using a systematic approach and when that approach fails, simply search for further possibilities. I don't think that approach can be automated easily because there's (quite a bit) of heuristics involved when to apply the switch in approach: systemematic vs. searching.

kind regards,

Jos

[NeoPa]

You may be right Jos. Personally I prefer to apply the logic if I can.

As I said before, I don't have the whole algorithm coded in my solver (It was never really designed as a solver per se) so I used the code for what it could tell me, then applied the rest of the algorithm manually (as it was I doing it, the brute force approach would have taken a lot longer and been much less fun). When that still left me short (The only example I can recall where this logic has done so) I used the brute force approach (quite simply as it turned out).

If I ever do take this project on further (unlikely) I think I would prefer to try to appy the logic as specified rather than the simpler brute force approach. Not because it couldn't do the job as quickly, but simply because it would be more challenging and 'fun'.

[JosAH]

You may be right Jos. Personally I prefer to apply the logic if I can.

As I said before, I don't have the whole algorithm coded in my solver (It was never really designed as a solver per se) so I used the code for what it could tell me, then applied the rest of the algorithm manually (as it was I doing it, the brute force approach would have taken a lot longer and been much less fun). When that still left me short (The only example I can recall where this logic has done so) I used the brute force approach (quite simply as it turned out).

If I ever do take this project on further (unlikely) I think I would prefer to try to appy the logic as specified rather than the simpler brute force approach. Not because it couldn't do the job as quickly, but simply because it would be more challenging and 'fun'.

We're running around in circles this way: there are Sudoku problems that have more than one solution (see my second example, the empty puzzle). No logic whatsoever will give you a single solution because more than one solution is possible. No matter any fun, it won't give you a unique solution when more than one solution is possible unless you either apply some heuristics and 'local search' or you apply a brute force approach. I know these things, I've been there (still in it, sometimes over my head ;-) and done that. Feasibility checks can't help you when more than one solution exist. Local search is too 'narrow minded' to help you out of a multiple choice event and math simply lacks so all that remains is a stupid (not so) brute force strategy (see my old article in the howtos section).

kind regards,

Jos