## Solving Sudokus with Java and tree data structures

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:

public interface ExpandTreeStrategy<T> { public ExpandAction<T> 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.

public class ExpandSudokuLookingForSolutionStrategy implements ExpandTreeStrategy<Sudoku> { private final SudokuAnaliser sudokuAnaliser; public ExpandSudokuLookingForSolutionStrategy(SudokuAnaliser sudokuAnaliser) { this.sudokuAnaliser = sudokuAnaliser; } @Override public ExpandAction<Sudoku> 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<Sudoku> continueWithSudokuVariantsForSquareLocationWithLessPossibleValues(SudokuAnalysis sudokuAnalysis) { List<SudokuMovement> movements = sudokuAnalysis.getPossibleMovementsForSquareWithLessPossibleValues(); List <Sudoku> nextSudokus = new ArrayList<Sudoku>(); for (SudokuMovement movement : movements) { nextSudokus.add(sudokuAnalysis.getSudoku().with(movement)); } return ExpandAction.continueWith(nextSudokus); } private ExpandAction<Sudoku> continueWithSudokuWithAllDirectSolutionsFilled(SudokuAnalysis sudokuAnalysis) { List<SudokuMovement> 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.

public class TreeFactory<T> { private final ExpandTreeStrategy<T> expandTreeStrategy; public TreeFactory(ExpandTreeStrategy<T> expandTreeStrategy) { this.expandTreeStrategy = expandTreeStrategy; } public TreeResult<T> buildTree (T seed){ System.out.println(seed); ExpandAction<T> expandActionResult = expandTreeStrategy.expand (seed); if (expandActionResult.isStopBranch ()) return TreeResult.stopBranch (seed); if (expandActionResult.isStopTree ()) return TreeResult.stopTree (seed); Node<T> rootNode = new Node<T> (seed); List<Node<T>> currentBranch = new ArrayList<Node<T>>(); currentBranch.add(rootNode); Iterator<T> childIterator = expandActionResult.getChildIterator(); TreeResult<T> lastSubTreeResult = null; while (childIterator.hasNext()){ Node<T> next = new Node<T> (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:

public static void main(String[] args) { Sudoku sudoku = new Sudoku( new SquareValue [][]{ {__, __, __, __, __, __, _6, __, __}, {__, __, _3, _7, __, __, __, __, _1}, {__, _8, __, _1, __, _6, _9, _4, __}, {_7, __, __, _5, __, __, __, __, __}, {__, __, _5, __, _4, __, _8, __, __}, {__, __, __, __, __, _2, __, __, _7}, {__, _2, _9, _6, __, _4, __, _3, __}, {_6, __, __, __, __, _8, _4, __, __}, {__, __, _4, __, __, __, __, __, __} } ); IteratorStrategy rowNavigator = OneLineIteratorStrategy.horizontal(); IteratorStrategy columnNavigator = OneLineIteratorStrategy.vertical(); IteratorStrategy matrixNavigator = MatrixIteratorStrategy.instance(); SudokuProcessor sudokuProcessor = new SudokuProcessorImpl(rowNavigator, columnNavigator, matrixNavigator); SudokuAnaliser sudokuAnaliser = new SudokuAnaliserImpl(sudokuProcessor ); ExpandTreeStrategy<Sudoku> expandTreeStrategy = new ExpandSudokuLookingForSolutionStrategy(sudokuAnaliser); TreeFactory<Sudoku> treeFactory = new TreeFactory<Sudoku>(expandTreeStrategy); TreeResult<Sudoku> buildTree = treeFactory.buildTree(sudoku); List<Sudoku> lastBranch = buildTree.getLastBranch(); System.out.println("Solution: " + lastBranch.get(lastBranch.size()-1)); }

[…] Solving Sudokus with Java and tree data structures | Making Good Software (tags: java sudoku) […]

links for 2011-03-26 « pabloidz26 Mar 11 at 5:02 am