com.eriksilkensen.sudoku
Class BackTrackingStrategy
java.lang.Object
com.eriksilkensen.sudoku.SolvingStrategy
com.eriksilkensen.sudoku.BackTrackingStrategy
public class BackTrackingStrategy
- extends SolvingStrategy
SolvingStrategy that solves Sudoku Boards by recursively tracking
through the Cells and trying numbers 1 - 9 until it finds out a
Cell has been placed incorrectly - in which case it 'backtracks'
until a correct one has been found.
This SolvingStrategy is sufficiently efficient to be used in-game
"on-the-fly" to solve Boards. It's average speed has been clocked
at 4.88 milliseconds per Board on a 3.0GHz Pentium 4 processor.
This rounds to solving roughly 205 Boards per second.
This Strategy hasn't been optimized for optimal performance. It just
guesses until it finally 'gets it right', which could mean sometimes over
100,000 runs. This could be cut down significantly by allowing the program
to make an "educated guess"... but the end result isn't worth the trouble.
- Since:
- 1.0
- Version:
- 02/13/07
- Author:
- Erik Silkensen
|
Method Summary |
Board |
solve(Board board)
Implented from SolvingStrategy, solves the specified Board |
| Methods inherited from class java.lang.Object |
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait |
BackTrackingStrategy
public BackTrackingStrategy()
solve
public Board solve(Board board)
- Implented from SolvingStrategy, solves the specified Board