How can I make this backtracking stop without using System.exit(0)?

Question

static void LasVegas(int []tablero, int f, int ultimaReina){


    HashSet<Integer> enterosUsados = new HashSet<Integer>();


    if (ultimaReina!=-1) enterosUsados.add(ultimaReina);
    if ((ultimaReina-1) >=0){enterosUsados.add(ultimaReina-1);}
    if ((ultimaReina+1 != tablero.length) && (ultimaReina!=-1)){enterosUsados.add(ultimaReina+1);}
  //  if(ultimaReina+1!=tablero.length){enterosUsados.add(ultimaReina+1);}

    Random random = new Random();
        int posReina;

        if (f==tablero.length){
            printBoard(tablero);
            stop=System.currentTimeMillis();
            System.out.println(stop-start);
            System.exit(0);
            return;
        }

        do {

            do{
            posReina= Math.abs(random.nextInt())%tablero.length;
            }
            while(enterosUsados.add(posReina)==false);


            tablero[f]=posReina;

            if (check(tablero, f)){
                LasVegas(tablero, f+1, posReina);
            }



    } while (enterosUsados.size()<tablero.length);

  }

public static void main(String[] args) {

       // testChiCuadrado(410,30);

        int [] tablero = new int[8];
        Arrays.fill(tablero, -1);

        start = System.currentTimeMillis();
        LasVegas(tablero, 0, -1);


    }

static boolean  check (int [] array, int f){

       for (int i=0; i<f; i++){

       if (array[i]==array[f]) return false;

       if( Math.abs(array[f]-array[i])== Math.abs(f-i)) return false;


       } return true;



   }


   static void printBoard(int [] tablero) {

       char [] linea = new char[tablero.length];
       Arrays.fill(linea, '*');
       for (int i=0;i<tablero.length;i++){

           linea[tablero[i]]='D';
           System.out.println(new String(linea));
           linea[tablero[i]]='*';

       }

   }

I'm using a Las Vegas algorithm to generate random queen positions on a board, I'd like to do timing of it via multiple runs but I'm using System.exit(0) to stop the backtracking when a solution is found, if I don't stop there my algorithm gives other solutions, which I don't want.

Here:

       if (f==tablero.length){
            printBoard(tablero);
            stop=System.currentTimeMillis();
            System.out.println(stop-start);
            System.exit(0);
            return;
        } 

How can I change that and make the algorithm stop without System.exit(0) so that I can call It multiple times within a loop?

Answer 1

Change the return type of LasVegas to boolean. Remove the call to System.exit() and change the immediately following return; statement to return true;. Change the recursive call to:

if (LasVegas(tablero, f+1, posReina)) return true;

Answer 2

You can make the function return bool

static bool LasVegas( ...

and instead of Exit return false. Return true in the other case.

Also when calling the function recursively just check the result and if false, the return false:

       if (check(tablero, f)){
            if (!LasVegas(tablero, f+1, posReina))
                return false;
       }

Answer 3

replace the exit with a return;
in a while loop you can call break; to exit it

Answer 4

I have a good suggestion here:

If you are done with backtracking and you don't want to continue.

1. create a static or dummy variable (boolean or int)
2. once you are done assign some value to it (lets say true or 1)
3. Check the dummy variable value in Backtrack method and 'return'.

if(done) return; // Here all the backtrack methods will simply return true to the called one and do nothing. Important thing is this piece of code should be in the beginning of the backtracking method.