//copyright (C) 2007 Mocanu Cristian Romeo
package balls;
import java.util.Set;
import java.util.LinkedHashSet;
import java.util.Observable;
/**
* Describe class
<code>BallsSolver</code> here.
*
* @author <a
href="mailto:chrimeea@yahoo.com">Cristian Mocanu</a>
* @version 1.0
*/
public class BallsSolver extends Observable {
private int
totalBalls = 12;
private int
totalSteps = 3;
private boolean
strict = true;
private int stages
= 0;
public
BallsSolver() {
}
public
BallsSolver(int tb, int ts, boolean s) {
totalBalls
= tb;
totalSteps
= ts;
strict = s;
}
public int
getTotalStages() {
int n = 1;
for (int j
= 1; j < totalSteps - 1; j++) {
n += Math.pow(3, j);
}
return
(int) Math.pow(totalBalls / 2, n) * 2;
}
public
BallsSolution solve() {
BallsSolution
s = findSolutions(new Knowledge(totalBalls), totalSteps);
stages =
getTotalStages();
setChanged();
notifyObservers(stages);
return s;
}
private static
boolean isRedundant(Knowledge lightk, Knowledge heavyk, Knowledge equalk) {
boolean
ilegal_light = !lightk.isLegal();
boolean
ilegal_heavy = !heavyk.isLegal();
boolean
ilegal_equal = !equalk.isLegal();
return
(((ilegal_light && ilegal_heavy) ||
(ilegal_light && ilegal_equal) ||
(ilegal_heavy && ilegal_equal)));
}
private boolean
nextTransition(Transition t) {
int s =
t.getSize();
boolean r =
t.nextTransition();
int n;
if (r) {
n = t.getSize() - s;
} else {
n = (totalBalls / 2) - s;
}
if (n >
0) {
stages += n;
setChanged();
notifyObservers(stages);
}
return r;
}
private
BallsSolution findSolutions(Knowledge knowledge, int steps) {
if
(knowledge.isSolution()) {
return new BallsSolution(knowledge);
} else if
(steps == 0) {
return new BallsSolution();
}
Transition
transition = new Transition(knowledge);
Knowledge
lightk, heavyk, equalk;
do {
if (!nextTransition(transition)) {
return
new BallsSolution();
}
lightk =
knowledge.extractLightKnowledge(transition);
heavyk =
knowledge.extractHeavyKnowledge(transition);
equalk =
knowledge.extractEqualKnowledge(transition);
} while
(isRedundant(lightk, heavyk, equalk));
BallsSolution
sol = new BallsSolution(knowledge);
while
(true) {
BallsSolution sLight =
findSolutions(lightk, steps - 1);
if (sLight.hasSolution()) {
BallsSolution
sHeavy = findSolutions(heavyk, steps - 1);
if
(sHeavy.hasSolution()) {
BallsSolution sEqual =
findSolutions(equalk, steps - 1);
if (sEqual.hasSolution()) {
SolutionBean
sb = new SolutionBean();
sb.setTransition(transition);
sb.setSolutionsLight(sLight);
sb.setSolutionsHeavy(sHeavy);
sb.setSolutionsEqual(sEqual);
sol.addSolution(sb);
}
}
}
do {
if
(!nextTransition(transition)) {
if (sol.isEmptySolutions()) {
sol.setHasSolution(false);
}
return sol;
}
lightk
= knowledge.extractLightKnowledge(transition);
heavyk
= knowledge.extractHeavyKnowledge(transition);
equalk
= knowledge.extractEqualKnowledge(transition);
} while (BallsSolver.isRedundant(lightk,
heavyk, equalk));
}
}
}