Android how to stop recursive function when I got one result

Question

I am new with Android. I am writing simple app that help user solve Sudoku. User will be asked to input some numbers my program will provide only ONE solution for that puzzle.

My recursive function to find results works properly but I dont know how to stop that function when I got first solution. Therefore, my app keep running and then crash.

Here is my code

public class Solver extends ActionBarActivity implements OnClickListener{

private final String TAG = "Solver";
public final int[][] a = new int[9][9];
private SolverView solverView;
public static final int[][] temp = {
    {1,1,1,2,2,2,3,3,3},
    {1,1,1,2,2,2,3,3,3},
    {1,1,1,2,2,2,3,3,3},
    {4,4,4,5,5,5,6,6,6},
    {4,4,4,5,5,5,6,6,6},
    {4,4,4,5,5,5,6,6,6},
    {7,7,7,8,8,8,9,9,9},
    {7,7,7,8,8,8,9,9,9},
    {7,7,7,8,8,8,9,9,9}
};

@Override
protected void onCreate(Bundle savedInstanceState){
    super.onCreate(savedInstanceState);
    solverView = new SolverView(this);
    setContentView(R.layout.activity_solver);
    solverView.requestFocus();
    solverView.bringToFront();
    setContentView(solverView);

}

@Override
public boolean onCreateOptionsMenu(Menu menu) {
    getMenuInflater().inflate(R.menu.solver, menu);
    return true;
}

@Override
public boolean onOptionsItemSelected(MenuItem item) {
    int id = item.getItemId();
    if (id == R.id.action_settings) {
        Log.d(TAG, "menuSelect: do something");
        run(a, 0);
        return true;
    }
    return super.onOptionsItemSelected(item);
}

@Override
public void onClick(View v) {
    // TODO Auto-generated method stub
    if (v.getId() == R.id.solve) {
        Log.d(TAG, "Solve button pressed");
    }
}

protected void showKeypad(int x, int y) {
    Dialog dialog = new Keyboard(this, this.solverView);
    dialog.show();
}

public boolean setCellIfValid(int selU, int selV, int t) {
    Log.d(TAG, " in setCellIfValid " + selU + " " + selV + " " + t);
    this.a[selU][selV] = t;
    solverView.invalidate();
    return true;
}

public String getCellString(int i, int j) {
    int v = this.a[i][j];

    if (v == 0)
        return "";
    else
        return String.valueOf(v);

}

public static void run(int[][] a, int n) {
    if (n >= 81) {
        printArray(a);
    // I WANT MY PROGRAM STOP HERE
        return;
    }
    int i = n / 9;
    int j = n % 9;
    if (a[i][j] != 0) run(a, n + 1);
    for (int k = 1; k <= 9; k++) 
        if (valid(a, i, j, k)) {
            a[i][j] = k;
            run(a, n + 1);
            a[i][j] = 0;
        }
}

public static boolean valid(int[][] a, int u, int v, int k) {
    //check column
    for (int i = 0; i < 9; i++)
        if (a[i][v] == k) return false;
    //check row
    for (int j = 0; j < 9; j++)
        if (a[u][j] == k) return false;
    //check small square
    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++)
            if (temp[i][j] == temp[u][v] && a[i][j] == k)
                return false;
    return true;

}

public static void printArray(int[][] a) {
    for (int i = 0; i < a.length; i++) {
        for (int j = 0; j < a[0].length; j++)
            System.out.print(a[i][j] + " ");
        System.out.println();
    }

}

}

Anyone could help me? Thank you so much for reading. Sincerely

Answer 1

You have two possible approaches to choose from. The best is to discard the recursive approach and try an iterative one. This way you can stop searching for answers when you find an answer. This doesn't need to be an iterative function per se: it could be tail-recursive as well.

The easier solution is to store a global variable, say boolean solutionFound, and initialize it to false. Then, when one of your recursions find a solution, just change the flag to true. The recursive function should always check for the flag, and return if it's true.

This is pseudocode of sorts that I find myself using when ever I made a brute-force sudoku solver:

void solveSquare(currentLayout, row, column) {
    if row > maxRows
        print(layout);
        return;

    if column > maxColumns
        solveSquare(currentLayout, row + 1, 0)
        return;

    foreach digit d in [1, 2, 3, 4, 5, 6, 7, 8, 9] :
        if isValidDigitAtSquare(currentLayout, row, column)
            temp = currentLayout[row][column];
            currentLayout[row][column] = d;
            solveSquare(currentLayout, row, column + 1);
            currentLayout[row][column] = temp;
}

The above pseudocode assumes that there exists only one solution for a sudoku, since for any decent (some prefer valid) sudoku there exists only one solution. For this particular pseudocode, all I would have to do to ever return only one solution is to add the flag like follows:

boolean solutionFound = false;

void solveSquare(currentLayout, row, column) {
    if solutionFound
        return;

    if row > maxRows
        print(layout);
        solutionFound = true;
        return;

    if column > maxColumns
        solveSquare(currentLayout, row + 1, 0)
        return;

    foreach digit d in [1, 2, 3, 4, 5, 6, 7, 8, 9] :
        if isValidDigitAtSquare(currentLayout, row, column)
            temp = currentLayout[row][column];
            currentLayout[row][column] = d;
            solveSquare(currentLayout, row, column + 1);
            currentLayout[row][column] = temp;
}

Answer 2

Try putting break; in for loop inside if condition where you want to kill it. Hop it solver your problem.