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:
Top 10000 Sudokus

 
Post new topic   Reply to topic    Sudoku Programmers Forum Index -> Puzzles
View previous topic :: View next topic  
Author Message
Ruud
Site Admin
Joined: 17 Sep 2005
Posts: 708
:
Location: Netherlands

Items
PostPosted: Fri Jun 22, 2007 11:09 pm    Post subject: Top 10000 Sudokus Reply with quote

There is a new collection that you can use to test your high-end solvers. The Top 10000 only contains Sudokus which SudoCue can only solve with tabling.

The failing techniques are:
- Singles
- Locked candidates
- Naked/Hidden subsets
- Fish, Finned Fish, Sashimi Fish
- Skyscraper, 2-string kite, Empty Rectangle
- Simple colors, Multi-colors
- Remote pairs
- XY-Wing, XYZ-Wing
- APE
- Sue-de-coq
- ALS-xz rule
- XY-chains
- 3D coloring w. weak interactions (AIC w/o embedded patterns)
- UR types 1-4
- BUG+1
- Nishio (single-digit patterns)

As usual, my puzzle collections are free for personal use.
_________________
Meet me at sudocue.net
Back to top
View user's profile Send private message Visit poster's website
whizter

Joined: 19 Jul 2007
Posts: 30
:

Items
PostPosted: Mon Aug 06, 2007 10:36 pm    Post subject: Reply with quote

My solver can solve 69 of these, and it only uses techniques that you mentioned.

Code:


69/10000 puzzles solved in 82.974205939 seconds. 9931 failures.

Methods used:

        2447x    Full House
        57522x   Hidden Single
        6988x    Naked Single
        5839x    Naked Pair
        29319x   Locked Candidates
        2869x    Naked Triple
        2429x    Hidden Pair
        321x     Hidden Triple
        721x     X-Wing
        546x     XY-Wing
        959x     XYZ-Wing
        197x     Swordfish
        2x       BUG+1
        1087x    XY-Chain
        11612x   3D Medusa
        23x      Naked Quad
        3x       Hidden Quad
        2x       Jellyfish
Back to top
View user's profile Send private message
gsf

Joined: 18 Aug 2005
Posts: 484
:
Location: NJ USA

Items
PostPosted: Tue Aug 07, 2007 4:49 am    Post subject: Reply with quote

with my solver:
5321 are solved with basic methods and XY cycles
another 4452 are solved with Y-knots (failed Y cycles aka contradiction chains using singles)
and 32 more are solved with rookery overlays (templates)
the remaining 195 require backtracking
Back to top
View user's profile Send private message Visit poster's website
a r n e

Joined: 27 Mar 2008
Posts: 9
:
Location: Norway

Items
PostPosted: Thu Mar 27, 2008 8:48 pm    Post subject: Reply with quote

Hi.

The SuDoKu-Cracker only tries to solve as fast as posible. Your Top 10000 are solved in 31 sec (30.907).

arne.
Back to top
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 484
:
Location: NJ USA

Items
PostPosted: Thu Mar 27, 2008 9:18 pm    Post subject: Reply with quote

a r n e wrote:

The SuDoKu-Cracker only tries to solve as fast as posible. Your Top 10000 are solved in 31 sec (30.907).

full featured solver all constraint methods enabled: ~10 puzzles/sec/Ghz
full featured solver limited to singles+backtracking: ~2400 puzzles/sec/Ghz
pure backtracking solver: ~6000 puzzles/sec/Ghz
Back to top
View user's profile Send private message Visit poster's website
a r n e

Joined: 27 Mar 2008
Posts: 9
:
Location: Norway

Items
PostPosted: Fri Mar 28, 2008 8:42 am    Post subject: Reply with quote

Thanks, you gave me an idea.

My Solver works fastest with full featured solver limited to singles + backtracking.

On an AMD Sempron; 548 MHz; Windows XP
It takes 10 sec (9.890) to solve this Top 10000
On a mixed (Easy to Expert) database, it takes 2.6 sec to solve 10000 puzzles.

arne.
Back to top
View user's profile Send private message Visit poster's website
gsf

Joined: 18 Aug 2005
Posts: 484
:
Location: NJ USA

Items
PostPosted: Fri Mar 28, 2008 2:04 pm    Post subject: Reply with quote

a r n e wrote:

My Solver works fastest with full featured solver limited to singles + backtracking.

On an AMD Sempron; 548 MHz; Windows XP
It takes 10 sec (9.890) to solve this Top 10000

that would be ~1800 puzzles/sec/Ghz
Back to top
View user's profile Send private message Visit poster's website
Sisophon2001

Joined: 05 Mar 2008
Posts: 32
:
Location: Cambodia

Items
PostPosted: Sun Mar 30, 2008 8:25 am    Post subject: Reply with quote

I am new to this level of Sudoku, although I have made a puzzle solver, and generator for the more basic methods. I am working at the moment on expanding my understanding of solving techniques.

Using the development code I am working on, my results more or less match Ruud's, and perhaps the others who responded. I did not implement tabling, and use forcing nets at the last stop before using backtracking.

1041 puzzles need backtracking and the rest are solvable only with forcing nets. I must assume (if my code does not have any bugs) that Ruud's implementation of tabling goes more than one step deep, so that it can investigate cases where there is more than one chain present. Forcing nets mirrors what I would do myself is stuck with a difficult puzzle, so I think this is useful to implement as it provides some information useful to the user.

Looking at whizter results I would think that his/hers implementation of 3D Medusa is picking up even more than my forcing net. 3DMedusa looks like it should covers almost everything, from what I read. What do others think?

gsf is using techniques not documented in the sudopedia - I checked his web site, and it would take much more time that I gave it to absorb the information provided - so I am not sure if these techniques are easy to learn for human solvers. If they are human solving techniques, then they look worth learning, judging by his results.

These are the techniques I currently implement,
- Singles
- Locked candidates
- Naked/Hidden subsets
- Fish, Finned Fish, Sashimi Fish
- XY-Wing, XYZ-Wing
- Sue-de-coq
- ALS-XZ rule ( in progress - still buggy so not used in tests)
- Forcing Chains
- XY-chains
- BUG+1 & BUG+2
- Nishio
- Forcing Net

Bifurcation is use internally for analysis, but not used as a solving technique.

I am printing the results to console, and redirecting to file, so this is not the best way to test for speed. My code with all test methods enabled is slow enough that I can have a shower while waiting for the results of 10,000 tests. I don't want to time it. I will worry about testing for speed when I understand the solving techniques.

I enjoyed the tests, and reading the replies.

Garvan
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
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