Implement a backtracking algorithmus to solve Sudokus

degree of difficulty: 1

Sudoku is a mathematical puzzle based on a 9 x 9 matrix. This matrix is subdivided into 3 x 3 submatrices. The aim of the game is to complete a partial filled matrix with numbers from 1 to 9 such that every number occurs exactly once in every row, column und 3 x 3 submatrix. With backtracking all combinations can be systematically found.

To decide efficiently whether a new number is allowed to place in a field, you should think of an data structure with which for a given row r and column c the nubmer z can be placed into the field or not. This data structure is similiar to the one used for the eight queens problem.

Solution

Generate new random Sudokus

degree of difficulty: 2

Before solving this Java programming exercises you should have finished the Java backtracking algorithm to solve Sudokus.

You can create new Sudoku puzzles by inserting n random numbers in the range from 1 - 9 and checking for each new number, whether the rules of the game still apply or not. After that, you can call the backtracking algorithm to solve the new Sudoku: if a solution have been found, your Java programm has created a new Sudoku puzzle; if not, you start the whole process again.

This method is able to create new Sudoku puzzles with a certain probability 0 < p < 1. It is unlikly, but possible, that your algorithm never terminates. But when it terminates, the result is always correct. Such algorithms based on randomize creation of problem solutions are called .

Add a Java method that creates new Sudoku puzzles with n numbers to the existing backtracking algorithm.

Solution

Solve English peg solitaire with backtracking

Simple wood version of English peg solitaire with start position.

degree of difficulty: 1

English peg solitare is a puzzle where the board has the form of a cross. It consists of 32 fields. 31 of these fields contain a peg. The single field in the middle of the board is empty. (We mark a peg with X and an empty field with O in the following examples)

The rules of this game a simple:

At the start there are only a few possible moves, but the choices are increasing during the game.

The following tables give the initial position of the pegs and subsequent moves.

XXX
XXX
XXXXXXX
XXXOXXX
XXXXXXX
XXX
XXX
-->
XXX
XXX
XXXXXXX
XOOXXXX
XXXXXXX
XXX
XXX
-->
XXX
XXX
XXXXXXX
XOXXXXX
XXOXXXX
OXX
XXX
-->
XXX
XXX
XXXXXXX
XOXXXXX
XXXOOXX
OXX
XXX
more moves ... -->
OOO
OOO
OOOOOOO
OOOXOOO
OOOOOOO
OOO
OOO

Implement a recusive backtracking algorithm in Java, that finds a solution to this puzzle. The solution can be stored as a sequence of boards: one for each move. The board should be implemented as a Java class with an internal 7x7 matrix. In the backtracking algorithm you must compute all possible jumps for a given situation.

With a 2.2 Ghz Athlon 64 I found a solution within 200 ms. Without heuristics or optimizations to the code. A solution can be found with brute-force.

Solution