Re: infinite recursion
My original class that contains infinite recursion is as follows:
import java.util.Arrays;
import java.util.Iterator;
import java.util.Vector;
/**
* Sudoku solver. Launch method {@link #Solver()} to solve puzzles.
* <br /><b>J2SE version must be 5.0 or greater, due to use of
generics
* (specifically Vector<E> and Iterator<E>)</b>.
* *** TESTING ***
* @author Andrey Vul
*/
public class Solver2 implements Cloneable {
// the board data
short[] cells;
//v2 0th bit
byte[] zeroBit;
//is the puzzle solved
static boolean solution;
/** Default constructor. Creates a blank [9 * 9] board. */
public Solver2() {
cells = new short[81];
zeroBit = new byte[11];
Arrays.fill(cells, (short)0);
Arrays.fill(zeroBit, (byte)0);
}
/** Returns a copy of the current board. */
protected Solver2 clone() {
Solver2 dest = new Solver2();
System.arraycopy(cells, 0, dest.cells, 0, 81);
System.arraycopy(zeroBit, 0, dest.zeroBit, 0, 11);
return dest;
}
//check bit
boolean checkBit(int i, boolean val) {
int _byte = (int)Math.floor((i + 1) / 8.0);
return (zeroBit[_byte] & (1 << (i % 8))) != 0 ? val : !val;
}
/**
* Returns the number of unavailable positions. Works opposite to
AllOptions(val)
* @param val Value to check for
* @return The number of unavailable positions
*/
short countConstraints(short val) {
//counter
short cc = 0;
//count the number of unavailable positions
short i;
for (i = 0; i < 9; i++)
//1 == unavailable therefore bitwise& != 0 if there are constraints
if (((1 << i) & val) != 0)
++cc;
return cc;
}
/**
* Find the position that has the least possible values
* @return the index of the most constrained position
*/
short mostConstrained() {
//constraint counter
short max = -1;
//currently most constrained value
short maxp = -1;
//find most constrained position
short i, v;
for (i = 0; i < 81; i++) {
//if zero is available (which is always the case)
if (checkBit(i, false)) {
v = countConstraints(cells[i]);
//more constrained, update max and maxp
if (v >= max) {
max = v;
maxp = i;
}
}
}
return maxp;
}
/**
* Finds all the possible options for value val. Remember that
setValue creates
* the exclusion mask.
* @param val The current cell
* @return The possible options as an int array
*/
short[] allOptions(short val) {
//because java doesn't have dynamic-size arrays
Vector<Short> cc = new Vector<Short>(0);
Iterator<Short> it;
short[] rv;
//check which numbers are available
short i;
for (i = 0; i < 9; ++i)
//bitmask check (1 == unavailable, 0 == available)
if (((1 << i) & val) == 0)
//available, add number to cc
cc.add(cc.size(), (short)(i + 1));
//create return array
rv = new short[cc.size()];
it = cc.iterator();
i = 0;
while (it.hasNext())
rv[i++] = it.next();
return rv;
}
/**
* Set the current value in position pos. This method adds exclusion
masks
* for val to every position in the current row, column, and zone. It
then
* unmasks val in position pos.
* @param pos Position
* @param val Value (for position)
*/
void setValue(short pos, short val) {
//column position
short x = (short)(pos % 9);
//row position
short y = (short)(pos / 9);
//zone positions
short zx = (short)((x / 3) * 3);
short zy = (short)((y / 3) * 3);
//exclusion bit
short add = (short)(1 << (val - 1));
short k;
//mask the current number (as a bit) in the current column, row, and
zone
for (k = 0; k < 9; k++) {
//mask the current number (bit) in the current column
cells[x + k * 9] |= add;
//mask the current number (bit) in the current row
cells[k + y * 9] |= add;
//mask the current number (bit) in the current zone
cells[zx + (k % 3) + 9 * (zy + (k / 3))] |= add;
}
//the current number is implemented as a reverse bit
//(0 == current number, 1 == not the number)
cells[pos] = (short)(0x1ff & ~add);
}
/**
* Sanity check. <b>If this returns false, it means that there is no
solution!</b>
* @return Sanity status (<tt>true</tt> or <tt>false</tt>)
*/
boolean isOK() {
int i;
for (i = 0; i < 81; ++i)
if (((this.cells[i] & 0x1ff) == 0x1ff) && checkBit(i, false))
return false;
return true;
}
/**
* Check if the puzzle is solved yet. This is a sanity check because,
if
* the puzzle is solved, then bit 0 is full <b>in each and every
* position</b>.
* @return Is the puzzle solved, <tt>true</tt> or <tt>false</tt>
*/
boolean isSolved() {
int i;
for (i = 0; i < 81; ++i) {
if (checkBit(i, false))
return false;
}
return true;
}
/**
* Search for solutions.
* @return <tt>null</tt> if there is 1 or fewer solutions and a
Solver
* object if there are 2 solutions (or more will not be implemented
* because that will be pointless).
*/
Solver2 searchSolutions() {
short p;
int i;
Solver2 ns;
short[] l;
while (isOK()) {
if (isSolved()) {
solution = true;
return this;
}
//start solving from most constrained position
p = mostConstrained();
//no solution
if (p < 0)
return null;
//get all the available options for cell p
l = allOptions(cells[p]);
//no solution
if (l.length < 1)
return null;
//try each option in cell p by recursing ourselves
//(i.e., (...(ns = this) ... = this))
for (i = 0; i < l.length; ++i) {
//recurse
ns = clone();
ns.setValue(p, l[i]);
ns = ns.searchSolutions();
//solution found, recurse back up
if (ns != null)
return ns;
}
//finally try first option
setValue(p, l[0]);
}
//failed sanity check
return null;
}
/**
* Convert the current Solver to an int array.
* @return The current solver as an int array
*/
protected short[] toArray() {
short[] arr = new short[81];
short i, j;
for (i = 0; i < 81; i++)
/* unmasked bit is our number, therefore we check which bit is
unmasked by
* using a bitwise|, which would equal 1023 when we are at the
correct
* value of j
*/
for (j = 0; j < 9; j++)
if (((cells[i] | (1 << j)) == 0x1ff) && checkBit(i, true)) {
arr[i] = (short)(j + 1);
break;
}
return arr;
}
/**
* Convert an int array to a Solver
* @param array Input int array
* @return a Solver containing the values in <tt>array</tt>
*/
static Solver2 toBoard(short[] array) {
Solver2 a = new Solver2();
short i;
for (i = 0; i < 81; i++)
/* MAKE SURE that the number is between 1 and 9, inclusive so that
the
* solver does NOT mask 0 because that would break function isOK()
and
* hence prevent the solver from reaching a solution.
*/
if (array[i] >= 1 && array[i] <= 9)
a.setValue(i, array[i]);
return a;
}
/**
* Solve the board, returning an int array for each solution.
* @param board Input array for solver
* @return The solution(s), as an array of int array(s)
*/
public static short[] solve(short[] board){
//reset
solution = false;
//solve
Solver2 s = toBoard(board).searchSolutions();
//return
if (solution)
return s.toArray();
else
return new short[81];
}
}
The infinite recursion is somewhere in the method searchSolutions().
But where is it and why was the top of the exception stack at
allOptions()?