Extreme difficulty puzzle

dukuso · Posted: Thu Jul 21, 2005 5:28 am Post subject:

7 guesses, 472 placements.

This is when using the 4 standard checks :
forced placement in a row,column,block,cell.

Nick70 · Posted: Thu Jul 21, 2005 9:40 am Post subject:

6 double forcing chains and 1 triple forcing chain to reach the solution without guessing.

tilps · Posted: Thu Jul 21, 2005 10:35 am Post subject:

Yeah, now that i've 'unlocked' my solvers potential this puzzle has been rerated as a 1.2.3

1 lookahead, 2 logic steps, involving triples.

I shall endeaveour to find a harder one.

tilps · Posted: Thu Jul 21, 2005 10:50 am Post subject:

dukuso · Posted: Fri Jul 22, 2005 11:45 am Post subject:

here are the posts from the other thread in the "solving" section

my solver rated it much less hard,
when I rotated it or just changed the order of processing
the moves.

7.. ... .19
46. 19. ...
... 682 7.4
.9. ... ..7
... 3.. 4.5
..6 7.. ...
..1 ... ...
2.. .74 ...
... 2.. 3..

>this is the hardest sudoku, which my computer could find
>with hillclimbing in some hours.
>It requires 199 guesses and 11574 placements by my program !
>There was a big gap to the 2nd hardest found,
>which required only 64 guesses and 3719 placements.

but my solver rated it much less hard,
when I rotated it or just changed the order of processing
the moves.

Last edited by dukuso on Fri Jul 22, 2005 11:20 am; edited 6 times in total

Nick70

Joined: 08 Jun 2005
Posts: 41
:

Items
Posted: Fri Jul 22, 2005 7:11 am Post subject:

Not that hard, can be solved withoug guessing using turbot fish / xy-wing / double forcing chains.

This one, on the other hand, cannot:

Code:
..1.8.6.4
.376.....
5........
.....5...
..6.1.8..
...4.....
........3
.....752.
8.2.9.7..

Back to top

tilps

Joined: 19 Jun 2005
Posts: 18
:

Items
Posted: Fri Jul 22, 2005 7:20 am Post subject:

Original one is rated 1.2.2 by my current solver - see puzzles section for a 1.3.2 and a 1.2.3 puzzle

1.2.2 is 1 lookahead invoking 2 'trivial' logic steps from a possibility pair needed to make progress at some point during the logical solve.

Just a random note, when posting boards its best to use the 'code' button to wrap the board. And if you are feeling really friendly, dashes are usually used to mark group boundries and whitespace or dots to mark empty squares, rather than the otherway round.

Nick70s example is rated 1.2.3 - 1 lookahead invoking 2 'trivial' logic steps from a possibility triplet.

Back to top

dukuso

Joined: 14 Jul 2005
Posts: 13
:

Items
Posted: Fri Jul 22, 2005 11:26 am Post subject:

thanks.

I'm still learning how to post sudokus here, what's a "dash" ?

I'm not sure how your rating works. Does it also work
for 16*16 sudokus ?

Maybe I can refine my method to create hard sudokus later...

tilps · Posted: Fri Jul 22, 2005 1:41 pm Post subject:

My rating system is based off the methods of runtime constructed logic used to find the solution. The 'hardest' runtime constructed logic used defines its rating. If a puzzle can be solved using the 'simple' logic rules alone it gets a rating of 0

Then comes lookahead 1. In lookahead one 'sets' of possibilities are considered. If there are 2 places for the number 2 in a row, then both of those possibilities are considered, and simple logic is applied to each possibility. If both possibilities have a common elimination then that elmination can be logically applied to the original board. The number of 'passes' of simple logic required to reach the elimination in each board is the second number in the rating. A 1.0 requires no simple logic passes to eliminate something on any of the possabilities being considered. A 1.1 requires one simple logic pass on at least one of the possibiltiies being considered, in order to reach the common elimination. The third digit represents the number of possibilities which had to be simultaneously searched to locate the common elimination. If there are 2 possibilities for the number 2 in a column and investigating that requires 1 logic pass, that is a 1.1.2 If there are 3 possibilities for the number 3 in a box and they are all in the same row, they might eliminate the option of a number 3 somewhere else in that row without any logic passes. That is a 1.0.3.

Then comes lookahead 2. Lookahead 2 is lookahead 1, but in addiction to simple logic passes, a lookahead 1 pass is allowed on each of the possibiltiies under consideration to further enhance the chance of discovering common eliminations. Lookahead 2 is required for locked tripples. I dont currently have a more detailed scoring system for lookahead 2 because I am yet to discover any evidence that lookahead 2 is needed in 3x3(9x9) puzzles and correspondingly havent put much effort into it. I have a 'tester' class which when run should discover 'flaws', places where my current logic generator fails to generate logic to make progress on a puzzle which it is possible to make progress on. I have run this for a few hours on 3x3 with lookahead 1 and found no flaws. Given that there are a Huge number of 3x3 sudokus, there is ofcourse a chance I have missed a case which causes a flaw.

I have however found flaws on 4x4(16x16), which suggests that lookahead 2 is required (and maybe higher) to generally solve 4x4 puzzles. My solver and rating system is general to any AxB sudoku, although its slow enough on 4x4 that I havent gone any higher.

and a dash is the '-' character.

dukuso · Posted: Fri Jul 22, 2005 2:40 pm Post subject:

thanks for the explanation.
As I understand you just give 3 numbers representing the running time
of your solver with lookahead 0,1,2 .

What eliminations do you include at lookahead 0 ?

Your rating doesn't consider, how many ways there are to solve the puzzle. Say there are many different ways of same rating-level
to solve a sudoku, you rate it the same as if there were only one
way. For a computer this might be non-important but for
a human solver this could be a big difference.

There is also the problem, which I observed, that e.g. a rotation
of the grid could give a different rating.
Does this also happen with your rating ?

tilps · Posted: Fri Jul 22, 2005 4:00 pm Post subject:

The numbers dont represent the running time of the solve, they represent the 'hardest logical step taken' during the solve. A solve of a 0 will never take as long as a solve of a 1.3.3, but comparing how long it takes my rating solver to solve a 1.2.3 and a 1.3.2, you will get mixed results.

I havent tested whether rotations affected my solver, but any impact should be extremly minor as during a 'rating' solve as opposed to a 'fast' solve, I ensure that i've tried everything easier before trying anything harder. Also none of the operations my solver uses are affected by rotations, the only thing which may change is the order in which steps of the same difficulty are taken.

In my oppinion number of different ways to solve a puzzle is not as important as the 'hardest step', because at the point of the hardest step, there is only one way to go forwards, it is the part of the puzzle where you sit there stumped for ages before finally deriving some new logic to make progress.

However, my ratings are only a guide, as many(most?) 1.1.2's are not as simple to see as an xwing, but an xwing is a 1.1.2 step.

Lookahead 0 is no eliminations, only placements. If a cell has 1 possibility, its placed. If a row/column/box has 1 place for a given number, its placed. That is all. All other logical 'tricks' that I have seen are small subsets of lookahead 1. (except for locked tripples, which is lookahead 2)

dukuso · Posted: Sat Jul 23, 2005 7:11 am Post subject:

tilps · Posted: Sat Jul 23, 2005 1:56 pm Post subject:

My 'rating system' doesn't use backtracking, not in the traditional sense at least. Human solvers use the basic rules, and also use patterns or simple forcing chains, or similar. My system uses a limited lookahead to deduce what logic is available without bruteforcing every possible logic type that people have come up with. As a result, my system deduces logical solution paths, some of which are quite difficult from a players standpoint. A rought guide of how hard it is for a player is how far forwards they have to look from a given situation to realise a comon elimination, thats the second digit of my 3 digit scores. The third digit is what basis you have to start from. Other then 1.0.3, people pretty much only ever work out logical eliminations based off pairs. What complicates things is that within the concept of 'having to look 2 steps ahead', while that includes the swordfish, it also includes things alot harder to see. But reguardless, a player is more likely to see something 2 steps ahead then 3 steps ahead, on average. So the ratings do form somewhat of a guide as to the difficulty of a puzzle for a human solver.

dukuso · Posted: Sun Jul 24, 2005 7:52 am Post subject:

>My 'rating system' doesn't use backtracking,
>not in the traditional sense at least.
>Human solvers use the basic rules, and also
>use patterns or simple forcing chains, or similar.
>My system uses a limited lookahead to deduce what

it can no longer be limited, when the gridsize increases.
And we have no proof that it's limited with 9*9

>logic is available without bruteforcing every
>possible logic type that people have come up with.
>As a result, my system deduces logical solution paths,
>some of which are quite difficult from a players
>standpoint. A rought guide of how hard it is for
>a player is how far forwards they have to look
>from a given situation to realise a comon elimination,
>thats the second digit of my 3 digit scores.

even when the moves are forced ? I mean, suppose
there is a bifurcation and one way leads to a
contradiction after lots of forced moves -
the exact number depends on the order in which
you perform the forced moves. Does this number
of forced moves go into your scoring ?

>The third digit is what basis you have to start
>from. Other then 1.0.3, people pretty much only
>ever work out logical eliminations based off pairs.
>What complicates things is that within the concept
>of 'having to look 2 steps ahead', while that includes
>the swordfish, it also includes things alot harder
>to see. But reguardless, a player is more likely
>to see something 2 steps ahead then 3 steps ahead,
>on average.

depends on the other possible ideas in that position.
If that's the only chance to proceed, then he will
see it. If there are many other ideas, which don't
work but this is not easy to see, then the puzzle
is a lot harder for the human. Also in your score ?

>So the ratings do form somewhat of a
>guide as to the difficulty of a puzzle for a human solver.

OK. But it's subjective. Unlikely that another
programmer will come up with exactly the same rating.
Each newspaper and program will have its own rating.
And with larger gridsize your rating will be different
for puzzles which are just rotations or reflections
of each other.

dukuso · Posted: Sun Jul 24, 2005 8:02 am Post subject:

I implemented my 1-level-lookahead as desribed earlier.
Almost all puzzles can be solved with this.
I went through my old list of downloaded puzzles
and only found 4 which can't be solved by this
lookahead which is just :
try all bifurcations, fill in forced moves, if you come to a dead end,
choose the other way in the bifurcation as a semi-forced move.
Forced moves are only the immediate placements in a
row,column,cell,block - 4*81 possibilities to check -
as defined by the constraints of the exact-cover-problem.

Just 4 sudokus which couldn't be solved by this:

....3....
93..6.8..
56......4
..2.16...
85.47....
6...29..3
7.....21.
.........
.......59

..26.....
.9....4..
.1...9..7
....46..5
..4.9..8.
...71.3.4
8...31...
3..98....
...4...32

3...6...5
.2.....4.
..7...2..
...6.7...
9...8...6
...9.1...
..2...7..
.4.....1.
6...5...9

8.2.....4
.9......7
..5..139.
.8..17...
...5.2..1
.....8.36
..71.....
4...7....
32...5...

tilps · Posted: Sun Jul 24, 2005 8:47 am Post subject:

For interest sake i ran these through my rating solver.

dukuso · Posted: Sun Jul 24, 2005 9:06 am Post subject: