From WikiZMSI

Graph search (sudoku, sliding puzzle)

Classroom

• Implement a class representing a sudoku board state. The class should be general i.e. allow for boards of aribitrary sizes n^2 x n^2 (typicallay: n = 3). Prepare methods allowing for: (1) converting a sudoku object to a string - toString(), (2) populating a 9 x 9 sudoku object from a string - fromString(...), (3) checking if a sudoku is legal (correct).

• Download the SaC library (including the user guide in English).

• Attach the SaC library under Eclipse (indicating the needed libraries - .jar files, attaching the javadoc documentation).

• Change the sudoku class so that it extends (inherits from) the class sac.graph.GraphStateImpl - implementation of the following methods will be then necessary: generateChildren(...), isSolution(...), hashCode() and attaching a heuristic function via the static method setHFunction(...).

• Experiments. Test the work of the Best-first-search algorithm for several exemplary sudokus (can be found in the internet). Display information about the algorithm at the stoppage time: number of states in Open and Closed states, duration times, number of solutions, etc. Check the influence of different configuration settings (GraphSearchConfigurator class). Make a sudoku harder by incrementally subtracting givens from the initial board (observe the growth of visited states until the moment when more than one unique solution is found). Generate all 4 x 4 sudokus.

Homework

• Write the program solving the "sliding puzzle (n^2 - 1)". Attention: please implement the puzzle state as a two-dimensional array (so that it differs from an existing implementation in the SaC library, where a one-dimensional array is used).

• In particular do the following: make your class extend the sac.graph.GraphStateImpl class, implement: generateChildren(...), isSolution(...), hashCode() methods.

• Implement as separate classes two heuristic functions: "misplaced tiles" and "Manhattan".

• Carry out a batch experiment to compare two heuristics, using 100 problems (puzzles) mixed randomly for n = 3. Indications: (1) "random" puzzles can be generated starting from a correctly arranged board and making 1000 random mixing moves, without a care about possible cancellation of opposing moves, but with a care about not counting empty moves at the borders; (2) for each fixed problem heuristics should be changed via the setHFunction(...) method on your sliding puzzle class. At each stoppage moment, measure the following quantities: number of states in Open and Closed sets, duration time, path length. As the final comparison, give averages of those quantities per each heuristics.

• On request, be able to quickly repeat the above experiment for the following settings: n = 4, 10 random puzzle generated via 30 mixing moves.