4
\$\begingroup\$

I am implementing recursive backtracking algorithm for sudoku. Below is the code to create board with random filling. I wonder if I can make it better in any terms of readable coding especially validation methods. in Board class.

public class Board {
private int[][] board;
public final static int SIZE = 9;

public Board() {
    create();
}

public int[][] getBoard() {
    return board;
}

private void create() {
    int openspots = 20;
    board = new int[SIZE][SIZE];
    Random rand = new Random();
    int random, randomrow, randomcolumn;

    while (openspots-- > 0) {
        random = rand.nextInt(SIZE) + 1;
        randomrow = rand.nextInt(SIZE);
        randomcolumn = (rand.nextInt(SIZE));

        if (board[randomrow][randomcolumn] == 0) {
            board[randomrow][randomcolumn] = random;
            int count = 0;

            while (!isValid(randomrow, randomcolumn)) {
                if (count++ == 9) {
                    board[randomrow][randomcolumn] = 0;
                    openspots++;
                    break;
                }

                random = rand.nextInt(SIZE) + 1;
                board[randomrow][randomcolumn] = random;
            }
        }
    }
}

public void printBoard() {
    for (int row = 0; row < SIZE; row++) {
        for (int column = 0; column < SIZE; column++) {
            System.out.print(board[row][column] + " ");
        }
        System.out.println();
    }
}

public boolean isValid(int row, int column) {
    return isValidRow(row) && isValidColumn(column) && isValidBlock(row, column);
}

private boolean isValidRow(int row) {
    if (row > 8 || row < 0)
        throw new IllegalArgumentException("Row must be between 0 and " + (SIZE - 1) + " inclusive!");

    Set<Integer> set = new HashSet<>();

    for (int i = 0; i < SIZE; i++) {
        if (board[row][i] != 0 && set.contains(board[row][i])) {
            return false;
        } else {
            set.add(board[row][i]);
        }
    }

    return true;
}

private boolean isValidColumn(int column) {
    if (column > 8 || column < 0)
        throw new IllegalArgumentException("Column must be between 0 and " + (SIZE - 1) + " inclusive!");

    Set<Integer> set = new HashSet<>();

    for (int i = 0; i < SIZE; i++) {
        if (board[i][column] != 0 && set.contains(board[i][column])) {
            return false;
        } else {
            set.add(board[i][column]);
        }
    }

    return true;
}

private boolean isValidBlock(int row, int column) {
    if (column > 8 || column < 0)
        throw new IllegalArgumentException("Column must be between 0 and " + (SIZE - 1) + " inclusive!");

    int blockrow = (row / 3) * 3;
    int blockcolumn = (column / 3) * 3;

    Set<Integer> set = new HashSet<>();

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[blockrow + i][blockcolumn + j] != 0 && set.contains(board[blockrow + i][blockcolumn + j])) {
                return false;
            } else {
                set.add(board[blockrow + i][blockcolumn + j]);
            }
        }
    }

    return true;
}
}

The one below is the solver class which has the main algorithm to solve sudoku.

public class Solver {

public boolean solve(Board board) {
    int[][] boardarr = board.getBoard();

    for (int i = 0; i < board.SIZE; i++) {
        for (int j = 0; j < board.SIZE; j++) {
            if (boardarr[i][j] == 0) {
                for (int k = 1; k <= board.SIZE; k++) {
                    boardarr[i][j] = k;
                    if (board.isValid(i,j) && solve(board)) {
                        return true;
                    }
                    boardarr[i][j] = 0;
                }
                return false;
            }
        }
    }

    return true;
}
}
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$
    – Vogel612
    Mar 3 '20 at 12:16
4
\$\begingroup\$

Object Orientated Programming

you don't use object orientated programming! that would clean up the code in a large scale

public class Board {
    //private int[][] board; primitive obsession - use objects instead
    private Field[][] fields;
    private Column[] columns;
    private Row[] rows;
    private Block[] blocks;
    public final static int SIZE = 9;  

    ...      
}

you could provide the proper methods for the field - so you could easily represent the field - instead of trying to interpret an int value.

you could provide methods that are specific for these objects - you could even define an interface for common code, like isFieldValid(Field candidate) for Row, Column and Block

Naming

consider these names and you might find better

Random rand = new Random();
int random, randomrow, randomcolumn;

maybe it would be

Field candidate;

again here, in Java we don't use the hungarian notation and name a variable by it's type:

//int[][] boardarr = board.getBoard();
int[][] board = board.getBoard(); //would be better
Field[][] fields = board.getFields(); //even more better

Data Structure

if you would use Objects for your Sudoku-Solver you could re-use values (here an example snippet for Block)

class Block {
    final private Set<Field> fields = new HashSet<>();

    boolean isFieldValid(Field field) {
        //Set<Integer> set = new HashSet<>(); we already have such set 
        //and don't need to create a new one whenever we check
        return !fields.contains(field);
    }
}

Magic numbers

you already provide a SIZE = 9 constant - so why don't you use a proper one for the block size?

int blockrow = (row / 3) * 3;
int blockcolumn = (column / 3) * 3;

Testing

i assume you provide enough tests but just don't put these in the question

Summary

very nice piece of code - i'm glad you have posted it here! The algorithm seems straight forward, i like it! The OO-thing is the only flaw here. I would appreciate if you would provide another question with applied OOP!

\$\endgroup\$
4
  • \$\begingroup\$ Regarding the solving algorithm, the Column, Row and Block classes are essentially the same. They are collections of <SIZE> elements with the restriction that any given number can ocur exactly once in the collection. The order of the Fields inside the collections is meaningful mainly for presentation only. Also, each Field exists in three collections simultaneously. This symmetry is something that can be taken advantage of when writing the algorithms. \$\endgroup\$ Mar 3 '20 at 8:17
  • \$\begingroup\$ @TorbenPutkonen you are totally correct. I had in mind that these Objects would be used in further context: Panel.highLight(Row row); or ColumnAdviser.showHint(Column colum); but using OOP they can be designed that they have one parent class that implements the checkField(Field f) interface... - but regarding the solving algortihm that is totally overkill and can be reduced! very right! \$\endgroup\$ Mar 3 '20 at 8:29
  • \$\begingroup\$ thank you so much for the reply. I made some improvemnts in the code according to your advice. (made a parent board class for another board games like n-queens) Can you check again? I cannot figure out Field thing as it complicates things \$\endgroup\$ Mar 3 '20 at 12:04
  • \$\begingroup\$ as mentioned please ask another question! i think we're all keen on seeing your progress! \$\endgroup\$ Mar 3 '20 at 12:26
1
\$\begingroup\$

A small side note: in create(), you wrote

int openspots = 20;
// ...
while (openspots-- > 0) {
// ...
}

While it looks clean, it's weird to read and should probably be written as a for-loop. This way, you also reduce the scope of openspots to inside the loop and don't clutter up your namespace inside of create(). Also, the twenty seems a bit like a magic number to me, you shold probably put it into a constant. This would make the loop look something like this:

for (int openspots = CONST - 1; openspots >= 0; openspots--) {
// ...
}
\$\endgroup\$
1
  • \$\begingroup\$ that had hit me as well - good one =) +1 \$\endgroup\$ Mar 4 '20 at 11:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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