Looking for really hard sudoku puzzles

[jkmyoung]

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.

[Nepomuk]

Well, I have some on my mobile which that solver might not be able to solve, so here are a few:

|xx1|xxx|xxx|
|x2x|345|xxx|
|xxx|xxx|267|

|x4x|x6x|xxx|
|87x|xxx|x51|
|xxx|x1x|x9x|

|563|xxx|xxx|
|xxx|927|xxx|
|xxx|xxx|8xx|

|x1x|x2x|3xx|
|x2x|4xx|xxx|
|x3x|5xx|6xx|

|3xx|x7x|xx1|
|8xx|xxx|xx9|
|4xx|x6x|xx5|

|xx9|xx1|x8x|
|xxx|xx2|x5x|
|xx7|x3x|x4x|

|xxx|x1x|xx2|
|3xx|4xx|x5x|
|6xx|7xx|x8x|

|xx1|x5x|9xx|
|xx4|xxx|2xx|
|xx5|x6x|7xx|

|x5x|xx8|xx6|
|x7x|xx2|xx3|
|9xx|x4x|xxx|

("x" being an empty field) Hope that helps.

Greetings,
Nepomuk

[JosAH]

Thanks for those puzzles; I just checked: my old solver solves them all instantaneously . (see that old article about Sudoku).

kind regards,

Jos

ps. solving took 14, 2 and 9 ms respectively but that includes the class loading etc. Those are highly inaccurate timings.

[jkmyoung]

Managed to find a bug in the program thanks to your inputs. After running those 3 problems through again, I got.
1. Solved. 5 cycles.
2. Not enough data, or unsolvable puzzle.
3. Not enough data, or unsolvable puzzle.

Will have to look up ways to refine the algorithm, so that it can solve the last 2.

[JosAH]

@jkmyoung: can you tell a bit about your algorithm? The solver I wrote just uses a brute force search and a bit of local cleverness to quickly determine whether or not a value in a cell is possible. Basically it can't go any faster than it goes without any 'intelligence'.

kind regards,

Jos

ps. what's a 'cycle' in your algorithm?

[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..

We also have 3 X 9 integers for the rows, cols, and nonets for the numbers that are already set.

After the numbers are loaded, we loop through the following process.
Main loop:
Side Loop1: Check rows.
Examine the 9 numbers in the current row. If there are any values such that only 1 cell can have them, and they aren't set yet, then set them. If there is no possible cell for a value, throw an error.

Side Loop2: Check cols,
Side Loop3: Check nonets,
Side Loop4: Check each individual cell.
If a cell has only one possible value and isn't set yet, then mark it as set.

End Main loop

A 'cycle' is one iteration through the main loop.

[JosAH]

I don't understand how your algorithm 'starts up'. Suppose there's an empty Sudoku puzzle: every row/column/sub-square/cell can store one of nine values so none is assigned in your cycle ...

kind regards,

Jos

[jkmyoung]

Ah sorry, didn't think it made a difference.

Loading:
The program only reads in 81 digits, from 0-9. 0 is an empty space, 1-9 are set numbers. It ignores all other input. It determines if there are any duplicate numbers in any row/column/nonet, and if so throws an "InvalidInp ut" error.

Running:
If no changes are made within a single cycle, then the program returns:
Not enough data, or unsolvable puzzle.

Side Loop4: Check each individual cell. If there is no possible value for a cell, the program throws an error stating something like "No possible value for cell (x,y)"

===============
So if you have an empty puzzle, no changes will be made in a cycle.
- Program returns "Not enough data, or unsolvable puzzle."

===============
If you have an impossible puzzle like

-23------
456------
789------
---------
---------
---------
---------
---------
1--------

The puzzle will return:
"No possible value for cell (1,1)"

[JosAH]

So if you have an empty puzzle, no changes will be made in a cycle.
- Program returns "Not enough data, or unsolvable puzzle."

Ah, ok; so your algorithm completes a partially filled board if only one solution is possible, i.e. it doesn't find any or all possible solutions given a partial solution, right?

kind regards,

Jos

[jkmyoung]

Yes. Have thought about it, but haven't figured out a way beyond brute force, so haven't implemented it yet.

[ashitpro]

I'd implemented this long ago...
It worked with algorythm strategy what we call as backtracking... Or may be you can say brute force...
It used to solved even empty sudoku

[JosAH]

I'd implemented this long ago...
It worked with algorythm strategy what we call as backtracking... Or may be you can say brute force...
It used to solved even empty sudoku

That's what he was talking about: how to find anything more clever than just a brute force algorithm. I once tried it by using ILP (Integer Linear Programming) but it failed miserably: although the solver found a solution it was much slower than my simple brute force approach (see an article about it in the Java howtos section).

kind regards,

Jos

[r035198x]

I'm interested in the ILP approach. Did you find out why it is slower?

[JosAH]

I'm interested in the ILP approach. Did you find out why it is slower?

I used the binary version, i.e. Xijv == 1 if square at i,j == v. You need 9x9 constraints to model the puzzle and you need 9x9x9 binary variables. I think that the search space is a bit bigger than just enumerating the feasable possibilites. Since the entire puzzle is a feasability problem the linear relaxation (simplex or interior point) doesn't buy you much.

kind regards,

Jos

[NeoPa]

I have an Excel spreadsheet that handles solving and allowing user entry (with checking and optional assistance). It implements some of the techniques I use when solving, but is otherwise brute-force / iterative.

I moved on to Killers a while back, but even displaying them in Excel was more than I wanted to get into as a simple diversion.

If anyone gets bored with the Deadly Killers (reference The Times) then try restricting yourself only to writing the solutions from the top-left cell and proceeding in a clockwise spiral (Making notes is clearly not allowed).