标签
PostgreSQL , 数独 , 求解 , 动态规划
背景
使用《PostgreSQL 生成任意基数数独 - 3》 提供的方法，可以生成有解数独。在不知道数独答案的情况下，如何暴力破解呢？
实际上可以修改一下《PostgreSQL 生成任意基数数独 - 2》 里面的随机生成数独的函数，破解数独。
破解数独函数如下
create or replace function resolve_sudoku(
vsudoku int[] -- 求解数独
) returns int[] as $$
declare
res int[]; -- 结果
dims int := array_length(vsudoku,1); -- X,Y,BOX集合元素个数
dim int := sqrt(dims); -- 基数
vxyb xyb[]; -- 存储每个像素在XYB方向上未填充的元素个数
x int; -- 从xyb[]集合中，按指定方法选中一个像素。 X坐标
y int; -- 从xyb[]集合中，按指定方法选中一个像素。 Y坐标
vloops int := 2*dims; -- 计算N次(实际上就是随机多少次能覆盖到所有的值，值的取值空间为dims，通常来说执行DIMS次，能覆盖到所有的随机数)
vloop int :=0; -- 计算N次计数器
cnt int := 0; -- 统计当前数独总共填充了多少个元素
rand int; -- 随机值
begin
-- 求解
res := vsudoku;
loop
-- 生成每个像素X,Y,B方向的未知值个数
select comp_xyb(res, dim) into vxyb;
-- 选择下一个要填充的像素（根据未知值个数排行，从总未知值最多，按单轴最多的位置中随机取一个位置）
select ax,ay into x,y from
unnest(vxyb) t
where
t.x+t.y+t.b <> 0
order by
(t.x+t.y+t.b) desc ,
greatest(t.x,t.y,t.b) desc
limit 1;
-- 如果全部为0,0,0，说明已解完，返回res。
if not found then
raise notice '计算有解，计算%次，结束。', cnt;
return res;
end if;
-- 初始化以下计算循环次数
vloop := 0;
loop
-- 生成随机值
rand := 1+(random()*(dims-1))::int;
-- 这轮循环无法生成并返回空
if vloop >= vloops then
raise notice '本像素已循环%次，计算无解。已填充%个元素。无解数独如下: %', vloop, cnt, res;
-- return res;
return null;
end if;
-- 循环次数+1
vloop := vloop+1;
-- 横向验证
perform 1 where array(select res[x][generate_series(1,dims)]) && array[rand];
if found then
continue;
end if;
-- 纵向验证
perform 1 where array(select res[generate_series(1,dims)][y]) && array[rand];
if found then
continue;
end if;
-- BOX验证
perform 1 where
array(
select res[xx][yy] from
(select generate_series(((((x-1)/dim)::int)*dim)+1, ((((x-1)/dim)::int)*dim)+dim) xx) t1,
(select generate_series(((((y-1)/dim)::int)*dim)+1, ((((y-1)/dim)::int)*dim)+dim) yy) t2
) && array[rand];
if found then
continue;
end if;
-- 这个像素值，通过验证
res[x][y] := rand;
-- raise notice 'res[%][%] %', x, y, rand;
-- 通过验证并跳出循环，找下一个需要填充的像素
cnt := cnt+1;
exit;
end loop;
end loop;
end;
$$ language plpgsql strict volatile;
例子
1、首先按难易程度生成几个数独
postgres=# select gen_sudoku_question(20);
gen_sudoku_question
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
{{1,6,7,9,5,8,4,3,2},{9,5,8,4,3,2,1,6,7},{4,3,2,1,6,7,9,5,8},{6,7,1,5,8,9,3,2,4},{5,8,9,3,2,4,6,7,1},{3,2,4,6,7,1,5,8,9},{7,1,6,8,9,5,2,4,3},{8,9,5,2,4,3,7,1,6},{2,4,3,7,1,6,8,9,5}}
{{1,0,7,9,0,8,4,3,2},{9,0,8,0,3,2,0,6,7},{4,3,2,1,6,7,0,5,8},{6,0,1,0,8,9,0,2,4},{5,0,9,3,2,4,0,7,1},{3,2,0,6,7,1,5,8,9},{7,1,0,0,0,5,0,4,3},{0,9,5,2,4,0,7,1,6},{0,4,3,7,0,6,8,9,5}}
(2 rows)
postgres=# select gen_sudoku_question(41);
NOTICE: relation "tmp_sudoku" already exists, skipping
gen_sudoku_question
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
{{5,3,9,2,6,7,1,4,8},{1,4,8,5,3,9,2,6,7},{2,6,7,1,4,8,5,3,9},{9,5,3,7,2,6,8,1,4},{8,1,4,9,5,3,7,2,6},{7,2,6,8,1,4,9,5,3},{3,9,5,6,7,2,4,8,1},{4,8,1,3,9,5,6,7,2},{6,7,2,4,8,1,3,9,5}}
{{5,0,0,2,0,7,1,0,8},{0,4,0,0,0,9,0,6,7},{2,0,7,0,0,0,0,0,0},{9,0,3,0,2,6,8,1,4},{0,1,0,0,0,0,7,0,6},{0,0,6,0,0,0,0,5,3},{0,9,0,6,0,2,4,0,1},{4,8,0,0,9,0,6,7,2},{6,0,2,4,0,1,0,0,5}}
(2 rows)
postgres=# select gen_sudoku_question(51);
NOTICE: relation "tmp_sudoku" already exists, skipping
gen_sudoku_question
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
{{3,4,5,8,1,6,2,9,7},{8,1,6,2,9,7,3,4,5},{2,9,7,3,4,5,8,1,6},{4,5,3,1,6,8,9,7,2},{1,6,8,9,7,2,4,5,3},{9,7,2,4,5,3,1,6,8},{5,3,4,6,8,1,7,2,9},{6,8,1,7,2,9,5,3,4},{7,2,9,5,3,4,6,8,1}}
{{0,4,5,0,0,6,2,9,0},{8,1,0,0,0,0,0,4,0},{2,0,0,3,4,0,8,0,6},{0,0,3,1,6,8,0,0,0},{0,0,8,0,0,0,4,5,0},{0,0,0,4,0,0,1,6,0},{0,0,0,0,0,1,0,0,9},{6,0,0,7,0,0,0,3,4},{0,0,0,0,0,0,0,0,1}}
(2 rows)
2、使用上面创建的函数破解数独
填充20个值的数独基本上秒解。
postgres=# select res from (select resolve_sudoku('{{1,0,7,9,0,8,4,3,2},{9,0,8,0,3,2,0,6,7},{4,3,2,1,6,7,0,5,8},{6,0,1,0,8,9,0,2,4},{5,0,9,3,2,4,0,7,1},{3,2,0,6,7,1,5,8,9},{7,1,0,0,0,5,0,4,3},{0,9,5,2,4,0,7,1,6},{0,4,3,7,0,6,8,9,5}}'::int[]) res from generate_series(1,100) ) t where t.res is not null ;
res
---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
{{1,6,7,9,5,8,4,3,2},{9,5,8,4,3,2,1,6,7},{4,3,2,1,6,7,9,5,8},{6,7,1,5,8,9,3,2,4},{5,8,9,3,2,4,6,7,1},{3,2,4,6,7,1,5,8,9},{7,1,6,8,9,5,2,4,3},{8,9,5,2,4,3,7,1,6},{2,4,3,7,1,6,8,9,5}}
(1 row)
但是对于需要填充41个，51个的，这种暴力尝试的方式，跑1000次也解不出来。
还是需要一个非常行之有效的。
目前的暴力破解存在的问题，一个值一旦确定下来（XYB方向满足约束）之后，后面就不会去修正它，从而导致了一个错误后面的计算全是浪费的。增加了破解成本。
扩展
在数据库中执行计划也与之类似，目前大多数执行计划是静态的，一旦执行计划确定下来了，后面就只能按照执行计划执行，无法中途调整。
所以，动态执行计划也成为目前很多数据库优化器突破的方向，在执行过程中，根据执行过程中的统计信息，不断修正执行计划，达到最佳的目的。
实际上，导航也与之类似，如果你根据当前的路况规划好了导航，在行驶过程中，可能某些路段发生了变化（拥堵情况），静态导航就无法修正这样的问题，还是按一开始既定的线路行驶。而动态导航，可以根据实时路况进行修正，选择下一跳。
在生产中有很多类似的例子，比如数据路由，负载均衡等等。
