Sudoku Puzzle Part 1: Sudoku Class

Question

I was recently given a Sudoku Puzzle to solve, and since I began solving many Sudoku puzzles after, I decided to attempt to create a Sudoku Puzzle viewer with JavaFX. I am not done yet, but have decided to split it into parts so that it is easier to fix future problems. Part 1 is the Sudoku class. The Sudoku class does:

• Represents a legal (follows "each row, column, and box may only contain each digit from 1-9 only once") Sudoku puzzle
• Allows to check and edit squares, as long as the puzzle stays legal
• Can get a random puzzle (may change to generate puzzle)

The code is below:

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;
import java.io.IOException;
import java.util.Arrays;
import java.util.Random;

public class Sudoku {

    public static final int SUDOKU_SIZE = 9;
    public static final int SUDOKU_SQUARE_SIZE = 3;

    private static final int ROW_TEST = 0;
    private static final int COL_TEST = 1;
    private static final int SQ3_TEST = 2;

    private static final int NUM_OF_PUZZLES = 1;

    private final int[][] puzzle;

    private static final Random random = new Random();

    /**
     * Creates a new Sudoku Puzzle from a 9x9 board. If array is larger than
     * 9x9, then it will ignore the elements out of range. Note that it will
     * still take puzzles that are unsolvable or solved, but will throw an
     * {@link java.lang.IllegalArgumentException IllegalArgumentException} if
     * the puzzle is illegal. The puzzle is illegal if it does not follow the
     * standard Sudoku rules: "Each row, column, and box may only contain one of
     * each number from 1-9."
     * 
     * @param board
     *            the board to copy from
     */
    public Sudoku(int[][] puzzle) {
        checkBoard(puzzle);
        this.puzzle = Arrays.copyOf(puzzle, SUDOKU_SIZE);
        for (int i = 0; i < SUDOKU_SIZE; i++) {
            this.puzzle[i] = Arrays.copyOf(puzzle[i], SUDOKU_SIZE);
        }
    }

    private void checkBoard(int[][] puzzle) {
        boolean[] alreadyHasNumber = new boolean[SUDOKU_SIZE];
        for (int i = ROW_TEST; i <= SQ3_TEST; i++) {
            for (int j = 0; j < SUDOKU_SIZE; j++) {
                for (int k = 0; k < SUDOKU_SIZE; k++) {
                    int num = getNumFromTest(puzzle, i, j, k);
                    if (num != -1) {
                        if (!alreadyHasNumber[num]) {
                            alreadyHasNumber[num] = true;
                        } else {
                            throw new IllegalArgumentException(
                                    "Puzzle is not legal.");
                        }
                    }
                }
                for (int k = 0; k < SUDOKU_SIZE; k++) {
                    alreadyHasNumber[k] = false;
                }
            }
        }
    }

    private int getNumFromTest(int[][] puzzle, int testType, int i, int j) {
        switch (testType) {
        case ROW_TEST:
            return puzzle[i][j] - 1;
        case COL_TEST:
            return puzzle[j][i] - 1;
        case SQ3_TEST:
            return puzzle[(i / SUDOKU_SQUARE_SIZE) * SUDOKU_SQUARE_SIZE + j
                    / SUDOKU_SQUARE_SIZE][i % SUDOKU_SQUARE_SIZE
                            * SUDOKU_SQUARE_SIZE + j % SUDOKU_SQUARE_SIZE] - 1;
        default:
            return 0;
        }
    }

    /**
     * Returns the digit in the specified square, 0 if empty.
     * 
     * Calling with arguments (0, 0) will get the digit on the top left corner,
     * and (8, 8) will point to the bottom right corner. (8, 0) will point to
     * the top right corner, while (0, 8) will point to the bottom left corner.
     * 
     * Note that in (x, y), x is the column number and y is the row number.
     * 
     * @param x
     *            the column which the digit is to be taken from
     * @param y
     *            the row which the digit is to be taken from
     * @throws IllegalArgumentException
     *             if x or y is out of range
     * @return the digit in the specified square
     */
    public int getDigit(int x, int y) {
        if (!isInRange(x) || !isInRange(y)) {
            throw new IllegalArgumentException(
                    "the given square is out of range");
        }
        return puzzle[y - 1][x - 1];
    }

    /**
     * Sets the specified square's number to the specified digit.
     * 
     * Calling with arguments (0, 0) will get the digit on the top left corner,
     * and (8, 8) will point to the bottom right corner. (8, 0) will point to
     * the top right corner, while (0, 8) will point to the bottom left corner.
     * 
     * Note that in (x, y), x is the column number and y is the row number.
     * 
     * This method will return <code>false</code> if the set is illegal. The set
     * is illegal if it changes the puzzle in a way that forces it to not follow
     * the standard Sudoku rules: "Each row, column, and box may only contain
     * one of each number from 1-9."
     * 
     * @param x
     *            the column number of the square to set the digit
     * @param y
     *            the row number of the square to set the digit
     * @param digit
     *            the digit to set the square to
     * @throws IllegalArgumentException
     *             if x or y is out of range
     * @return <code>true</code> if successful (legal set), <code>false</code>
     *         otherwise.
     */
    public boolean setDigit(int x, int y, int digit) {
        if (!isInRange(x) || !isInRange(y)) {
            throw new IllegalArgumentException(
                    "the given square is out of range");
        }
        if (getDigit(x, y) != digit) {
            if (digit < 1 || digit > SUDOKU_SIZE) {
                throw new IllegalArgumentException("digit is out of range");
            }
            // check row
            boolean[] alreadyHasNumber = new boolean[SUDOKU_SIZE];
            alreadyHasNumber[digit - 1] = true;
            for (int i = 1; i <= SUDOKU_SIZE; i++) {
                if (i != x) {
                    int num = getDigit(i, y) - 1;
                    if (num != -1) {
                        if (!alreadyHasNumber[num]) {
                            alreadyHasNumber[num] = true;
                        } else {
                            return false;
                        }
                    }
                }
            }
            for (int i = 0; i < SUDOKU_SIZE; i++) {
                if (i != digit - 1) {
                    alreadyHasNumber[i] = false;
                }
            }
            // check column
            for (int i = 1; i <= SUDOKU_SIZE; i++) {
                if (i != y) {
                    int num = getDigit(x, i) - 1;
                    if (num != -1) {
                        if (!alreadyHasNumber[num]) {
                            alreadyHasNumber[num] = true;
                        } else {
                            return false;
                        }
                    }
                }
            }
            for (int i = 0; i < SUDOKU_SIZE; i++) {
                if (i != digit - 1) {
                    alreadyHasNumber[i] = false;
                }
            }
            // check box
            for (int i = 0, j = (x - 1) - ((x - 1) % SUDOKU_SQUARE_SIZE), k = (y
                    - 1) - ((y - 1)
                            % SUDOKU_SQUARE_SIZE); i < SUDOKU_SIZE; i++) {
                int tempX = j + i % SUDOKU_SQUARE_SIZE;
                int tempY = k + i / SUDOKU_SQUARE_SIZE;
                if (tempX != x - 1 && tempY != y - 1) {
                    int num = puzzle[tempY][tempX] - 1;
                    if (num != -1) {
                        if (!alreadyHasNumber[num]) {
                            alreadyHasNumber[num] = true;
                        } else {
                            return false;
                        }
                    }
                }
            }
        }
        return true;
    }

    public static Sudoku getRandomPuzzle() {
        return new Sudoku(readFile(random.nextInt(NUM_OF_PUZZLES) + 1));
    }

    private static int[][] readFile(int puzzleNum) {
        // TODO
        File file = new File("puzzle" + puzzleNum);
        int[][] result = new int[Sudoku.SUDOKU_SIZE][Sudoku.SUDOKU_SIZE];
        try (BufferedReader reader = new BufferedReader(new FileReader(file))) {
            for (int i = 0; i < Sudoku.SUDOKU_SIZE; i++) {
                String[] line = reader.readLine().split(" ");
                for (int j = 0; j < Sudoku.SUDOKU_SIZE; j++) {
                    result[i][j] = Integer.parseInt(line[j]);
                }
            }
        } catch (IOException e) {
            e.printStackTrace();
        }
        return result;
    }

    private boolean isInRange(int i) {
        return i > 0 && i <= SUDOKU_SIZE;
    }

}

Some concerns:

1. In the setDigit() and checkBoard() class, there is a boolean array alreadyHasNum. After each loop, should this array reset, or should I create a new one?

2. Does the logic make sense? (As in, does the way I handle row/column numbers and board checking make sense)

3. Anything else?

Answer 1

A few things right off the top.

If you have any ambitions about discovering solutions to the puzzles, then you should first read Knuth's Dancing Links paper and Norvig's sudoku essay.

private int getNumFromTest(int[][] puzzle, int testType, int i, int j) {
    switch (testType) {
    case ROW_TEST:
        return puzzle[i][j] - 1;
    case COL_TEST:
        return puzzle[j][i] - 1;
    case SQ3_TEST:
        return puzzle[(i / SUDOKU_SQUARE_SIZE) * SUDOKU_SQUARE_SIZE + j
                / SUDOKU_SQUARE_SIZE][i % SUDOKU_SQUARE_SIZE
                        * SUDOKU_SQUARE_SIZE + j % SUDOKU_SQUARE_SIZE] - 1;
    default:
        return 0;
    }
}

Major code smell here -- you are using a switch to change behavior. That almost always means there is an underlying class that you haven't discovered yet. In this case, you have evidence of a constraint/specification interface that has three distinct implementations.

for (int i = ROW_TEST; i <= SQ3_TEST; i++) 

Major symptom here - you are enumerating over indexes, not because you want an int, but because you want to get something else that the int lets you have (in this case, the constraint I mentioned earlier). This strongly implies that you should be reading from a collection - a Set if there is no particular order, a List if the order matters.

private void checkBoard(int[][] puzzle) {
    boolean[] alreadyHasNumber = new boolean[SUDOKU_SIZE];
    for (int i = ROW_TEST; i <= SQ3_TEST; i++) {
        for (int j = 0; j < SUDOKU_SIZE; j++) {
            for (int k = 0; k < SUDOKU_SIZE; k++) {
                int num = getNumFromTest(puzzle, i, j, k);
                if (num != -1) {
                    if (!alreadyHasNumber[num]) {
                        alreadyHasNumber[num] = true;
                    } else {
                        throw new IllegalArgumentException(
                                "Puzzle is not legal.");
                    }
                }
            }
            for (int k = 0; k < SUDOKU_SIZE; k++) {
                alreadyHasNumber[k] = false;
            }
        }
    }
}

This code here is a mess, because you are writing about "how to do it" without writing out what you are trying to do first. So let's walk through it carefully; the rule you are trying to validate is that no number should appear more than once in any related grouping of cells. In particular, notice that the "no duplicates" part doesn't care which group of cells we're talking about -- there are always going to be nine cells in the group, and no number should appear more than once in the group.

This suggests that there should be a function that takes a list of up to 9 numbers, and makes sure there is no duplication there, and also there's a thing that takes a 9x9 grid and gives you some nine cells in the same group. Actually, 27 things -- there are 9 that each know how to select a different row, 9 that know how to select a different column, 9 that know how to select a different square. So your validation check is really something like

for (Selector s : selectors) {
    CellValues cellValues = s.getCellValues(board);
    if ( ! noDuplicates.isSatisfiedBy(cellValues) ) {
        throw new IllegalArgumentException(...);
    }
}

More general notes

// Convention: ALLCAPS for static data members unless you have a compelling
// reason.
private static final Random RANDOM = new Random();

public static Sudoku getRandomPuzzle() {
    return new Sudoku(readFile(RANDOM.nextInt(NUM_OF_PUZZLES) + 1));
}

Really bad idea, because introducing random numbers in this way makes it very hard to construct a reliable test of this code. At a minimum, you want to separate the random number generation from how you use it, so that you can write a test without the randomness.

public static Sudoku getRandomPuzzle() {
    return getPuzzle(RANDOM.nextInt(NUM_OF_PUZZLES));
}

public static Sudoku getPuzzle(int puzzleId) {
    return new Sudoku(readFile(puzzleId + 1));
} 

Better still, allow somebody to pass you a Random -- there's no particular reason here that only your RNG should be used.

public static Sudoku getRandomPuzzle() {
    return getPuzzle(RANDOM);
}

public static Sudoku getRandomPuzzle(Random random) {
    return getPuzzle(random.nextInt(NUM_OF_PUZZLES));
}

public static Sudoku getPuzzle(int puzzleId) {
    return new Sudoku(readFile(puzzleId + 1));
} 

Of course, there's no particular reason that the source of the puzzle needs to be a File; there's room for an abstraction here of a puzzle Factory or Repository (or maybe both).

Answer 2

If array is larger than * 9x9, then it will ignore the elements out of range

It is usually reccomended to fail fast, fail loudly. I suggest failing if the array has the wrong size as that surely indicates a bug in the calling code