Stuck on Backtracking step on a Sudoku Homework

Question

I'm quite new to java (specially backtracking) and I'm doing a recursive sudoku solver for almost two days with no sucess. I think that my backtracking step is wrong, but I really dont know how to fix it. The input is a .txt with numbers and the character "." representing where the program needs to fulfill. (p.s: The Std.In is a library given by my teacher's textbook which reads the .txt and helps convert it into the semiboard array).

I know that the problem isn't on the backtrack (the one which checks if the number has already been assigned acoarding to the sudoku rules) and associated functions.

The StdIn library can be downloaded in the following website: https://introcs.cs.princeton.edu/java/stdlib/

public class Sudoku {
    private static void Solve(int[] board) {
        SolveCell(board, 0);
    }

    private static void SolveCell(int[] board, int cell) {
        if (cell == 81) {
            show(board);
            return;
        }
        if (board[cell] != 0) {
            SolveCell(board, cell + 1);
            return;
        }
        for (int n = 1; n <= 9; n++) {
            if (!backtrack(board, cell, n)) {
                board[cell] = n;
                SolveCell(board, cell + 1);
            }
        }
        board[cell] = 0;
    }

    private static void show(int[] board) {
        for (int i = 0; i < 81; i++) {
            if ((i + 1) % 9 == 0) {
                System.out.println(board[i]);
            } else {
                System.out.print(board[i]);
                System.out.print(" ");
            }
        }
    }

    private static int choose1(int cell) {
        int l = 0;
        for (int i = 0; i <= 8; i++) {
            if (cell > i * 9 - 1 && cell < (i + 1) * 9 - 1) {
                l = i * 9;
            }
        }
        return l;
    }

    private static int choose2(int cell) {
        int l = 0;
        for (int i = 0; i <= 8; i++) {
            if (cell + i % 9 == 0) {
                l = i;
                return l;
            }
        }
        return l;
    }

    private static int choose3(int cell) {
        int l = 0;
        for (int i = 0; i <= 9; i += 3) {
            for (int j = 0; j <= 81; j += 27) {
                if ((cell % 9 > i && cell % 9 < i + 3) && (cell > j && cell < j + 27)) {
                    l = i + j;
                    return l;
                }
            }
        }
        return l;
    }

    private static boolean backtrack(int[] board, int cell, int n) {
        int linechecker = choose1(cell);
        for (int i = 0; i < 9; i++) {
            if (board[linechecker + i] == n && linechecker + i != cell) {
                return true;
            }
        }
        int columnchecker = choose2(cell);
        for (int i = 0; i < 9; i++) {
            if (board[columnchecker + 9 * i] == n && columnchecker + 9 * i != cell) {
                return true;
            }
        }
        int squarechecker = choose3(cell);
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 27; j += 9) {
                if (board[squarechecker + i + j] == n && squarechecker + i + j != cell) {
                    return true;
                }
            }
        }
        return false;
    }

    public static void main(String[] args) {
        int[] board = new int[81];
        String[] semiboard = new String[81];
        for (int i = 0; i < 81; i++) {
            semiboard[i] = StdIn.readString();
            if (semiboard[i].matches("\\d")) {
                board[i] = Integer.parseInt(semiboard[i]);
            } else {
                board[i] = 0;
            }
        }

        Solve(board);
    }
}

I'm receiving a null output with no Exception message.

here is the .txt:

. . . . 6 . . . 5 
6 2 4 . . . . 1 . 
. . 1 . . . 3 . . 
. . . . . 4 . 3 7 
. . . 1 . . 5 . . 
. . 7 5 . . . 9 . 
. 8 2 4 7 . . . . 
. 9 . 3 1 . . . . 
. . . . 2 9 . 5 3 

The StdIn.readString is defined in the following link: https://introcs.cs.princeton.edu/java/stdlib/StdIn.java.html

Answer 1

You never reached a state in which the condition cell == 81 was true. I didn't do the debug to exactly say what the cause was.

Basically your backtrack method was faulty. Here is how it looks now:

    private static boolean backtrack(int[] board, int cell, int value) {
    int line = cell / 9;
    //check line
    for (int i = 0; i < 9; i++) {
        if ((board[line * 9 + i] == value)) {
            return true;
        }
    }

    int column = cell % 9;
    //check column
    for (int i = 0; i < 9; i++) {
        if (board[column + i * 9] == value) {
            return true;
        }
    }

    int squareLine = line - (line % 3);
    int squareColumn = column - (column % 3);
    //check square
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[(squareLine + i) * 9 + (squareColumn + j)] == value) {
                return true;
            }
        }
    }

    return false;
}

Before you copy paste it be warned that some teachers or professors also look into Stack Overflow to see if you copied the code from somewhere else. So you might be better of staring at this solution and try to figure out where your solution goes wrong and try to correct these parts yourself.