infinite recursion
9 Message(s) by 6 Author(s) originally posted in java help
| From: andreyvul |
Date: Thursday, October 11, 2007
|
This
method is supposed to return an
array of shorts which represent
all of the possibilities for a given sudoku square (where each value
is a not-masked bitset with
element + 1 equalling position). So far,
it gets stuck in an
infinite recursion . Where is the inifinite
recursion in this method and how do I fix it?
short[] allOptions(short val) {
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;
}
| From: Eric Sosman |
Date: Thursday, October 11, 2007
|
wrote in
message On 10/11/07 13:30,:
This method is supposed to return an array of shorts which represent
all of the possibilities for a given sudoku square (where each value
is a not-masked bitset with element + 1 equalling position). So far,
it gets stuck in an infinite recursion.
How long did you wait? ;-)> Where is the inifinite
recursion in this method and how do I fix it?
[code snipped; see up-thread]
I do not see *any* recursion in this method, infinite
or otherwise. (There are some things that could be done
more smoothly, but there's no recursion.) Why do you
think the method exhibits infinite recursion?
--
Eric.Sosman@xxxxxxxxxxx
| From: Patricia Shanahan |
Date: Thursday, October 11, 2007
|
wrote in message:
wrote in message On 10/11/07 13:30,:
This method is supposed to return an array of shorts which represent
all of the possibilities for a given sudoku square (where each value
is a not-masked bitset with element + 1 equalling position). So far,
it gets stuck in an infinite recursion.
How long did you wait? ;-)
Where is the inifinite
recursion in this method and how do I fix it?
[code snipped; see up-thread]
I do not see *any* recursion in this method, infinite
or otherwise. (There are some things that could be done
more smoothly, but there's no recursion.) Why do you
think the method exhibits infinite recursion?
Moreover, the two
loop s each have a low upper bound on the number of
iterations, so it is an unlikely place to be the
root cause of an
infinite loop.
Perhaps it gets called by something that contains a bug?
Alternatively, the
program could be one that terminates, but not in a
reasonable amount of time.
Patricia
| From: Roedy Green |
Date: Thursday, October 11, 2007
|
On Thu, 11 Oct 2007 10:30:23 -0700, andreyvul
<andrey.vul@xxxxxxxxxxx>
wrote in message, quoted or indirectly quoted someone who said :
infinite recursion.
See
http://mindprod.com/jgloss/recursion.html
You are using the term incorrectly. I think you mean you suspect an
infinite loop.
the following loop isn't infinite, but it'd take longer than you
would be prepared to wait to execute:
long times = Long.MAX_
VAL UE - 10;
int k=0;
for ( long I = 0; i< times; i++)
{
k++;
}
--
Roedy
Green Canadian Mind Products
The JAVA Glossary
http://mindprod.com
| From: rossum |
Date: Thursday, October 11, 2007
|
On Thu, 11 Oct 2007 10:30:23 -0700, andreyvul
<andrey.vul@xxxxxxxxxxx>
wrote in message:
This method is supposed to return an array of shorts which represent
all of the possibilities for a given sudoku square (where each value
is a not-masked bitset with element + 1 equalling position). So far,
it gets stuck in an infinite recursion. Where is the inifinite
recursion in this method and how do I fix it?
short[] allOptions(short val) {
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;
}
I put this into a small test harness and it worked fine, terminating
as expected. I suspect that your problem is in the code that calls
this function.
rossum
| From: Roedy Green |
Date: Friday, October 12, 2007
|
On Thu, 11 Oct 2007 10:30:23 -0700, andreyvul
<andrey.vul@xxxxxxxxxxx>
wrote in message, quoted or indirectly quoted someone who said :
short[] allOptions(short val) {
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;
}
Here is your code tidied up a bit:
Vector -> ArrayList
use of for:each loop
one
parm add
standard idiom for I
do not
reuse i.
import JAVA.util.ArrayList;
public
class Temp
{
short[] allOptions( short val )
{
ArrayList
<Short> cc = new ArrayList
<Short>(10);
// Check which numbers are available
for ( int I = 0; I < 9; i++ )
{
// Bitmask check (1 == unavailable, 0 == available)
if ( ( ( 1 << I ) & val ) == 0 )
{
// Available, add number to tail end of cc
cc.add( (short)( I + 1 ) );
}
}
// Create return array using for:each loop
// We can not use toArray since it
// won't
accept short[] as a parm
short[] rv = new short[ cc.size() ];
int I = 0;
for ( short s: cc )
{
rv[i++] = s;
}
return rv;
}
}
--
Roedy Green Canadian Mind Products
The JAVA Glossary
http://mindprod.com
| From: andreyvul |
Date: Monday, October 15, 2007
|
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 {@xxxxxxxxxxx #
Solve r()} 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 ***
* @xxxxxxxxxxx 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)
* @xxxxxxxxxxx val Value to check for
* @xxxxxxxxxxx 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
* @xxxxxxxxxxx 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.
* @xxxxxxxxxxx val The current cell
* @xxxxxxxxxxx The possible options as an int array
*/
short[] allOptions(short val) {
//because JAVA does not 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.
* @xxxxxxxxxxx pos Position
* @xxxxxxxxxxx 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>
* @xxxxxxxxxxx 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>.
* @xxxxxxxxxxx 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.
* @xxxxxxxxxxx <tt>null
</tt> if there is 1 or fewer solutions and a
Solver
* object if there are 2 solutions (or more won't 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.
* @xxxxxxxxxxx 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'd 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
* @xxxxxxxxxxx array Input int array
* @xxxxxxxxxxx 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 doesn't mask 0 because that'd 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.
* @xxxxxxxxxxx board Input array for solver
* @xxxxxxxxxxx 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()?
| From: Patricia Shanahan |
Date: Tuesday, October 16, 2007
|
wrote in message:
...
The infinite recursion is somewhere in the method searchSolutions().
But where is it and why was the top of the exception stack at
allOptions()?
Presumably you've a VERY long exception stack, since the symptom is
infinite recursion. Most of the entries will be the same method and
line
number, or repeats of a small sequence of methods and line numbers.
Those lines are the ones you really need to look at.
Patricia
| From: shendoku.de |
Date: Tuesday, October 16, 2007
|
If you want to try out something new in sudoku, try shendoku, using
the sudoku rules but playing two people, one against the other, like
battleshipps. They have a free version to
download at
http://www.shendoku.c=
om/sample.pdf
. Anything else they are bringing out or they are working on you can
find at www.shendoku.com or at they=B4r blog www.shendoku.blogspot.com .
Have fun, I am. I specially like one slogan I heard about Shendoku:
SUDOKU is like masturbation (on your own).... SHENDOKU is like sex (it
takes two).