#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: |
-------------------------+--------------------------------------------------
Changes (by newvalueoldvalue):
* author: => Rob Beezer, Tom Boothby
Comment:
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.
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/3084#comment:3>
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
-~----------~----~----~----~------~----~------~--~---
