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   

Fastest computer aided solving

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku
View previous topic :: View next topic  
Author Message
Puzzler

Joined: 04 May 2009
Posts: 36
:

Items
PostPosted: Sat Feb 06, 2010 8:09 pm    Post subject: Fastest computer aided solving Reply with quote

Out of curiosity Iíve been gathering statistics on how long it takes me to solve complex Sudoku puzzles using Starfish Sudoku.

My results are:

Rating ......... Average time to solve
Easy ......... 24 seconds
Medium ......... 1 Minute 31 seconds
Hard ......... 2 minutes 35 seconds
Diabolical ......... 4 minutes 12 seconds
Evil ......... 4 minutes 36 seconds


Not that Sudoku puzzling needs to be a race, but Iím curious how other computer-assisted solvers fare.

The challenge Iíd like to propose is for programmers to produce a solver that assists a human to solve a Sudoku in the shortest possible time.

I established the difficulty ratings as follows:

Technique difficulty
The highest order technique needed to solve the puzzle

1......Naked Singles
2......Hidden Singles
3......Naked Pairs
4......Pointing Rows and Pointing Columns
5......Naked Triples
6......Claiming Candidates
7......Naked Quads
8......Hidden Pairs
9......X-Wing
10....XY Wing, Type 1 and 2
11....XYZ Wing
12....Unique Rectangle
13....Hidden Triples
14....Swordfish (2 x 3 and 3 x 3)
15....Simple Color Trap
16....Simple Color Collision
17....Multiple Colors
18....Jellyfish
19.... X-Color Trap
20....Hidden Quads

Puzzle Difficulty
Having determined the highest technique used in the solving of each puzzle, the puzzles are then grouped as follows:

Rating......... Technique Difficulty Range
Easy ......... 1-4
Medium ......... 5-8
Hard ......... 9-12
Diabolical ......... 13-17
Evil ......... 17+

The rules are:

1. The solver can provide filtering that allows the player to determine patterns, but cannot provide specific hints.
2. The solver can only Autoplay Naked Singles and Hidden Singles. These patterns are so simple, it can be assumed that no skill is required to find them.
3. Solve time only counts if the player has made no mistakes during play

Go!

Very Happy[url][/url]
Back to top
View user's profile Send private message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Fri Feb 12, 2010 5:26 pm    Post subject: Reply with quote

I'm sorry to say Puzzler that you started this race very very late .....

Most of the work & programming regarding human assisted solvers with the techniques you mention has been done & dusted years ago....

Is this a spam attempt? .... I see several of your postes over many forums with 0 responses Idea

tarek
Back to top
View user's profile Send private message
Puzzler

Joined: 04 May 2009
Posts: 36
:

Items
PostPosted: Fri Feb 12, 2010 6:47 pm    Post subject: Not spam at all! Reply with quote

Hi Tarek

This is not spam at all. There is little activity on these forums and certainly no benefit to me for spamming. I'm proud of the player I've developed and would like others to enjoy it. I thought the point of these forums was to share ones ideas? Perhaps I was mistaken.

All of the techniques implemented in Starfish Sudoku were developed by much smarter people that me, and I'm very grateful for their work and for them sharing their work. For example AngusJ's Simple Sudoku was a major inpiration for me and it's to his credit that I've built upon his work.

Late to the game or not, I don't feel we should ever stop trying to improve playability and the fun factor.

Starfish Sudoku implements filtering in a way I believe to be unique (at least I haven't seen any solver do it this way). As a result, I have learned that it is possible to solve very complex Sudokus very quickly, by letting the computer do the work of identifying the conjugate chaind and the human see the patterns. It's also a heck of a lot of fun and I find myself playing far too often!

I'd would be very interested in seeing other implementations, so do please send me a link to you solver if you have one. I always enjoy learning, and it pleases me to be able to complement anothers work too.

Regards

Puzzler
Back to top
View user's profile Send private message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Sat Feb 13, 2010 2:32 pm    Post subject: Re: Not spam at all! Reply with quote

Puzzler wrote:
Hi Tarek

This is not spam at all. There is little activity on these forums and certainly no benefit to me for spamming.
This inactivity for such a long period was the reason behind my query. You've cleared it now & I hope you weren't offended.

Could you post a representative puzzle for each difficulty level with your solvers time next to it.

This would allow better comparison.

tarek
Back to top
View user's profile Send private message
Puzzler

Joined: 04 May 2009
Posts: 36
:

Items
PostPosted: Tue Feb 16, 2010 2:27 am    Post subject: Solve times Reply with quote

Hi Tarek

Thank you for your comments. I must admit I was hoping to generate some interest and was a bit disappointed that no-one has responded, but showing off a solver in this forum is a bit like taking coals to Newcastle, so I can understand that people are more interested in the programming aspect than playing.

I liked your suggestion so here are some results. The puzzles were randomly selected from the database of about 29,000.

The times are for a computer assisted human (me!)

Easy - 14 seconds
010200093000040000000510000090080000800050006630000087008029000307000000500100060
This is a bit misleading because all I had to do was find one naked single and the solver autoplayed the rest of the naked & hidden singles.

Medium Ė 1:31
050600000020000010000000008000200450100000600300700000800000003000005700000010000
Lotís of pointing rows, a unique rectangle and naked triples.

Hard Ė 2:01
000000805020300000000000100740000020005080000000001000300240000001000600000500000
An x-wing and several xy-wings

Diabolical - 5:42
002076000010000800000000000247000000000000930600000000450100000000000072000500000
Unique rectangle, several simple color traps

Evil - 03:19
004008060080020000000001040030900170905700430000060000007000300001090000400300010
Simple color collision, unique rectangle

Evil - 07:38
205006000000071005007500060000000016506000903870000000030007400400390000000800301
Four multi-color traps, yuck!

Evil Ė 3:35
200300000040000500000106000000070405300080000100000000050420000600000010000000000
Four simple color traps and a multi-color trap


The following puzzles donít count because I had to take a gimme to solve them, but they were still fun.

Unsolvable 3:38
630200000000000071000000000001087040000040000000000600200600300507000000040000000
Simple color trap, 1 gimme.

Unsolvable 4:46
600070000000000504000000300000105000000400200200000060054300000000060020000000008
Multi-color trap, x-color trap and 1 gimme

Tareksí Pearly 6000
At least four Gimmeís per puzzle! You should be had up for cruelty to dumb animals


Very Happy
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Wed Feb 17, 2010 3:53 pm    Post subject: Reply with quote

Puzzler wrote:

    Medium
    [ 17 clues ]
Code:

050600000020000010000000008000200450100000600300700000800000003000005700000010000


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


Lots of pointing rows,
a unique rectangle
and naked triples.

one "hidden" duo solves it
Back to top
View user's profile Send private message Visit poster's website
Puzzler

Joined: 04 May 2009
Posts: 36
:

Items
PostPosted: Thu Feb 18, 2010 2:19 am    Post subject: Reply with quote

Pat wrote:

one "hidden" duo solves it


Cool! I'll check that out.

I have to say I'm not much of a one for the "hidden" tuples.

I just can never see them!

Cheers
Back to top
View user's profile Send private message
tarek

Joined: 31 Dec 2005
Posts: 153
:
Location: London, UK

Items
PostPosted: Thu Feb 18, 2010 9:03 am    Post subject: Reply with quote

I haven't had the chance to compare with my solver yet ....

Your method heirarchy is slightly strange .....

in a breadth first Human assisted solving you would want to rank some methods differently ...

As suggested by Pat ... the hidden double is one of the easiest to spot ....

How could you spot naked quad before a hidden double is beyond me Shocked

tarek
Back to top
View user's profile Send private message
Puzzler

Joined: 04 May 2009
Posts: 36
:

Items
PostPosted: Fri Feb 19, 2010 10:10 pm    Post subject: Reply with quote

tarek wrote:
I haven't had the chance to compare with my solver yet ....

Your method heirarchy is slightly strange .....

in a breadth first Human assisted solving you would want to rank some methods differently ...

As suggested by Pat ... the hidden double is one of the easiest to spot ....

How could you spot naked quad before a hidden double is beyond me Shocked

tarek


Hmm. I looked at the puzzle again the way I would normally solve it, and I guess it's just habit that I always start by filtering for each candidate -1 then 2, etc. I dealt with a series of pointing rows/columns, and let the autosolver ripple through the naked and hidden singles. I completed it in 1:27, so my time was pretty consistent

I then looked at it again and opted to deal with the hidden pair "25" in column 3. Again, I let the autosolver do the grunt work of dealing with naked and hidden singles. It really didn't get me much further ahead as it ended up taking 2:05 to solve.

I tried again, (cheating by using a hint to look for hidden pairs as I went along) and even then my time was 2:17, so this is a slower method for me. Actually, without the hint I'd have taken ages longer because I'm hopeless at spotting hiddens. How do you guys spot them so fast? Exclamation

On the question about finding naked quads, I have a filter that looks for naked tuples (pairs, trips and quads), and once it brings them up it's pretty straightfoward to see the patterns and deal with the eliminations. (They're either true nakeds, unique rectangles, x-wings, xy-wings or xyz-wings)

You've both commented that hidden pairs are the easiest way to solve this puzzle, so I'm very interested in learning more, because I'm obviously missing something crucial here.

Cheers

Puzzler
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Sun Feb 21, 2010 8:13 am    Post subject: Reply with quote

Puzzler wrote:
I have to say I'm not much of a one for the "hidden" tuples.

I just can never see them!
    you're using the software to do all "hidden singles"

      this saves you a lot of boring work

        but --
        you never get practice with "hidden singles",
        so how do you expect to find "hidden" duos?
Back to top
View user's profile Send private message Visit poster's website
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Sun Feb 21, 2010 8:18 am    Post subject: Reply with quote

Puzzler wrote:
I then looked at it again and opted to deal with the hidden pair "25" in column 3

just to clarify,
after "hidden singles"
there is nothing interesting in column 3
-- the "hidden" duo in row 7 solves the puzzle
Back to top
View user's profile Send private message Visit poster's website
Puzzler

Joined: 04 May 2009
Posts: 36
:

Items
PostPosted: Sun Feb 21, 2010 10:42 pm    Post subject: Reply with quote

Pat wrote:
Puzzler wrote:
I then looked at it again and opted to deal with the hidden pair "25" in column 3

just to clarify,
after "hidden singles"
there is nothing interesting in column 3
-- the "hidden" duo in row 7 solves the puzzle


Ok, you're making feel dumb now Very Happy

I can see a hidden single 3 in R5C8. When I resolve this, the only hidden pair I can see is 25 in R56C3.

I can't see a hidden pair in row 7. Are we doing the same puzzle? Confused

I take your point that I use software to find hidden singles.

I'm quite a visual person so I play Sudoku by looking for patterns in highlighted subsets of the data, and I don't really pay as much attention to the candidate values themselves. For example highlighting all candidate n's makes it very easy to spot hidden singles, pointing rows, etc. It's why I particularly like the coloring techniques.

Finding hidden pairs means I'd need to actually pay attention to the candidate values Shocked

As my skill level has improved I'm able to spot more and more complex patterns, but of course I hit a ceiling eventually and need to move on to even more complex techniques. I'm trying to get my head around Nice Loops & Forcing chains right now, and it's giving me a headache!
Back to top
View user's profile Send private message
Pat

Joined: 06 Sep 2006
Posts: 128
:

Items
PostPosted: Tue Feb 23, 2010 7:25 am    Post subject: Reply with quote

Puzzler wrote:

I can see a hidden single 3 in R5C8. When I resolve this, the only hidden pair I can see is 25 in R56C3.

I can't see a hidden pair in row 7. Are we doing the same puzzle? Confused

    so you only do "hidden singles" in a box?

    there are plenty more "hidden singles"
    ( in a row or in a column )

    this should get you to 55 known cells

    at that point i know you will see a duo in row 7
    ( either a "hidden" duo or a "naked" duo -- whichever you prefer )


Puzzler wrote:
I'm hopeless at spotting hiddens.
How do you guys spot them so fast? Exclamation
    i solve on paper,
    even the "singles" i must manually find;
    therefore, my times will be much longer than any software-assisted times

      in any case, my times are not fast --
      i'm not entering any tournament

        personally, my interest is in finding the "easiest" path for any puzzle
        -- i've been known to fiddle with a puzzle after solving it,
        just to see if i can spot a simpler path
Back to top
View user's profile Send private message Visit poster's website
Display posts from previous:   
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Programming sudoku 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