523066680

回复 15# slore

对于回溯法，有一个优化很有效果。示意图（注意除了中间有个独立的候选数字2，右上角还有个框选的数字8）：


程序给定的单元候选数字中，大多单元格有多个可选数字，但是可以进一步排除。例如：
如果累计一行中的所有候选数，某个数字只出现一次，那么这个数字就是必选数字。同样，一列、一宫(3x3 block)的区域内也是如此。

我为程序增加了一个while 循环，反复筛选并填充唯一的数字，直到再也没有，然后才开始递归解题。

Sudoku:
3,0,0,0,1,0,0,0,0
0,0,0,0,0,0,0,9,0
0,8,0,2,0,0,0,0,6
0,0,0,0,7,0,3,4,0
0,5,6,0,0,0,0,0,0
0,0,0,0,0,0,0,0,0
0,0,0,5,0,0,0,0,0
0,0,0,6,0,8,0,0,2
1,0,0,0,0,0,0,3,0

Fill only one possible cells
R:1 C:8 Fill:3
R:3 C:5 Fill:6
R:3 C:8 Fill:5
R:6 C:5 Fill:1
R:0 C:1 Fill:6
R:1 C:4 Fill:6
R:6 C:0 Fill:6
R:8 C:6 Fill:6
R:5 C:7 Fill:6
R:8 C:2 Fill:5
R:8 C:8 Fill:8
R:6 C:2 Fill:8
R:6 C:7 Fill:7

Result:
3,6,0,0,1,0,0,0,0
0,0,0,0,6,0,0,9,3
0,8,0,2,0,0,0,0,6
0,0,0,0,7,6,3,4,5
0,5,6,0,0,0,0,0,0
0,0,0,0,0,0,0,6,0
6,0,8,5,0,1,0,7,0
0,0,0,6,0,8,0,0,2
1,0,5,0,0,0,6,3,8

Solve:
3,6,9,4,1,5,2,8,7
2,4,1,8,6,7,5,9,3
5,8,7,2,9,3,4,1,6
8,1,2,9,7,6,3,4,5
9,5,6,3,8,4,7,2,1
4,7,3,1,5,2,8,6,9
6,3,8,5,2,1,9,7,4
7,9,4,6,3,8,1,5,2
1,2,5,7,4,9,6,3,8
time used: 0.211s

slore

回复 16# 523066680

VBS当时写代码,就有这个逻辑.先CreatePlan里面有presolvecount,然后才SolvePanes递归的.

bbaa

我来了,等下用我之前的生成类试试

bbaa

回复 18# bbaa


    随机法真的 身败名裂

Allowed memory size of 134217728 bytes exhausted (tried to allocate 40 bytes)
复制代码

523066680

回复 19# bbaa

      对于题目和结果判断，你先用现成的题库弄上网站跑跑看？我前面发的题库分为5种难度等级，你可以随机抽取。
这些题只有一种答案，也都在文件里了，检验方便。（虽然这样提供了作弊条件，可以直接POST现有答案，不过也就是试试效果）

search_Sudoku

闲时再弄弄, JS 还有些冗余的变量及逻辑
保存为 htm 文件, 浏览器 F12 控制台看运行

<script>
    var cntEmptyCell = 9 * 9;
    var schPath = [];
    var P = [[], [], [], [], [], [], [], [], []];
    // i 行 j 列
    for (let i = 0; i < 9; i++)
        for (let j = 0; j < 9; j++) {
            P[i][j] = {fill: 0, maybe: 0x1FF, choose: 9, block: (Math.floor(i / 3) * 3 + Math.floor(j / 3))};
        }
    var problems = [
        '001000008800010532750024090005302060670500004010780900098053406426179803537460219',
        '503092000700000008006007310020600000065000730007043500000706102070000800400009000',
        '700306000000000050060000018000081000000000000900000200000200900050400000080000007',
        '030000001200806000000005000000000000000000650043070000600002080090000000000010003',
        '010000200300800000000504000800090000000070120500000000000000000020130000400000005',
        '510000700076089000004000805400100007000030000090706010000460201047000300005000084'
    ];
    var problem;
    problem = problems[3];
    const LOOPCNT_CTRL = 50000;
    var LOOPCNT_OUTPUT_BEGIN = LOOPCNT_CTRL - 50;
    var a_p = Array.from(problem);
    var minchoose = 10, i_minchoose = 0, j_minchoose = 0;
    // 题面初始化
    for (let i = 0; i < 9; i++)
        for (let j = 0; j < 9; j++)
            if (a_p[i * 9 + j] - 0 != 0) {
                P[i][j].maybe = P[i][j].fill = 1 << (a_p[i * 9 + j] - 1);
                P[i][j].choose = 1;
                cntEmptyCell -= 1;
                for (let u = 0; u < 9; u++)
                    if ((u != i) && (P[u][j].fill == 0)) {
                        if ((P[u][j].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
                            P[u][j].choose -= 1;
                            if (P[u][j].choose < minchoose) {
                                minchoose = P[u][j].choose;
                                i_minchoose = u;
                                j_minchoose = j;
                            }
                            P[u][j].maybe &= ~(P[i][j].fill);
                        }
                    }
                for (let v = 0; v < 9; v++) {
                    if ((v != j) && (P[i][v].fill == 0)) {
                        if ((P[i][v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
                            P[i][v].choose -= 1;
                            if (P[i][v].choose < minchoose) {
                                minchoose = P[i][v].choose;
                                i_minchoose = i;
                                j_minchoose = v;
                            }
                            P[i][v].maybe &= ~(P[i][j].fill);
                        }
                    }
                }
                g = P[i][j].block;
                // 3X3 块的左上角坐标
                r = Math.floor(g / 3) * 3;
                c = g % 3 * 3;
                for (let u = 0; u < 3; u++)
                    for (let v = 0; v < 3; v++) {
                        if (!(r + u == i && c + v == j) && (P[r + u][c + v].fill == 0)) {
                            if ((P[r + u][c + v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
                                P[r + u][c + v].choose -= 1;
                                if (P[r + u][c + v].choose < minchoose) {
                                    minchoose = P[r + u][c + v].choose;
                                    i_minchoose = r + u;
                                    j_minchoose = c + v;
                                }
                                P[r + u][c + v].maybe &= ~(P[i][j].fill);
                            }
                        }
                    }
                // console.log('F=' + a_p[i * 9 + j] + ', i=' + i + ', j=' + j + ', g=' + P[i][j].block + '\n');
            }
    console.log('题面初始化后\n');
    console.log('cntEmptyCell=' + cntEmptyCell + '\n');
    print_fill_intuitive();
    // 初始化尝试填数
    let try_num;
    try_num = 1 << 8;
    while ((try_num != 0) && ((P[i_minchoose][j_minchoose].maybe & try_num) == 0)) {
        try_num >>= 1;
    }
    if (try_num == 0) {
        throw 'error problem\n';
    }
    let maybe;
    let fail_flag = false;
    let success = false;
    let loopcnt = 0;
    // 节点状态:
    // NEW_POS: 填数未失败,新位置填第一个试数
    // NEXT_TRY: 失败换填下一个试数
    // UNDO_POS: 所有试数失败撤消填数
    let state_code = 'NEW_POS';
    do {
        loopcnt++;
        if (fail_flag) {
            // 撤消所有 SET_MAYBE
            while (schPath[0].type == 'SET_MAYBE') {
                P[schPath[0].row][schPath[0].col].maybe = schPath[0].oldMaybe;
                P[schPath[0].row][schPath[0].col].choose += 1;
                schPath.shift();
            }
            // 撤消 FILL_POS
            // 若 try_num 不是最后一个可试数,
            // try_num 取下一个可试数, fail_flag 设为 false
            if (schPath[0].type == 'FILL_POS') {
                i = schPath[0].row;
                j = schPath[0].col;
                P[i][j].fill = schPath[0].oldFill;
                P[i][j].choose = schPath[0].oldChoose;
                P[i][j].maybe = schPath[0].oldMaybe;
                if (schPath[0].oldFill == 0)
                    cntEmptyCell += 1;
                // 下一个可试的数
                try_num = schPath[0].fillValue >> 1;
                schPath.shift();
                // 试探是否还有下一个可试填数
                while ((try_num != 0) && ((P[i][j].maybe & try_num) == 0)) {
                    try_num >>= 1;
                }
                if (try_num != 0) {
                    fail_flag = false;
                    state_code = 'NEXT_TRY';
                } else {
                    fail_flag = true;
                    state_code = 'UNDO_POS';
                }
            }
        } else {
            if (state_code == 'NEW_POS') {
                if (cntEmptyCell == 0) {
                    // 成功, 输出结果并退出
                    console.log('\n\n' + 'SUCCESS! @ ' + 'loopcnt = ' + loopcnt + '\n\n' + 'problem and answer:\n\n' + PA_STR());
                    print_fill_intuitive();
                    // print_state();
                    success = true;
                    break;
                }
                minchoose = 10; // 准备搜索下一轮的最少选择位置
                i = i_minchoose;
                j = j_minchoose;
                // 初始化 try_num
                try_num = 1 << 8;
                while ((try_num != 0) && ((P[i][j].maybe & try_num) == 0)) {
                    try_num >>= 1;
                }
            } else if (state_code == 'NEXT_TRY') {
            }
            if (try_num == 0) {
                throw 'BUG: try_num == 0';
            } else {
                // TRYFILL
                schPath.unshift({type: 'FILL_POS', oldFill: P[i][j].fill, row: i, col: j, fillValue: try_num, fillValue_fact: get_fill_intuitive(try_num), oldChoose: P[i][j].choose, oldMaybe: P[i][j].maybe});
                if (P[i][j].fill == 0)
                    cntEmptyCell -= 1;
                P[i][j].choose = 1;
                P[i][j].maybe = try_num;
                P[i][j].fill = try_num;
                for (let u = 0; !fail_flag && (u < 9); u++)
                    if ((u != i) && (P[u][j].fill == 0)) {
                        if ((P[u][j].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
                            // 搜索栈压栈
                            schPath.unshift({type: 'SET_MAYBE', row: u, col: j, oldMaybe: P[u][j].maybe});
                            P[u][j].choose -= 1;
                            if (P[u][j].choose < minchoose) {
                                minchoose = P[u][j].choose;
                                i_minchoose = u;
                                j_minchoose = j;
                            }
                            maybe = P[u][j].maybe &= ~(P[i][j].fill);
                            if (maybe == 0) {
                                fail_flag = true;
                                break;
                            }
                        }
                    }
                for (let v = 0; !fail_flag && (v < 9); v++) {
                    if ((v != j) && (P[i][v].fill == 0)) {
                        if ((P[i][v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
                            // 搜索栈压栈
                            schPath.unshift({type: 'SET_MAYBE', row: i, col: v, oldMaybe: P[i][v].maybe});
                            P[i][v].choose -= 1;
                            if (P[i][v].choose < minchoose) {
                                minchoose = P[i][v].choose;
                                i_minchoose = i;
                                j_minchoose = v;
                            }
                            maybe = P[i][v].maybe &= ~(P[i][j].fill);
                            if (maybe == 0) {
                                fail_flag = true;
                                break;
                            }
                        }
                    }
                }
                if (!fail_flag) {
                    g = P[i][j].block;
                    // 3X3 块的左上角坐标
                    r = Math.floor(g / 3) * 3;
                    c = g % 3 * 3;
                    for (let u = 0; !fail_flag && (u < 3); u++)
                        for (let v = 0; !fail_flag && (v < 3); v++) {
                            if (!(r + u == i && c + v == j) && (P[r + u][c + v].fill == 0)) {
                                if ((P[r + u][c + v].maybe & P[i][j].fill) != 0) { // 按位与必须括起来, 它比不等号优先级低
                                    // 搜索栈压栈
                                    schPath.unshift({type: 'SET_MAYBE', row: r + u, col: c + v, oldMaybe: P[r + u][c + v].maybe});
                                    P[r + u][c + v].choose -= 1;
                                    if (P[r + u][c + v].choose < minchoose) {
                                        minchoose = P[r + u][c + v].choose;
                                        i_minchoose = r + u;
                                        j_minchoose = c + v;
                                    }
                                    maybe = P[r + u][c + v].maybe &= ~(P[i][j].fill);
                                    if (maybe == 0) {
                                        fail_flag = true;
                                        break;
                                    }
                                }
                            }
                        }
                }
                for (let u = 0; u < 9; u++)
                    for (let v = 0; v < 9; v++) {
                        if (!(u == i && v == j) && P[u][v].fill == 0) {
                            if (P[u][v].choose < minchoose) {
                                minchoose = P[u][v].choose;
                                i_minchoose = u;
                                j_minchoose = v;
                            }
                        }
                    }
                if (COUNT_EmptyCell() != cntEmptyCell) {
                    throw 'BUG: COUNT_EmptyCell = ' + COUNT_EmptyCell();
                }
            }
            if (fail_flag) {
                state_code = 'NEXT_TRY';
            } else {
                state_code = 'NEW_POS';
            }
        }
    } while ((true || (loopcnt < LOOPCNT_CTRL)) && (schPath.length > 0 || (!fail_flag && state_code == 'NEXT_TRY' && try_num != 0)));
    function print_choose_num() {
        console.log('\n\n\n' + 'print_choose_num:' + '\n\n');
        for (let i = 0; i < 9; i++) {
            let line = i + ': ';
            for (let j = 0; j < 9; j++) {
                line += ((P[i][j].fill != 0) ? '+' : P[i][j].choose) + ' ';
            }
            console.log(line);
        }
    }
    function print_maybe_bin() {
        console.log('\n\n\n' + 'print_maybe_bin:' + '\n\n');
        for (let i = 0; i < 9; i++) {
            let line = i + ': ';
            for (let j = 0; j < 9; j++) {
                line += ('000000000' + P[i][j].maybe.toString(2)).slice(-9).replace(/0/g, '_') + ' ';
            }
            console.log(line);
        }
    }
    function print_block_num() {
        for (let i = 0; i < 9; i++) {
            let line = i + ': ';
            for (let j = 0; j < 9; j++) {
                line += ', ' + P[i][j].block;
            }
            console.log(line);
        }
    }
    function print_fill_bin() {
        console.log('\n\n\n' + 'print_fill_bin:' + '\n\n');
        for (let i = 0; i < 9; i++) {
            let line = i + ': ';
            for (let j = 0; j < 9; j++) {
                line += ('000000000' + P[i][j].fill.toString(2)).slice(-9).replace(/0/g, '_') + ' ';
            }
            console.log(line);
        }
    }
    function print_fill_intuitive() {
        console.log('\n\n\n' + 'print_fill_intuitive:' + '\n\n');
        for (let i = 0; i < 9; i++) {
            let line = i + ': ';
            for (let j = 0; j < 9; j++) {
                line += get_fill_intuitive(P[i][j].fill) + ' ';
            }
            console.log(line);
        }
    }
    function COUNT_EmptyCell() {
        let sum = 0;
        for (let i = 0; i < 9; i++)
            for (let j = 0; j < 9; j++)
                if (P[i][j].fill == 0)
                    sum++;
        return sum;
    }
    function get_fill_intuitive(y) {
        if (y == 0) {
            return '_'
        } else
            return (Math.round(Math.log(y) / Math.log(2)) + 1);
    }
    function print_state() {
        console.log('\n\n\n' + 'BEGIN print_state:' + '\n\n');
        print_fill_intuitive();
        print_fill_bin();
        print_choose_num();
        print_maybe_bin();
        console.log('\n\n\n' + 'END print_state.' + '\n\n');
        console.log('\n\n\n' + 'loopcnt = ' + loopcnt);
    }
    function print_choose_state() {
        console.log('\n\n\n' + 'BEGIN print_choose_state:' + '\n\n');
        print_choose_num();
        print_maybe_bin();
        console.log('\n\n\n' + 'END print_choose_state.' + '\n\n');
        console.log('\n\n\n' + 'loopcnt = ' + loopcnt);
    }
    function PA_STR() {
        let t = problem;
        for (let i = 0; i < 9; i++)
            for (let j = 0; j < 9; j++)
                t += get_fill_intuitive(P[i][j].fill);
        return t;
    }
/*
搜索算法
数组存储
P 二维数组 9 行 X 9 列,
    元素为对象 引用方式: P[行号,列号]
        {
            fill:   填数 -- 0 为未填,否则为已填的数值,
            maybe:  可选数的完全可能 -- 以2进制位表达,右至左数第1位表示可选1,第2位表示可选2,...第9位表示可选9, 当此属性值为0x1FF表示1~9全部可选,
                    当有任意一个位置的 maybe 为 0 时, 说明最后试填的数失败, 必须撤回
            choose: 可选数的数目 -- 也就是 maybe 的所有二进制位上 '1' 的总数,
            block:  区块号 -- 值范围[0..8]
         };
cntEmptyCell -- 未填数单元格计数
解成功判断: if (cntEmptyCell == 0) 成功, 输出结果并退出
最大关联位置 -- 以当前线索简单判断最少可能选择的位置
节点状态:
NEW_POS: 填数未失败,新位置填第一个试数
NEXT_TRY: 失败换填下一个试数
UNDO_POS: 所有试数失败撤消填数
初始化题面并找出最大关联位置
节点状态 = NEW_POS
试填失败标志: fail_flag = false
:loop
if (fail_flag == true) {
    撤消搜索栈顶的所有 SET_MAYBE 操作并 弹栈搜索栈
    撤消 FILL_POS 操作 弹栈搜索栈
    如果 当前 处理位置还有可试填的其他数值可能(同时设置好下一个试填数值),
        fail_flag = false;
        节点状态 = 'NEXT_TRY';
    否则
        fail_flag = true;
        节点状态 = 'UNDO_POS';
} else {
    if (节点状态 == 'NEW_POS') {
        检测解出是否成功(成功则输出并退出程序)
        操作位置设为最大关联位置
        找出操作位置上第一个可选数值(0x100 --> 0x1 的次序)
    }
    执行 FILL_POS 操作 并 压栈搜索栈, 将同行同列同区块的 maybe 值作相应处理 并 压栈搜索栈, 找出所有未填数单元格中的 最大关联位置
    处理 maybe 值时 如果 发现无解 (任意一个位置的 maybe == 0), 则 设置失败标志 fail_flag = true
}
当 搜索栈未空 或 (fail_flag 为假 且 节点状态 == 'NEXT_TRY' 且 存在可试填数)
    goto :loop
搜索栈结构:
结点: {type: FILL_POS 或 SET_MAYBE, row:行坐标, col:列坐标, oldMaybe: Maybe原值, fillValue}
type 为 FILL_POS 时, 有 fillValue 值
fillValue 可能的值: 从 2 ** 8 (256) 0X100 开始 依次 >> 1 位, 直到 1, 不包括 0
*/
</script>
复制代码

523066680

Rosettacode 上面有一段js的示例，代码较长不粘贴了
http://rosettacode.org/wiki/Sudoku#JavaScript
效率是很高，但是实现细节有问题，某些题型会崩溃

sudoku_nd3.txt
//'7.56...19........89....8.....81.2.7...13..4.237...5.9.8.3..1.25...5....41........',
//'.....4...7.......2.....61.....2.......4...3..8..79.6....78....9.36........1......',
//'...3.1...49......638.......1.5..7.......9...8.........6...4...........5...3...71.',

sudoku_nd4.txt
//'......3......2.1..1.84.9.....7....2..3.6...7...6.7...8....5846.2........9..1.....',
//'.....53..6.....5.8...1...2.45.8...1.3.....4.5..2.........2.18....7.3..6..2...4...',
//'....9..3...5..2.4.7.94....13.1....98.4.9........8..6..2...13..7..36...151....9...',
复制代码

开始我以为是 js 限制递归层数太少，用Perl和C分别实现后发现主要还是和实现有关，递归回溯过程的数据处理写对了就不会有崩溃的情况。

顺便贴一些相关的：
Python 版DLX实现
http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html

#!/usr/bin/env python3
# http://www.cs.mcgill.ca/~aassaf9/python/algorithm_x.html

# Author: Ali Assaf <ali.assaf.mail@gmail.com>
# Copyright: (C) 2010 Ali Assaf
# License: GNU General Public License <http://www.gnu.org/licenses/>

from itertools import product

def solve_sudoku(size, grid):
    R, C = size
    N = R * C
    X = ([("rc", rc) for rc in product(range(N), range(N))] +
         [("rn", rn) for rn in product(range(N), range(1, N + 1))] +
         [("cn", cn) for cn in product(range(N), range(1, N + 1))] +
         [("bn", bn) for bn in product(range(N), range(1, N + 1))])
    Y = dict()
    for r, c, n in product(range(N), range(N), range(1, N + 1)):
        b = (r // R) * R + (c // C) # Box number
        Y[(r, c, n)] = [
            ("rc", (r, c)),
            ("rn", (r, n)),
            ("cn", (c, n)),
            ("bn", (b, n))]
    X, Y = exact_cover(X, Y)
    for i, row in enumerate(grid):
        for j, n in enumerate(row):
            if n:
                select(X, Y, (i, j, n))
    for solution in solve(X, Y, []):
        for (r, c, n) in solution:
            grid[r][c] = n
        yield grid

def exact_cover(X, Y):
    X = {j: set() for j in X}
    for i, row in Y.items():
        for j in row:
            X[j].add(i)
    return X, Y

def solve(X, Y, solution):
    if not X:
        yield list(solution)
    else:
        c = min(X, key=lambda c: len(X[c]))
        for r in list(X[c]):
            solution.append(r)
            cols = select(X, Y, r)
            for s in solve(X, Y, solution):
                yield s
            deselect(X, Y, r, cols)
            solution.pop()

def select(X, Y, r):
    cols = []
    for j in Y[r]:
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].remove(i)
        cols.append(X.pop(j))
    return cols

def deselect(X, Y, r, cols):
    for j in reversed(Y[r]):
        X[j] = cols.pop()
        for i in X[j]:
            for k in Y[i]:
                if k != j:
                    X[k].add(i)

grid = [
    [0,0,0,4,0,2,0,0,0],
    [0,0,0,0,0,5,0,0,3],
    [1,0,0,0,7,0,0,9,6],
    [6,0,0,0,3,0,0,0,0],
    [0,0,0,0,0,0,2,0,0],
    [0,0,4,0,0,0,7,0,0],
    [0,0,0,0,9,0,0,0,0],
    [0,0,0,0,0,0,0,0,1],
    [0,0,5,7,0,4,0,0,0]]

for solution in solve_sudoku((3, 3), grid):
    print(*solution, sep='\n')
复制代码

跳跃的舞者，舞蹈链（Dancing Links）算法——求解精确覆盖问题
算法实践——舞蹈链（Dancing Links）算法求解数独

17提示数的题库资源
四万多道17提示数的数独题
用C链表实现的DLX算法，加-O2编译优化，i7 CPU，printf不计入，解这四万多题只要3-6秒。
（参考算法实践——舞蹈链（Dancing Links）算法求解数独 最后一个评论，这个人用C重新实现，也是3秒。）

happy886rr

回复 22# 523066680
太牛叉了，4万道6秒。

523066680

正在学着用 github，代码已提交
https://github.com/vicyang/Sudoku/tree/master/Solver/DancingLinks

ChinaUnix 的rubyish把他的方案也写成了C版本，我在上面套了 fill_one_possible_num 函数 后，解sudoku17.txt 也是6秒，
在 i7 cpu 主机上面，3秒


Rubyish/solve_multiGame.c

happy886rr

回复 24# 523066680
不错，代码整理的很整齐。方便今后他人研究分析。

CrLf

回复 22# 523066680


    那个算法666，看来把人脑的算法套用给电脑，的确不合适