6
\$\begingroup\$

I wrote this java Class to solve a standard 9x9 sudoku board. It uses backtracking to solve each field of the board.

I am really interested in feedback for the "isValid" and "isBlockValid" Methods, because they are redundant.

Here is my code on github.

Also here is the code:

public class SudokuSolver {

    private boolean solve(int[][] board, int counter){

        int col = (int) counter / board.length;
        int row = counter % board.length;

        if (col >= board.length){
            printBoard(board);
            return true;
        }

        if (board[row][col] == 0) {

        for (int n = 1; n <= board.length; n++) {

            if (isValid(n,row,col, board)){
                board[row][col] = n;

                if (solve(board,counter+1)){
                    return true;
                }

            }
            board[row][col] = 0;

        }
        }else{
            if (solve(board,counter+1)){
                return true;
            }
        }

        return false;
    }

    public void startSolving(int[][] board){
        if(!solve(board, 0)){
            System.out.println("no solution");
        }
    }

    private boolean isValid(int n, int row, int col, int[][] board){

        int i;
        int j;

        for (i = 0; i < board.length; i++) {
            if(board[row][i] == n){
                return false;
            }
        }

        for (i = 0; i < board.length; i++) {
            if(board[i][col] == n){
                return false;
            }
        }

        //check if block is valid - do not know any other way for solving this

        // check block 1
        if (row >= 0 && col >= 0 && row <= 2 && col <= 2){
           if(!isBlockValid(n, row, col, board, 0, 2, 0, 2)){
               return false;
           }
        }

        // check block 2
        if (row >= 0 && col >= 3 && row <= 2 && col <= 5){
            if(!isBlockValid(n, row, col, board, 0, 2, 3, 5)){
                return false;
            }
        }

        // check block 3
        if (row >= 0 && col >= 6 && row <= 2 && col <= 8){
            if(!isBlockValid(n, row, col, board, 0, 2, 6, 8)){
                return false;
            }
        }

        // check block 4
        if (row >= 3 && col >= 0 && row <= 5 && col <= 2){
            if(!isBlockValid(n, row, col, board, 3, 5, 0, 2)){
                return false;
            }
        }

        // check block 5
        if (row >= 3 && col >= 3 && row <= 5 && col <= 5){
            if(!isBlockValid(n, row, col, board, 3, 5, 3, 5)){
                return false;
            }
        }

        // check block 6
        if (row >= 3 && col >= 6 && row <= 5 && col <= 8){
            if(!isBlockValid(n, row, col, board, 3, 5, 6, 8)){
                return false;
            }
        }

        // check block 7
        if (row >= 6 && col >= 0 && row <= 8 && col <= 2){
            if(!isBlockValid(n, row, col, board, 6, 8, 0, 2)){
                return false;
            }
        }

        // check block 8
        if (row >= 6 && col >= 3 && row <= 8 && col <= 5){
            if(!isBlockValid(n, row, col, board, 6, 8, 3, 5)){
                return false;
            }
        }

        // check block 9
        if (row >= 6 && col >= 6 && row <= 8 && col <= 8){
            if(!isBlockValid(n, row, col, board, 6, 8, 6, 8)){
                return false;
            }
        }

        return true;
    }

    private boolean isBlockValid(int n, int row, int col, int[][] board, int starti, int stopi, int startj, int stopj){

        for (int i = starti; i <= stopi; i++) {

            for (int j = startj; j <= stopj; j++) {

                if (board[i][j] == n) {
                    return false;
                }
            }
        }

        return true;
    }

    private void printBoard(int[][] board){

        System.out.println();

        for (int[] row : board){
            System.out.print("|");
            for (int col : row){
                System.out.print(col);
                System.out.print("|");
            }
            System.out.println();
        }
        System.out.println();
    }

    public static void main(String[] args) {

        int[][] board =
                {{2,0,5,0,0,0,0,0,0},
                {3,0,8,6,0,0,9,0,0},
                {0,0,0,1,0,0,4,0,0},
                {0,0,0,0,5,0,0,1,0},
                {0,0,0,0,9,0,0,2,0},
                {8,7,0,0,2,0,0,0,0},
                {0,0,0,0,8,9,0,0,3},
                {0,0,6,0,0,3,0,0,5},
                {5,0,4,0,0,0,0,0,1}};
        
        SudokuSolver sudokuSolver = new SudokuSolver();
        sudokuSolver.startSolving(board);
    }
}


```
\$\endgroup\$
4
  • \$\begingroup\$ For the duplicate bit of isValid where you check each block. Consider, a block can be described by the top left position, given the top left position you can determine the squares to look at. So, consider writing something which can take (for example, there are other, perhaps better, ways) [[0, 0], [0, 3], [0, 6], [3, 0], ... ] and check the block described by each pair is a good block. \$\endgroup\$ Oct 19, 2020 at 20:33
  • \$\begingroup\$ It is worth saying, that you could have probably come to this conclusion yourself with an intermediate refactor. Where you did like [[0, 0, 2, 2], [0, 3, 2, 5], ...] (taking your bounds from each for loop) and then went through the array of quadruples and called isBlockValid. There's a good lesson here about how repeatedly refactoring will lead you to cleaner and cleaner solutions. \$\endgroup\$ Oct 19, 2020 at 20:36
  • \$\begingroup\$ I understand what you mean by describing a block only by the top left position but I would still need all the if statements to determine in which block the field-to-prove is. Or am I missing something? \$\endgroup\$
    – apocs
    Oct 19, 2020 at 23:56
  • \$\begingroup\$ The thing is, you can work out which block you need to check, and then just check that one. Let's just stick with your isBlockValid for now, have a function workItOut which takes the row and col and then returns the correct 4 numbers to pass into isBlockValid for that row, col. Then in your code, call workItOut, get the 4 numbers, call isBlockValid with those 4 numbers, if it's not true return false. \$\endgroup\$ Oct 20, 2020 at 0:01

4 Answers 4

7
\$\begingroup\$

To remove duplication,

    // check block 1
    if (row >= 0 && col >= 0 && row <= 2 && col <= 2){
       if(!isBlockValid(n, row, col, board, 0, 2, 0, 2)){
           return false;
       }
    }

you can rewrite these nine sections as this single block

final int blockRow = 3 * (row / 3);
final int blockCol = 3 * (col / 3);
return isBlockValid(n, row, col, board, blockRow, blockRow + 2, blockCol, blockCol + 2);

Note that it would probably be easier to just pass in blockRow and blockCol and do the + 2 in the isBlockValid method.

I would also consider passing the board into the constructor so that you don't have to pass it around constantly.

And of course, you don't use row or col in your isBlockValid method, so there is no reason to pass them. So something like

return isBlockValid(n,
    VERTICAL_SIZE * (row / VERTICAL_SIZE),
    HORIZONTAL_SIZE * (col / HORIZONTAL_SIZE));

and

private boolean isBlockValid(int n, int row, int col) {
    for (int bottom = row + VERTICAL_SIZE; row < bottom; row++) {
        for (int right = col + HORIZONTAL_SIZE; col < right; col++) {
            if (board[row][col] == n) {
                return false;
            }
        }
    }

    return true;
}

public final int HORIZONTAL_SIZE = 3;
public final int VERTICAL_SIZE = 3;

This also gets rid of your magic numbers. Perhaps this too should be set in the constructor. But even constants are going to be easier to change later.

An exclusive upper bound is more idiomatic and allows us to reuse the same constants.

\$\endgroup\$
4
\$\begingroup\$

I realise that this isn't as much of a review as a rewrite, but I still think it's on topic as an answer on this site as sometimes the right answer to your problem is to take a completely different approach that avoids the problems in the original attempt by design rather than tweaks.

I wrote a sudoku solver a long time ago. One of the things I did to reduce duplication and make processing efficient is to use an appropriate data structure.

The board consists of cells that contain a list of candidate-sets and a nullable number. The candidate sets each contain the set of numbers allowed for coming/row/block. Something like this:

class Cell{
    List<Set<Integer>> candidates;
    Integer value=null;

    // During board setup, generate one set for each row, column and block
    // and initialize with 1...9
    // Pass appropriate list of row, column and block for each cell
    Cell(List<Set<Integer>> c){
        candidates = c;
    }

    void set(int v){
        for(var c : candidates) {
             c.remove(v);
        }
        value = v;
    }

    boolean isSet(){
        return value != null;
    }

    Set<Integer> allowed(){
        var ans = new HashSet<>(candidates.get(0));
        for(var c : candidates) {
            ans.retainAll(c);
        } 
        return ans;
    }
}

This allows fast computation of the allowed values you can try in the back tracking search (this essentially implements constraint propagation for first order constraints) and it does so in a general way over rows, columns and blocks making the code simpler.

Note that the code here represents a change in approach. Instead of checking validity at every step, we prevent generating invalid states to begin with. You'll detect that you've reached a dead end in the solving prices when the allowed set of numbers for a cel that is empty is the empty set.

Pseudocode for a solver could then be:

class Board{
    List<Cell> board;
    
    Board deepCopy(){...}

    List<Cell> getUnsolved(){
        return board.stream().filter(X -> !X.isSet()).collect(toList());
    }
    

    boolean isSolved(){ return getUnsolved().isEmpty (); }

    Board solve(){
        var b = deepCopy ();
        b.deterministicSolve();
        List<Cell> unsolved = b.getUnsolved();
        if (unsolved.isEmpty()){
            return b;
        }
        // Sorting makes solving faster by reducing the branching factor
        // close to the search root and allowing constraint propagation to
        // work more efficiently
        unsolved.sort(byLowestAllowedNumberOfValues);
        Cell c = unsolved.get(0);  // pick most constrained cell to guess values for
        for(var v : c.allowed()){
            c.set(v);
            var ans = b.solve();
            if(ans.isSolved()){
                return ans;
            }
        }
        throw new Exception("no solution exists!");
    } 

    void deterministicSolve (){
        boolean changed = true;
        while(changed){
            changed=false;
            for(var c : board){
                var allowed = c.allowed();
                if(allowed.size()==1){
                    c.set(allowed.get(0));
                    changed=true;
                }
             }
        }
    }
}

Note that the pseudocode is generic, free repetition, and iteration over rows, columns and blocks, and free of magic numbers, you only need the magic constants when setting up the board.

About the solving process: the deterministic part solves any cells for which there is only one possible value, I found that this was a necessary step as it severely reduces both the branching factor and tree depth of the search space, significantly improving run time.

In the depth first search (DFS) part of the solve (solve() function) we take care to guide the tree exploration to select cells with few possible values first. This results in a narrower search tree and as solving the tightly constrained values first typically makes other cells tightly constrained this effect applies throughout the search tree. Essentially it reduces the search space and a small cost per search node. The use of the sets for the constraints in the cells efficiently allows computation of the allowed set of values which makes the above code cleaner and efficient.

Sorry for the sloppiness in the naming and formatting of the code, I wrote this on a phone.

Edit: note that there are other techniques that can be added to the deterministic solve function to make the runtime even faster. I just showed the lowest hanging fruit.

\$\endgroup\$
2
\$\begingroup\$

One approach to unify all the various validity tests is to introduce what I'd call "groups":

  • Each row is a group.
  • Each column is a group.
  • Each of the 3*3 blocks is a group.

Each group consists of 9 cells, and can be represented by a list of 9 coordinates.

You can create the 27 groups either by manually writing down the coordinate lists (tedious and error-prone), or (better) by generating them with a few loops in an initialization step.

Then validating a number for a given coordinate means:

  • Find all groups containing this coordinate (there should always be 3 hits).
  • Check whether the number is already present at one of the group's coordinates.

Rows, columns and blocks get treated the same, by the very same piece of code, as now they are just lists of coordinates.

The indirection of going through corrdinates lists might cost you a tiny bit of performance, but I'm not even sure of that. If performance is an issue, use a profiler.

EDIT

I just recognized that this is basically part of EmilyL's approach, so look at her answer instead.

\$\endgroup\$
1
\$\begingroup\$

In addition to your specific question on the isValid() methods, a few hints on code style, as this is the CodeReview site.

Your solve() method is well done regarding its recursive calls, but it mixes computation and user interface (output) when it finally found the solution.

In professional development, we separate these concerns as much as possible, e.g. to have one solver core, providing solutions to different user interfaces, e.g. console output, graphical user interface, or web service.

Changing that in your code is easy. When you found the solution, just return true. All recursion layers above will simply pass this upwards, and the top-level caller (startSolving() in your case) will receive the information about success or failure, and in the success case, the board will contain the solution. So you can just move the printBoard() call out there, and then solve() is free of UI code and re-usable in other environments.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.