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.
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.
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.
|more moves ... -->||
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.