Sudoku Programmers Forum Index

 
 FAQFAQ   SearchSearch   MemberlistMemberlist   UsergroupsUsergroups   RegisterRegister   ProfileProfile   Log inLog in          Games  Calendar

Log in to check your private messagesLog in to check your private messages   

Extreme difficulty puzzle
Goto page 1, 2, 3  Next
 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Puzzles
View previous topic :: View next topic  
Author Message
tilps

Joined: 19 Jun 2005
Posts: 44
:

Items
PostPosted: Wed Jul 20, 2005 6:55 am    Post subject: Extreme difficulty puzzle Reply with quote

Code:
..9..2...
.3..9....
.5.78...9
.4.3..2..
..72.85..
..1..5.6.
6...79.8.
....2..5.
...4..7..


This is the first 3x3 sudoku I have generated which my solver has rated as difficulty level 1.3. By contrast the rubylips '48-unwind' puzzle is a 1.2.

1.3 is 'kindof' equivelent to there being at least one case of something of the order of the jellyfish required to solve. 1.2 is swordfish level (except all the swordfish puzzles end up being rated 1.1, because my solver finds other 'easier' logic attacks to eliminate possibilities), 1.1 xwing, 1.0 trivial pair elimination.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Thu Jul 21, 2005 5:28 am    Post subject: Reply with quote

7 guesses, 472 placements.

This is when using the 4 standard checks :
forced placement in a row,column,block,cell.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Nick70

Joined: 08 Jun 2005
Posts: 160
:

Items
PostPosted: Thu Jul 21, 2005 9:40 am    Post subject: Reply with quote

6 double forcing chains and 1 triple forcing chain to reach the solution without guessing.
Back to top
View user's profile Send private message
tilps

Joined: 19 Jun 2005
Posts: 44
:

Items
PostPosted: Thu Jul 21, 2005 10:35 am    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
tilps

Joined: 19 Jun 2005
Posts: 44
:

Items
PostPosted: Thu Jul 21, 2005 10:50 am    Post subject: Reply with quote

Code:
..7..4...
..2...91.
.6..5...4
.3.62.1..
6...7...2
..1.85.6.
2...1..4.
.18...6..
...7..3..


a 1.3.2

1 lookahead, 3 logic steps, involving doubles.

Looking at the solution path it uses 1 lookahead 1 logicstep involving quadruples, along the way. But my rating system rates longer logic paths higher reguardless of number of chains required. Also said moves elimination may not have been used, since a higher rated move immediately followed it.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Fri Jul 22, 2005 11:45 am    Post subject: Reply with quote

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...
Back to top
View user's profile Send private message Send e-mail Visit poster's website
tilps

Joined: 19 Jun 2005
Posts: 44
:

Items
PostPosted: Fri Jul 22, 2005 1:41 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Fri Jul 22, 2005 2:40 pm    Post subject: Reply with quote

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 ?
Back to top
View user's profile Send private message Send e-mail Visit poster's website
tilps

Joined: 19 Jun 2005
Posts: 44
:

Items
PostPosted: Fri Jul 22, 2005 4:00 pm    Post subject: Reply with quote

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)
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sat Jul 23, 2005 7:11 am    Post subject: Reply with quote

tilps wrote:
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)



once you proceed to larger puzzles, backtracking will occur
much more often. Then "hardest step" and "running time"
should be almost the same. Rotations will only affect
the score, when there is backtracking and you pick
the "first" bifurcation from where to start the backtracking.
(there usually are many bifurcations at a given level)
This ordering changes by rotation and a bad choice here can
affect the score.

Your "hardest step" scoring is not so much how humans
would score hardness. (I prefer computer-hardness = solving
time) .
(1)Suppose you have a straight tree without branches,
now you add one branch of depth 1
(2) straight line with many branches of depth1 starting from it
They have equal score, although there are more chances to go wrong
in the 2nd case.



(1)-----------------------<___________________


(2)----<___<_______<____<__________<____
Back to top
View user's profile Send private message Send e-mail Visit poster's website
tilps

Joined: 19 Jun 2005
Posts: 44
:

Items
PostPosted: Sat Jul 23, 2005 1:56 pm    Post subject: Reply with quote

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.
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sun Jul 24, 2005 7:52 am    Post subject: Reply with quote

>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.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sun Jul 24, 2005 8:02 am    Post subject: Reply with quote

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...
Back to top
View user's profile Send private message Send e-mail Visit poster's website
tilps

Joined: 19 Jun 2005
Posts: 44
:

Items
PostPosted: Sun Jul 24, 2005 8:47 am    Post subject: Reply with quote

For interest sake i ran these through my rating solver.

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

1.0.2

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

1.2.2

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

1.2.3

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

1.1.3


To answer some questions from the previous post
Quote:
Does this number of forced moves go into your scoring ?

That is the second number. The second number is the greatest of the number of forced moves required on each branch on the branching point, to reach a common elimination. The third number is the number of branches on the branching point used.
Also, my solver does not reach contradictions, it doesnt try something to find out if it fails. It tries all sides of a branching point, to find out what common things they tell us about a puzzle. The xwing is an example of this. There is a branching point in the two options in a row for a number, in either of those cases, the second row contains the same number, in the opposite column. Therefore there are common eliminations of that number, in those columns, which arent in those rows.
The first number is the number of branching points you have to go through to generate the common eliminations. You'll note all the 3x3 puzzles my solver has ever seen (over 1million of them), all solve without increasing that number to 2.

Quote:
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 ?

In my limited experience as a sudoku player, i'm yet to see a puzzle where there arent always a huge number of ideas, which don't lead to any progress.

Quote:
And with larger gridsize your rating will be different for puzzles which are just rotations or reflections of each other.

I challenge you to find a pair of sudokus which are reflections/rotations/permutations which my solver wont rate identically. I would be very interested to see this happen.

Since we're here
1.6.3 - current hardest

Code:
..3|.5.|4..
7..|.6.|...
.5.|8..|.6.
-----------
5..|..3|..4
.1.|.7.|.8.
2..|4..|..7
-----------
.4.|..8|.5.
...|.4.|..9
..6|.1.|2..
Back to top
View user's profile Send private message
dukuso

Joined: 14 Jul 2005
Posts: 424
:
Location: germany

Items
PostPosted: Sun Jul 24, 2005 9:06 am    Post subject: Reply with quote

tilps wrote:
I challenge you to find a pair of sudokus which are reflections/rotations/permutations which my solver wont rate identically. I would be very interested to see this happen.

Since we're here
1.6.3 - current hardest

Code:
..3|.5.|4..
7..|.6.|...
.5.|8..|.6.
-----------
5..|..3|..4
.1.|.7.|.8.
2..|4..|..7
-----------
.4.|..8|.5.
...|.4.|..9
..6|.1.|2..



yes, this is also hard for my program. With the rotations,
can't you just try it randomly ? It often gives me big differences.
Back to top
View user's profile Send private message Send e-mail Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Puzzles All times are GMT
Goto page 1, 2, 3  Next
Page 1 of 3

 
Jump to:  
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
Sudoku Programmers topic RSS feed 


Powered by phpBB © 2001, 2005 phpBB Group

Igloo Theme Version 1.0 :: Created By: Andrew Charron