Java中的Sudoku Solver

Question

这是一份张贴在这里上的作业。

这是我第一次尝试OO。这个设计可以吗？或者有什么非常不对劲的地方，我一点也没看到。任何建议都是最受欢迎和最需要的。

import java.util.*;

/*
 * Encapsulates a Sudoku grid to be solved.
 * This project is based on the assignment given in CS108 Stanford.
 */
public class Sudoku {

    /* "Spot" inner class that represents a single spot
     * on the grid of the Sudoku game.
     * Each Spot object knows its place on the Sudoku grid as
     * it stores the row and column number as fields.
     */
    private class Spot implements Comparable<Spot> {

        /* Properties/fields of each individual Spot */
        private int row, col;
        private int value;
        private int part;

        /* Stores all possible values for a Spot that is empty
         * according to the rules of the game */
        private HashSet<Integer> possibleValues;

        Spot(int x, int y, int val) {
            row = x;
            col = y;
            value = val;
            part = getPart(x, y);

            possibleValues = new HashSet<>();
        }

        Spot(Spot s) {
            this(s.row, s.col, s.value);
            part = s.part;
            possibleValues = new HashSet<>(s.possibleValues);
        }

        /* Sets the value for this Spot on the Solution Grid (solutionGrid) */
        void setValue(int val) {
            value = val;
        }

        /* Returns the value of this Spot */
        int getValue() {
            return value;
        }

        /* Returns the part of the grid where this Spot belongs */
        int getPartForSpot() {
            return part;
        }

        /* Returns true iff this Spot is not filled */
        boolean isEmpty() {
            return value == 0;
        }

        /* Returns a HashSet of all legal values that can be 
         * filled in this Spot.
         */
        HashSet<Integer> getPossibleValues() {
            if (value != 0) return null;

            /* temporarily assign all 9 numbers */
            for (int i = 1; i <= Sudoku.SIZE; i++)
                possibleValues.add(i);

            /* Remove all the values that cannot be placed at this Spot */
            possibleValues.removeAll(valInRows.get(row));
            possibleValues.removeAll(valInCols.get(col));
            possibleValues.removeAll(valInParts.get(part));
            return possibleValues;
        }

        /* Updates the Spot on the solution grid with the row and col of 
         * this Spot with the current value that this spot holds.
         */
        public void updateValueInGrid() {
            solutionGrid[row][col].value = value;
        }

        public int getRow() {
            return row;
        }

        public int getCol() {
            return col;
        }

        @Override
        public int compareTo(Spot that) {
            return this.possibleValues.size() - that.possibleValues.size();
        }

        @Override
        public boolean equals(Object o) {
            if (o == null) return false;
            if (!(o instanceof Spot)) return false;

            Spot that = (Spot) o;
            return this.row == that.row && this.col == that.col;
        }

        @Override
        public int hashCode() {
            return possibleValues.size() * 25;
        }

        @Override
        public String toString() {
            return value + "";
        }

        /* Helper method that returns the Part in which the 
         * coordinates x and y belong on the grid. 
         */
        private int getPart(int x, int y) {
            if (x < 3) {
                if (y < 3) return PART1;
                else if (y < 6) return PART4;
                else return PART7;
            }
            if (x < 6) {
                if (y < 3) return PART2;
                else if (y < 6) return PART5;
                else return PART8;
            }
            else {
                if (y < 3) return PART3;
                else if (y < 6) return PART6;
                else return PART9;
            }   
        }
    } // End of Spot class

    /* Member variables for the puzzle and solution grids */
    private Spot[][] puzzleGrid;
    private Spot[][] solutionGrid;

    /* List of all the possible solutions for the puzzle represented as
     * an ArrayList of only the Spots that needed to be filled with a 
     * solution */
    private List<ArrayList<Spot>> solutions;

    /* The ivars to store the current State of the Grid.
     * valInRows:- has a HashSet at each index that stores all the filled
     * in values for that particular row
     * valInCols:- Same as valInRows but for the columns
     * valInParts:- For the 3x3 parts of the grid */
    private ArrayList<HashSet<Integer>> valInRows, valInCols, valInParts;

    private long timeTakenForSolution;

    /* Parts of the grid each of size 3x3. Counting from the
     * top left to top right then the next row below.
     * 0 1 2
     * 3 4 5
     * 6 7 8
     */
    private static final int PART1 = 0;
    private static final int PART2 = 1;
    private static final int PART3 = 2;
    private static final int PART4 = 3;
    private static final int PART5 = 4;
    private static final int PART6 = 5;
    private static final int PART7 = 6;
    private static final int PART8 = 7;
    private static final int PART9 = 8;

    // Provided easy 1 6 grid
    public static final int[][] easyGrid = Sudoku.stringsToGrid(
    "1 6 4 0 0 0 0 0 2",
    "2 0 0 4 0 3 9 1 0",
    "0 0 5 0 8 0 4 0 7",
    "0 9 0 0 0 6 5 0 0",
    "5 0 0 1 0 2 0 0 8",
    "0 0 8 9 0 0 0 3 0",
    "8 0 9 0 4 0 2 0 0",
    "0 7 3 5 0 9 0 0 1",
    "4 0 0 0 0 0 6 7 9");


    // Provided medium 5 3 grid
    public static final int[][] mediumGrid = Sudoku.stringsToGrid(
     "530070000",
     "600195000",
     "098000060",
     "800060003",
     "400803001",
     "700020006",
     "060000280",
     "000419005",
     "000080079");

    // Provided hard 3 7 grid
    // 1 solution this way, 6 solutions if the 7 is changed to 0
    public static final int[][] hardGrid = Sudoku.stringsToGrid(
    "3 7 0 0 0 0 0 8 0",
    "0 0 1 0 9 3 0 0 0",
    "0 4 0 7 8 0 0 0 3",
    "0 9 3 8 0 0 0 1 2",
    "0 0 0 0 4 0 0 0 0",
    "5 2 0 0 0 6 7 9 0",
    "6 0 0 0 2 1 0 4 0",
    "0 0 0 5 3 0 9 0 0",
    "0 3 0 0 0 0 0 5 1");



    public static final int SIZE = 9;  // size of the whole 9x9 puzzle
    public static final int PART = 3;  // size of each 3x3 part
    public static final int MAX_SOLUTIONS = 100;

    // Provided various static utility methods to
    // convert data formats to int[][] grid.

    /**
     * Returns a 2-d grid parsed from strings, one string per row.
     * The "..." is a Java 5 feature that essentially
     * makes "rows" a String[] array.
     * (provided utility)
     * @param rows array of row strings
     * @return grid
     */
    public static int[][] stringsToGrid(String... rows) {
        int[][] result = new int[rows.length][];
        for (int row = 0; row<rows.length; row++) {
            result[row] = stringToInts(rows[row]);
        }
        return result;
    }


    /**
     * Given a single string containing 81 numbers, returns a 9x9 grid.
     * Skips all the non-numbers in the text.
     * (provided utility)
     * @param text string of 81 numbers
     * @return grid
     */
    public static int[][] textToGrid(String text) {
        int[] nums = stringToInts(text);
        if (nums.length != SIZE*SIZE) {
            throw new RuntimeException("Needed 81 numbers, but got:" + nums.length);
        }

        int[][] result = new int[SIZE][SIZE];
        int count = 0;
        for (int row = 0; row<SIZE; row++) {
            for (int col=0; col<SIZE; col++) {
                result[row][col] = nums[count];
                count++;
            }
        }
        return result;
    }


    /**
     * Given a string containing digits, like "1 23 4",
     * returns an int[] of those digits {1 2 3 4}.
     * (provided utility)
     * @param string string containing ints
     * @return array of ints
     */
    public static int[] stringToInts(String string) {
        int[] a = new int[string.length()];
        int found = 0;
        for (int i=0; i<string.length(); i++) {
            if (Character.isDigit(string.charAt(i))) {
                a[found] = Integer.parseInt(string.substring(i, i+1));
                found++;
            }
        }
        int[] result = new int[found];
        System.arraycopy(a, 0, result, 0, found);
        return result;
    }


    /**
     * Sets up the Sudoku puzzle grid based on the integers given
     * as a 2D array or matrix.
     */
    public Sudoku(int[][] ints) {
        puzzleGrid = new Spot[SIZE][SIZE];
        solutionGrid = new Spot[SIZE][SIZE];

        solutions = new ArrayList<>();

        valInRows = new ArrayList<HashSet<Integer>>(SIZE);
        valInCols = new ArrayList<HashSet<Integer>>(SIZE);
        valInParts = new ArrayList<HashSet<Integer>>(SIZE);

        /* Initializing all the HashSets */
        for (int i = 0; i < SIZE; i++) {
            valInRows.add(new HashSet<Integer>());
            valInCols.add(new HashSet<Integer>());
            valInParts.add(new HashSet<Integer>());
        }

        /* Setting up the Sudoku puzzle grid with the appropriate Spots.
         * And adding all the values in the relevant Rows, Cols and Parts
         * to set up the initial state of the grid. */
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                int val = ints[i][j];
                Spot newSpot = new Spot(i, j, val);
                puzzleGrid[i][j] = newSpot;

                if (!newSpot.isEmpty()) {
                    valInRows.get(i).add(val);
                    valInCols.get(j).add(val);
                    valInParts.get(newSpot.getPartForSpot()).add(val);
                }
            }
        }
    }

    /** 
     * Sets up the Sudoku puzzle grid based on the given text. The
     * text must contain 81 numbers. Whitespaces are ignored.
     * If the text is invalid, an exception is thrown.
     * @param text string of 81 numbers
     */
    public Sudoku(String text) {
        this(Sudoku.textToGrid(text));
    }

    /**
     * Solves the puzzle and returns the number of solutions.
     * @return number of solutions
     */
    public int solve() {
        /* List of all the empty spots in the puzzleGrid */
        ArrayList<Spot> emptySpots = getEmptySpotsList();

        /* List of Spots that will hold the solution values for the puzzleGrid */
        ArrayList<Spot> solvedSpots = new ArrayList<>();

        long startTime = System.currentTimeMillis();

        solveSudoku(emptySpots, solvedSpots, 0);

        long endTime = System.currentTimeMillis();
        timeTakenForSolution = endTime - startTime;

        if (solutions.size() == 0) /* If no solution found */
            return 0;

        /* Update the solutionGrid field */
        fillSolutionGrid();

        return solutions.size();
    }

    /* Recursive method solves the puzzleGrid
     * Strategy:
     * =========
     * 1. The emptySpots are sorted by the number of possibleValues
     *    as solutions. So start with the one that has the least possible
     *    values to check.
     * 2. Fill each emptySpot recursively but backtrack immediately when 
     *    a Spot is reached which cannot be filled by any of its possibleValues.
     * 3. Keep adding the filled(solved) spots to the List "solvedSpots"  
     * 4. When a complete solution is reached add the current solvedSpots
     *    list to the list of solutions.
     * 5. Return only when all possible solutions have been exhausted.
     * 
     * Note: index holds the current index of the emptySpots ArrayList.
     */
    private void solveSudoku(ArrayList<Spot> emptySpots,
            ArrayList<Spot> solvedSpots, int index) {

        /* Only allow MAX_SOLUTIONS */
        if (solutions.size() >= Sudoku.MAX_SOLUTIONS)
            return;

        /* Base Case: When the current chain of values has arrived at a solution */
        if (index >= emptySpots.size()) {
            solutions.add(new ArrayList<>(solvedSpots));
            return;
        }

        /* Current emptySpot that is being considered to be filled */
        Spot currentSpot = new Spot(emptySpots.get(index));

        /* Try all the possible values for this empty Spot */
        for (int value : currentSpot.possibleValues) {

            /* Check if the value is valid according to the current 
             * state of the grid */
            if (valueIsValid(value, currentSpot)) {
                currentSpot.setValue(value);
                updateGridStateWithValue(value, currentSpot);

                solvedSpots.add(currentSpot);

                int newIndex = index + 1;
                solveSudoku(emptySpots, solvedSpots, newIndex);

                /* Backtrack when the method above returns */
                emptySpots.get(index).setValue(0);
                solvedSpots.remove(currentSpot);
                updateGridStateWithValue(value, currentSpot);
            }
        }
    }

    /* Fills the solutionGrid field with the first solution that was
     * found while solving the puzzle.
     */
    private void fillSolutionGrid() {
        ArrayList<Spot> solvedSpots = solutions.get(0);

        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                solutionGrid[i][j] = new Spot(puzzleGrid[i][j]);
            }
        }

        for (Spot spot : solvedSpots)
            spot.updateValueInGrid();
    }

    /* Checks if the given value is valid for the given currentSpot by 
     * checking it against all values in this Spot's row, column and Part
     */
    private boolean valueIsValid(int value, Spot currentSpot) {
        int row = currentSpot.getRow();
        int col = currentSpot.getCol();
        int part = currentSpot.getPartForSpot();

        return (!valInRows.get(row).contains(value)) &&
                (!valInCols.get(col).contains(value)) &&
                (!valInParts.get(part).contains(value));
    }

    /* Updates the state of the grid. If the given value already exists
     * as a part of the grid state, then it is removed otherwise it is
     * added to the current state.
     */
    private void updateGridStateWithValue(int value, Spot currentSpot) {
        HashSet<Integer> valsInCurrentRow = valInRows.get(currentSpot.getRow());
        HashSet<Integer> valsInCurrentCol = valInCols.get(currentSpot.getCol());
        HashSet<Integer> valsInCurrentPart = valInParts.get(currentSpot.getPartForSpot());

        if (valsInCurrentRow.contains(value))
            valsInCurrentRow.remove(value);
        else 
            valsInCurrentRow.add(value);

        if (valsInCurrentCol.contains(value))
            valsInCurrentCol.remove(value);
        else 
            valsInCurrentCol.add(value);

        if (valsInCurrentPart.contains(value))
            valsInCurrentPart.remove(value);
        else 
            valsInCurrentPart.add(value);

    }


    /* Helper method to compute the possible values for each empty spot and
     * return the spots as an ArrayList sorted by the number of possible values
     * from low to high.
     */
    private ArrayList<Spot> getEmptySpotsList() {
        ArrayList<Spot> result = new ArrayList<>();
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                Spot thisSpot = puzzleGrid[i][j];
                if (thisSpot.isEmpty()) {
                    thisSpot.getPossibleValues();
                    result.add(thisSpot);
                }
            }
        }
        Collections.sort(result);
        return result;
    }

    /**
     * Returns the Solution to the Sudoku puzzle as a String.
     * @return solution to the puzzle
     */
    public String getSolutionText() {
        if (solutions.size() == 0) return "No Solutions";
        String result = "";
        for (Spot[] sArr : solutionGrid) {
            result += "[";
            for (Spot s : sArr)
                result += s.toString() + ", ";
            result += "] \n";
        }
        return result;
    }

    /**
     * Returns the elapsed time spent find the solutions for
     * the puzzle
     * @return time taken to solve the puzzle
     */
    public long getElapsed() {
        return timeTakenForSolution;
    }

    @Override
    public String toString() {
        String result = "";
        for (Spot[] sArr : puzzleGrid) {
            result += "[";
            for (Spot s : sArr)
                result += s.toString() + ", ";
            result += "] \n";
        }
        return result;
    }

    /* Just for simple testing */
    public static void main(String[] args) {
        Sudoku sudoku;
        sudoku = new Sudoku(easyGrid);

        System.out.println(sudoku); // print the raw problem
        int count = sudoku.solve();
        System.out.println("solutions:" + count);
        System.out.println("elapsed:" + sudoku.getElapsed() + "ms");
        System.out.println(sudoku.getSolutionText());
    }

}

Answer 1

代码总体上是好的，但是有一些注释：

1. 总是尝试公开抽象类型，而不是具体的实现，所以使用List代替ArrayList，对于字段类型和返回类型使用Set而不是HashSet，如果您想迁移到不同的具体类型，OOP将更多地隐藏实现而不是隐藏数据。
2. 使用this，这样您就不会对参数使用可怕的名称，例如Spot(int行、int col、int值){ this.row = row；this.col = col；this.value = value；}
3. getPart是私有的，这很好，所以它不能被子类覆盖，因为它在构造函数中被调用，但是我要说声明它为final，所以即使稍后更改它的可访问性，它仍然是安全的。
4. 您可以使用String.valueOf代替@覆盖公共字符串toString() {返回值+“；}

Answer 2

永恒不变的土地是好的。处理那些保证永远不会改变的事情要容易得多。所以，只要有可能做一些final，就去做。例如，所有这些行：

私有整数行；私有点undefined puzzleGrid；私有点undefined solutionGrid；私有List>解决方案；

..。还有许多其他的，可能是最终的(您的代码仍然在编译)，所以让它们成为最终的。

尽可能在变量声明、方法参数和方法返回类型中使用接口类型。例如，在这些示例中没有使用HashSet：

私有HashSet possibleValues；HashSet getPossibleValues() { // .}

使用Set代替：

private Set<Integer> possibleValues;

Set<Integer> getPossibleValues() {
    // ...
}

只有在声明中使用像HashSet这样的实现类型而不是Set时，才需要实现的特定特性。如果接口方法是您所需要的，那么您应该始终使用接口类型。

有时您使用<> (菱形操作符)，有时不使用：

解决方案=新的ArrayList<>()；valInRows =新的ArrayList>(大小)；valInCols =新的ArrayList>(大小)；valInParts =新的ArrayList>(大小)；

只要经常使用它：

solutions = new ArrayList<>();

valInRows = new ArrayList<>(SIZE);
valInCols = new ArrayList<>(SIZE);
valInParts = new ArrayList<>(SIZE);

在这个if-else中：

如果(x < 6) {如果(y < 3)返回PART2；如果(y < 6)返回PART5；否则返回PART8；}{如果(y < 3)返回PART3；如果(y < 6)返回PART6；否则返回PART9}；

注意，x < 6部件的所有执行分支都将返回。因此，您实际上不需要else，您可以编写如下更简单的代码：

if (x < 6) {
    if (y < 3) return PART2;
    else if (y < 6) return PART5;
    else return PART8;
}
if (y < 3) return PART3;
else if (y < 6) return PART6;
else return PART9;

使用适当的单元测试来验证实现的正确性，而不是在主方法中打印文本，例如：

@Test
public void testEasyGrid() {
    Sudoku sudoku = new Sudoku(Sudoku.easyGrid);
    int count = sudoku.solve();
    assertEquals(1, count);
    assertEquals(
            "[1, 6, 4, 7, 9, 5, 3, 8, 2, ] \n" +
            "[2, 8, 7, 4, 6, 3, 9, 1, 5, ] \n" +
            "[9, 3, 5, 2, 8, 1, 4, 6, 7, ] \n" +
            "[7, 9, 1, 8, 7, 6, 5, 2, 4, ] \n" +
            "[5, 4, 6, 1, 3, 2, 7, 9, 8, ] \n" +
            "[7, 2, 8, 9, 5, 4, 1, 3, 6, ] \n" +
            "[8, 1, 9, 6, 4, 7, 2, 5, 3, ] \n" +
            "[6, 7, 3, 5, 2, 9, 8, 4, 1, ] \n" +
            "[4, 5, 2, 3, 1, 8, 6, 7, 9, ] \n", sudoku.getSolutionText());
}

Answer 3

/* Helper method that returns the Part in which the 
 * coordinates x and y belong on the grid. 
 */
private int getPart(int x, int y) {
    if (x < 3) {
        if (y < 3) return PART1;
        else if (y < 6) return PART4;
        else return PART7;
    }
    if (x < 6) {
        if (y < 3) return PART2;
        else if (y < 6) return PART5;
        else return PART8;
    }
    else {
        if (y < 3) return PART3;
        else if (y < 6) return PART6;
        else return PART9;
    }   
}

呃..。这实际上完全基于两个数学运算:除法和模运算。

另外，你的PART1，PART2等变量.这些东西的真正用途是什么？PARTx =x-1.这种“一刀切”的方法在编程中很常见，不值得有9个命名的变量来解决。

所以让我们看看这里：

• 如果x小于3时，则返回第1、第4或第7部分。
• 如果x介于3和5之间(包括在内)，则返回第2、5、8部分。所以比上面多一个。
• 如果x是6或更多，则返回第3、6、9部分。再一次，比上面多一个。

对于y：

• 如果y小于3，则返回第1、2或3部分。
• 如果y介于3和5之间，则返回第4、5或6部分。(我这次连你的代码都没查过，我只知道)。
• 如果y是6或更多，则返回第7、8或9部分。

由于部件本质上是int值x-1，所以最好直接返回这些值。

这方面的计算很简单：

private int getPart(int x, int y) {
    int xGroup = x / 3;
    int yGroup = y / 3;
    return yGroup * 3 + xGroup;
}

看看它有多干净！

Extensibility

现在，您只支持经典的9x9 Sudoku。如果您改变了对待行、列和“框”的方式，并将所有这些都看作是一个SudokuRule，那么您的代码就会突然变成更灵活，可以解决更多的数独。。

真的，当你想到它的时候，一行和一列有什么区别？一个盒子和一排有什么区别？只有属于这一“规则”的领域。行是对可以放在那里的数字的限制。简单的规则是，一行中的所有数字都是唯一的。列也是这样，列中的所有数字都必须是唯一的。一个盒子也是如此。因此，如果将这些规则存储为数据结构，那么您可以创建这些规则，以解决超级数独、诺诺米诺，甚至是武士数独！