import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
class Position {
public final int x;
public final int y;
public Position(int x, int y) {
this.x = x;
this.y = y;
}
@Override
public boolean equals(Object o) {
if(!(o instanceof Position))
return false;
Position that = (Position)o;
if(this.x == that.x && this.y == that.y)
return true;
return false;
}
@Override
public int hashCode() {
return x*31 + y;
}
@Override
public String toString() {
return "[" + x + "," + y + "]";
}
}
public class PuzzleSolver <P,M> extends ConcurrentPuzzleSolver<P, M> {
private static final Set<Position> positions = new HashSet<>();
private static Random r = new Random();
private static int SIZE = 10;
private static final Position GOAL = new Position(SIZE/2, SIZE/2);
static {
for(int i = 0; i < SIZE; i++) {
for(int j = 0; j < SIZE; j ++) {
positions.add(new Position(i, j));
}
}
for(int i = 0; i < SIZE * SIZE/2; i++) {
positions.remove(new Position(r.nextInt(SIZE), r.nextInt(SIZE)));
}
}
public static void main(String[] args) {
Puzzle<Position, Position> p = new Puzzle<Position, Position>(){
@Override
public Position initialPosition() {
return new Position(0, 0);
}
@Override
public boolean isGoal(Position position) {
return position.equals(GOAL);
}
@Override
public Set<Position> legalMoves(Position position) {
Set<Position> adj = new HashSet<>();
for(int i = -1; i <= 1; i++) {
for(int j = -1; j <= 1; j++) {
if(i*j != 0)
continue;
Position p = new Position(position.x + i, position.y + j);
if(positions.contains(p)) {
adj.add(p);
}
}
}
return adj;
}
@Override
public Position move(Position position, Position move) {
return move;
}};
PuzzleSolver<Position, Position> ps = new PuzzleSolver<>(p);
try {
List<Position> solution = ps.solve();
System.out.println("puzzle board:");
System.out.println(positions);
System.out.println("goal: " + GOAL);
System.out.println("path from " + p.initialPosition() + " to goal: " + GOAL);
System.out.println(solution);
} catch (InterruptedException e) {
e.printStackTrace();
}
}
PuzzleSolver(Puzzle<P, M> puzzle) {
super(puzzle);
}
private final AtomicInteger taskCount = new AtomicInteger(0);
protected Runnable newTask(P p, M m, PuzzleNode<P, M> n) {
return new CountingSolverTask(p, m, n);
}
class CountingSolverTask extends SolverTask {
CountingSolverTask(P pos, M move, PuzzleNode<P, M> prev) {
super(pos, move, prev);
taskCount.incrementAndGet();
}
public void run() {
try {
super.run();
} finally {
if (taskCount.decrementAndGet() == 0)
solution.setValue(null);
}
}
}
}
interface Puzzle <P, M> {
P initialPosition();
boolean isGoal(P position);
Set<M> legalMoves(P position);
P move(P position, M move);
}
class SequentialPuzzleSolver <P, M> {
private final Puzzle<P, M> puzzle;
private final Set<P> seen = new HashSet<P>();
public SequentialPuzzleSolver(Puzzle<P, M> puzzle) {
this.puzzle = puzzle;
}
public List<M> solve() {
P pos = puzzle.initialPosition();
return search(new PuzzleNode<P, M>(pos, null, null));
}
private List<M> search(PuzzleNode<P, M> node) {
if (!seen.contains(node.pos)) {
seen.add(node.pos);
if (puzzle.isGoal(node.pos))
return node.asMoveList();
for (M move : puzzle.legalMoves(node.pos)) {
P pos = puzzle.move(node.pos, move);
PuzzleNode<P, M> child = new PuzzleNode<P, M>(pos, move, node);
List<M> result = search(child);
if (result != null)
return result;
}
}
return null;
}
}
class ConcurrentPuzzleSolver <P, M> {
private final Puzzle<P, M> puzzle;
private final ExecutorService exec;
private final ConcurrentMap<P, Boolean> seen;
protected final ValueLatch<PuzzleNode<P, M>> solution = new ValueLatch<PuzzleNode<P, M>>();
public ConcurrentPuzzleSolver(Puzzle<P, M> puzzle) {
this.puzzle = puzzle;
this.exec = initThreadPool();
this.seen = new ConcurrentHashMap<P, Boolean>();
if (exec instanceof ThreadPoolExecutor) {
ThreadPoolExecutor tpe = (ThreadPoolExecutor) exec;
tpe.setRejectedExecutionHandler(new ThreadPoolExecutor.DiscardPolicy());
}
}
private ExecutorService initThreadPool() {
return Executors.newCachedThreadPool();
}
public List<M> solve() throws InterruptedException {
try {
P p = puzzle.initialPosition();
exec.execute(newTask(p, null, null));
// block until solution found
PuzzleNode<P, M> solnPuzzleNode = solution.getValue();
return (solnPuzzleNode == null) ? null : solnPuzzleNode.asMoveList();
} finally {
exec.shutdown();
}
}
protected Runnable newTask(P p, M m, PuzzleNode<P, M> n) {
return new SolverTask(p, m, n);
}
protected class SolverTask extends PuzzleNode<P, M> implements Runnable {
SolverTask(P pos, M move, PuzzleNode<P, M> prev) {
super(pos, move, prev);
}
public void run() {
if (solution.isSet()
|| seen.putIfAbsent(pos, true) != null)
return; // already solved or seen this position
if (puzzle.isGoal(pos))
solution.setValue(this);
else
for (M m : puzzle.legalMoves(pos))
exec.execute(newTask(puzzle.move(pos, m), m, this));
}
}
}
class ValueLatch <T> {
private T value = null;
private final CountDownLatch done = new CountDownLatch(1);
public boolean isSet() {
return (done.getCount() == 0);
}
public synchronized void setValue(T newValue) {
if (!isSet()) {
value = newValue;
done.countDown();
}
}
public T getValue() throws InterruptedException {
done.await();
synchronized (this) {
return value;
}
}
}
class PuzzleNode <P, M> {
final P pos;
final M move;
final PuzzleNode<P, M> prev;
public PuzzleNode(P pos, M move, PuzzleNode<P, M> prev) {
this.pos = pos;
this.move = move;
this.prev = prev;
}
List<M> asMoveList() {
List<M> solution = new LinkedList<M>();
for (PuzzleNode<P, M> n = this; n.move != null; n = n.prev)
solution.add(0, n.move);
return solution;
}
}
The above example creates a set of positions in a square area with SIZE x SIZE, put the goal at the middle of the square. Then the program start the search at position [0,0], then finally reach the goal and returns the path.
