View previous topic :: View next topic |
Author |
Message |
| Puzzler
| Joined: 04 May 2009 | Posts: 36 | : | | Items |
|
Posted: Sat Feb 06, 2010 8:09 pm Post subject: Fastest computer aided solving |
|
|
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!
[url][/url] |
|
Back to top |
|
|
| tarek
| Joined: 31 Dec 2005 | Posts: 153 | : | Location: London, UK | Items |
|
Posted: Fri Feb 12, 2010 5:26 pm Post subject: |
|
|
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
tarek |
|
Back to top |
|
|
| Puzzler
| Joined: 04 May 2009 | Posts: 36 | : | | Items |
|
Posted: Fri Feb 12, 2010 6:47 pm Post subject: Not spam at all! |
|
|
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 |
|
|
| tarek
| Joined: 31 Dec 2005 | Posts: 153 | : | Location: London, UK | Items |
|
Posted: Sat Feb 13, 2010 2:32 pm Post subject: Re: Not spam at all! |
|
|
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 |
|
|
| Puzzler
| Joined: 04 May 2009 | Posts: 36 | : | | Items |
|
Posted: Tue Feb 16, 2010 2:27 am Post subject: Solve times |
|
|
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
|
|
Back to top |
|
|
| Pat
| Joined: 06 Sep 2006 | Posts: 128 | : | | Items |
|
Posted: Wed Feb 17, 2010 3:53 pm Post subject: |
|
|
Puzzler wrote: | 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 |
|
|
| Puzzler
| Joined: 04 May 2009 | Posts: 36 | : | | Items |
|
Posted: Thu Feb 18, 2010 2:19 am Post subject: |
|
|
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 |
|
|
| tarek
| Joined: 31 Dec 2005 | Posts: 153 | : | Location: London, UK | Items |
|
Posted: Thu Feb 18, 2010 9:03 am Post subject: |
|
|
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
tarek |
|
Back to top |
|
|
| Puzzler
| Joined: 04 May 2009 | Posts: 36 | : | | Items |
|
Posted: Fri Feb 19, 2010 10:10 pm Post subject: |
|
|
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
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?
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 |
|
|
| Pat
| Joined: 06 Sep 2006 | Posts: 128 | : | | Items |
|
Posted: Sun Feb 21, 2010 8:13 am Post subject: |
|
|
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 |
|
|
| Pat
| Joined: 06 Sep 2006 | Posts: 128 | : | | Items |
|
Posted: Sun Feb 21, 2010 8:18 am Post subject: |
|
|
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 |
|
|
| Puzzler
| Joined: 04 May 2009 | Posts: 36 | : | | Items |
|
Posted: Sun Feb 21, 2010 10:42 pm Post subject: |
|
|
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
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?
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
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 |
|
|
| Pat
| Joined: 06 Sep 2006 | Posts: 128 | : | | Items |
|
Posted: Tue Feb 23, 2010 7:25 am Post subject: |
|
|
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?
|
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?
|
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 |
|
|
|