标簽
PostgreSQL , 數獨
https://github.com/digoal/blog/blob/master/201803/20180319_01.md#%E8%83%8C%E6%99%AF 背景
不知道什麼時候開始數獨遊戲風靡起來了，數獨遊戲由一個N*N的矩陣組成，N必須是一個可以被開根的數值，例如4,9,16,25等。
任意一個像素，必須在三個方向上保證值唯一。這三個方向分别是X,Y,BOX。XY很好了解就是縱橫的一條線（X,Y的像素個數就是N）。BOX指這個像素所在的BOX（BOX是由 (N的平方根)*(N的平方根) 個像素組成的矩陣）。
如圖，一個9*9個像素的數獨。（我把基數稱為3）
https://github.com/digoal/blog/blob/master/201803/20180319_01_pic_001.jpg1616的數獨，16行，16列。同時分成44個BOX。（我把基數稱為4）
那麼如何生成一個有解的數獨呢？
這個方法可行嗎？
以下方法是按從左到右，從上到下的順序來生成随機數的，看起來可行，實際上大多數情況下都無法生成有解數獨，因為前面還比較容易滿足條件，後面基本上就無法滿足條件了。
create or replace function gen_sudoku( dim int -- 基數 ) returns int[] as $$ declare res int[]; vloops int := 2 * (dim^5); vloop int :=0; ovloops int := 2 * (dim^5); ovloop int :=0; rand int; begin -- 初始化矩陣 select array( select (select array_agg(0) from generate_series(1,(dim^2)::int)) from generate_series(1,(dim^2)::int)) into res; loop -- 無法生成并傳回 if ovloop >= ovloops then raise notice '已循環%次，可能無法生成數獨。', ovloop; return res; end if; ovloop := ovloop+1; <<outer>> for x in 1..dim^2 loop raise notice 'start again %', ovloop; for y in 1..dim^2 loop vloop := 0; loop -- 生成随機值 rand := 1+(random()*((dim^2)-1))::int; -- 這輪循環無法生成并傳回 if vloop >= vloops then -- raise notice '1 %此數已循環%次，可能無法生成數獨。', rand, vloop; -- return res; exit outer; end if; vloop := vloop+1; -- 橫向驗證 perform 1 where array(select res[x][generate_series(1,(dim^2)::int)]) && array[rand]; if found then --raise notice '2 %此數已循環%次，可能無法生成數獨。%', rand, vloop, array(select res[x][generate_series(1,(dim^2)::int)]) ; continue; end if; -- 縱向驗證 perform 1 where array(select res[generate_series(1,(dim^2)::int)][y]) && array[rand]; if found then --raise notice '3 %此數已循環%次，可能無法生成數獨。%', rand, vloop, array(select res[generate_series(1,(dim^2)::int)][y]); 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 --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); continue; end if; -- 通過驗證 res[x][y] := rand; raise notice 'res[%][%] %', x, y, rand; -- 跳出循環 exit; end loop; end loop; end loop; end loop; return res; end; $$ language plpgsql strict; 以上方法最大的問題是，因為是左右，前後順序在生成數獨，實際上越到後面，會導緻可以填充的滿足XYB限制值越少，甚至沒有。
為了盡可能的每次填充的值都有較大機率，可以在生成順序上進行調整，不使用從左到右，從上到下的方法。
而是每一步都選擇在XYB方向上還有最大機率（即最多沒有填充的值）的像素。（我不清楚下圍棋先占4個角，是不是也是同樣的道理？）
https://github.com/digoal/blog/blob/master/201803/20180319_01.md#%E5%A6%82%E4%BD%95%E6%89%BE%E5%88%B0%E6%AF%8F%E4%B8%AA%E5%83%8F%E7%B4%A0%E5%9C%A8xyb%E7%BB%B4%E5%BA%A6%E4%B8%8A%E8%BF%98%E6%9C%89%E5%A4%9A%E5%B0%91%E4%B8%AA%E6%9C%AA%E5%A1%AB%E5%85%85%E7%9A%84%E5%80%BC 如何找到每個像素在XYB次元上還有多少個未填充的值？
輸入一個矩陣，得到另一個矩陣，表示目前位置在XYB軸的未填充值的個數。（非空值的xyb傳回x,y,0,0,0）因為非空值不需要再填充它，是以無所謂。
1、首先要建立一個類型，包括數獨矩陣的 X,Y坐标。以及這個坐标的橫、豎、BOX三個方向上的剩餘未填充值的個數。
create type xyb as ( ax int, -- 橫坐标 ay int, -- 縱坐标 x int, -- 橫向還有多少未填充像素 y int, -- 豎向還有多少未填充像素 b int -- BOX内還有多少未填充像素 ); 2、編寫一個函數，用來計算一個為完成數獨矩陣，其每一個像素的XYB值。
create or replace function comp_xyb( int[], -- 包含一些值的數獨二維矩陣，當像素值為0時，表示這個值沒有填充 int -- 數獨的基數（比如2,3，。。。），3就是常見的9*9數獨，4就是16*16數獨。 ) returns xyb[] -- 傳回一個複合類型的數組矩陣，矩陣像素和輸入矩陣一樣，每個像素表示這個像素在XYB軸上還有多少個沒有填充的值（沒有填充的值用0表示） as $$ declare dims int := ($2)^2; -- 基數的平方，表示行、列、BOX的像素個數。也是每個方向上的矩陣标記上限 res xyb[]; -- 結果 vx int; -- 橫向還有多少未填充像素 vy int; -- 豎向還有多少未填充像素 vb int; -- BOX内還有多少未填充像素 lx int; -- box的X方向矩陣下标 ux int; -- box的X方向矩陣上标 ly int; -- box的Y方向矩陣下标 uy int; -- box的Y方向矩陣上标 begin -- 初始化矩陣 select array ( select array( select format('(%s,%s,0,0,0)', x, y) from generate_series(1,dims) t(y)) from (select generate_series(1, dims) x) t ) into res; -- X坐标 for x in 1..dims loop -- Y坐标 for y in 1..dims loop -- 如果這個像素的值不等于0，說明已經是一個已經填充過的像素，傳回0,0,0 if ($1)[x][y] <> 0 then -- 不計算已填充了非0值的像素 continue; else -- x，計算X方向有多少個未填充的像素 select sum(case arr when 0 then 1 else 0 end) from (select ($1)[x][generate_series(1, dims)] as arr) t into vx; -- y，計算Y方向有多少個未填充的像素 select sum(case arr when 0 then 1 else 0 end) from (select ($1)[generate_series(1, dims)][y] as arr) t into vy; -- b，計算BOX内有多少個未填充的像素 -- x下限 lx := ((x-1)/$2)::int * $2 + 1; -- x上限 ux := ((x-1)/$2)::int * $2 + $2; -- y下限 ly := ((y-1)/$2)::int * $2 + 1; -- y上限 uy := ((y-1)/$2)::int * $2 + $2; -- 計算BOX内有多少個未填充的像素 select sum(case arr when 0 then 1 else 0 end) from (select ($1)[xx][yy] as arr from (select generate_series(lx,ux) xx) t1, (select generate_series(ly,uy) yy) t2 ) t into vb; -- 将XYB的值，寫入結果變量的對應像素中 res[x][y] := format('(%s,%s,%s,%s,%s)',x,y,vx,vy,vb)::xyb; end if; end loop; end loop; return res; end; $$ language plpgsql strict immutable; 3、用法舉例
計算以下2為基數，4*4的矩陣的xyb值
{1,2,3,4}, {0,1,1,0}, {0,1,1,0}, {0,1,1,0} 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); array ----------------------------------------------------------- {"(1,1,0,0,0)","(1,2,0,0,0)","(1,3,0,0,0)","(1,4,0,0,0)"} {"(2,1,2,3,1)","(2,2,0,0,0)","(2,3,0,0,0)","(2,4,2,3,1)"} {"(3,1,2,3,2)","(3,2,0,0,0)","(3,3,0,0,0)","(3,4,2,3,2)"} {"(4,1,2,3,2)","(4,2,0,0,0)","(4,3,0,0,0)","(4,4,2,3,2)"} (4 rows) 使用unnest可以解開，按XYB三個方向總大小排序，再按某個方向最大排序，進而做到逐級收斂，真正每一次填充的像素，都是具備最大機率的像素。
postgres=# select * from unnest( comp_xyb('{{1,2,3,4},{0,1,1,0},{0,1,1,0},{0,1,1,0}}', 2) ) 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; ax | ay | x | y | b ----+----+---+---+--- 3 | 1 | 2 | 3 | 2 3 | 4 | 2 | 3 | 2 4 | 1 | 2 | 3 | 2 4 | 4 | 2 | 3 | 2 2 | 1 | 2 | 3 | 1 2 | 4 | 2 | 3 | 1 (6 rows) 通過這個SQL得到了某個像素，這個像素的XYB方向上，還有最多的像素沒有被填充。
是以這個像素如果生成一個随機值的話，違反數獨的限制（或者叫沖突）的機率是最小的。
postgres=# select * from unnest( comp_xyb('{{1,2,3,4},{0,1,1,0},{0,1,1,0},{0,1,1,0}}', 2) ) 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; ax | ay | x | y | b ----+----+---+---+--- 3 | 1 | 2 | 3 | 2 (1 row) 用AX,ZY坐标值，往矩陣的這個像素填充符合數獨條件的随機值，可以大幅提高構造可解數獨的機率。
https://github.com/digoal/blog/blob/master/201803/20180319_01.md#%E5%B0%8F%E7%BB%93 小結
本文先介紹如何得到這樣的一個像素，填充一個值進行，這個值的取值區間應該是最大的（最不會與數獨的遊戲規則違背），進而更大可能的生成一個完整可解的數獨。
下面一篇文章再介紹如何生成一個N*N的數獨。
https://github.com/digoal/blog/blob/master/201803/20180319_01.md#%E5%8F%82%E8%80%83 參考
http://poj.org/problem?id=3074NP完全問題近似求解。
《PostgreSQL 生成任意基數數獨 - 1》 《PostgreSQL 生成任意基數數獨 - 2》 《PostgreSQL 生成任意基數數獨 - 3》![spring data JPA中的主鍵政策[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)