#3084: [with patch, needs review] Solve Sudoku faster!
-------------------------+--------------------------------------------------
Reporter: boothby | Owner: cwitty
Type: enhancement | Status: new
Priority: trivial | Milestone: sage-4.0.2
Component: misc | Keywords:
Reviewer: | Author: Rob Beezer, Tom Boothby
Merged: |
-------------------------+--------------------------------------------------
Comment(by rbeezer):
Replying to [comment:4 mvngu]:
> If the patch results in better performance, there should be ("good")
code to illustrate this both before and after applying the patch. Such
information is good for release tours.
Minh,
Here you go.
Thanks,
Rob
{{{
Original doctest example
A =
'5...8..49...5...3..673....115..........2.8..........187....415..3...2...49..5...3'
A 17-hint puzzle (no 16-hint puzzles known)
B =
'....1.9..8..4.....2.........7..3..........2.4.......58.6....13.7..2........8.....'
Difficult for backtracking, Wikipedia's "worst case"
C =
'..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9'
Timings on 3 GHz Intel Core Duo, KUbuntu 8.10
4.0.1 = backtracking via recursive calls
DLX = Exact Cover, Dancing Links algorithm
BackTrack = Cythonized backtracking with propogation
4.0.1 Patch/DLX Patch/BT Factors
A 34 ms 1.11 ms 187 us 31x, 182x
B 1494 s 1.20 ms 441 ms 1245000x, 3388x
C 4798 s 1.21 ms 944 ms 4000000x, 5000x
}}}
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/3084#comment:5>
Sage <http://sagemath.org/>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--~--~---------~--~----~------------~-------~--~----~
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected]
To unsubscribe from this group, send email to
[email protected]
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en
-~----------~----~----~----~------~----~------~--~---
