4
\$\begingroup\$

I have this command line program that asks the user to (partially) input the source sudoku with some missing values, and after that validates the input and solves it.

See what I have:

SudokuSolver.java:

package net.coderodde.sudoku;

import java.awt.Point;
import java.util.Objects;

/**
 * This class implements a backtracking algorithm for solving square sudokus.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 25, 2016)
 */
public class SudokuSolver {

    private static final int MINIMUM_DIMENSION = 1;
    private static final int UNUSED = 0;

    private final int dimension;
    private final int minisquareDimension;
    private Sudoku input;
    private final IntSet[] rowSetArray;
    private final IntSet[] columnSetArray;
    private final IntSet[][] minisquareSetMatrix;
    private final Point point = new Point();
    private Sudoku solution;

    public SudokuSolver(int dimension) {
        this.minisquareDimension = checkDimension(dimension);
        this.dimension = dimension;

        rowSetArray    = new IntSet[dimension];
        columnSetArray = new IntSet[dimension];

        minisquareSetMatrix = new IntSet[minisquareDimension]
                                        [minisquareDimension];

        for (int i = 0; i < dimension; ++i) {
            rowSetArray   [i] = new IntSet(dimension + 1);
            columnSetArray[i] = new IntSet(dimension + 1);
        }

        for (int y = 0; y < minisquareDimension; ++y) {
            for (int x = 0; x < minisquareDimension; ++x) {
                minisquareSetMatrix[y][x] = new IntSet(dimension + 1);
            }
        }
    }

    public Sudoku solve(Sudoku input) {
        Objects.requireNonNull(input, "The input sudoku is null.");
        this.input = new Sudoku(input);
        fixInputSudoku();
        clearSets();
        tryInitializeSets();
        solution = new Sudoku(dimension);
        solve();
        return solution;
    }

    // Checks that the requested dimension d = k^2 for some positive integer 
    // k, which means that we can form "miniquares". For example, if the 
    // dimension is 9, the dimension of a minisquare is 3.
    private int checkDimension(int dimension) {
        if (dimension < MINIMUM_DIMENSION) {
            throw new IllegalArgumentException(
                    "The requested sudoku dimension (" + dimension +
                    ") is too small. Must be at least " + MINIMUM_DIMENSION + 
                    ".");
        }

        int i = 1;

        while (i * i < dimension) {
            ++i;
        }

        if (i * i > dimension) {
            throw new IllegalArgumentException(
                    "The requested sudoku dimension (" + dimension + 
                    ") is not a square of a positive integer.");
        }

        return i;
    }

    private void fixInputSudoku() {
        int dimension = input.getDimension();

        for (int y = 0; y < dimension; ++y) {
            for (int x = 0; x < dimension; ++x) {
                int currentValue = input.get(x, y);

                if (currentValue < 1 || currentValue > dimension) {
                    input.set(x, y, UNUSED);
                }
            }
        }
    }

    private void clearSets() {
        for (int i = 0; i < dimension; ++i) {
            rowSetArray   [i].clear();
            columnSetArray[i].clear();
        }

        for (int y = 0; y < minisquareDimension; ++y) {
            for (int x = 0; x < minisquareDimension; ++x) {
                minisquareSetMatrix[y][x].clear();
            }
        }
    }

    private void tryInitializeSets() {
        for (int y = 0; y < dimension; ++y) {
            for (int x = 0; x < dimension; ++x) {
                int currentValue = input.get(x, y);

                if (rowSetArray[y].contains(currentValue)) {
                    throw new IllegalArgumentException(
                        "The cell (x = " + x + ", y = " + y + ") with " +
                        "value " + currentValue + 
                        " is a duplicate in its row.");
                }

                if (columnSetArray[x].contains(currentValue)) {
                    throw new IllegalArgumentException(
                        "The cell (x = " + x + ", y = " + y + ") with " +
                        "value " + currentValue + 
                        " is a duplicate in its column.");
                }

                loadMinisquareCoordinates(x, y);

                if (minisquareSetMatrix[point.y][point.x].contains(currentValue)) {
                    throw new IllegalArgumentException(
                        "The cell (x = " + x + ", y = " + y + ") with " +
                        "value " + currentValue + 
                        " is a duplicate in its minisquare.");
                }

                if (isValidCellValue(currentValue)) {
                    rowSetArray   [y].add(currentValue);
                    columnSetArray[x].add(currentValue);
                    // This call saves the result in the field 'point'.
                    minisquareSetMatrix[point.y][point.x].add(currentValue);
                }
            }
        }
    }

    private boolean isValidCellValue(int value) {
        return 0 < value && value <= dimension;
    }

    private void loadMinisquareCoordinates(int x, int y) {
        point.x = x / minisquareDimension;
        point.y = y / minisquareDimension;
    }

    private void solve() {
        solve(0, 0);
    }

    private boolean solve(int x, int y) {
        if (x == dimension) {
            // "Carriage return": we are done with row 'y', so move to the row
            // 'y + 1' and set 'x' to zero.
            x = 0;
            ++y;
        }

        if (y == dimension) {
            // We have found a solution, signal success by return 'true'.
            return true;
        }

        if (input.get(x, y) != UNUSED) {
            // Just load a predefined value from the input matrix to solution,
            // and proceed further.
            solution.set(x, y, input.get(x, y));
            return solve(x + 1, y);
        } 

            // Find least number fitting in the current cell (x, y).
        for (int i = 1; i <= dimension; ++i) {
            if (!columnSetArray[x].contains(i)
                    && !rowSetArray[y].contains(i)) {
                loadMinisquareCoordinates(x, y);

                if (!minisquareSetMatrix[point.y][point.x].contains(i)) {
                    solution.set(x, y, i);
                    rowSetArray   [y].add(i);
                    columnSetArray[x].add(i);
                    minisquareSetMatrix[point.y][point.x].add(i);

                    if (solve(x + 1, y)) {
                        // A solution found; stop backtracking by returning
                        // at each recursion level.
                        return true;
                    }

                    // Setting 'i' at current cell (x, y) did not lead towards
                    // solution; remove from the sets and try larger value 
                    // for 'i' in the next iteration.
                    rowSetArray   [y].remove(i);
                    columnSetArray[x].remove(i);

                    // Reload the minisquare coordinates as they are likely to
                    // be invalid due to recursion.
                    loadMinisquareCoordinates(x, y);
                    minisquareSetMatrix[point.y][point.x].remove(i);
                }
            }
        }

        // No number fits at this (x, y), backtrack a little.
        return false;
    }
}

Sudoku.java:

package net.coderodde.sudoku;

/**
 * This class represents a sudoku matrix. It may be of any dimension and may 
 * contain arbitrary values at each cells.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 25, 2016)
 */
public class Sudoku {

    public static final int MINIMUM_DIMENSION = 1;
    private final int[][] matrix;

    public Sudoku(int dimension) {
        checkDimension(dimension);
        this.matrix = new int[dimension][dimension];
    }

    public Sudoku(Sudoku sudoku) {
        this(sudoku.matrix.length);

        for (int y = 0; y < sudoku.matrix.length; ++y) {
            this.matrix[y] = sudoku.matrix[y].clone();
        }
    }

    public int get(int x, int y) {
        return matrix[y][x];
    }

    public void set(int x, int y, int value) {
        matrix[y][x] = value;
    }

    public int getDimension() {
        return matrix.length;
    }

    public boolean isValid() {
        int dimension = getDimension();
        int minisquareDimension = getMinisquareDimension();
        IntSet[] rowSetArray    = new IntSet[dimension];
        IntSet[] columnSetArray = new IntSet[dimension];
        IntSet[][] minisquareSetMatrix = new IntSet[minisquareDimension]
                                                   [minisquareDimension];

        for (int i = 0; i < dimension; ++i) {
            rowSetArray[i]    = new IntSet(dimension + 1);
            columnSetArray[i] = new IntSet(dimension + 1);
        }

        for (int squareY = 0; squareY < minisquareDimension; ++squareY) {
            for (int squareX = 0; squareX < minisquareDimension; ++squareX) {
                minisquareSetMatrix[squareY]
                                   [squareX] = new IntSet(dimension + 1);
            }
        }

        for (int y = 0; y < dimension; ++y) {
            for (int x = 0; x < dimension; ++x) {
                int currentValue = get(x, y);

                if (rowSetArray[y].contains(currentValue)
                        || columnSetArray[x].contains(currentValue)) {
                    return false;
                }

                int squareX = x / minisquareDimension;
                int squareY = y / minisquareDimension;

                if (minisquareSetMatrix[squareY]
                                       [squareX].contains(currentValue)) {
                    return false;
                }
            }
        }

        return true;
    }

    @Override
    public String toString() {
        String maximumCellValueString = "" + matrix.length;
        int fieldLength = maximumCellValueString.length();
        StringBuilder sb = new StringBuilder();

        for (int y = 0; y < matrix.length; ++y) {
            sb.append(rowToString(y, fieldLength));
            sb.append('\n');
        }

        return sb.toString();
    }

    private String rowToString(int y, int fieldLength) {
        StringBuilder sb = new StringBuilder();

        for (int x = 0; x < matrix.length; ++x) {
            sb.append(String.format("%" + fieldLength + "d", get(x, y)));

            if (x < matrix.length - 1) {
                sb.append(' ');
            }
        }

        return sb.toString();
    } 

    private void checkDimension(int dimension) {
        if (dimension < MINIMUM_DIMENSION) {
            throw new IllegalArgumentException(
                    "The input dimension is too low: " + dimension + 
                    ", should be at least " + MINIMUM_DIMENSION + ".");
        } 
    }

    private int getMinisquareDimension() {
        int i = 1;
        int dimension = getDimension();

        while (i * i < dimension) {
            ++i;
        }

        if (i * i > dimension) {
            throw new IllegalStateException(
                    "Impossible to form minisquares: " +
                    "the dimension of this sudoku (" + dimension + ") is not " +
                    "a square of a positive integer");
        }

        return i;
    }
}

IntSet.java:

package net.coderodde.sudoku;

/**
 * This class implements a trivial integer set used for keeping track which 
 * cell values are allowed at each sudoku cell.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 25, 2016)
 */
final class IntSet {

    private final boolean[] table;

    IntSet(int sudokuDimension) {
        this.table = new boolean[sudokuDimension];
    }

    void add(int number) {
        table[number] = true;
    }

    boolean contains(int number) {
        return table[number];
    }

    void remove(int number) {
        table[number] = false;
    }

    void clear() {
        for (int i = 0; i < table.length; ++i) {
            table[i] = false;
        }
    }
}

App.java:

package net.coderodde.sudoku;

import java.util.Scanner;

/**
 * This class implements a command line utility for solving sudokus.
 * 
 * @author Rodion "rodde" Efremov
 * @version 1.6 (Feb 25, 2016)
 */
public class App {

    /**
     * Default dimension of the input sudoku.
     */
    private static final int DEFAULT_DIMENSION = 9;

    private final int dimension;
    private Sudoku inputSudoku;
    private SudokuSolver solver;

    public App(int dimension) {
        this.dimension = dimension;

        try {
            this.inputSudoku = new Sudoku(dimension);
        } catch (IllegalArgumentException ex) {
            System.err.println("ERROR: " + ex.getMessage());
            System.exit(1);
        }
    }

    private void createSolver() {
        this.solver = new SudokuSolver(dimension);
    }

    private void scanDigits() {
        int cellsToScan = dimension * dimension;
        int y = 0;
        int x = 0;

        try (Scanner scanner = new Scanner(System.in)) {
            while (cellsToScan > 0) {
                if (!scanner.hasNextInt()) {
                    break;
                }

                int cellValue = scanner.nextInt();
                inputSudoku.set(x++, y, cellValue);

                if (x == dimension) {
                    x = 0;
                    ++y;
                }

                --cellsToScan;
            }
        }
    }

    private void solve() {
        System.out.println("[Input sudoku]");
        System.out.println(inputSudoku);

        try {
            long startTime = System.nanoTime();
            Sudoku solution = solver.solve(inputSudoku);
            long endTime = System.nanoTime();

            if (!solution.isValid()) {
                throw new IllegalStateException(
                        "ERROR: The computed solution is not valid.");
            }

            System.out.println("[Solution]");
            System.out.println(solution);
            System.out.printf("Solution took %.2f milliseconds.\n", 
                              (endTime - startTime) / 1e6);
        } catch (Exception ex) {
            System.err.println("ERROR: " + ex.getMessage());
            System.exit(1);
        }
    }

    public static void main(String[] args) {
        int requestedDimension = getDimension(args);
        App app = new App(requestedDimension);

        try {
            app.createSolver();
        } catch (IllegalArgumentException ex) {
            System.err.println("ERROR: " + ex.getMessage());
            System.exit(1);
        }

        app.scanDigits();
        app.solve();
    }

    private static int getDimension(String[] args) {
        int dimension = DEFAULT_DIMENSION;

        if (args.length > 0) {
            try {
                dimension = Integer.parseInt(args[0]);
            } catch (NumberFormatException ex) {
                System.err.println(
                        "ERROR: \"" + args[0] + "\" is not an integer.");
                System.exit(1);
            }
        }

        return dimension;
    }
}

Usage guidance

In order to solve your sudokus, you could start the program and input the matrix at the command line. A better approach is to save your source sudoku into a file sudoku.txt:

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

and type cat sudoku.txt | java -jar YOUR.jar 9 (It can handle any square sudoku of dimension \$n\$ if \$n = m^2\$, where \$m\$ is a positive integer; \$n = 1, 4, 9, 16, 25, ....\$.)

Critique request

Please, tell me anything that comes to mind.

\$\endgroup\$
  • 2
    \$\begingroup\$ Many of your methods could (and should) be declared static (e.g. checkDimension). And the int i = 1; should be a constant instead of 1 (it is the square root of MINIMUM_DIMENSION as far as I can see, so probably MINIMUM_DIMENSION should be declared in terms of this new constant instead) \$\endgroup\$ – Hulk Feb 26 '16 at 6:50
5
\$\begingroup\$

Use java functions instead of reinventing the wheel

    int i = 1;
    while (i * i < dimension) {
        ++i;
    }

There is a java function for this, Math.sqrt() when using a while loop like that people need to realize its just a home made implementation of the mentioned function.

int i = (int)math.sqrt(dimension);

Don't shut the program done on invalid input

        try {
            dimension = Integer.parseInt(args[0]);
        } catch (NumberFormatException ex) {
            System.err.println(
                    "ERROR: \"" + args[0] + "\" is not an integer.");
            System.exit(1);
        }

Provided you wanted to reuse this piece of code in an environment where java solves multiple sudoku's in parallel, if at least 1 input file is invalid, then the whole java process will be killed. Instead, throw the exception back to the caller, so it can deal with it, using a custom (checked) exception even makes it more clear that the caller can expect that some input files are invalid.

Again, dont reinvent the wheel

final class IntSet {

You define your own class for keeping boolean constants, java already has this class since version 1.6, its called BitSet

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

Choose better names for functions

private int checkDimension(int dimension) - this function does not "check dimension". It returns the size of minisquares! So name it calculateMiniSquareDimension(int largeSquareDimension). Maybe shortcut Dim for Dimension will be OK.

Avoid class envy

function void fixInputSudoku() works on fields of input object (by using get and set). It is better to move this function to class Sudoku therefore.

\$\endgroup\$

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.