﻿ Java Programming Exercises - Backtracking

## 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.

## Solve English peg solitaire with backtracking 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:

• you can take a peg and jump over another neighbouring peg
• the peg you jumped over is removed from the board
• you solved the puzzle if at the end only on peg exists and is located in the middle of the board

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.

 X X X X X X X X X X X X X X X X O X X X X X X X X X X X X X X X X
-->
 X X X X X X X X X X X X X X O O X X X X X X X X X X X X X X X X X
-->
 X X X X X X X X X X X X X X O X X X X X X X O X X X X O X X X X X
-->
 X X X X X X X X X X X X X X O X X X X X X X X O O X X O X X X X X
more moves ... -->
 O O O O O O O O O O O O O O O O X O O O O O O O O O O O O O O O O

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.