不同难度的数独游戏

Question

我创造了一个不同难度的数独游戏。

数独董事会的创建过程分为三个阶段：

1. 创建一个空板
2. 在黑板上塞满号码
3. 在满满的棋盘上打洞

分配的数字满足所有Sudoku游戏条件，每个谜题都有一个唯一的解决方案(在创建过程中得到验证)。

也有五个层次的困难:非常容易，容易，适度，困难和非常困难。不同层次的创建算法都是基于本文件的松散的。为了获得不同的难度，我设置了不同数量的空白单元格，并在棋盘创建过程中(在造洞阶段)使用不同的迭代顺序。

示范版本：

• 不同级别的板创建(控制台)
• 全GUI实现

如果有人好奇并且愿意的话，整个代码都在一个类中，这样可以方便地运行。但这并不是我真正的实现，它当然是按下面的方式分为不同的类(这里没有GUI)。

创建者：

/**
 * 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;
    }
}

牢房：

/**
 * 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;
    }
}

董事会：

/**
 * 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 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;
    }
}

级别：

/**
 * 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;
    }
}

迭代：

/**
 * 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;
}

我想回顾一下我的代码，或者任何评论。我也希望任何提示，使我的算法更快，如硬水平，创建一个板有时甚至需要10秒。

Answer 1

创建一个板

通过Creator.create(Level)创建板的当前流程如下所示：

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();
    }
}

撇开计算逻辑不说，这似乎是解决、保存和返回创建的Board的一种冗长的方法。

首先，每次多次调用create(Level)将覆盖board类变量，这是所需的方法吗？如果一个Creator实例可以生成多个Boards，那么board最好将其作为一个方法中的变量，并让它四处传递。但是，如果每个Board实例只有一个Creator，那么您需要检查是否每次调用create(Level)时都要重新创建Board。

下面两个步骤，getFullBoard()和saveSolution()似乎依赖于必须已经引用board的假设。同样，您可能需要考虑是否要将board作为它们的方法参数。从方法签名中可以更清楚地看出，但是如果您更习惯于确保将board正确实例化为类变量，那么这也是可行的。

也不清楚这几行到底是怎么回事。如果我要逐字逐句地阅读它们(请记住，这是跳过随机+生成空白单元，这听起来也很奇怪)：

1. 获得一个完整的板需要将板设置为求解器，然后求解单元格(作为另一种方法调用)。
2. 然后，通过将解决方案设置为每个板单元来保存解决方案。
3. 最后，通过保存每个单元来保存板。

您可以考虑重新构造方法调用的方式，甚至是名称本身。

equals()比较

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

这是您可能希望使用临时变量并使用行格式帮助的少数几个位置之一：

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();
}

我遇到的另一种样式是提供一个equals(Cell)方法：

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());
}

顺便说一句，考虑让您的Cell类final吗？

声明排序

final private ...
private final ...

请保持一致。:)

Java 8?

如果您碰巧在Java 8上，可以使用for-loops处理Stream-based，甚至可以使用新的Iterable.forEach(Consumer)方法来简化一些-based。

例如，在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;
}

对于Board.toString()：

public String toString() {
    return Arrays.stream(grid)
            .map(r -> Arrays.stream(r).mapToObj(String::valueOf)
                            .collect(Collectors.joining(",")))
            .collect(Collectors.joining("\n"));
}

Answer 2

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

这里的问题是，在例程中引入随机数会使自动测试很难产生确定性的结果。

至少，您希望能够在测试中控制随机数生成器的种子，因此下面的代码应该如下所示

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

同样的问题，戴着不同的面具

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>)有一个孪生兄弟Collections.shuffle(List<T>, Random)，您应该使用它。

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;
}

下一个版本有点难--这个方法是私有的，测试代码通常不能访问私有方法。

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

如果我们从更大的角度看，我们可以看到一个更大的问题.

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

这里的代码味道是，您正在使用switch语句来指定行为。指定行为是对象的作用。对于randomOrderIterator，行为是创建一个对象( List，然后是引用列表的Iterator )。需要一个工厂..。

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

因此，董事会查找要使用哪个工厂，然后将创建迭代器的工作委托给工厂。你可以做些小事

@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);
}

这种方法的问题在于，您的SLike实现采用的是Cell[][]而不是List<Cell>。为什么在SLike案例中使用一个完全不同的单元格集合？

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);
        }
    }
}

噢!这是同一组细胞的不同集合。这里有一种更好的方法，就是认识到实际上只有一个单元格集合，有多种方法访问它。您需要适配器--一个知道如何将(行、行)元组计算到列表中正确位置的GridAdapter，以及一个对块执行类似运算的BlockAdapter。

有了可用的适配器，SLikeOrderCellIteratorFactory.create是不可实现的；它接受List<Cell>作为参数，在列表周围放置一个GridAdapter，然后让适配器计算它需要的单元格。

(当然，简单地按类似one的顺序预先计算数组索引，并使用固定的模板一次复制一个单元格来构建新集合可能更容易)。

所有这些重构的要点:一旦工厂就位，控制工厂所需的随机性就像在构造函数中分配正确的RNG一样简单

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();
    }
}