| veroslav
| | Joined: 05 Jun 2006 | | Posts: 7 | | : | |
Items |
|
 Posted: Tue Jul 25, 2006 5:23 pm Post subject: search() in DLX loops forever (code inside) |
 |
|
I have a weird problem that only occurs sometimes. I am using my DLX solver in order to generate puzzles and it works good, most of the time. However sometimes when checking if entered numbers in the board lead to a solution, search() - method never returns and just loops. I am stunned as it is very hard to find the error, as it works 90% of the time, with the solver being called several times and performing just fine. Here is my code:
| Code: |
private void search(int k) {
if(masterHeader.getRight() == masterHeader) {
++nbrSolutions;
if(showSolution)
printSolution(k);
if(nbrSolutions == 2) {
multipleSolutions = true;
}
return;
}
X ok = null;
X c = chooseColumnObject();
coverColumn(c);
for(X r = c.getLower(); r != c; r = r.getLower()) {
ok = r;
solution.add(k, ok);
for(X j = r.getRight(); j != r; j = j.getRight()) {
coverColumn(j.getListHeader());
}
if(!multipleSolutions)
search(k+1);
r = solution.get(k);
c = r.getListHeader();
for(X j = r.getLeft(); j != r; j = j.getLeft()) {
uncoverColumn(j.getListHeader());
}
}
uncoverColumn(c.getListHeader());
}
private X chooseColumnObject() {
X smallest = masterHeader.getRight();
int s = smallest.getSize();
int currentSize;
for(X j = smallest; j != masterHeader; j = j.getRight()) {
currentSize = j.getSize();
if(currentSize == 1)
return j;
else if(currentSize < s) {
smallest = j;
s = currentSize;
}
}
return smallest;
}
private void coverColumn(X c) {
c.getRight().setLeft(c.getLeft());
c.getLeft().setRight(c.getRight());
for(X i = c.getLower(); i != c; i = i.getLower()) {
for(X j = i.getRight(); j != i; j = j.getRight()) {
j.getLower().setUpper(j.getUpper());
j.getUpper().setLower(j.getLower());
j.getListHeader().decreaseSize();
}
}
}
private void uncoverColumn(X c) {
for(X i = c.getUpper(); i != c; i = i.getUpper()) {
for(X j = i.getLeft(); j != i; j = j.getLeft()) {
j.getListHeader().increaseSize();
j.getLower().setUpper(j);
j.getUpper().setLower(j);
}
}
c.getRight().setLeft(c);
c.getLeft().setRight(c);
}
|
I am thankfull for any help, as I have been debugging for several days now and I am getting tired. Thanx in advance.
/Veroslav |
|
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
