[挑战]解数独程序与数独题目生成

523066680

以下是从某网站提取的5种难度的数独游戏（难度从1-5，循着网站是可以找到答案的）：
001000008800010532750024090005302060670500004010780900098053406426179803537460219
503092000700000008006007310020600000065000730007043500000706102070000800400009000
700306000000000050060000018000081000000000000900000200000200900050400000080000007
030000001200806000000005000000000000000000650043070000600002080090000000000010003
010000200300800000000504000800090000000070120500000000000000000020130000400000005

写程序对这五个数独题目求解，并计算解每道题的时间消耗。
编程语言：不限

------------------------------------------ 2017-09-18补充 ------------------------------------------
如果解决上面五道题耗时不超过1秒，可以尝试批量解题库中的题，并统计时间消耗。

题库下载：http://523066680.ys168.com/
Perl/数独/数独题库200801-201709_含答案.zip

题库按键值对存储，key 是时间戳，value 中前81个字符是题目，后81个字符是唯一答案。
nd0 - nd4 表示不同的难度。

523066680

脚本，每填入一个数字，重新判断并缩小范围，第四道数独花了五百多秒 ……

2,6,1,9,3,5,7,4,8
8,4,9,6,1,7,5,3,2
7,5,3,8,2,4,6,9,1
9,8,5,3,4,2,1,6,7
6,7,2,5,9,1,3,8,4
3,1,4,7,8,6,9,2,5
1,9,8,2,5,3,4,7,6
4,2,6,1,7,9,8,5,3
5,3,7,4,6,8,2,1,9
Game level: 1, time used: 0.000s

8,3,6,9,4,7,5,2,1
2,5,1,8,3,6,4,9,7
4,7,9,1,2,5,8,3,6
9,6,8,2,5,1,3,7,4
1,2,7,4,8,3,6,5,9
5,4,3,6,7,9,2,1,8
6,1,4,3,9,2,7,8,5
3,9,5,7,6,8,1,4,2
7,8,2,5,1,4,9,6,3
Game level: 4, time used: 537.594s
复制代码

--------------- 2017-09-14 蜜汁 Trick ----------------

8,3,6,9,4,7,5,2,1
2,5,1,8,3,6,4,9,7
4,7,9,1,2,5,8,3,6
9,6,8,2,5,1,3,7,4
1,2,7,4,8,3,6,5,9
5,4,3,6,7,9,2,1,8
6,1,4,3,9,2,7,8,5
3,9,5,7,6,8,1,4,2
7,8,2,5,1,4,9,6,3
[Finished in 2.2s]
复制代码

523066680

回复 3# CrLf

    也不是完全的暴力跑，前三项规则已经应用了，后两项还没有试过。题目的前两道数独秒出结果，第四道耗时很长。

523066680

回复 5# slore

题库在这个网站抓的 免费的在线数独
http://bbs.bathome.net/thread-45401-1-1.html

http://523066680.ys168.com/
Perl/数独/数独题库200801-201709_含答案.zip

难度分为 入门，初级，中级，高级，骨灰级。1楼的题来自每个等级的第一道题目。这个等级划分我也觉得有点问题……  
初级的比如：数独 - 2008年1月6日 - 初级
000600500001007000004000000050002000060000800000001007080900000000500001007000004
比同等级的其他题目明显数字要少，可选数字可能性更多。

523066680

Rosettacode 有一段 Perl 代码非常简短，不过这段代码因为简短而牺牲了性能，有很多冗余的循环。
http://rosettacode.org/wiki/Sudoku#Perl

523066680

初始版本

=info
    解数独 初版
    523066680 2017-09
=cut

use IO::Handle;
use Time::HiRes qw/time/;
STDOUT->autoflush(1);

my @games = 
qw/
    001000008800010532750024090005302060670500004010780900098053406426179803537460219
    503092000700000008006007310020600000065000730007043500000706102070000800400009000
    700306000000000050060000018000081000000000000900000200000200900050400000080000007
    030000001200806000000005000000000000000000650043070000600002080090000000000010003
    010000200300800000000504000800090000000070120500000000000000000020130000400000005
/;

our @unsolve;
our $block = [];  #区块引用
my $mat = [[]];
my $level = 0;
my $time_a;

#创建区块引用，以便于操作
make_block_refs( $block, $mat );

while ( $level <= $#games )
{
    #字符串转矩阵
    str_to_mat( $games[$level] , $mat );
    $time_a = time();

    #设置 @unsolve 数组，存储空缺元素的坐标
    set_unsolve_array($mat);
    solve($mat, 0);
    
    print_mat($mat);
    printf "Game level: %d, time used: %.3fs\n\n", $level+1, time() - $time_a;
    $level++;
}

sub solve
{
    my ($mat, $prev, $lv) = @_;
    my @possible;
    my ($row, $col);
    my $current;

    for my $i ( $prev .. $#unsolve )
    {
        ($row, $col) = @{$unsolve[$i]};
        if ( $mat->[$row][$col] == 0 )
        {
            $current = $i;
            @possible = get_possible_num( $mat, $row, $col );
            last;
        }
    }

    if ( not defined $current ) { return 1 }
    else
    {   
        return 0 if ( $#possible < 0 )
    }

    my $res = 0;
    for my $p ( @possible )
    {
        $mat->[ $row ][ $col ] = $p;
        $res = solve($mat, $current+1, $lv+1);
        last if ($res == 1);
    }

    #使对应单元恢复为0 否则影响递归判断
    $mat->[$row][$col] = 0 if ($res == 0) ;
    return $res;
}

sub get_possible_num
{
    our ($block, %hash);
    my ($mat, $row, $col) = @_;
    my %possible = (1,1,2,2,3,3,4,4,5,5,6,6,7,7,8,8,9,9);

    #排除元素
    for my $n ( 0 .. 8 ) 
    {
        delete $possible{ $mat->[$n][$col] };
        delete $possible{ $mat->[$row][$n] };
        delete $possible{ ${$block->[$row/3][$col/3][$n]} };
    }

    return sort keys %possible;
}

sub get_possible_num_2
{
    our ($block, %hash);
    my ($mat, $row, $col) = @_;
    my @possible = (0,1,2,3,4,5,6,7,8,9);

    #区块坐标
    my $blockrow = int($row/3);
    my $blockcol = int($col/3);

    #排除元素
    for my $n ( 0 .. 9 ) 
    {
        $possible[ $mat->[$n][$col] ] = 0;
        $possible[ $mat->[$row][$n] ] = 0;
        $possible[ ${$block->[$blockrow][$blockcol][$n]} ] = 0;
    }

    return grep { $_ } @possible;
}

sub set_unsolve_array
{
    our ( @unsolve );
    my ($mat) = @_;

    @unsolve = ();
    for my $row ( 0..8 )
    {
        for my $col ( 0..8 )
        {
            if ( $mat->[$row][$col] == 0 )
            {
                push @unsolve, [ $row, $col, [get_possible_num( $mat, $row, $col )] ];
            }
        }
    }

    #根据可选数字的数量由少到多排序
    #@unsolve = sort { $#{$a->[2]} <=> $#{$b->[2]} } @unsolve;
}

sub make_block_refs
{
    my ($block, $mat) = @_;

    #将数独的九个宫对应的引用分组保存
    for my $r ( 0..2 )
    {
        for my $c ( 0..2 )
        {
            for my $rr ( $r*3 .. $r*3+2 )
            {
                for my $cc ( $c*3 .. $c*3+2 )
                {
                    push @{ $block->[$r][$c] }, \$mat->[$rr][$cc];
                }
            }
        }
    }
}

sub str_to_mat
{
    my ( $str, $mat ) = @_;
    my $idx = 0;

    for my $row ( 0 .. 8 )
    {
        for my $col ( 0 .. 8 )
        {
            $mat->[$row][$col] = substr( $str, $idx++, 1 );
        }
    }
}

sub print_mat
{
    my ($mat) = @_;
    grep { print join(",", @{$mat->[$_]} ),"\n" } ( 0..8 );
}
复制代码

Game level: 1, time used: 0.001s
Game level: 2, time used: 0.002s
Game level: 3, time used: 11.373s
Game level: 4, time used: 432.737s
Game level: 5, time used: 24.571s

结果相当难看，有空试试 Dancing Links

523066680

最近换了个方案，遇到难度高的题目时比原来的方案快得多（但还是没有Rubyish @Chinaunix 的代码快）

给定一个题目，判断 1-9 每个数字的全局分布情况（可能性）。
比如1可能分布的情况有6种，测试每一种，把9个1全部填入数独，然后继续测试其他数字的分布。

题目

140968000000000900600057300000000007300000840000196500070000405406010030000000000

数字1的可能分布情况

140968000000001900600057310010000007300000841000196500071000405406010030000000100
140968000000001900600057310000000107310000840000196500071000405406010030000000001
140968000000001900600057301000000107310000840000196500071000405406010030000000010
140968000000001900600057301000000107310000840000196500070000415406010030001000000
140968000000001900600057301000000107301000840000196500070000415406010030010000000
140968000000001900600057301000000017310000840000196500071000405406010030000000100

完整代码：

=info
    方案 - 遍历数字分布情况
    523066680 2017-09
=cut

use File::Slurp;
use IO::Handle;
STDOUT->autoflush(1);

# my $gamedata = eval read_file("../sudoku_nd1.txt");
# grep { push @games, $gamedata->{$_} } sort keys %$gamedata;

@games = 
qw/
    001000008800010532750024090005302060670500004010780900098053406426179803537460219
    503092000700000008006007310020600000065000730007043500000706102070000800400009000
    700306000000000050060000018000081000000000000900000200000200900050400000080000007
    030000001200806000000005000000000000000000650043070000600002080090000000000010003
    010000200300800000000504000800090000000070120500000000000000000020130000400000005
/;

our @order;
our $answer_mat = [[]];
my $mat;
my $res;
my $allcase;
my $answer_str;

#坐标对应区块位置的表
our @blk = map { int($_ / 3) } ( 0..8 );

while ( $index <= $#games )
{
    $mat = [[]];
    $time_a = time();
    str_to_mat( $games[$index] , $mat );

    $allcase = [ map { [] } (0..9) ];
    grep { possible_mat($mat, $_, $allcase->[$_], 0) } (1..9);
    @order = sort { $#{$allcase->[$a]} <=> $#{$allcase->[$b]} } ( 0 .. 9 );

    $res = recursive( $mat, 1 ); #起点为1，下标 0占位

    if ($res == 1) 
    {
        print_mat_inline( $answer_mat );
    }
    else { die "false\n" }

    printf "Game index: %d, time used: %.3fs\n\n", $index, time() - $time_a;
    $index++;
}

sub recursive
{
    our (@order, $answer_mat);
    
    my ( $mat, $lv ) = @_;
    my @case;

    if ( $lv > 9 )
    {
        $answer_mat = $mat;
        return 1;
    }

    $target = $order[$lv];
    possible_mat($mat, $target, \@case, 0);

    my $t_mat = [[]];
    my $res = 0;

    for my $s ( @case )
    {
        str_to_mat( $s, $t_mat );
        $res = recursive( $t_mat, $lv+1 );
        last if ($res == 1);
    }

    return $res;
}

sub possible_mat
{
    my ( $mat, $target, $aref, $lv ) = @_;
    # level means row

    my $str;
    if ($lv == 9)
    {
        $count++;
        push @$aref, mat_to_str($mat);
        return 1;
    }

    my @cols = get_possible_column( $mat, $lv, $target );

    my $res = 0;
    my $ever;
    for my $c ( @cols )
    {
        $ever = $mat->[$lv][$c];
        $mat->[$lv][$c] = $target;
        $res = possible_mat( $mat, $target, $aref, $lv+1 );
        $mat->[$lv][$c] = $ever;
    }

    return $res;
}

sub get_possible_column
{
    our @blk;
    my ( $mat, $row, $target ) = @_;
    my @cols = ( 0..8 );

    for my $c ( 0..8 )
    {
        #如果当前行已经存在这个数字，则直接返回这个数字的位置。
        if ( $mat->[$row][$c] == $target )
        {
            return ( $c );
        }
        elsif ( $mat->[$row][$c] != 0 )
        {
            $cols[$c] = -1;
        }

        for my $r ( 0..8 )
        {
            if ( $mat->[$r][$c] == $target )
            {
                $cols[$c] = -1;
                if ( $blk[$r] == $blk[$row] )
                {
                    $cols[ $blk[$c] * 3 + 0] = -1;
                    $cols[ $blk[$c] * 3 + 1] = -1;
                    $cols[ $blk[$c] * 3 + 2] = -1;
                }
            }
        }
    }

    return grep { $_ != -1 } @cols;
}

sub str_to_mat
{
    my ( $str, $mat ) = @_;
    my $idx = 0;

    for my $row ( 0 .. 8 )
    {
        for my $col ( 0 .. 8 )
        {
            $mat->[$row][$col] = substr( $str, $idx++, 1 );
        }
    }
}

sub mat_to_str
{
    my ( $mat ) = @_;
    return join("", map { join("", @{$mat->[$_]} ) } (0..8));
}

sub print_mat
{
    my ($mat) = @_;
    grep { print join(",", @{$mat->[$_]} ),"\n" } ( 0..8 );
}

sub print_mat_inline
{
    my ($mat) = @_;
    grep { print join("", @{$mat->[$_]} ),"" } ( 0..8 );
    print "\n";
}
复制代码

261935748849617532753824691985342167672591384314786925198253476426179853537468219
Game index: 0, time used: 0.000s

513892467749361258286457319324675981165928734897143526958736142672514893431289675
Game index: 1, time used: 0.000s

718356492492817653563924718624781539835692174971543286147238965356479821289165347
Game index: 2, time used: 0.000s

836947521251836497479125836968251374127483659543679218614392785395768142782514963
Game index: 3, time used: 0.000s

718963254354827961296514873872391546943675128561248739187456392625139487439782615
Game index: 4, time used: 1.000s

跑完 sudoku_nd0.txt 三千多道题需要十多秒，跑完 sudoku_nd4.txt 大约六百秒。
CU Rubyish 的代码，跑完 nd0 零点几秒，nd4 一百多秒

523066680

回复 11# slore

    线程的方案留到最后，单线程仍然有更快的算法，快到解 sudoku_nd4.txt 所有题只要十多秒。

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

523066680

回复 19# bbaa

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

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秒。）

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