Solving Sudoku Using Object Oriented programming Java & Tree Data Structure

Solving Sudokus with Java and tree data structures

with one comment

A few weeks ago I published Java and tree data structures a post where I mentioned that I would try to put together some code to handle tree data structures… Well, this is the first installment of what I hope it will become a series of articles/code that will look into creating this tree library.

This first article/code is going to be about building trees dynamically. It is going to be illustrated by an example on how to use dynamic tree building to find the solution for a Sudoku. All the source code is available for downloading in a SVN repository, the URLs are:

Tree source code: https://subversion.assembla.com/svn/making-good-software/trunk/mgsTrees
Sudoku source code: https://subversion.assembla.com/svn/making-good-software/trunk/mgsSudoku
Dynamic tree building to find a solution

One widely used technique in computer science is to use a tree data structure to find the solution for something that needs to be solved but which solution is not obvious and requires many steps. One example could be chess, or a puzzle, a crossword, or like in this case, a sudoku.

The premise is simple, given an initial state, start building a tree of developed states from this original step until we find the state we were looking for. In the specific case of a sudoku, start building a tree where the branches are the different valid developments for that sudoku and stop when we find the solution.

The key element for building a tree dynamically is recursivity, starting from the original state, we find what the next candidate are, and them we do the same with each of them. In the mgsTrees library this can be easily accomplished by implementing an interface:
view plaincopy to clipboardprint?

1. public interface ExpandTreeStrategy {
2. public ExpandAction expand (T toExpand);
3. }

public interface ExpandTreeStrategy {
public ExpandAction expand (T toExpand);
}

The return type of the ExpandTreeStrategy is an ExpandAction. An ExpandAction has 3 flavors.

* stopBranch: It signals that this node is not expandable. In the Sudoku solver this is used when an ilegal Sudoku is reached.
* stopTree: It signals that is not necessary to keep building the tree. In the sudoku solver this is used when the solution is found.
* continueWith: This is used to specify what are the next states to look at. In the sudoku solver this is used when a intermediate sudoku is reached to specify what the next candidates are.

This is how to create the ExpandTreeStrategy Implementation for the Sudoku solver.
view plaincopy to clipboardprint?

1. public class ExpandSudokuLookingForSolutionStrategy implements ExpandTreeStrategy {
2. private final SudokuAnaliser sudokuAnaliser;
3.
4. public ExpandSudokuLookingForSolutionStrategy(SudokuAnaliser sudokuAnaliser) {
5. this.sudokuAnaliser = sudokuAnaliser;
6. }
7.
8. @Override
9. public ExpandAction expand(Sudoku toExpand) {
10. SudokuAnalysis sudokuAnalysis = sudokuAnaliser.analise(toExpand) ;
11.
12. if (sudokuAnalysis.isSolved()) return ExpandAction.stopTree ();
13. if (! sudokuAnalysis.isLegal()) return ExpandAction.stopBranch ();
14.
15. if (sudokuAnalysis.hasDirectSolutions()) {
16. return continueWithSudokuWithAllDirectSolutionsFilled(sudokuAnalysis);
17. } else if (sudokuAnalysis.hasNextCandidates()){
18. return continueWithSudokuVariantsForSquareLocationWithLessPossibleValues(sudokuAnalysis);
19. }else{
20. throw new RuntimeException("Is not possible to have a sudoku not solved, legal and without direct soluctions or candidates");
21. }
22. }
23.
24. private ExpandAction continueWithSudokuVariantsForSquareLocationWithLessPossibleValues(SudokuAnalysis sudokuAnalysis) {
25. List movements = sudokuAnalysis.getPossibleMovementsForSquareWithLessPossibleValues();
26. List nextSudokus = new ArrayList();
27. for (SudokuMovement movement : movements) {
28. nextSudokus.add(sudokuAnalysis.getSudoku().with(movement));
29. }
30. return ExpandAction.continueWith(nextSudokus);
31. }
32.
33. private ExpandAction continueWithSudokuWithAllDirectSolutionsFilled(SudokuAnalysis sudokuAnalysis) {
34. List movements = sudokuAnalysis.getAllDirectSolutionMovements();
35. return ExpandAction.continueWith(sudokuAnalysis.getSudoku().with(movements));
36. }
37. }

public class ExpandSudokuLookingForSolutionStrategy implements ExpandTreeStrategy {
private final SudokuAnaliser sudokuAnaliser;

public ExpandSudokuLookingForSolutionStrategy(SudokuAnaliser sudokuAnaliser) {
this.sudokuAnaliser = sudokuAnaliser;
}

@Override
public ExpandAction expand(Sudoku toExpand) {
SudokuAnalysis sudokuAnalysis = sudokuAnaliser.analise(toExpand) ;

if (sudokuAnalysis.isSolved()) return ExpandAction.stopTree ();
if (! sudokuAnalysis.isLegal()) return ExpandAction.stopBranch ();

if (sudokuAnalysis.hasDirectSolutions()) {
return continueWithSudokuWithAllDirectSolutionsFilled(sudokuAnalysis);
} else if (sudokuAnalysis.hasNextCandidates()){
return continueWithSudokuVariantsForSquareLocationWithLessPossibleValues(sudokuAnalysis);
}else{
throw new RuntimeException("Is not possible to have a sudoku not solved, legal and without direct soluctions or candidates");
}
}

private ExpandAction continueWithSudokuVariantsForSquareLocationWithLessPossibleValues(SudokuAnalysis sudokuAnalysis) {
List movements = sudokuAnalysis.getPossibleMovementsForSquareWithLessPossibleValues();
List nextSudokus = new ArrayList();
for (SudokuMovement movement : movements) {
nextSudokus.add(sudokuAnalysis.getSudoku().with(movement));
}
return ExpandAction.continueWith(nextSudokus);
}

private ExpandAction continueWithSudokuWithAllDirectSolutionsFilled(SudokuAnalysis sudokuAnalysis) {
List movements = sudokuAnalysis.getAllDirectSolutionMovements();
return ExpandAction.continueWith(sudokuAnalysis.getSudoku().with(movements));
}
}

At the end the entire tree building logic is wired in the TreeFactory class, which has a method, buildTree, that takes the starting point for the tree, and which constructor takes the ExpandStrategy to be used to build the tree. The result of this call is a TreeResult, which contains three main methods;

* getTree(): The resulting tree
* isBuildInterrupted(): Will tell you if the build is interrupted, in the case of the SudokuSolver this would mean that the solution was found.
* getLastBranch(): A sequential ordered list of all the last branch nodes startging from the root node, the original node. In the case of the sudoku solver this is used to retrieve in case that the solution is found (isBuildInterrupted == true) the sequence of Sudokus from the original one to the solution.

view plaincopy to clipboardprint?

1. public class TreeFactory {
2. private final ExpandTreeStrategy expandTreeStrategy;
3.
4. public TreeFactory(ExpandTreeStrategy expandTreeStrategy) {
5. this.expandTreeStrategy = expandTreeStrategy;
6. }
7.
8. public TreeResult buildTree (T seed){
9. System.out.println(seed);
10. ExpandAction expandActionResult = expandTreeStrategy.expand (seed);
11. if (expandActionResult.isStopBranch ()) return TreeResult.stopBranch (seed);
12. if (expandActionResult.isStopTree ()) return TreeResult.stopTree (seed);
13.
14. Node rootNode = new Node (seed);
15. List> currentBranch = new ArrayList>();
16. currentBranch.add(rootNode);
17.
18. Iterator childIterator = expandActionResult.getChildIterator();
19. TreeResult lastSubTreeResult = null;
20. while (childIterator.hasNext()){
21. Node next = new Node (childIterator.next());
22. lastSubTreeResult = buildTree(next.getContent());
23. rootNode.addChild(lastSubTreeResult.getTree().getRootNode());
24. if (lastSubTreeResult.isBuildInterrupted()) {
25. currentBranch.addAll(lastSubTreeResult.getLastNodeBranch());
26. return TreeResult.interrupt (rootNode, currentBranch);
27. }
28. }
29.
30. currentBranch.addAll(lastSubTreeResult.getLastNodeBranch());
31. return TreeResult.buildCompleted (rootNode, currentBranch);
32. }
33. }

public class TreeFactory {
private final ExpandTreeStrategy expandTreeStrategy;

public TreeFactory(ExpandTreeStrategy expandTreeStrategy) {
this.expandTreeStrategy = expandTreeStrategy;
}

public TreeResult buildTree (T seed){
System.out.println(seed);
ExpandAction expandActionResult = expandTreeStrategy.expand (seed);
if (expandActionResult.isStopBranch ()) return TreeResult.stopBranch (seed);
if (expandActionResult.isStopTree ()) return TreeResult.stopTree (seed);

Node rootNode = new Node (seed);
List> currentBranch = new ArrayList>();
currentBranch.add(rootNode);

Iterator childIterator = expandActionResult.getChildIterator();
TreeResult lastSubTreeResult = null;
while (childIterator.hasNext()){
Node next = new Node (childIterator.next());
lastSubTreeResult = buildTree(next.getContent());
rootNode.addChild(lastSubTreeResult.getTree().getRootNode());
if (lastSubTreeResult.isBuildInterrupted()) {
currentBranch.addAll(lastSubTreeResult.getLastNodeBranch());
return TreeResult.interrupt (rootNode, currentBranch);
}
}

currentBranch.addAll(lastSubTreeResult.getLastNodeBranch());
return TreeResult.buildCompleted (rootNode, currentBranch);
}
}

The final code to solve any given Sudoku will look like:
view plaincopy to clipboardprint?

1. public static void main(String[] args) {
2. Sudoku sudoku = new Sudoku(
3. new SquareValue [][]{
4. {__, __, __, __, __, __, _6, __, __},
5. {__, __, _3, _7, __, __, __, __, _1},
6. {__, _8, __, _1, __, _6, _9, _4, __},
7.
8. {_7, __, __, _5, __, __, __, __, __},
9. {__, __, _5, __, _4, __, _8, __, __},
10. {__, __, __, __, __, _2, __, __, _7},
11.
12. {__, _2, _9, _6, __, _4, __, _3, __},
13. {_6, __, __, __, __, _8, _4, __, __},
14. {__, __, _4, __, __, __, __, __, __}
15. }
16. );
17.
18. IteratorStrategy rowNavigator = OneLineIteratorStrategy.horizontal();
19. IteratorStrategy columnNavigator = OneLineIteratorStrategy.vertical();
20. IteratorStrategy matrixNavigator = MatrixIteratorStrategy.instance();
21. SudokuProcessor sudokuProcessor = new SudokuProcessorImpl(rowNavigator, columnNavigator, matrixNavigator);
22. SudokuAnaliser sudokuAnaliser = new SudokuAnaliserImpl(sudokuProcessor );
23. ExpandTreeStrategy expandTreeStrategy = new ExpandSudokuLookingForSolutionStrategy(sudokuAnaliser);
24. TreeFactory treeFactory = new TreeFactory(expandTreeStrategy);
25.
26. TreeResult buildTree = treeFactory.buildTree(sudoku);
27. List lastBranch = buildTree.getLastBranch();
28. System.out.println("Solution: " + lastBranch.get(lastBranch.size()-1));
29. }

Source
Tree :https://subversion.assembla.com/svn/making-good-software/trunk/mgsTrees
Sudoku:https://subversion.assembla.com/svn/making-good-software/trunk/mgsSudoku