Java Solver

Strongly typed Java library that solves user defined problems with various graph search algorithms.

As an example, it can solve NPuzzle (Wikipedia) and NQueens (Wikipedia) out of the box.

Overview

To define your custom problem you must implement the Problem interface. For example implementations see NPuzzleProblem or NQueensProblem classes.

You also need to define a heuristic for that problem implementing the Heuristic interface. For example implementations see NPuzzleHeuristic or NQueensHeuristic classes.

Then you can try to find a solution for your problem using a built-in solver that can be instantiated using VisitFactory or SearchFactory classes.

Built-in algorithms

Here we describe the built-in search algorithms. Developers may add new algorithms by implementing the relative Java interface.

Visits

A Visit algorithm starts from an initial (user defined) problem configuration and explores the move graph to find the shortest path possible that brings from the initial configuration to a correct solution. Some visits are guaranteed to find an optimal path, while others sacrifice optimality for efficiency.

Implements the Visit interface.

built-in visits:

• A* (Wikipedia)
• Best First (Wikipedia)
• BFS (Wikipedia)
• Dijkstra (Wikipedia)

Searches

A Search algorithm starts from an initial problem configuration (usually randomly picked) and iteratively apply moves in order to get close to a solution. Only the found solution is returned, while the path that brings from the initial configuration to the solution is not of interest when using this kind of algorithms.

The correctness of the found solution is not guaranteed. If the search does not find a correct solution it returns a configuration that is as much close as possible to correctness.

Implements the Search interface.

built-in searches:

• Steepest Descent (Wikipedia)

Quick demo

The Main class can be used to quickly solve NPuzzle or NQueens problems.

You can quickly build an executable jar file using Maven.

mvn clean package

Then you'll find your executable jar file at target/epieffe-solver.jar.

NPuzzle demo

The executable jar file can easily solve NPuzzle problem instances using the Best First visit.

You need to pass an initial problem configuration to the executable jar file as a csv file path command line argument.

Some example NPuzzle initial configurations can be found in the examples folder.

java -jar target/epieffe-solver.jar npuzzle examples/npuzzle1.csv

NQueens demo

The jar file can also solve NQueens problem instances using the Steepest Descent search.

You need to pass the number of queens in the chess board as a command line argument.

java -jar target/epieffe-solver.jar nqueens 8

Import as dependency in your project

Obviously you can add the epieffe-solver.jar to the classpath. Then you can define your custom Problem and Heuristic and try to feed the built-in searches and visits with your custom problem.

If you are using Maven in your project you can easily add this library to the classpath as a Maven dependency.

First install this library in your local Maven repository:

mvn clean install

Then you can add this dependency in your project's pom.xml file.

<dependency>
    <groupId>epieffe</groupId>
    <artifactId>epieffe-solver</artifactId>
    <version>1.0.0</version>
</dependency>