blob: 9b78f277f964c8d333fe4f90d78cd06f421cd705 (
plain) (
blame)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
|
import java.util.HashSet;
import java.util.PriorityQueue;
import java.util.Queue;
/**
* A class that implements a breadth-first search algorithm
* for finding the Configurations for which the isSolution predicate holds
*
* @author Pieter Koopman, Sjaak Smetsers
* @author Camil Staps, s4498062
*/
@SuppressWarnings("Convert2Diamond") // We disable these warnings for Java <=1.7 compatibility.
public class Solver
{
// A queue for maintaining graphs that are not visited yet.
private final Queue<Node<Configuration>> toExamine = new PriorityQueue<Node<Configuration>>();
private final HashSet<Configuration> examined = new HashSet<Configuration>();
private Node winner = null;
public Solver(Configuration g) {
toExamine.add(new Node(null, g));
}
/* A skeleton implementation of the solver
* @return a string representation of the solution
*/
public boolean solve () {
while (!toExamine.isEmpty()) {
Node next = toExamine.remove();
Configuration nextConfiguration = (Configuration) next.getItem();
examined.add(nextConfiguration);
if (nextConfiguration.isSolution()) {
winner = next;
return true;
} else {
for (Configuration succ: nextConfiguration.successors()) {
if (!examined.contains(succ)) {
toExamine.add(new Node(next, succ));
}
}
}
}
return false;
}
/**
* Return the winning Node (from which the path can be reconstructed)
* @return the node in which we found a solution
*/
public Node getWinner() {
return winner;
}
}
|
