Connecting Tech Pros Worldwide Help | Site Map

Looking for really hard sudoku puzzles

Moderator
 
Join Date: Mar 2006
Posts: 1,103
: Dec 17 '08
Does anyone have some super, super hard Sudoku puzzles?

Back in February this year, I had enough time to finally program a Sudoku solver in Java. Right now, I'm looking for solvable puzzles, but ones that my program cannot solve. However, most hard puzzles in the newspapers are solved within 2-3 cycles so far.

The ones I've found on google which are said to be hard, get solved in 3 cycles.

Any help would be very much appreciated!
========================================
The program works on the possible values for each cell.
1. Determine the possible values in each cell.
2. Check rows. If there is any value in which only 1 empty cell can take that value, set empty cell to that value.
3. Columns.
4. Nonets, (3X3 Squares.)
5. Indiviual cells.
JosAH's Avatar
Expert
 
Join Date: Mar 2007
Posts: 10,611
#51: Jan 22 '09

re: Looking for really hard sudoku puzzles


Quote:

Originally Posted by NeoPa View Post

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's Avatar
Administrator
 
Join Date: Oct 2006
Location: London - UK
Posts: 15,672
#52: Jan 22 '09

re: Looking for really hard sudoku puzzles


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's Avatar
Expert
 
Join Date: Mar 2007
Posts: 10,611
#53: Jan 22 '09

re: Looking for really hard sudoku puzzles


Quote:

Originally Posted by NeoPa View Post

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
Moderator
 
Join Date: Mar 2006
Posts: 1,103
#54: Jan 23 '09

re: Looking for really hard sudoku puzzles


...I shall have to find a better sudoku solver, which isn't blocked at work.
JosAH's Avatar
Expert
 
Join Date: Mar 2007
Posts: 10,611
#55: Jan 23 '09

re: Looking for really hard sudoku puzzles


Quote:

Originally Posted by jkmyoung View Post

...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
Moderator
 
Join Date: Mar 2006
Posts: 1,103
#56: Jan 23 '09

re: Looking for really hard sudoku puzzles


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's Avatar
Administrator
 
Join Date: Oct 2006
Location: London - UK
Posts: 15,672
#57: Jan 23 '09

re: Looking for really hard sudoku puzzles


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's Avatar
Expert
 
Join Date: Mar 2007
Posts: 10,611
#58: Jan 24 '09

re: Looking for really hard sudoku puzzles


Quote:

Originally Posted by NeoPa View Post

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's Avatar
Administrator
 
Join Date: Oct 2006
Location: London - UK
Posts: 15,672
#59: Jan 25 '09

re: Looking for really hard sudoku puzzles


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's Avatar
Expert
 
Join Date: Mar 2007
Posts: 10,611
#60: Jan 26 '09

re: Looking for really hard sudoku puzzles


Quote:

Originally Posted by NeoPa View Post

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
NeoPa's Avatar
Administrator
 
Join Date: Oct 2006
Location: London - UK
Posts: 15,672
#61: Jan 26 '09

re: Looking for really hard sudoku puzzles


I see the circles Jos ;)

I guess we can agree to view things from different perspectives huh.
JosAH's Avatar
Expert
 
Join Date: Mar 2007
Posts: 10,611
#62: Jan 26 '09

re: Looking for really hard sudoku puzzles


Quote:

Originally Posted by NeoPa View Post

I see the circles Jos ;)

I guess we can agree to view things from different perspectives huh.

Yup; there's one difference though: I'm right and you're not; there are puzzles that are partially solved that don't have a unique solution (see the empty puzzle) and trying to find one by inferring feasibility rules doesn't make it ;-)

kind regards,

Jos
NeoPa's Avatar
Administrator
 
Join Date: Oct 2006
Location: London - UK
Posts: 15,672
#63: Jan 26 '09

re: Looking for really hard sudoku puzzles


Quote:

Originally Posted by JosAH View Post

Yup; there's one difference though: I'm right and you're not;

Of course! How could I have been so blind? :D
Reply


Similar Algorithms / Advanced Math bytes