Ticket #3084 (closed enhancement: fixed)
[with patch, positive review] Solve Sudoku faster!
| Reported by: | boothby | Owned by: | cwitty |
|---|---|---|---|
| Priority: | trivial | Milestone: | sage-4.1 |
| Component: | misc | Keywords: | |
| Cc: | Work issues: | ||
| Report Upstream: | Reviewers: | Nick Alexander | |
| Authors: | Rob Beezer, Tom Boothby | Merged in: | sage-4.1.alpha0 |
| Dependencies: | Stopgaps: |
Description
I've got a faster Sudoku-solving class than what's currently in Sage.
Attachments
-
sudoku.patch
(4.6 KB) -
added by boothby 5 years ago.
-
trac_3084_sudoku_class.patch
(54.8 KB) -
added by rbeezer 4 years ago.
- Apply just this patch
Change History
comment:1 Changed 5 years ago by boothby
- Owner changed from mabshoff to cwitty
- Type changed from defect to enhancement
- Component changed from Cygwin to misc
comment:2 Changed 5 years ago by boothby
- Summary changed from Solve Sudoku faster! to [with patch, not ready] Solve Sudoku faster!
comment:3 Changed 4 years ago by rbeezer
- Summary changed from [with patch, not ready] Solve Sudoku faster! to [with patch, needs review] Solve Sudoku faster!
- Authors set to Rob Beezer, Tom Boothby
Current patch has a "sudoku puzzle" class, with tools for input/output of puzzles and two algorithms for finding solutions, including obtaining multiple solutions.
DLX algorithm by Tom Boothby consistently solves 9x9 hard puzzles at a rate of about 700 per second on modern, but not extravagant, hardware. Cythonized backtracking algorithm by Rob Beezer is more variable in performance, and can solve some hard puzzles at the rate of 4000 per second, though other problems can take close to a full second.
DLX will work on any size puzzle (array dimensions must be perfect squares), string format works on up to 36x36, backtracking works on up to 16x16 since memory is not allocated dynamically.
comment:4 follow-up: ↓ 5 Changed 4 years ago by 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.
comment:5 in reply to: ↑ 4 Changed 4 years ago by rbeezer
Replying to 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
comment:6 Changed 4 years ago by ncalexan
- Reviewers set to Nick Alexander
- Summary changed from [with patch, needs review] Solve Sudoku faster! to [with patch, positive review] Solve Sudoku faster!
This looks great, albeit with some long lines (in the algorithm description, not doctests). Apply!
On sage.math:
sage: %timeit sage.games.sudoku.Sudoku('5...8..49...5...3..673....115..........2.8..........187....415..3...2...49..5...3').solve().next()
1000 loops, best of 3: 1.37 ms per loop
sage: %timeit sage.games.sudoku.Sudoku('....1.9..8..4.....2.........7..3..........2.4.......58.6....13.7..2........8.....').solve().next()
1000 loops, best of 3: 1.48 ms per loop
sage: %timeit sage.games.sudoku.Sudoku('..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9').solve().next()1000 loops, best of 3: 1.48 ms per loop
