PostgreSQL 生成任意基数数独 - 2
背景
《PostgreSQL 生成任意基数数独 - 1》 提供了一种方法,计算一个未完成的数独矩阵每个像素在XYB方向上还有多少个未填充的像素。
通过XYB的值,进行各种排序,选出下一个要填充的像素,进行随机填充。
可以通过调整规则,实现不同的填充位置选择,从而达到生成可解数独的目的。
创建一个生成以N为基数的数独的函数
函数输入条件为N(基数),例如81个像素的数独,基数为3。(3*3)平方。
返回一个数独(如果无解的话,raise出来).
create or replace function gen_sudoku(
dim int -- 基数
) returns int[] as $$
declare
res int[]; -- 结果
dims int := dim^2; -- X,Y,BOX集合元素个数
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
-- 初始化矩阵
select array( select (select array_agg(0) from generate_series(1,dims)) from generate_series(1,dims)) into res;
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、生成基数为2的数独,16个像素。
postgres=# select sudo from (select gen_sudoku(2) as sudo from generate_series(1,50)) t where sudo is not null limit 1;
NOTICE: 计算有解,计算16次,结束。
sudo
-------------------------------------------
{{3,4,2,1},{2,1,4,3},{1,2,3,4},{4,3,1,2}}
(1 row)
Time: 30.798 ms
2、生成基数为3的数独,81个像素。
但是非常的遗憾,填充个数50个左右,后面就没法符合速度条件进行填充了。
postgres=# select sudo from (select gen_sudoku(3) as sudo from generate_series(1,10)) t where sudo is not null limit 1;
NOTICE: 本像素已循环18次,计算无解。已填充45个元素。无解数独如下: {{5,3,6,2,0,0,0,8,0},{0,9,0,5,8,4,6,0,0},{7,0,0,6,0,0,5,2,4},{6,4,5,3,0,0,0,9,0},{0,8,0,9,7,5,0,4,0},{1,0,0,0,2,0,3,7,8},{0,7,4,0,5,6,0,0,3},{0,0,3,0,1,2,8,0,5},{9,0,8,0,0,3,4,0,6}}
NOTICE: 本像素已循环18次,计算无解。已填充46个元素。无解数独如下: {{8,3,9,2,4,0,0,5,0},{0,2,0,6,3,9,8,0,0},{1,0,0,5,0,0,4,7,6},{7,8,2,3,0,0,0,1,0},{0,9,0,4,2,6,0,8,0},{3,0,0,0,8,0,5,4,7},{0,4,7,0,1,5,0,0,8},{0,0,6,0,7,4,2,0,3},{5,0,8,0,0,3,7,0,1}}
NOTICE: 本像素已循环18次,计算无解。已填充49个元素。无解数独如下: {{8,4,6,1,9,0,0,2,0},{9,2,0,7,5,6,8,0,0},{3,0,0,4,0,0,1,5,6},{5,7,3,2,0,1,0,4,0},{0,9,4,3,8,7,0,1,0},{6,0,0,0,4,0,3,9,8},{0,5,8,0,6,4,0,0,7},{0,0,1,0,3,2,5,0,4},{4,0,2,0,0,5,6,0,1}}
NOTICE: 本像素已循环18次,计算无解。已填充45个元素。无解数独如下: {{6,8,2,3,0,0,0,4,0},{0,5,0,7,2,1,9,0,0},{7,0,0,9,0,0,1,5,3},{1,3,4,6,0,0,0,9,0},{0,9,0,8,1,3,0,6,0},{8,0,0,0,4,0,3,2,7},{0,2,7,0,5,6,0,0,4},{0,0,9,0,8,2,7,0,5},{4,0,3,0,0,7,8,0,2}}
NOTICE: 本像素已循环18次,计算无解。已填充45个元素。无解数独如下: {{1,6,7,9,0,0,0,5,0},{0,2,0,4,3,8,7,0,0},{4,0,0,5,0,0,8,6,3},{3,5,8,7,0,0,0,2,0},{0,7,0,1,2,6,0,3,0},{6,0,0,0,9,0,5,4,1},{0,8,1,0,5,2,0,0,4},{0,0,5,0,7,3,6,0,2},{2,0,4,0,0,1,9,0,8}}
NOTICE: 本像素已循环18次,计算无解。已填充50个元素。无解数独如下: {{2,3,5,6,9,0,0,7,0},{6,7,0,2,8,4,1,0,0},{4,0,0,7,0,0,9,8,5},{1,4,7,3,0,8,0,5,0},{0,9,3,5,7,6,0,4,0},{5,0,0,0,4,0,2,6,3},{0,2,8,4,3,7,0,0,1},{0,0,1,0,6,5,3,0,2},{3,0,6,0,0,2,8,0,7}}
NOTICE: 本像素已循环18次,计算无解。已填充46个元素。无解数独如下: {{2,6,7,9,5,0,0,8,0},{0,5,0,2,4,1,3,0,0},{1,0,0,6,0,0,4,5,7},{8,7,9,4,0,0,0,3,0},{0,1,0,3,2,6,0,4,0},{3,0,0,0,8,0,6,2,9},{0,3,5,0,1,7,0,0,2},{0,0,8,0,6,3,9,0,5},{4,0,6,0,0,9,8,0,1}}
NOTICE: 本像素已循环18次,计算无解。已填充29个元素。无解数独如下: {{4,3,2,5,0,0,0,0,0},{0,0,0,6,8,7,0,0,0},{0,0,0,0,0,0,1,9,4},{6,5,0,4,0,0,0,7,0},{0,1,0,8,3,0,0,0,0},{2,0,0,0,0,0,3,5,0},{0,0,3,0,0,8,0,0,5},{0,0,4,0,5,9,0,0,0},{9,0,0,0,0,0,2,0,3}}
NOTICE: 本像素已循环18次,计算无解。已填充46个元素。无解数独如下: {{4,8,3,5,9,0,0,1,0},{0,5,0,7,4,1,2,0,0},{1,0,0,2,0,0,7,3,8},{9,6,8,3,0,0,0,4,0},{0,2,0,4,1,5,0,7,0},{7,0,0,0,8,0,3,5,6},{0,4,9,0,5,3,0,0,7},{0,0,2,0,7,6,5,0,3},{6,0,7,0,0,4,8,0,2}}
NOTICE: 本像素已循环18次,计算无解。已填充56个元素。无解数独如下: {{5,6,3,8,4,0,7,2,0},{4,2,0,9,7,1,5,0,0},{8,9,0,2,0,0,1,4,3},{3,7,5,4,0,9,0,6,2},{0,4,9,1,2,8,0,5,0},{2,0,6,0,5,0,9,3,8},{0,3,2,5,1,7,0,0,6},{0,5,8,0,6,4,3,0,9},{6,0,1,0,0,3,4,8,7}}
sudo
------
(0 rows)
Time: 1037.195 ms (00:01.037)
调整选取填充像素的方法
1、从各维度冲突最大的开始填充
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) ,
greatest(t.x,t.y,t.b)
limit 1;
使用这种选择像素的方法,从填充像素个数来看,很快就会发现无解,因为冲突最大化了。
NOTICE: 本像素已循环18次,计算无解。已填充35个元素。无解数独如下: {{5,7,2,4,6,3,1,8,9},{8,1,4,5,7,9,2,3,6},{6,9,3,2,8,1,5,4,7},{9,4,6,0,0,0,0,0,0},{3,5,7,0,0,0,0,0,0},{1,8,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}
NOTICE: 本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{1,2,6,7,9,8,0,0,0},{3,8,4,1,5,2,0,0,0},{5,7,9,4,6,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}
NOTICE: 本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{1,2,5,9,3,4,0,0,0},{7,9,6,2,1,8,0,0,0},{3,8,4,6,5,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}
NOTICE: 本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{7,5,6,8,4,9,0,0,0},{4,3,8,5,2,6,0,0,0},{2,1,9,7,3,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}
NOTICE: 本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{7,2,6,9,5,3,0,0,0},{3,4,1,6,8,2,0,0,0},{5,8,9,7,4,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}
NOTICE: 本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{8,3,7,6,4,2,0,0,0},{1,6,5,8,9,3,0,0,0},{4,9,2,7,5,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}
NOTICE: 本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{8,7,4,9,6,5,0,0,0},{3,5,2,7,4,8,0,0,0},{1,6,9,2,3,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}
NOTICE: 本像素已循环18次,计算无解。已填充8个元素。无解数独如下: {{7,4,5,0,0,0,0,0,0},{9,3,2,0,0,0,0,0,0},{8,6,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}
NOTICE: 本像素已循环18次,计算无解。已填充17个元素。无解数独如下: {{3,6,7,5,1,8,0,0,0},{5,1,2,9,6,3,0,0,0},{4,8,9,7,2,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}
NOTICE: 本像素已循环18次,计算无解。已填充8个元素。无解数独如下: {{3,2,8,0,0,0,0,0,0},{7,4,9,0,0,0,0,0,0},{6,5,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0},{0,0,0,0,0,0,0,0,0}}
sudo
------
(0 rows)
Time: 486.963 ms
2、你还可与根据其他的想法来选择每次需要填充的像素。
从BOX维度冲突最小,x,y维度冲突最小的像素开始填充
select ax,ay into x,y from
unnest(vxyb) t
where
t.x+t.y+t.b <> 0
order by
t.b desc ,
greatest(t.x,t.y) desc
limit 1;
小结
暂时使用这几种方法,经过少量的计算,无法生成有解的数独。
1、选择下一个要填充的像素(根据未知值个数排行,从总未知值最多,按单轴最多的位置中随机取一个位置)
2、从BOX维度冲突最小,x,y维度冲突最小的像素开始填充
3、从各维度冲突最大的开始填充
随机的方法生成数独,效率比较低,维度越高,生成成功的概率越低。需要寻找更高效的生成数独的方法。
参考
NP完全问题近似求解。