数独生成速度 [英] Sudoku generation speed

问题描述

我写了一个回溯算法来生成任意大小的数独.我的问题是这种生成算法的速度变化.

I wrote a backtracking algorithm to generate sudokus with arbitrary size. My problem is the varying speed of this generation algorithm.

我添加了一些控制台输出以查看结果.我生成了约20个数独，大小为16x16，每个数独都有1ms到150ms的生成时间.下一个超过了10分钟，甚至没有完成. (我停止了程序).考虑到这一点，我认为我在回溯实现中犯了一个错误，这阻止了算法的发展.

I added some console output to see the results. I generated ~20 Sudokus with the size of 16x16, each one had 1ms to 150ms generating time. The next one took over 10 minutes, and it didn't even finish. (I stopped the program). In consideration of that, I think I made a mistake in the backtracking implementation, which prevents the algorithm from advancing.

这是代码:

public class Generator {
    public static NormalSudoku generateNormal(int size) {
    NormalSudoku ns = new NormalSudoku(size);
    boolean[][][] track = new boolean[size][size][size];
    ArrayList<Integer> vals = new ArrayList<Integer>();
    fill(vals, size);

    int row = 0;
    int col = 0;
    int val = 0;

    int count = 0;
    while (row < size) {
        boolean found = false;
        while (!vals.isEmpty() && !found) {
            val = vals.get((int) (Math.random() * vals.size()));
            track[row][col][val - 1] = true;
            if (ns.checkValue(row, col, val)) {
                 ns.setValue(row, col, val);
                 fill(vals, size);
                 col++;
                found = true;
            } else {
                 vals.remove(Integer.valueOf(val));
            }

            if (col >= size) {
                 row++;
                 col = 0;
            }
        }
        if (vals.isEmpty()) {
        ns.setValue(row, col, 0);
        for (int i = 0; i < size; i++) {
            track[row][col][i] = false;
        }
        col--;
        if (col < 0) {
            row--;
            col = size - 1;
        }
        ns.setValue(row, col, 0);
        fill(vals, track, row, col);
        }
    }
    return ns;
    }

    private static void fill(ArrayList<Integer> vals, int size) {
    vals.clear();
    for (int i = 1; i <= size; i++) {
        vals.add(i);
    }
    }

    private static void fill(ArrayList<Integer> vals, boolean[][][] track,
        int row, int col) {
    vals.clear();
    for (int i = 0; i < track[row][col].length; i++) {
        if (!track[row][col][i]) {
        vals.add(Integer.valueOf(i + 1));
        }
    }
    }
}

代码说明:

boolean [] [] []轨道:

boolean[][][] track:

某种已经尝试过的值的清单(以减少多次尝试相同随机值的开销).如果我已经尝试将val放在此字段上，则将track [row] [col] [val]设置为true.如果我返回，则必须清除该单元格的标记，以使值再次变为可能.

some sort of checklist for the values which are already tried (to reduce overhead of trying the same random value multiple times). I put track[row][col][val] on true if I already tried to put val on this field. If I go back, I have to clear the marks for that cell, to make the values possible again.

ns.checkValue:

ns.checkValue:

设置单元格上的值，检查数独是否仍然正确，再次设置旧值并返回true/false.

Sets the value on the cell, checks if the sudoku is still correct, sets the old value again and returns true/false.

ns.setValue:

ns.setValue:

只需在单元格上设置值即可.

Simply sets the value on the cell.

值:

一个数组列表，其中包含尚未对该单元格尝试的值.如果我继续前进，清单显然必须包含所有可能的数字. 如果我回溯，该列表只需包含尚未尝试的数字. (我使用track数组实现了这一点.)

An array list containing the values which are not tried yet for that cell. If I move forward, the list obviously must contain every possible number. If I backtrack, the list only has to contain the numbers which aren't tried yet. (I use the track array to realize that).

我在做什么错了?

礼物

推荐答案

由于某些原因，您首先从vals列表中选择了一个随机数，该随机数通常充满了10个以上的数字，因此您浪费了大量时间那里. 我测试了您的代码，关于解决时间的长短确实是相当随机的. 例如关于这种临时解决方案

Ok first thing for some reason you chose a random number from vals list which most of the time is full with 10+ numbers, so you lose quite alot of time there. I tested your code and it really is quite random about the duration of the solving. For instance on this temporary solving

[12, 9, 14, 7, 5, 13, 8, 2, 15, 3, 4, 6, 16, 1, 10, 11]
[1, 2, 13, 15, 12, 16, 14, 4, 11, 8, 10, 9, 5, 6, 0, 0]
....

填充单元格(2,15)和(2,16)花费了太多时间，因为它出于某种原因从列表值中选择了一个具有10个可用值的随机值，但是可能的值是数字3和7.

It takes too much time to fill cells (2,15) and (2,16) becouse it chooses a random from list vals with 10 values available for some reason but the possible values are numbers 3 and 7.

在vals列表中，您应该从当前行，当前列和区域中排除数字.

In the vals list you should exclude numbers from the current row and current column and region.

但是，这并不能改善算法.

However this does not improve much the algorithm.

您的算法是:

1. For current cell try all values until you find one that fits.
2. If it fits track it and move on to next cell.
3. If no value fits take step back, try value on the previous cell that was not used yet.

由于随机性，如果在第一个位置上的某个位置的值不好，则您在第3点上花费了太多时间.

Becouse of the randomness your taking too much time on point 3 if some value is not on good place in some very first positions.

这篇关于数独生成速度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！