回溯法求解数独

问题描述

昨晚，朋友问了一个关于求解数独的问题。ta称其所用回溯算法虽能成功求解，但耗时颇多，而参考B站算法只需2s。我询问ta是不是没有及时剪枝或者用于判断数独的函数太慢。此时的我还只是上数据与结构课时听了回溯法这一算法的概念，从未真正用过，不过事情的结果证明我所提及的两个问题在代码中都有出现。

问题简单概括，就是给定一个数独矩阵，要求给出一组解，需使用matlab完成。给出问题框架如下：

F =[NaN    2   NaN   NaN     3   NaN   NaN     4   NaN;
     6   NaN   NaN   NaN   NaN   NaN   NaN   NaN     3;
   NaN   NaN     4   NaN   NaN   NaN     5   NaN   NaN;
   NaN   NaN   NaN     8   NaN     6   NaN   NaN   NaN;
     8   NaN   NaN   NaN     1   NaN   NaN   NaN     6;
   NaN   NaN   NaN     7   NaN     5   NaN   NaN   NaN;
   NaN   NaN     7   NaN   NaN   NaN     6   NaN   NaN;
     4   NaN   NaN   NaN   NaN   NaN   NaN   NaN     8;
   NaN     3   NaN   NaN     4   NaN   NaN     2   NaN];

tic
res = sudoku_solve(F,1);
elapsedTime = toc;

disp(res);
disp(['代码执行时间: ', num2str(elapsedTime), '秒']);

漫长的debug

程序不能及时停止

一开始的解法如下：（此前已经弃用了unique()和setdiff()函数，效率大幅提升）

function sudoku_solve(matrix,id)
    if id>81
        disp(matrix);
        return;
    else
        row = floor((id-1)/9)+1;
        col = mod((id-1),9)+1;
        gong = matrix(3*floor((row-1)/3)+1:3*floor((row-1)/3)+3, 3*floor((col-1)/3)+1:3*floor((col-1)/3)+3);
        if ~isnan(matrix(row,col))
            sudoku_solve(matrix,id+1);
        else
            for num = 1:9
                if (~ismember(num,matrix(row, :))) ...
                && (~ismember(num,matrix(:, col)')) ...
                && (~ismember(num,gong(:)'))
                    matrix(row,col) = num;
                    sudoku_solve(matrix,id +1);
                end
            end
        end
    end
end

这里的代码就是朋友参考的B站的解法，在我电脑上求解原数独问题大致需要10s。但是它有一个bug：求解出来的数独的第一格填的数字是9，于是我们面向结果编程，将for循环改为for num = 9:-1:1，发现确实能很快输出正确结果，但是程序在输出结果后还会接续运行，最终实际运行时间与改之前无异。

面对这样的bug，我首先想到的是for循环中得到结果后没有及时返回（对应之前“没有及时剪枝”），所以在for循环中加入了这样的代码：

if id == 81
    return
end

只能说我的直觉是准的，但是对我的代码水平来说还是过于超前 : )

运行结果表明这样修改后程序效率没有提升，我顿时陷入迷茫。其实这个判断语句没有起到作用，得到结果后，多层调用的递归函数一层层返回，每一层的id值随深度依次增加，最深层是82，表明得到结果，然后返回到倒数第二层，此时id为81，判断语句为真，继续返回（还跳出了for循环）；但是倒数第三层以及后续的id都小于81，所以我新写的代码就失效了。所以这里也能看出出现bug的原因：正确结果没有及时返回，for循环体继续执行。

需要返回值

前一个bug还未解决，朋友提出了新需求，希望这个函数有返回值，于是ta修改代码如下：

function result = sudoku_solve(matrix,id)
    if id>81
        result = matrix;
        return;
    else
        row = floor((id-1)/9)+1;
        col = mod((id-1),9)+1;
        gong = matrix(3*floor((row-1)/3)+1:3*floor((row-1)/3)+3, 3*floor((col-1)/3)+1:3*floor((col-1)/3)+3);
        if ~isnan(matrix(row,col))
            result = sudoku_solve(matrix,id+1);
        else
            for num = 1:9
                if (~ismember(num,matrix(row, :))) ...
                && (~ismember(num,matrix(:, col)')) ...
                && (~ismember(num,gong(:)'))
                    matrix(row,col) = num;
                    result = sudoku_solve(matrix,id +1);
                end
            end
        end
    end
end

但是这样的代码运行会报错，原因在于不是每个分支都有return值。具体问题出现在for循环中的if语句，在判断为真的情况下，显然result是有赋值的；但是如果判断为假就会发生rseult未被定义的问题，该分支就没有返回值了。所以解决问题就是，在函数体开头就写上rseult = []。

然后，朋友提出了解决第一个bug的方法：在result = sudoku_solve(matrix,id +1);下添加如下代码：

if ~isempty(rseult)
    return;
end

这一改动很轻松地解决了此前程序算出正确结果后没有及时返回的问题，不会执行多余的运算，因此效率得到提升，在for num = 9:-1:1的情况下仅需2s左右。

运行时间还是太长

程序的运行时间太依赖与数独的解的情况，正如之前所说，这个数独的第一格填的是9，所以当我们使用for num = 9:-1:1时效率会比较高，直接跳过了回溯中的好几次漫长搜索过程。如果继续使用for num = 1:9的话，运行时间还是长达8s左右。

第二天上午（今早），朋友再次与我讨论回溯法的细节，我便试图优化程序以进一步提升效率。最终，我发现，matlab函数ismember()效率很慢。我修改了代码的一些结构，重写如下：

代码较长，点击展开 >folded

function [result] = sudoku_solve(matrix,id)
 
    result = [];

    if id>81
        result = matrix;
        return
    end

    row = floor((id-1)/9)+1;
    col = mod((id-1),9)+1;
    
    if ~isnan(matrix(row,col))
        result = sudoku_solve(matrix,id+1);
        return
    end

    g_row = 3*floor((row-1)/3);
    g_col = 3*floor((col-1)/3);
    gong = matrix(g_row+1:g_row+3, g_col+1:g_col+3);
    for num = 1:9
        if (~hasmember(num,matrix(row, :))) ...
        && (~hasmember(num,gong(:)')) ...
        && (~hasmember(num,matrix(:, col)'))

            matrix(row,col) = num;
            result = sudoku_solve(matrix,id +1);
            if ~isempty(result)
                return
            end
        end
    end  
end

function res = hasmember(num, array)

    res = false;
    for i=1:9
        if array(i) == num
            res = true;
            return
        end
    end
end

这一改动使得1:9耗时2秒，9:-1:1仅需0.6秒！

一点心得

前前后后大概花了3个多小时解决这个问题，唯一体会就是matlab一点也不适合写算法。

通过这个题加深了对回溯法的理解，随后较为轻松地解决了N皇后问题。