“灵巧”苏独蛮力

Question

在25x25 sudoku上运行了两天的C-蛮力器之后，我决定用Java重写，以便在一个可接受的时间框架内解决这个问题。想法是:让智能字段包含该字段的所有可能值，然后让bute-forcer只循环这些字段，希望减少时间。

经过几次挠头之后，我想到了这个：

主要：

import java.io.BufferedReader;
import java.io.File;
import java.io.FileReader;

public class SudokuMain {

    public static void main(String[] args) {
        String[] dims = null;
        String fields = null;

        File file = new File("./io/sudoku6");

        try (BufferedReader buf = new BufferedReader(new FileReader(file))) {

            dims = buf.readLine().split(" ");
            fields = buf.readLine();

        } catch (Exception e) {
            e.printStackTrace();
            System.exit(-1);
        }

        if (dims.length != 3) {
            throw new IllegalArgumentException("Invalid info header!");
        }

        int w = Integer.parseInt(dims[0]);
        int h = Integer.parseInt(dims[1]);
        int size = Integer.parseInt(dims[2]);

        if (fields.length() != size * size * 2) {
            throw new IllegalArgumentException(
                    String.format("Invalid sudoku! Expected length %s, got %s.\n", size * size * 2, fields.length()));
        }

        Sudoku sudoku = new Sudoku(w, h, size, fields);

        SudokuSolver.solve(sudoku);

    }
}

数独：

public class Sudoku {

    private Field fields[];

    public int fWidth, fHeight, size;

    public Sudoku(int w, int h, int size, String raw) {
        this.fWidth = w;
        this.fHeight = h;
        this.size = size;
        fields = new Field[size * size];

        try {
            for (int i = 0; i < size * size; i++) {
                int num = Integer.parseInt(raw.substring(0, 2));
                fields[i] = new Field(num, size);
                raw = raw.substring(2);
            }
        } catch (NumberFormatException e) {
            throw new IllegalArgumentException("Sudoku contains non-number characters!");
        }

    }

    public Field getFieldAt(int x, int y) {
        return fields[y * size + x];
    }

    public int getValueAt(int x, int y) {
        return fields[y * size + x].value;
    }

    public void setValueAt(int x, int y, int val) {
        fields[y * size + x].value = val;
    }

    private int[] getRow(int row) {
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = fields[i + row * size].value;
        }
        return res;
    }

    private int[] getCol(int col) {
        int[] res = new int[size];
        for (int i = 0; i < size; i++) {
            res[i] = fields[col + i * size].value;
        }
        return res;
    }

    public boolean isValid() {
        for (int y = 0; y < this.size; y++) {
            int[] values = new int[size + 1];
            for (int i : this.getRow(y)) {
                if (values[i] != 0) {
                    return false;
                } else {
                    values[i] = i;
                }
            }
        }

        for (int x = 0; x < this.size; x++) {
            int[] values = new int[size + 1];

            for (int i : this.getCol(x)) {
                if (values[i] != 0) {
                    return false;
                } else {
                    values[i] = i;
                }
            }
        }

        for (int yf = 0; yf < this.size; yf+=fHeight) {
            for (int xf = 0; xf < this.size; xf+=fWidth) {
                int[] values = new int[size + 1];
                for (int i : this.getBox(xf, yf)) {
                    if (values[i] != 0) {
                        return false;
                    } else {
                        values[i] = i;
                    }
                }
            }
        }
        return true;
    }

    private int[] getBox(int xf, int yf) {
        int[] res = new int[size];
        int i = 0;
        for (int y = 0; y < fHeight; y++) {
            for (int x = 0; x < fWidth; x++) {
                res[i] = fields[(y + yf) * size + (x+xf)].value;
                i++;
            }
        }
        return res;
    }

    public void print() {

        for (int a = 0; a < size * 3 + (size / fWidth) + 1; a++) {
            System.out.print('-');
        }
        System.out.println();

        for (int j = 0; j < size; j++) {
            for (int i = 0; i < size; i++) {
                if (i % fWidth == 0) {
                    System.out.print('|');
                }
                System.out.printf("%3d", fields[j * size + i].value);
            }

            System.out.print('|');
            System.out.println();

            if (j % fHeight == fHeight - 1) {
                for (int a = 0; a < (size * 3) + (size / fWidth) + 1; a++) {
                    System.out.print('-');
                }
                System.out.println();
            }
        }
        System.out.println();

    }

}

字段：

public class Field {

    public int value;
    private int possible[];

    public Field(int val, int size) {
        this.value = val;
        possible = new int[size + 1];

        for (int i = 0; i <= size; i++) {
            possible[i] = i;
        }
    }

    public void removePossible(int[] nums) {
        for (int num : nums)
            possible[num] = 0;
    }

    public int setIfOnePossible() {

        if (value != 0) {
            return 0;
        }

        int found = -1;
        for (int i = 1; i < possible.length; i++) {
            if (possible[i] != 0) {
                if (found == -1) {
                    found = i;
                } else {
                    return 0;
                }
            }
        }
        this.value = found;
        return 1;
    }

    public boolean isPossible(int n) {
        return possible[n] != 0;
    }

    public int countPossible() {
        int res = 0;
        if (value != 0) {
            return 0;
        }

        for (int i : possible) {
            if (i != 0) {
                res++;
            }
        }
        return res;
    }

}

SudokuSolver：

public class SudokuSolver {

    private static int tries;

    public static void solve(Sudoku s) {
        s.print();
        long then = System.currentTimeMillis();

        presolve(s);
        if (recsolve(s) && s.isValid()) {
            s.print();
            long mstime = System.currentTimeMillis() - then;

            int min = (int) (mstime / 1000 / 60 % 60);
            int sec = (int) (mstime / 1000 % 60);
            long ms = mstime - (min * 60 * 1000) - (sec * 1000);
            System.out.printf("Took %d min, %d s, %d ms\n", min, sec, ms);
            System.out.printf("%d tries.\n", tries);
        }
    }

    private static boolean recsolve(Sudoku s) {
        for (int y = 0; y < s.size; y++) {
            for (int x = 0; x < s.size; x++) {
                Field f = s.getFieldAt(x, y);
                if (f.value == 0) {
                    for (int n = 1; n <= s.size; n++) {
                        if (f.isPossible(n)) {
                            tries++;
                            s.setValueAt(x, y, n);
                            if (s.isValid() && recsolve(s)) {
                                return true;
                            }
                        }
                    }
                    s.setValueAt(x, y, 0);
                    return false;
                }
            }
        }
        return true;
    }

    private static void presolve(Sudoku s) {
        int possBefore = 0;
        for (int y = 0; y < s.size; y++) {
            for (int x = 0; x < s.size; x++) {
                possBefore += s.getFieldAt(x, y).countPossible();
            }
        }

        int set = 0;

        do {
            for (int y = 0; y < s.size; y++) {
                int[] found = new int[s.size + 1];
                for (int x = 0; x < s.size; x++) {
                    int value = s.getValueAt(x, y);
                    found[value] = value;
                }
                for (int i = 0; i < s.size; i++) {
                    s.getFieldAt(i, y).removePossible(found);
                }
            }

            for (int x = 0; x < s.size; x++) {
                int[] found = new int[s.size + 1];
                for (int y = 0; y < s.size; y++) {
                    int value = s.getValueAt(x, y);
                    found[value] = value;
                }
                for (int i = 0; i < s.size; i++) {
                    s.getFieldAt(x, i).removePossible(found);
                }
            }

            for (int yf = 0; yf < s.size; yf += s.fHeight) {
                for (int xf = 0; xf < s.size; xf += s.fWidth) {
                    int[] found = new int[s.size + 1];
                    for (int y = 0; y < s.fHeight; y++) {
                        for (int x = 0; x < s.fWidth; x++) {
                            int value = s.getValueAt(xf + x, yf + y);
                            found[value] = value;
                        }
                    }
                    for (int y = 0; y < s.fHeight; y++) {
                        for (int x = 0; x < s.fWidth; x++) {
                            s.getFieldAt(xf + x, yf + y).removePossible(found);

                        }
                    }
                }
            }

            set = 0;
            for (int y = 0; y < s.size; y++) {
                for (int x = 0; x < s.size; x++) {
                    set += s.getFieldAt(x, y).setIfOnePossible();
                }
            }
        } while (set != 0);

        int possAfter = 0;

        for (int y = 0; y < s.size; y++) {
            for (int x = 0; x < s.size; x++) {
                possAfter += s.getFieldAt(x, y).countPossible();
            }
        }
        System.out.printf("Excluded %s possible values for fields. (before %s, now %s)\n", possBefore - possAfter,
                possBefore, possAfter);
    }

}

这恰好比12x12 sudoku上的C程序快5秒，就像这样：

4 3 12
000000000001000000000312030001000000121006000000000002120403000000000700001000081200000007000600000705000002000300000400000000090000000711030010050009110700000002000000000600000200010000051200001200020000000408001100000200000000070803110000000000030912000000040002100400000000030000000000

(我还没有测试25x25。)

编辑:删除两个测试用例

Answer 1

在我看来，这段代码基本上没问题。我自己编写了一个Sudoku解析器，主要是为了测试我在当时的新集合框架上的编码技能(这再次显示了我的年龄)。

然后说几句话：

• 行、列和块可视为“组”。这样，甚至有可能允许数独与不同的或更多的群体。
• 我不知道我的Sudoku 12 x 12的速度，但我知道它在我基于双核2的IBM上运行了0.2秒，运行时间为9×9。这基本上就是VM的启动时间。
• 我对每个“组”的可能值进行了两步猜测->的简单简化，然后进行猜测。因此，如果可能的话，我不仅会在一开始运行presolve，而且会在每次猜测之后运行。有许多技巧可以用来“猜”得更好，但它们中的大多数似乎真的减慢了猜测的速度(我玩得很好，并在运行之后查找了这些技巧)。

至于守则：

• 数独w、h、size / fields的参数似乎都是相关的。只使用那些真正需要的。size = w * h不是吗？
• 现场课有点怪。它为value提供了一个特殊的领域，目前还不清楚是否需要它。它使用0作为特殊值。对于这样一个特殊的值，我将使用一个常量(例如NOT_POSSIBLE = 0)并记录使用。此外，它似乎依赖于对setIfOnePossible的外部调用才能进入下一个有效状态。我记得我使用了Set<Integer>，没有明显的问题(但是，我的目标是测试集合类)。setIfOnePossible返回一个值，但名称不清楚。
• public boolean isValid()有副作用。名为isValid的方法不应包含任何副作用，因此重命名该方法非常重要。
• raw = raw.substring(2)通常我们不赞成在循环中使用substring。越久parseInt方法或使用Matcher.find()的正则表达式如何？