我的书签
添加书签
移除书签背景
不知道什么时候开始数独游戏风靡起来了，数独游戏由一个N*N的矩阵组成，N必须是一个可以被开根的数值，例如4,9,16,25等。
任意一个像素，必须在三个方向上保证值唯一。这三个方向分别是X,Y,BOX。XY很好理解就是纵横的一条线（X,Y的像素个数就是N）。BOX指这个像素所在的BOX（BOX是由 (N的平方根)*(N的平方根) 个像素组成的矩阵）。
如图，一个9*9个像素的数独。（我把基数称为3）
1616的数独，16行，16列。同时分成44个BOX。（我把基数称为4）
那么如何生成一个有解的数独呢？
这个方法可行吗？
以下方法是按从左到右，从上到下的顺序来生成随机数的，看起来可行，实际上大多数情况下都无法生成有解数独，因为前面还比较容易满足条件，后面基本上就无法满足条件了。
1. create or replace function gen_sudoku(
2. dim int -- 基数
3. ) returns int[] as $$
4. declare
5. res int[];
6. vloops int := 2 * (dim^5);
7. vloop int :=0;
8. ovloops int := 2 * (dim^5);
9. ovloop int :=0;
10. rand int;
11. begin
12. -- 初始化矩阵
13. select array( select (select array_agg(0) from generate_series(1,(dim^2)::int)) from generate_series(1,(dim^2)::int)) into res;
15. loop
16. -- 无法生成并返回
17. if ovloop >= ovloops then
18. raise notice '已循环%次，可能无法生成数独。', ovloop;
19. return res;
20. end if;
21. ovloop := ovloop+1;
23. <<outer>>
24. for x in 1..dim^2 loop
25. raise notice 'start again %', ovloop;
26. for y in 1..dim^2 loop
27. vloop := 0;
28. loop
29. -- 生成随机值
30. rand := 1+(random()*((dim^2)-1))::int;
32. -- 这轮循环无法生成并返回
33. if vloop >= vloops then
34. -- raise notice '1 %此数已循环%次，可能无法生成数独。', rand, vloop;
35. -- return res;
36. exit outer;
37. end if;
38. vloop := vloop+1;
40. -- 横向验证
41. perform 1 where array(select res[x][generate_series(1,(dim^2)::int)]) && array[rand];
42. if found then
43. --raise notice '2 %此数已循环%次，可能无法生成数独。%', rand, vloop, array(select res[x][generate_series(1,(dim^2)::int)]) ;
44. continue;
45. end if;
47. -- 纵向验证
48. perform 1 where array(select res[generate_series(1,(dim^2)::int)][y]) && array[rand];
49. if found then
50. --raise notice '3 %此数已循环%次，可能无法生成数独。%', rand, vloop, array(select res[generate_series(1,(dim^2)::int)][y]);
51. continue;
52. end if;
54. -- BOX验证
55. 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];
56. if found then
57. --raise notice '4 %此数已循环%次，可能无法生成数独。%', rand, vloop, 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);
58. continue;
59. end if;
61. -- 通过验证
62. res[x][y] := rand;
63. raise notice 'res[%][%] %', x, y, rand;
64. -- 跳出循环
65. exit;
66. end loop;
67. end loop;
68. end loop;
69. end loop;
70. return res;
71. end;
72. $$ language plpgsql strict;
以上方法最大的问题是，因为是左右，前后顺序在生成数独，实际上越到后面，会导致可以填充的满足XYB约束值越少，甚至没有。
为了尽可能的每次填充的值都有较大概率，可以在生成顺序上进行调整，不使用从左到右，从上到下的方法。
而是每一步都选择在XYB方向上还有最大概率（即最多没有填充的值）的像素。（我不清楚下围棋先占4个角，是不是也是同样的道理？）
如何找到每个像素在XYB维度上还有多少个未填充的值？
输入一个矩阵，得到另一个矩阵，表示当前位置在XYB轴的未填充值的个数。（非空值的xyb返回x,y,0,0,0）因为非空值不需要再填充它，所以无所谓。
1、首先要创建一个类型，包括数独矩阵的 X,Y坐标。以及这个坐标的横、竖、BOX三个方向上的剩余未填充值的个数。
1. create type xyb as (
2. ax int, -- 横坐标
3. ay int, -- 纵坐标
4. x int, -- 横向还有多少未填充像素
5. y int, -- 竖向还有多少未填充像素
6. b int -- BOX内还有多少未填充像素
7. );
2、编写一个函数，用来计算一个为完成数独矩阵，其每一个像素的XYB值。
1. create or replace function comp_xyb(
2. int[], -- 包含一些值的数独二维矩阵，当像素值为0时，表示这个值没有填充
3. int -- 数独的基数（比如2,3，。。。），3就是常见的9*9数独，4就是16*16数独。
4. )
5. returns xyb[] -- 返回一个复合类型的数组矩阵，矩阵像素和输入矩阵一样，每个像素表示这个像素在XYB轴上还有多少个没有填充的值（没有填充的值用0表示）
6. as $$
7. declare
8. dims int := ($2)^2; -- 基数的平方，表示行、列、BOX的像素个数。也是每个方向上的矩阵标记上限
9. res xyb[]; -- 结果
11. vx int; -- 横向还有多少未填充像素
12. vy int; -- 竖向还有多少未填充像素
13. vb int; -- BOX内还有多少未填充像素
15. lx int; -- box的X方向矩阵下标
16. ux int; -- box的X方向矩阵上标
17. ly int; -- box的Y方向矩阵下标
18. uy int; -- box的Y方向矩阵上标
19. begin
20. -- 初始化矩阵
21. select array (
22. select array( select format('(%s,%s,0,0,0)', x, y) from generate_series(1,dims) t(y))
23. from (select generate_series(1, dims) x) t
24. )
25. into res;
27. -- X坐标
28. for x in 1..dims loop
29. -- Y坐标
30. for y in 1..dims loop
32. -- 如果这个像素的值不等于0，说明已经是一个已经填充过的像素，返回0,0,0
33. if ($1)[x][y] <> 0 then
34. -- 不计算已填充了非0值的像素
35. continue;
36. else
37. -- x，计算X方向有多少个未填充的像素
38. select sum(case arr when 0 then 1 else 0 end) from
39. (select ($1)[x][generate_series(1, dims)] as arr) t
40. into vx;
42. -- y，计算Y方向有多少个未填充的像素
43. select sum(case arr when 0 then 1 else 0 end) from
44. (select ($1)[generate_series(1, dims)][y] as arr) t
45. into vy;
47. -- b，计算BOX内有多少个未填充的像素
48. -- x下限
49. lx := ((x-1)/$2)::int * $2 + 1;
50. -- x上限
51. ux := ((x-1)/$2)::int * $2 + $2;
52. -- y下限
53. ly := ((y-1)/$2)::int * $2 + 1;
54. -- y上限
55. uy := ((y-1)/$2)::int * $2 + $2;
56. -- 计算BOX内有多少个未填充的像素
57. select sum(case arr when 0 then 1 else 0 end) from
58. (select ($1)[xx][yy] as arr from
59. (select generate_series(lx,ux) xx) t1, (select generate_series(ly,uy) yy) t2
60. ) t into vb;
62. -- 将XYB的值，写入结果变量的对应像素中
63. res[x][y] := format('(%s,%s,%s,%s,%s)',x,y,vx,vy,vb)::xyb;
64. end if;
65. end loop;
66. end loop;
67. return res;
68. end;
69. $$ language plpgsql strict immutable;
3、用法举例
计算以下2为基数，4*4的矩阵的xyb值
1. {1,2,3,4}
2. {0,1,1,0}
3. {0,1,1,0}
4. {0,1,1,0}
1. postgres=# select array(select (comp_xyb('{ {1,2,3,4},{0,1,1,0},{0,1,1,0},{0,1,1,0} }', 2))[x][generate_series(1,4)]) from generate_series(1,4) t(x);
2. array
3. -----------------------------------------------------------
4. {"(1,1,0,0,0)","(1,2,0,0,0)","(1,3,0,0,0)","(1,4,0,0,0)"}
5. {"(2,1,2,3,1)","(2,2,0,0,0)","(2,3,0,0,0)","(2,4,2,3,1)"}
6. {"(3,1,2,3,2)","(3,2,0,0,0)","(3,3,0,0,0)","(3,4,2,3,2)"}
7. {"(4,1,2,3,2)","(4,2,0,0,0)","(4,3,0,0,0)","(4,4,2,3,2)"}
8. (4 rows)
使用unnest可以解开，按XYB三个方向总大小排序，再按某个方向最大排序，从而做到逐级收敛，真正每一次填充的像素，都是具备最大概率的像素。
1. postgres=# select * from
2. unnest(
3. comp_xyb('{ {1,2,3,4},{0,1,1,0},{0,1,1,0},{0,1,1,0} }', 2)
4. ) t
5. where
6. t.x+t.y+t.b <> 0
7. order by
8. (t.x+t.y+t.b) desc,
9. greatest(t.x,t.y,t.b) desc;
11. ax | ay | x | y | b
12. ----+----+---+---+---
13. 3 | 1 | 2 | 3 | 2
14. 3 | 4 | 2 | 3 | 2
15. 4 | 1 | 2 | 3 | 2
16. 4 | 4 | 2 | 3 | 2
17. 2 | 1 | 2 | 3 | 1
18. 2 | 4 | 2 | 3 | 1
19. (6 rows)
通过这个SQL得到了某个像素，这个像素的XYB方向上，还有最多的像素没有被填充。
因此这个像素如果生成一个随机值的话，违反数独的约束（或者叫冲突）的概率是最小的。
1. postgres=# select * from
2. unnest(
3. comp_xyb('{ {1,2,3,4},{0,1,1,0},{0,1,1,0},{0,1,1,0} }', 2)
4. ) t
5. where
6. t.x+t.y+t.b <> 0
7. order by
8. (t.x+t.y+t.b) desc,
9. greatest(t.x,t.y,t.b) desc
10. limit 1;
12. ax | ay | x | y | b
13. ----+----+---+---+---
14. 3 | 1 | 2 | 3 | 2
15. (1 row)
用AX,ZY坐标值，往矩阵的这个像素填充符合数独条件的随机值，可以大幅提高构造可解数独的概率。
小结
本文先介绍如何得到这样的一个像素，填充一个值进行，这个值的取值区间应该是最大的（最不会与数独的游戏规则违背），从而更大可能的生成一个完整可解的数独。
下面一篇文章再介绍如何生成一个N*N的数独。
参考
http://poj.org/problem?id=3074
NP完全问题近似求解。
