6
\$\begingroup\$

I created a Sudoku game with varied difficulty level.

The Sudoku board creation process consist three stages:

  1. Creation of an empty board
  2. Filling the board with numbers
  3. Making holes in the filled game board

The assigned numbers fulfill all Sudoku game conditions, and every puzzle has a unique solution (verified in the creation process).

There are also 5 levels of difficulty: very easy, easy, moderate, hard and very hard. The creation algorithms for the different levels are loosely based on this document. To get varied difficulty, I set different numbers of blank cells and use different orders of iteration through game boards cells during board creation (at making holes stage).

Demonstration versions:

The whole code is in one class to make it easy to run, if someone is curious and would like to. But it is not my real implementation, which is of course divided into separate classes as below (here without GUI).

Creator:

/**
 * Creates a Sudoku game board according to given parameters.
 */
public class Creator {
    private Solver solver;
    private Board board;
    private List<Cell> blankCells;
    private int limit;

    public Creator() {
        solver = new Solver();
    }

    public Board create(Level level) {
        board = new Board();
        getFullBoard();
        saveSolution();
        randomizeBlankCellPositions(level);
        generateBlankCells(level.getBlankCellsNumber(), level.getIterationType());
        board.save();
        return board;
    }

    /**
     * @return a value of limit for blank cells for given Sudoku board.
     */
    public int getLimit() {
        return limit;
    }

    /**
     * @return Board object recently created by Creator.
     */
    public Board getBoard(){
        return board;
    }

    /**
     * Generates game board full of numbers.
     */
    private void getFullBoard() {
        solver.setBoard(board).solve(board.getCells(), 1);
    }


    /**
     * Iterates through all Cell of given board, and call setSolution() method, to save solution for future comparing
     * to user input.
     */
    private void saveSolution(){
        for(Cell cell : board){
            cell.setSolution();
        }
    }

    /**
     * It is used before generateBlankCells() method in cases when S-like iteration type is used with number of blank
     * Cells lower or near the half of Cells number. This prevents the game board to be unevenly distributed on board.
     * @param level which determines iteration type.
     */
    private void randomizeBlankCellPositions(Level level) {
        if(level.equals(Level.MODERATE) || level.equals(Level.HARD)) {
            generateBlankCells(30, Iteration.RANDOM);
        }
    }

    /**
     * Generates a blank Cells in full Sudoku game board.
     * @param limit number of blank cells given puzzle should have.
     * @param iteration used iteration type through Boards cells.
     */
    public void generateBlankCells(int limit, Iteration iteration) {
        this.limit = limit;
        board.setIterationOrder(iteration);
        ListIterator<Cell> iterator = board.iterator();
        board.save();

        while (iterator.hasNext()) {
            Cell current = iterator.next();
            current.save();


            if (!current.isBlank()) {
                current.setValue(0);
            } else {
                continue;
            }

            solver.setBoard(board);
            blankCells = getBlankCells(board);
            if(isOutOfLimits(limit)) {
                break;
            }

            if (hasMoreThanOneSolution(blankCells)) {
                board.load();
            } else {
                current.save();
            }
        }
        board.setIterationOrder(Iteration.LINEAR);
    }

    /**
     * Determines when there is too many number of solution for given type of task.
     * @param limit restraining value.
     * @return true if there is more or equal number of blank Cells in caparison to demanded fo given difficulty level,
     */
    public boolean isOutOfLimits(int limit) {
        return blankCells.size() >= limit;
    }

    /**
     * @param blanks List of blank Cells, which combination with hint numbers, is tested for solution uniqueness.
     * @return true if given set of values has one solution.
     */
    private boolean hasMoreThanOneSolution(List<Cell> blanks) {
        return solver.solve(blanks, 3) != 1;
    }

    /**
     * @param board Sudoku game board.
     * @return List of blank Cells in given Board.
     */
    public static List<Cell> getBlankCells(Board board) {
        List<Cell> blank = new ArrayList<Cell>();
        for(Cell cell : board) {
            if(cell.isBlank()) {
                blank.add(cell);
            }
        }
        return blank;
    }
}

Cell:

/**
 * The smallest separate Element of Sudoku game board, which holds a value from range 1-9 or is blank (value is 0).
 */
public class Cell{
    final private int row;
    final private int column;
    final private int block;
    private int value;
    private int save;
    private int solution;

    public Cell(int row, int column) {
        this.row = row;
        this.column = column;
        block = specifyBlock();
    }

    /**
     * @return row in which given cell is placed on Sudoku board
     */
    public int getRow() {
        return row;
    }

    /**
     * @return column in which given cell is placed on Sudoku board
     */
    public int getColumn() {
        return column;
    }

    /**
     *
     * @param value which the given cell will hold.
     */
    public void setValue(int value) {
        this.value = value;
    }

    /**
     * @return Value currently held by the given Cell object.
     */
    public int getValue() {
        return  value;
    }

    /**
     * @return a integer from range 1-9, which identify in which block of Sudoku game board the given Cell
     * object is placed.
     */
    public int getBlock() {
        return block;
    }

    /**
     * Verifies if value of given Cell object is blank (equal to 0).
     * @return true if value of Cell is 0.
     */
    public boolean isBlank() {
        return value==0;
    }

    /**
     * Saves the value of the given cell for future use. The value is saved until next usage of this method.
     */
    public void save() {
        save = value;
    }

    /**
     * Retrieves the value saved by save() method. It does not affect the stored value.
     */
    public void load() {
        value = save;
    }

    /**
     * Save a value which is solution for given Cell in particular game board for future use.
     */
    public void setSolution(){
        solution = value;
    }

    /**
     * Retrieves saved value as solution.
     * @return value which is solution for given Cell.
     */
    public int getSolution(){
        return solution;
    }
    /**
     * @return value currently held by the given cell.
     */
    @Override
    public String toString() {
        return String.valueOf(getValue());
    }

    /**
     * Compares two objects of Cell class.
     * @param obj object to which given Cell object is compared.
     * @return Returns true if both Cells have same value,  row and column field values, or false if compare
     * Cell objects have different values or one or both objects are null.
     */
    @Override
    public boolean equals(Object obj) {
        return obj != null && obj.getClass() == this.getClass() && ((Cell) obj).getValue() == this.getValue() &&
                ((Cell) obj).getRow() == this.getRow() && ((Cell) obj).getColumn() == this.getColumn();
    }

    /**
     * @return block of Sudoku game board, to which given Cell belongs.
     */
    public int specifyBlock() {
        int x = row /3;
        int y = column /3;
        int modifier = row <3 ? 0 : row <6 ? 2 : 4;
        return x+y+modifier;
    }
}

Board:

/**
 * Sudoku game board composed of Cell objects.
 */
public class Board implements Iterable<Cell>, Cloneable {

    final private Cell[][] grid;
    final private List<List<Cell>> blocks;
    final private List<Cell> cells;
    private Iteration iteration = Iteration.LINEAR;

    public Board() {
        grid = new Cell[9][9];
        blocks = createBlocks(9);
        cells = new ArrayList<Cell>(81);
        createCells();
    }

    /**
     * @return List of Cells objects of given game board.
     */
    public List<Cell> getCells() {
        return cells;
    }

    /**
     * @return List of Lists of Cells, which are grouping Cells by it position within board blocks.
     */
    public List<List<Cell>> getBlocks() { return blocks; }

    /**
     * Set type of iteration through Boards cells. It use Iteration enum class objects.
     * @param order Iteration enum type object assigned to given iteration type.
     */
    public void setIterationOrder(Iteration order) {
        iteration = order;
    }

    /**
     * Creates 2D array of Cells object, which make game board.
     */
    public void createCells() {
        for(int row = 0; row < 9; row++) {
            for(int col = 0; col < 9; col++) {
                Cell cell = new Cell(row,col);
                grid[row][col] = cell;
                cells.add(cell);
                blocks.get(cell.getBlock()).add(cell);
            }
        }
    }

    /**
     * It tests all three game conditions for particular Cell and value.
     * @param cell given Cell.
     * @param value which wil be assigned to Cell if it fulfills all conditions.
     * @return true if value in given Cell fulfills all three game conditions.
     */
    public boolean testConditions(Cell cell, int value) {
        return testBlock(cell, value) && testColumn(cell.getColumn(), value) && testRow(cell.getRow(), value);
    }

    /**
     * It tests if given value is unique in given game board row.
     * @param row checked row.
     * @param value tested value.
     * @return true if value is unique in given row.
     */
    private boolean testRow(int row, int value) {
        for(Cell cell : grid[row]) {
            if(value == cell.getValue()) return false;
        }
        return true;
    }

    /**
     * It tests if given value is unique in given game board column.
     * @param column checked column.
     * @param value tested value.
     * @return true if value is unique in given column.
     */
    private boolean testColumn(int column, int value) {
        for(Cell[] cells : grid) {
            if(value == cells[column].getValue()) return false;
        }
        return true;
    }

    /**
     * It tests if given value is unique in given game board block (3 x 3 Cells group).
     * @param testedCell tested Cell.
     * @param value tested value.
     * @return true if value is unique in given block.
     */
    private boolean testBlock(Cell testedCell, int value) {
        for(Cell cell : blocks.get(testedCell.getBlock())) {
            if(cell.getValue() == value) {
                return false;
            }
        }
        return true;
    }

    /**
     * Calls save() method on every Cell within Board.
     */
    public void save() {
        for(Cell cell : this) {
            cell.save();
        }
    }

    /**
     * Calls load() method on every Cell within Board.
     */
    public void load() {
        for (Cell cell : this) {
            cell.load();
        }
    }

    /**
     * @return ListIterator of random order List of all Cells of a given Board.
     */
    private ListIterator<Cell> randomOrderIterator() {
        ArrayList<Cell> randomOrder = new ArrayList<Cell>(cells);
        Collections.shuffle(randomOrder);
        return randomOrder.listIterator();
    }

    /**
     * @return ListIterator of sequential order List of all Cells of a given Board.
     */
    private ListIterator<Cell> linearOrderIterator() {
        return cells.listIterator();
    }

    /**
     * @return ListIterator of S-like order List of all Cells of a given Board.
     */
    private ListIterator<Cell> sLikeOrderIterator() {
        return s_LikeList().listIterator();
    }

    /**
     * @return ListIterator object of given Board object with set iteration order.
     */
    @Override
    public ListIterator<Cell> iterator() {
        switch (iteration) {
            case LINEAR:
                return linearOrderIterator();
            case RANDOM:
                return randomOrderIterator();
            case S_LIKE:
                return sLikeOrderIterator();
            default:
                return linearOrderIterator();
        }
    }

    /**
     * @return String contains all values of Cells within given Board.
     */
    @Override
    public String toString() {
        String result = "";
        for(int i = 0; i < 9; i++) {
            for(int j = 0; j < 9; j++) {
                result += grid[i][j].toString() + ",";
            }
            result += "\n";
        }
        return result;
    }

    /**
     * Creates the List of Lists of Cells of given Board.
     * @param capacity number of Cells in given Sudoku game board.
     * @return List of Lists of Cells assigned to specific blocks.
     */
    public List<List<Cell>> createBlocks(int capacity) {
        List<List<Cell>> list = new ArrayList<List<Cell>>(capacity);
        for(int i = 0; i < capacity; i++) {
            list.add(new ArrayList<Cell>());
        }
        return list;
    }

    /**
     * Using a 2D Cell array containing all Cell objects of given Sudoku game board, this method crates List of
     * same elements with changed order, which allows to iterate through Sudoku game board in S-like order.
     * @return List of Cells of given game board with changed order.
     */
    public List<Cell> s_LikeList() {
        List<Cell> sShape = new ArrayList<Cell>();
        List<Cell> temp;
        for(int i = 0; i < 9; i++) {
            if((i+1)%2==0) {
                temp = new ArrayList<Cell>(Arrays.asList(grid[i]));
                Collections.reverse(temp);
                sShape.addAll(temp);
            } else {
                sShape.addAll(Arrays.asList(grid[i]));
            }
        }
        return sShape;
    }

}

Solver:

/**
 * Solver object solves a given Sudoku board. It is used in stage of filling an empty Sudoku board with digits,
 * in verifying the uniqueness of solution and in checking a solution given by User.
 */
public class Solver {
    private Board board;
    private int count = 0;
    int index = 0;

    public Solver setBoard(Board board){
        this.board = board;
        count = 0;
        index = 0;
        return this;
    }

    /**
     * Recursive and backtracking method, which fills up the empty or partially solved Sudoku game board. It puts
     * a digit into the blank Cell objects, if it pass the game conditions. If there is no such value, it backtrace
     * to the last filled Cell object, which value could be changed. In effect it creates or solves a Sudoku puzzle.
     * @param blankCells List of blank Cell objects from given Sudoku game board.
     * @param limit randomly selected number of blank Cells the Sudoku board on given difficulty level could have.
     * @return the number of found solutions.
     */
    public int solve(List<Cell> blankCells, int limit){
        if(index < blankCells.size()){
            for(int i : randomOrderDigits()){
                if(testValue(blankCells.get(index), i)){
                    index += 1;
                    if(solve(blankCells, limit)>= limit){
                        return count;
                    }
                }
            }
            return backtrace(blankCells);
        } else {
            return finish();
        }
    }

    /**
     * Part of solve() method responsible for decrease of specified variables, what effects in backtracking during the
     * solve() method execution. It returns a same value as the salve() method, because if there is no more solutions
     * for given game board, and therefore solve() method would be terminated, it still returns counted number of
     * found solutions.
     * @param cells List of blank Cell objects from given Sudoku game board.
     * @return the number of found solution.
     */
    private int backtrace(List<Cell> cells){
        cells.get(index).setValue(0);
        index -= 1;
        return count;
    }

    /**
     * Increases the value of variable which holds the number of found solutions, and begin a backtracking process,
     * after the solve() method reaches a valid solution for the given game board. It returns a same value as the
     * salve() method, because if there is no more solutions for given game board, and therefore solve() method would
     * be terminated, it still returns counted number of found solutions.
     * @return the number of found solution.
     */
    public int finish(){
        count++;
        index -= 1;
        return count;
    }

    /**
     * Tests the game conditions for a given Cell object and value.
     * @param cell the tested Cell object.
     * @param i value which could be potentially placed in the given Cell object.
     * @return true if the Call with the given value fulfill the game conditions.
     */
    private boolean testValue(Cell cell, int i) {
        if (!board.testConditions(cell, i)) {
            return false;
        } else{
            cell.setValue(i);
            return true;
        }
    }

    /**
     * @return return a List containing a digits (without 0) in random order.
     */
    public List<Integer> randomOrderDigits() {
        List<Integer> values = new ArrayList<Integer>();
        for(int i = 1; i <= 9; i++) {
            values.add(i);
        }
        Collections.shuffle(values);
        return values;
    }
}

Level:

/**
 * Enum class for difficulty levels. Its min and max fields set a range, from which the number of blank cells
 * is randomly selected.
 */
public enum Level {

    VERY_EASY(28,30,Iteration.RANDOM),
    EASY(31,44,Iteration.RANDOM),
    MODERATE(45,49,Iteration.S_LIKE),
    HARD(49,54,Iteration.S_LIKE),
    VERY_HARD(55,61,Iteration.LINEAR);

    private final int min;
    private final int max;
    private final Iteration iterationType;

    Level(int min, int max, Iteration iterationType) {
        this.min = min;
        this.max = max;
        this.iterationType = iterationType;
    }

    /**
     * It causes a differentiation of number of blank cells in game boards on the same difficulty level,
     * in separate games.
     * @return random number from range from minimal to maximal number of blank cells for given difficulty level.
     */
    public int getBlankCellsNumber(){
        return new Random().nextInt((max - min) + 1) + min;
    }

    /**
     * @return a iteration type used in creation of game boards on given difficulty level.
     */
    public Iteration getIterationType(){
        return iterationType;
    }
}

Iteration:

/**
 * Enum class for types of iterating through cells of given Sudoku board. The different types of iteration are
 * used during creation of game boards of varied difficulty.
 */

public enum Iteration {
    LINEAR, RANDOM, S_LIKE;
}

I would like a review of my code, or any comments at all. I would also like any hints on making my algorithm faster, as for hard levels, creating a board could take sometimes even ~10 sec.

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

Creating a board

The current flow of creating a board via Creator.create(Level) looks like this:

public Creator() {
    solver = new Solver();
}

public Board create(Level level) {
    board = new Board();
    getFullBoard();
    saveSolution();
    // ...
    board.save();
    return board;
}

private void getFullBoard() {
    solver.setBoard(board).solve(board.getCells(), 1);
}

private void saveSolution(){
    for(Cell cell : board){
        cell.setSolution();
    }
}

// from Board
public void save() {
    for(Cell cell : this) {
        cell.save();
    }
}

Computation logic aside, this seems like a long-winded way of solving, saving and returning the created Board.

For starters, calling create(Level) multiple times will override the board class variable every time, is this the desired approach? If one Creator instance can generate multiple Boards, then perhaps it will be better for board to made as a in-method variable, and have it passed around. However, if there should only be one Board per Creator instance, then you need to check that you are not re-creating a Board every time create(Level) is called.

The following two steps, getFullBoard() and saveSolution() seem to depend on the assumption that board must be referenced already. Again, you may want to consider whether you want to make board a method argument for them. It might be clearer from the method signatures, but if you more comfortable with ensuring board is properly instantiated as a class variable, then that works too.

It is also not clear-cut to grasp what exactly is going on in these few lines. If I were to read them literally (bearing in mind this is skipping the randomizing + generating blank cells, which sounds odd too):

  1. Getting a full board involves setting the board to the solver, and then solving the cells (as another method call).
  2. Then, save the solution by setting the solution per board cell.
  3. Finally, save the board by saving each cell.

You can consider either restructuring how the method calls are made, and even the names themselves...

equals() comparison

public boolean equals(Object obj) {
    return obj != null && obj.getClass() == this.getClass() && ((Cell) obj) /* ... */ &&
            ((Cell) obj).getRow() == this.getRow() && ((Cell) obj) /* ... */;
}

This is one of the few places where you may want to use a temporary variable, and employ the help of line formatting:

public boolean equals(Object obj) {
    if (obj == this) {
        return true;
    }
    if (!(obj instanceof Cell)) {
        return false;
    }
    Cell o = (Cell) obj;
    return o.getValue() == getValue() &&
            o.getRow() == getRow() &&
            o.getColumn() == getColumn();
}

Another style that I have come across is to provide an equals(Cell) method:

public boolean equals(Object obj) {
    return obj == this || (obj instanceof Cell && equals((Cell) obj));
}

public boolean equals(Cell obj) {
    return obj == this || 
            (obj.getValue() == getValue() &&
            obj.getRow() == getRow() &&
            obj.getColumn() == getColumn());
}

BTW, consider making your Cell class final?

Declaration ordering

final private ...
private final ...

Please be consistent. :)

Java 8?

If you happen to be on Java 8, some of your for-loops can be simplified using the Stream-based processing, or even to use the new Iterable.forEach(Consumer) method.

For example, in Creator.getBlankCells(Board):

public static List<Cell> getBlankCells(Board board) {
    List<Cell> list = new ArrayList<Cell>();
    board.forEach(c -> { if (c.isBlank()) { list.add(c); }});
    return list;
}

And for Board.toString():

public String toString() {
    return Arrays.stream(grid)
            .map(r -> Arrays.stream(r).mapToObj(String::valueOf)
                            .collect(Collectors.joining(",")))
            .collect(Collectors.joining("\n"));
}
\$\endgroup\$
3
\$\begingroup\$
public int getBlankCellsNumber(){
    return new Random().nextInt((max - min) + 1) + min;
}

The problem here is that introducing random numbers into your routines makes it very difficult to produce deterministic outcomes for automated tests.

At a minimum, you want to be able to control the seed of the random number generator in your tests, so this code should instead look like

public int getBlankCellsNumber(Random random){
    return random.nextInt((max - min) + 1) + min;
}

Here's the same problem, wearing a different mask

public List<Integer> randomOrderDigits() {
    List<Integer> values = new ArrayList<Integer>();
    for(int i = 1; i <= 9; i++) {
        values.add(i);
    }
    Collections.shuffle(values);
    return values;
}

Collections.shuffle(List<T>) has a twin brother Collections.shuffle(List<T>, Random) that you should use instead.

public List<Integer> randomOrderDigits(Random random) {
    List<Integer> values = new ArrayList<Integer>();
    for(int i = 1; i <= 9; i++) {
        values.add(i);
    }
    Collections.shuffle(values, random);
    return values;
}

This next variation is a little bit harder -- the method is private, and test code doesn't normally have access to private methods.

private ListIterator<Cell> randomOrderIterator() {
    ArrayList<Cell> randomOrder = new ArrayList<Cell>(cells);
    Collections.shuffle(randomOrder);
    return randomOrder.listIterator();
}

If we look at the bigger picture, we can see a larger problem....

@Override
public ListIterator<Cell> iterator() {
    switch (iteration) {
        case LINEAR:
            return linearOrderIterator();
        case RANDOM:
            return randomOrderIterator();
        case S_LIKE:
            return sLikeOrderIterator();
        default:
            return linearOrderIterator();
    }
}

The code smell here is that you are using a switch statement to specify behavior. Specifying behavior is what objects are for. In the case of randomOrderIterator, the behavior is creating an object (a List, and then an Iterator referencing the list. That calls for a factory....

interface CellIteratorFactory {
    ListIterator<Cell> create(List<Cell> cells);
}

So the board looks up which factory to use, and then delegates to the factory the work of creating the iterator. You could do that trivially

@Override
public ListIterator<Cell> iterator() {
    CellIteratorFactory factory = new LinearCellIteratorFactory();
    switch (iteration) {
        case RANDOM:
            return new RandomCellIteratorFactory();
        case S_LIKE:
            return SLikeOrderCellIteratorFactory();
    }

    return factory.create(this.cells);
}

The problem with this approach is that your SLike implementation takes a Cell[][] instead of a List<Cell>. Which is kind of weird -- why are using a completely different collection of cells in the SLike case?

public void createCells() {
    for(int row = 0; row < 9; row++) {
        for(int col = 0; col < 9; col++) {
            Cell cell = new Cell(row,col);
            grid[row][col] = cell;
            cells.add(cell);
            blocks.get(cell.getBlock()).add(cell);
        }
    }
}

Oh! it's a different collection of the same cells. A better approach here is to recognize that there's really just one collection of cells, with multiple ways of accessing it. You need adapters -- a GridAdapter that knows how to math a (row,col) tuple to the correct position in the list, and a BlockAdapter that performs similar math for blocks.

With the adapters available, SLikeOrderCellIteratorFactory.create is not implementable; it accepts List<Cell> as an argument, slaps a GridAdapter around the list, and then let's the adapter calculate the cells that it needs.

(Of course, it might be easier to simply pre-calculate the array indexes in slike order, and build the new collection by copying the cells one at a time, using the fixed template).

The point to all of this refactoring: once you've got factories in place, controlling the randomness needed by the factory is as simple as assigning the correct RNG in the constructor

class RandomCellIteratorFactory {
    private final Random random;

    RandomCellIteratorFactory(Random random) {
        this.random = random;
    }

    ListIterator<Cell> create(List<Cell> cells) {
        ArrayList<Cell> randomOrder = new ArrayList<Cell>(cells);
        Collections.shuffle(randomOrder, this.random);
        return randomOrder.listIterator();
    }
}
\$\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.