Sudoku algorithm not backtracking properly

Question

I'm making a Sudoku solver which tries every possible value in a square and backtracks if it doesn't lead to a solution. I believe I have a nearly-working algorithm, but it only has worked so far on rows 0, 2, and 3 of a 16-cell puzzle.

public boolean fillBoard(int[][] board, int row, int col){
    int index = 1;              //Next value to try when an empty is found
    boolean solved = false;

    for(int i = row; i < width; i++){       //For each row
        for(int j = col; j < height; j++){  //For each column
            if(board[i][j]==0){             //0 represents empty
                while(!solved){
                    board[i][j] = index;
                    if(checker.checkRow(board[i]) 
                            && checker.checkColumn(columnToArray(board, j))
                            //&& checker.checkBox(<input>)
                            ){
                            solved = fillBoard(board, i, 0);
                    }else{
                        if(index < width){
                            index++;
                        }else{
                            return false;
                        }
                    }
                }
            }
        }
    }
    puzzle = copyPuzzle(board);
    return true;
}

Right now it doesn't check for the third Sudoku rule, it only checks for columns and rows. However, it should still return a puzzle that follows the row and column rules, right? And once the checkBox method is written, it should just be able to solve the puzzle. Where did I mess up here?

EDIT with a few examples:

For an input of

        {1, 2, 0, 0},
        {0, 4, 0, 0},
        {0, 0, 1, 0},
        {0, 0, 3, 2}

The program returns

1 2 4 3 4 4 4 4 2 3 1 4 4 1 3 2

For an input of

        {1, 0},
        {2, 0}

It solves it correctly.

For an input of

        { 1, 0, 3, 4, 0, 0 },
        { 4, 0, 6, 0, 0, 3 },
        { 2, 0, 1, 0, 6, 0 },
        { 5, 0, 4, 2, 0, 0 },
        { 3, 0, 2, 0, 4, 0 },
        { 6, 0, 5, 0, 0, 2 }

It returns the puzzle unsolved

EDIT: checkRow for those who have asked

public boolean checkRow(int[]row){
    HashSet<Integer> set = new HashSet<Integer>();
    for(int i = 0; i < row.length;i++){
        if(!set.add(row[i]) && row[i]>0){//Duplicate?
            return false;
                    }
                }
    return true;
}

Are checkRow and checkColumn just verifying that current row/column don't contain 0? The degenerate case for your recursion seems poorly defined, which would explain the algorithm returning an unsolved puzzle in the last instance. I'm thinking your return true needs to be return solved, and the value of solved needs to be updated for your base case. — nbrooks
– nbrooks, Commented Oct 1, 2016 at 17:16
@nbrooks checkRow and checkColumn add the values of the row or column to a set, unless the value is 0, and if the add fails, it returns false. They're checking to make sure that so far, all the values added to the row or column are valid there — realmature
– realmature, Commented Oct 1, 2016 at 17:20
@realmature you might want to post the implementation of checkRow and checkColumn. Also, an unrelated tip: try to keep your methods clean without too many nested statements. Sometimes neatness will cause the issue to jump out at you. — souldzin
– souldzin, Commented Oct 1, 2016 at 17:22

realmature · Accepted Answer · 2016-10-01 18:20:46Z

The issue was that it didn't reset the space to 0 when the value was incorrect, so if it ever reached the max index and wasn't correct, it just left it. The below code works. Just waiting on another person in my group to deliver the box-checking method, but I will probably end up having to do that myself.

public boolean fillBoard(int[][] board, int row, int col){
    int index = 1;              //Next value to try when an empty is found
    boolean solved = false;

    for(int i = row; i < width; i++){       //For each row
        for(int j = col; j < height; j++){  //For each column
            if(board[i][j]==0){             //0 represents empty
                while(!solved){             //While the puzzle is unsolved
                    board[i][j] = index;    //Try to fill with index
                    if(checker.checkRow(board[i]) 
                            && checker.checkColumn(columnToArray(board, j))
                            //&& checker.checkBox(<input>)
                            ){
                            solved = fillBoard(board, i, 0); //Next space
                    }
                    if(!solved) board[i][j] = 0;
                    if(index < width){
                        index++;
                    }else{
                        return false;
                    }                        
                }
            }
        }
    }
    puzzle = copyPuzzle(board);
    return true;
}

Collectives™ on Stack Overflow

Sudoku algorithm not backtracking properly

1 Answer 1

Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

Comments

Your Answer

Sign up or log in

Post as a guest

Related