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   

NEWS:
One of my hardest grids

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Puzzles
View previous topic :: View next topic  
Author Message
patrick84

Joined: 07 Feb 2011
Posts: 5
:

Items
PostPosted: Tue Feb 08, 2011 10:45 am    Post subject: One of my hardest grids Reply with quote

Hi all,

Here's a grid which I suppose to be VERY VERY hard, but solvable with known technics (no hypothesis) :
000005070001070200870000006096300820000090000047100950380000005005030700000004030

What do you think about it ? and.. how much time your solvers take to find the solution ? (i'm not sure it's an english sentence..)
Back to top
View user's profile Send private message
JasonLion
Site Admin
Joined: 16 Nov 2008
Posts: 162
:
Location: Silver Spring, MD

Items
PostPosted: Tue Feb 08, 2011 12:57 pm    Post subject: Reply with quote

SudokuExplainer rates that puzzle at 7.2, with 10 forcing chains. That is reasonably difficult, but not hard by the standards around here (which are extreme).

My brute force solver can solve it in under 1/1000th of a second, while my logical solver takes 6/1000ths of a second.
Back to top
View user's profile Send private message
daj95376

Joined: 05 Feb 2006
Posts: 431
:

Items
PostPosted: Tue Feb 08, 2011 5:34 pm    Post subject: Reply with quote

Fun puzzle! Solution sans basics.

The (single/sole) generic chain is as close as it comes to difficult.

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


         finned Swordfish c347\r157      <> 4    r1c5


S-Wing: 3 strong inference using 2 values

(4)r3c5 = r4c5 - (4=1)r4c9 - r1c9 = (1)r3c8  =>  r3c5<>1; r3c8<>4


extended L-Wing: 4 strong inference using 2 values

{(2)r7c3 = r7c5 - r3c5 = (2-4)r3c4 = r5c4} - r5c7 = (4)r7c7  =>  r7c3<>4


 r12c14  <69> UR Type 2.2233             <> 8    r89c4,r1c5


generic chain:

(1=6)r1c5 - (6=8)r6c5 - r9c5 = r8c6 - r8c8 = (8-4)r2c8 = r2c9 - (4=1)r4c9  =>  r1c9<>1


take your pick (any one!): 3 strong inference using 2 values

M-Wing 6A (9=2)r8c4 - r7c5 = (2-9)r7c3 = (9)r9c3        =>  r9c4<>9
M-Wing 7A (9=2)r8c4 - r7c5 = (2-9)r7c3 = (9)r7c8        =>  r8c89<>9
M-Wing 7B (2=9)r9c3 - r9c4 = (9-2)r8c4 = (2)r8c9        =>  r9c9<>2

W-Wing    (9=2)r8c4 - r7c5 = r7c3 - (2=9)r9c3           =>  r9c4<>9
W-Wing    (9=2)r8c4 - r8c9 = r9c9 - (2=9)r9c3           =>  r9c4<>9

S-Wing    (2)r7c5 = r7c3 - (2=9)r9c3 - r9c4  = (9)r8c4  =>  r8c4<>2
S-Wing    (9)r8c4 = r9c4 - (9=2)r9c3 - r9c9  = (2)r8c9  =>  r8c4<>2; r8c9<>9

L-Wing    (9)r8c4 = r9c4  - r9c3 = (9-2)r7c3 = (2)r7c5  =>  r8c4<>2
L-Wing    (9)r8c4 = r8c89 - r7c8 = (9-2)r7c3 = (2)r7c5  =>  r8c4<>2

______________________________________________________________________________________
Back to top
View user's profile Send private message
patrick84

Joined: 07 Feb 2011
Posts: 5
:

Items
PostPosted: Mon Feb 14, 2011 10:19 am    Post subject: Reply with quote

wow

thanks for your replies !

JasonLion how is made your logical solver ? mine takes 1/2 second to solve it (and describe each step) !!
Back to top
View user's profile Send private message
JasonLion
Site Admin
Joined: 16 Nov 2008
Posts: 162
:
Location: Silver Spring, MD

Items
PostPosted: Mon Feb 14, 2011 1:00 pm    Post subject: Reply with quote

My logical solver has been heavily optimized for speed, using bit vectors stored as ints, and other similar techniques, to optimize each of the logical solving techniques. My code needs to work well on smartphones with slow processors, so I had to put a fair bit of effort into making the code fast.

For examples of how I optimize things, take a look at JSolve, my open source brute force solver.

Once you get into the right mind set, it is simply a matter of thinking about how to best apply fairly straightforward optimizations to each of the solving techniques. Applying optimizations to may different solving techniques can be tedious, but it isn't magical or even especially difficult. It is simply a matter of finding a way to look at things that minimizes the search space and maps efficiently into machine instructions.
Back to top
View user's profile Send private message
patrick84

Joined: 07 Feb 2011
Posts: 5
:

Items
PostPosted: Wed Feb 16, 2011 12:47 pm    Post subject: Reply with quote

Yep i've to make an effort with optimizations !

But making a good solver for a smartphone it's just amazing because there's no much memory and a very slow processor. Wow..
Back to top
View user's profile Send private message
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Puzzles All times are GMT
Page 1 of 1

 
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
FREE FORUM HOSTING by AtFreeForum. Terms of Service - Privacy Policy
FASHION ACCESSORIES - BLING BLING - LADIES WATCHES - KOREAN CHILDREN CLOTHING - ONLINE BARGAIN STORE - FASHION JEWELLERIES