数独生成器

本文介绍了一种用Java实现的数独生成器。

数独盘面是个九宫，每一宫又分为九个小格。在这八十一格中给出一定的已知数字和解题条件，利用逻辑和推理，在其他的空格上填入1-9的数字。使1-9每个数字在每一行、每一列和每一宫中都只出现一次，所以又称“九宫格”。

算法：

本文的实现采用的是回溯法。也就是说，从盘面的第一个格出发，按顺序遍历所有格子。对每一个格子随机生成一个数字，并判断该数字在当前的盘面下是否是合法的。如果不合法，比如同一行已经有相同的数字了，则随机换一个数字。如果当前位置所有数字都不合法，那么就回退到前一个位置，换一个数字，以此类推。

要点：

• 在为每一个格子随机生成数字的时候，为了提高效率，要保证生成的数据是不重复的。这里使用的方法是，在初始化阶段就为每一个格子生成一个包含1~9的随机顺序的List。这样在遍历到某一个格子时，只需要按顺序把这个格子所对应的list里的值以此取出，就可以获取随机并且不重复的1~9的值。生成随机顺序列表可以利用Java的Collections.shuffle方法:

    private static List randomValues() {
        List result = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);

        Collections.shuffle(result);

        return result;
    }

•  为了判断指定位置的某一个值是否合法，我们需要判断三个条件：
  1. 该点所在行是否有相同值
  2. 该点所在列是否有相同值
  3. 该点所在九宫是否有相同值
  我们知道，判断是否有重复值的最快的方法是用HashSet。因此，我们为每一行，每一列，以及每个九宫格都维护了一个HashSet。每当确定一个值以后，就相应地把该值添加到它所在的行，列和九宫格所对应的HashSet中。同样，在判断某一点的值是否冲突时，只要检查该点的行，列和九宫格所对应的HashSet中是否有相同的值即可。
• 遍历和回退采用的是递归的方法，这样使得逻辑更加清晰。

代码

下面是完整代码：

import org.slf4j.Logger;
import org.slf4j.LoggerFactory;
import java.util.*;

public class Sudoku {
    private static final Logger LOG = LoggerFactory.getLogger( Sudoku.class );

    private static List[][] grid = new List[9][];
    private static int[][] gridIndex = new int[9][];
    private static HashSet[] rowSets = new HashSet[9];
    private static HashSet[] colSets = new HashSet[9];;
    private static HashSet[] blockSets = new HashSet[9];;

    private static List randomValues() {
        List result = Arrays.asList(1, 2, 3, 4, 5, 6, 7, 8, 9);

        Collections.shuffle(result);

        return result;
    }

    private static int blockIndex(int row, int col) {
        return (row / 3) * 3 + (col / 3);
    }

    private static boolean check(int row, int col) {
        if (row == 9 || col == 9) {
            return true;
        }

        while (gridIndex[row][col] < 9) {
            Integer value = grid[row][col].get(gridIndex[row][col]);

            if (rowSets[row].contains(value) ||
                    colSets[col].contains(value) ||
                    blockSets[blockIndex(row, col)].contains(value)) {
                gridIndex[row][col]++;
                continue;
            }

            // the current value looks good, set maps
            rowSets[row].add(value);
            colSets[col].add(value);
            blockSets[blockIndex(row, col)].add(value);

            // check next point
            int nextCol = (col + 1) % 9;
            int nextRow = row + (col + 1) / 9;
            if (check(nextRow, nextCol) == false) {
                // rollback
                rowSets[row].remove(value);
                colSets[col].remove(value);
                blockSets[blockIndex(row, col)].remove(value);

                gridIndex[row][col]++;
                continue;
            }

            return true;
        }

        gridIndex[row][col] = 0;

        return false;
    }

    private static void printResult() {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                System.out.printf("%d ", grid[i][j].get(gridIndex[i][j]));
            }
            System.out.println("");
        }
    }

    public static void main(String[] args) {
        // init random value lists
        for (int i = 0; i < grid.length; i++) {
            grid[i] = new List[9];
            gridIndex[i] = new int[] {0, 0, 0, 0, 0, 0, 0, 0, 0};
            for (int j = 0; j < grid[i].length; j++) {
                grid[i][j] = randomValues();
            }
        }

        // init hashsets for rows, cols and blocks
        for (int i = 0; i < 9; i++) {
            rowSets[i] = new HashSet<>();
            colSets[i] = new HashSet<>();
            blockSets[i] = new HashSet<>();
        }

        check(0, 0);

        printResult();
    }
}

运行结果：

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