Java Concurrent Modification Recursion Behaviour

Question

Im writing a java program to solve Tricky Triangles (checker like game on a triangle - Here are the rules, and heres a picture )

The program works by interating through all possible moves, recursively making the move, then iterating through the new possible moves and so on an so forth until a base case is found.

The base cases are as follows:

1. The number of possible moves = 0

My code

UPDATED (2/26/2017) to resolve concurrent modification error public int stackSolve(Triangle inputTriangle, Stack stackIn,int depth) throws InvalidArgumentException{

    System.out.println("in stackSolve(). current Triangle: ");
    inputTriangle.printTriangle();

    if (inputTriangle.possibleMoves.size() ==0){

        System.out.println("num possible moves: 0");

        if (inputTriangle.nonNonEmptySpots() == 1){
            System.out.println("Winning solution found.");
            return 1;
        }
        else{
            System.out.println("non winning solution found. Going higher in recursion tree");
            return 0;
        }

    }
    else{
        System.out.println("Number of moves: "+inputTriangle.possibleMoves.size());
        for (Move mv : inputTriangle.possibleMoves){

            System.out.println("Making move : "+mv.toString());
            inputTriangle.makeMove(mv);
            System.out.println("move made");
            stackIn.push(mv);

            System.out.println("entering deeper in recursion tree, calling stackSolve on triangle");

            stackSolve(inputTriangle,stackIn,depth+1);  

            System.out.println("undoing move: "+mv);
            stackIn.pop();
            inputTriangle.undoMove(mv);
            System.out.println("MOVE UNDONE");
        }
        System.out.println("EXITED FOR LOOP");
        return 0;
    }

I have been experiencing odd behaviour with regards to the iteration through the possible moves. Recursion layer n is making the first move, recursing into recursion layer n+1, but when the program returns back to layer n, instead of continuing to iterate through the rest of the possible moves, the program goes to layer n-1. I would really appreciate it if someone could let me know why this is happening.

Here is the output of my code:

in stackSolve(). current Triangle: 

      - 
    2   3  
  4   5   6  

Number of moves: 2
Making move : MOVE object: from:4 | mid: 2 | to: 1
move made
entering deeper in recursion tree, calling stackSolve on triangle
in stackSolve(). current Triangle: 

      1  
    -  3  
  -  5   6  

Number of moves: 1
Making move : MOVE object: from:6 | mid: 5 | to: 4    
move made
entering deeper in recursion tree, calling stackSolve on triangle
in stackSolve(). current Triangle: 

      1  
    -  3  
  4   -  - 

Number of moves: 1
Making move : MOVE object: from:1 | mid: 3 | to: 6
move made
entering deeper in recursion tree, calling stackSolve on triangle
in stackSolve(). current Triangle: 

      - 
    -  - 
  4   -  6  

num possible moves: 0
non winning solution found. Going higher in recursion tree
undoing move: MOVE object: from:1 | mid: 3 | to: 6
MOVE UNDONE
EXITED FOR LOOP
undoing move: MOVE object: from:6 | mid: 5 | to: 4
MOVE UNDONE
EXITED FOR LOOP
undoing move: MOVE object: from:4 | mid: 2 | to: 1
MOVE UNDONE
Making move : MOVE object: from:6 | mid: 3 | to: 1
move made
entering deeper in recursion tree, calling stackSolve on triangle
in stackSolve(). current Triangle: 

      1  
    2   - 
  4   5   - 

Number of moves: 1
Making move : MOVE object: from:4 | mid: 5 | to: 6
move made
entering deeper in recursion tree, calling stackSolve on triangle
in stackSolve(). current Triangle: 

      1  
    2   - 
  -  -  6  

Number of moves: 1
Making move : MOVE object: from:1 | mid: 2 | to: 4
move made
entering deeper in recursion tree, calling stackSolve on triangle
in stackSolve(). current Triangle: 

      - 
    -  - 
  4   -  6  

num possible moves: 0
non winning solution found. Going higher in recursion tree
undoing move: MOVE object: from:1 | mid: 2 | to: 4
MOVE UNDONE
EXITED FOR LOOP
undoing move: MOVE object: from:4 | mid: 5 | to: 6
MOVE UNDONE
EXITED FOR LOOP
undoing move: MOVE object: from:6 | mid: 3 | to: 1
MOVE UNDONE
EXITED FOR LOOP
Triangle of Size: 6 solved in: -1.0 seconds

Here is the Triangle Class - very long

private double aColCoef = 1.0/8.0;
private double bColCoef = 1.0/2.0;
private double cColVal = 3.0/8.0;

private double aRowCoef = 1.0/2;
private double bRowCoef = 1.0/2;
private double cRowVal = 0.0;

private String emptySpotChar = "-";
private int numSpacesInPrint = 2;

public int numPieces;
private int initialEmptySpot;
private int numCols;
public int maxRows;

public ArrayList<Position> positions;
public ArrayList<Move> possibleMoves;


public Triangle(int numPieces, int initialEmptySpot) throws InvalidArgumentException {
    if (this.isValidNumPieces(numPieces)){
        this.numPieces = numPieces;
        this.initialEmptySpot = initialEmptySpot;

        this.numCols = solveQuadratic(this.aColCoef,this.bColCoef, (this.cColVal - numPieces));
        this.maxRows = solveQuadratic(this.aRowCoef,this.bRowCoef, this.cRowVal- numPieces);

        this.positions = getPositions(this.numPieces,initialEmptySpot);
        this.possibleMoves = new ArrayList<Move>();

        setPossibleMoves();
    }

    else{
        throw new InvalidArgumentException("Number of Pieces Invalid");         
    }

}

public Triangle(int numPieces, ArrayList<Integer> emptySpots) throws InvalidArgumentException {

    if (this.isValidNumPieces(numPieces)){
        this.numPieces = numPieces;
        this.initialEmptySpot = initialEmptySpot;

        this.numCols = solveQuadratic(this.aColCoef,this.bColCoef, (this.cColVal - numPieces));
        this.maxRows = solveQuadratic(this.aRowCoef,this.bRowCoef, this.cRowVal- numPieces);

        this.positions = getPositions(this.numPieces,emptySpots);
        this.possibleMoves = new ArrayList<Move>();

        setPossibleMoves();
    }

    else{
        throw new InvalidArgumentException("Number of Pieces Invalid");         
    }
}

private ArrayList<Position> getPositions(int numPieces, ArrayList<Integer> emptySpots) throws InvalidArgumentException {
    ArrayList<Position> returnPositions = new ArrayList<Position>();
    for (int i = 1; i <= numPieces; i++){
        boolean emptySpot = false;
        for (Integer j : emptySpots){
            if (j.intValue() == i){
                emptySpot = true;
            }
        }
        if (emptySpot){
            returnPositions.add(new Position(this,this.getCol(i), this.getRow(i),true,i));
        }
        else {
            returnPositions.add(new Position(this,this.getCol(i), this.getRow(i),false,i));
        }
    }
    return returnPositions;
}

private void setPossibleMoves() {
    possibleMoves.clear();
    for (int i = 0; i < this.positions.size(); i ++){
        positions.get(i).setPossibleMoveSpots();
    }
    for (Position pos : positions){
        this.possibleMoves.addAll(pos.getMoves());
    }
}

private ArrayList<Position> getPositions(int numPieces,int initEmptySpot) throws InvalidArgumentException {
    ArrayList<Position> returnPositions = new ArrayList<Position>();
    for (int i = 1; i <= numPieces; i++){
        if (i == initEmptySpot){
            returnPositions.add(new Position(this,this.getCol(i), this.getRow(i),true,i));
        }
        else {
            returnPositions.add(new Position(this,this.getCol(i), this.getRow(i),false,i));
        }
    }
    return returnPositions;
}

public void makeMove(Move mv){
    mv.makeMove();
    setPossibleMoves();
}

public void makeMove(int mv){
    possibleMoves.get(mv).makeMove();
    setPossibleMoves();
}

static int getMidValue(int x1, int x2) {
    return (int) (x1 + ((x2-x1)/2));
}

public Position getPositionObjectByN(int n) {
    return this.positions.get(n);
}

// returns position object given row and column value of the target position
public Position getPositionAt(int col, int row) {
    for (Position pos : this.positions){
        if (pos.row == row && pos.col == col){
            return pos;
        }
    }
    System.out.println("Position at: col:"+col+", row: "+row+" Does not exist.");
    return null;
}

private int getRow(int pieceNumber) throws InvalidArgumentException {
    if (!this.isValidNumPieces(pieceNumber)){
        while (!this.isValidNumPieces(pieceNumber)){
            pieceNumber--;
        }
        return ( this.solveQuadratic(this.aRowCoef, this.aRowCoef, this.cRowVal - pieceNumber ) + 1 );
    } 
    return this.solveQuadratic(this.aRowCoef, this.aRowCoef, this.cRowVal - pieceNumber);
}

private int getCol(int pieceNumber) throws InvalidArgumentException {
    if (pieceNumber == 1){
        return 0;
    }
    else if (this.isValidNumPieces(pieceNumber)){
        return this.getRow(pieceNumber) -1;
    }
    else{
        int upperBound = pieceNumber;
        while (!this.isValidNumPieces(upperBound)){
            upperBound++;
        }
        int upperBoundRow = this.getRow(upperBound);
        int numNumbersBack = upperBound - pieceNumber;
        return upperBoundRow - 2*numNumbersBack -1;
    }
}

private int solveQuadratic(double a, double b, double c) throws InvalidArgumentException {
    double d = Math.pow(b, 2) - 4 *a *c;
    if (d < 0){
        throw new InvalidArgumentException("Invalid Quadratic Arguments");
    }
    else if (d == 0){
        return (int) ((-b + Math.sqrt( Math.pow(b, 2) - 4 * a * c  ))/ (2*a));
    }
    else {
        int x1 = (int) ((-b + Math.sqrt( Math.pow(b, 2) - 4 * a * c  ))/ (2*a));
        int x2 = (int) ((-b - Math.sqrt( Math.pow(b, 2) - 4 * a * c  ))/ (2*a));
        if (x1> 0){
            return x1;
        }
        return x2;
    }
}

private boolean isValidNumPieces(int numPieces) {
    long calc_num = 8*numPieces+1;
     long t = (long) Math.sqrt(calc_num);
     if (t*t==calc_num) {
        return true;
     }
     return false;
}

public void printTriangle(){
    System.out.println();
    int rowHeight = this.maxRows;
    int indent = (int) (rowHeight * this.numSpacesInPrint);
    String spacer = stringRepeater(" ",this.numSpacesInPrint);
    int i = 1;

    System.out.print( stringRepeater(" ",indent) + spacer);

    while (i < (this.numPieces+1)){
        if (this.isValidNumPieces(i)){

            Position curPosition = getPositionObjectByN(i-1);

            if (!curPosition.isEmpty){
                if (i < 10){
                    System.out.print( spacer + i + " " );
                }

                else {
                    System.out.print( spacer + i);
                }

            }
            else{
                System.out.print( spacer + this.emptySpotChar);
            }

            i ++;
            System.out.print( " \n"+ stringRepeater(" ",indent) );
            indent -= this.numSpacesInPrint;
        }
        else{
            Position curPosition = this.getPositionObjectByN(i-1);
            if (!curPosition.isEmpty){
                if (i < 10){
                    System.out.print( spacer + i + " " );
                }

                else{
                    System.out.print( spacer + i);
                }

            }
            else{
                System.out.print( spacer + this.emptySpotChar);
            }
            i += 1;
        }
    }
    System.out.println();
 }

public void printMoves() {
    if (possibleMoves.size() ==0)
        System.out.println("NO Moves");
    for (Move mv : possibleMoves){
        System.out.println(mv);
    }
}

public void printPositions() {
    for (Position pos : this.positions){
        System.out.println(pos);
    }
}

public String stringRepeater(String input, int count){
    String returnStr = "";
    for (int i = 0 ; i < count; i++){
        returnStr = returnStr + input;
    }
    return returnStr;
}

// this method might not work
public boolean isValidSpot(int col, int row) {

    if ( row >= (Math.abs(col)+1) ){

        if ( (isOdd(col) && !isOdd(row) ) || (!isOdd(col) && isOdd(row) )  ){
            if (row <= maxRows){
                return true;
            }
            else{

            }
        }
        else{

        }

    }
    else{

    }
    return false;
}


private boolean isOdd(int i) {
    if (i % 2 == 0){
        return false;
    }
    return true;
}

public void reset() throws InvalidArgumentException{

    this.positions.clear();
    this.positions.addAll(this.getPositions(this.numPieces, this.initialEmptySpot));

    this.possibleMoves.clear();
    setPossibleMoves();
}

public void undoMove(Move mv){

    mv.from.isEmpty = false;
    mv.mid.isEmpty  = false;
    mv.to.isEmpty   = true;

    setPossibleMoves();
}

public Triangle returnCopy() throws InvalidArgumentException {

    ArrayList<Integer> emptySpots = new ArrayList<Integer>();
    for (Position p : positions){
        if (p.isEmpty){
            emptySpots.add(new Integer(p.n));
        }
    }
    Triangle copy = new Triangle(numPieces, emptySpots);
    return copy;
}

public int nonNonEmptySpots(){
    int ret = 0;
    for (Position p : positions){
        if (!p.isEmpty){
            ret++;
        }
    }
    return ret;
}

Answer 1

Without knowing the code of InputTriangle as @Massimo already asked for, I assume the following:

Within your problematic for-loop, you are iterating over the attribute inputTriangle.possibleMoves and this List is probably changing when the next recursion layer is making a move. Try cloning the possibleMoves before the for-loop.