Recursive backtracking in Java

[rickster11]

I'm trying to complete the good old Knight's tour (Knight piece must touch every square on board without touching a square twice.

My code goes all the way to the point where the knight is at a dead end, and I need to revisit the last stack... How do you get to the last stack? I thought I was supposed subtract one from my counter and call the method again. I can get to the last stack, and my variables will be reset to that stack right? How to do that? Is there a good tutorial somewhere? (I've looked).

Any help at all would be great. I've been working on this for 2 days now.

import static java.lang.System.out;
import java.util.Scanner;

public class knightsTour {
    Scanner myScanner = new Scanner (System.in);
    int cols = 8;
    int rows = 8;
    int [] rowMoves = {-2,-2, 1, 1, 2, 2, 1,-1};
    int [] colMoves = {-1, 1,-2, 2, 1,-1,-2,-2};
    int grid [] [] = new int [rows] [cols];
    int myRow = 0;
    int myCol = 0;
    int moveCounter = 0;
    int moveOption = 0;

    public static void main(String[] args) {

        knightsTour k = new knightsTour();
        k.grid [0] [0] = 1;
        int moveOption = 0;
        
        if (k.isClear()){
            out.println ("Done done");
        }
    }

    public boolean isClear (){
        //out.println ("Move Count in moveoption Array "+moveOption);

        while (moveOption < 8){
            int possRow = (myRow + rowMoves[moveOption]);
            int possCol = (myCol + colMoves[moveOption]);

           // out.println ("Poss row is "+possRow);
           // out.println ("Poss col is "+possCol);

            if (possRow < rows && possRow > 0 && possCol < cols && possCol > 0 && grid[possRow][possCol] != 1){
                myRow = possRow;
                myCol = possCol;
                moveCounter++;

                grid[myRow][myCol] = 1;

                out.println ("My new Row is "+ myRow+" my Col is "+myCol+" Move Number "+moveCounter);
                moveOption=0;
                return (isClear ());
            }
            else{
                moveOption++;
                //out.println("adding to move option");
            }
        }
            out.println ("reducing move counter");  //Gets here if knight is at dead end.
            moveCounter--;                          //Here is where I need to backtrack
            int blank = myScanner.nextInt();        //pause
            return (isClear ());
        }
    }

[IsharaComix]

Your recursive method has no base cases. Even if they did, your entire program is written in tail recursion, so whenever you return to a previous point in the stack, you don't have any control there because the only time you make the recursive call is in a return statement.

Here's how I would approach the knight's tour (in pseudocode):

/* Path is a list of coordinates that represent the tour so far. */
global list path = new list

boolean ktour( move ):
    path.append(move)
    if ( sizeof(path) == 64 /*tour is complete*/ ):
        return True
    for each move M that can be made:
        if ( ktour(M) ):
            return True
    path.remove(move)
    return False

/* Begin the program. */
ktour( (0,0) )

See how I never do a return(ktour(M)) ? I use the value of the method to take control of the program again whenever the method fails.

Good luck, and I hope this helps out.

[rickster11]

Thanks for your reply. This program has been killing me. I still don't have it working, but thanks to your help I think I am close.

Its still not backtracking right, and I can't figure out why.

I re-write the code in C++ since I heard it was much better for recursion. If you have a second, could you give me a little more guidance.

#include <iostream>
#include <vector>
using std::cout;
using std::endl;
using std::vector;

const int rowMoves [8] = {-2,-2, 1, 1, 2, 2, 1,-1};
const int colMoves [8] = {-1, 1,-2, 2, 1,-1,-2,-2};

int grid [8][8];
vector <int> pathRow;
vector <int> pathCol;
int counter = 0;
//int moveOption = 0;

bool ktour (int,int);

int main (void) 
{	
	int row = 0;
	int col = 0;

	ktour (row, col);
	system ("pause");
	return 1;
}

bool ktour (int row, int col)
{

	pathRow.push_back (row);
	pathCol.push_back (col);
	grid [row] [col] = 1;
	counter++;
	cout << pathRow.back() << ", " << pathCol.back();
	cout << "move #" << counter << endl;

	if (pathRow.size() == 64)
		return true;

	int possRow, possCol;

	for (int moveOption = 0; moveOption < 8; moveOption++)
	{
		possRow = row + rowMoves [moveOption];
		possCol = col + colMoves [moveOption];
		
		if (possRow < 8 && possRow >= 0 && possCol < 8 && possCol >= 0 && grid [possRow] [possCol] != 1)
		{
			if (ktour (possRow, possCol))
				return true;
		}
	}

	cout << "Popping back" << endl;
	pathRow.pop_back ();
	pathCol.pop_back ();
	counter--;
	
	return false;
}

[IsharaComix]

When you backtrack, you don't set grid[row][col] back to zero like you should.

Other than that, the program looks just fine. Of course, a brute-force implementation of the Knight's tour would probably take forever to run, so you may not get any meaningful results after executing the program. But it should give you a correct answer... eventually.

[pali185]

Hello, I got the task to create a program with backtracking, i can not create. Could you write a theory as I do, or write a better program. Entering the example below:

On paper it is written long number 123456789. Insert between some digits signs + or -.
So that you incurred after evaluating the expression given number 100.
For example: 123-45-67 +89 = 100
Write a program that finds and displays all the solutions. Use backtracking.

THANK YOU.

[jon.kiparsky]

You'll be more likely to get useful help if you start a new thread, this one is six months old and your post has nothing to do with the knight's tour problem.

You'll be even more likely to get useful help if you put in some effort instead of just asking people to do your homework for you. Why don't you try to solve the problem, and then ask questions about the places where you get stuck?

[pali185]

Examples are designed program that addresses the solution. But has several errors. This program should generate 3 ^ 9 = 19683 expressions (when calculating accurately). Instead, it generates a 9841 expressions. It is not a multiple of 3, but its half. The program input of Operators to 0 place - before '1' Strange input of the zero position and generates duplicate values. Can you help? Thank you.

//field in which I to insert operators
static String[] cislice = {"","1","","2","","3","","4","","5","","6","","7","","8","","9"};
//field with operators
static String [] operatory = {"","+","-"};
...
private static void BacktrackingSto(int krok,int operator){
        if(krok>cislice.length-1) return;

        //print out genera generated expressions
        for(int i=0;i<cislice.length;i++){
            System.out.print(cislice[i]);
        }System.out.println(); System.out.println();
        j++;  //number of generated expressions
            System.out.println("Backtracking "+krok+", "+operator);


         for(int i=0;i<3;i++){
            cislice[krok]= operatory[operator];
            BacktrackingSto(krok+2,i);
        }
    }