com.eriksilkensen.sudoku
Class BackTrackingStrategy

java.lang.Object
  extended by com.eriksilkensen.sudoku.SolvingStrategy
      extended by 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

Constructor Summary
BackTrackingStrategy()
           
 
Method Summary
 Board solve(Board board)
          Implented from SolvingStrategy, solves the specified Board
 
Methods inherited from class com.eriksilkensen.sudoku.SolvingStrategy
isLegalBoard, isLegalCell
 
Methods inherited from class java.lang.Object
clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait
 

Constructor Detail

BackTrackingStrategy

public BackTrackingStrategy()
Method Detail

solve

public Board solve(Board board)
Implented from SolvingStrategy, solves the specified Board