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]

@jkmyoung
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.