标簽
PostgreSQL , 數獨
https://github.com/digoal/blog/blob/master/201803/20180320_01.md#%E8%83%8C%E6%99%AF 背景
《PostgreSQL 生成任意基數數獨 - 1》提供了一種方法，計算一個未完成的數獨矩陣每個像素在XYB方向上還有多少個未填充的像素。
通過XYB的值，進行各種排序，選出下一個要填充的像素，進行随機填充。
可以通過調整規則，實作不同的填充位置選擇，進而達到生成可解數獨的目的。
https://github.com/digoal/blog/blob/master/201803/20180320_01.md#%E5%88%9B%E5%BB%BA%E4%B8%80%E4%B8%AA%E7%94%9F%E6%88%90%E4%BB%A5n%E4%B8%BA%E5%9F%BA%E6%95%B0%E7%9A%84%E6%95%B0%E7%8B%AC%E7%9A%84%E5%87%BD%E6%95%B0 建立一個生成以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; https://github.com/digoal/blog/blob/master/201803/20180320_01.md#%E7%94%9F%E6%88%90%E6%95%B0%E7%8B%AC%E6%B5%8B%E8%AF%95 生成數獨測試
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) https://github.com/digoal/blog/blob/master/201803/20180320_01.md#%E8%B0%83%E6%95%B4%E9%80%89%E5%8F%96%E5%A1%AB%E5%85%85%E5%83%8F%E7%B4%A0%E7%9A%84%E6%96%B9%E6%B3%95 調整選取填充像素的方法
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; https://github.com/digoal/blog/blob/master/201803/20180320_01.md#%E5%B0%8F%E7%BB%93 小結
暫時使用這幾種方法，經過少量的計算，無法生成有解的數獨。
1、選擇下一個要填充的像素（根據未知值個數排行，從總未知值最多，按單軸最多的位置中随機取一個位置）
2、從BOX次元沖突最小，x,y次元沖突最小的像素開始填充
3、從各次元沖突最大的開始填充
随機的方法生成數獨，效率比較低，次元越高，生成成功的機率越低。需要尋找更高效的生成數獨的方法。
https://github.com/digoal/blog/blob/master/201803/20180320_01.md#%E5%8F%82%E8%80%83 參考
NP完全問題近似求解。
《PostgreSQL 生成任意基數數獨 - 2》 《PostgreSQL 生成任意基數數獨 - 3》![spring data JPA中的主鍵政策[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)