标簽
PostgreSQL , 數獨 , 求解 , 動态規劃
https://github.com/digoal/blog/blob/master/201803/20180321_01.md#%E8%83%8C%E6%99%AF 背景
使用
《PostgreSQL 生成任意基數數獨 - 3》提供的方法，可以生成有解數獨。在不知道數獨答案的情況下，如何暴力破解呢？
實際上可以修改一下
《PostgreSQL 生成任意基數數獨 - 2》裡面的随機生成數獨的函數，破解數獨。
https://github.com/digoal/blog/blob/master/201803/20180321_01.md#%E7%A0%B4%E8%A7%A3%E6%95%B0%E7%8B%AC%E5%87%BD%E6%95%B0%E5%A6%82%E4%B8%8B 破解數獨函數如下
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; https://github.com/digoal/blog/blob/master/201803/20180321_01.md#%E4%BE%8B%E5%AD%90 例子
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方向滿足限制）之後，後面就不會去修正它，進而導緻了一個錯誤後面的計算全是浪費的。增加了破解成本。
https://github.com/digoal/blog/blob/master/201803/20180321_01.md#%E6%89%A9%E5%B1%95 擴充
在資料庫中執行計劃也與之類似，目前大多數執行計劃是靜态的，一旦執行計劃确定下來了，後面就隻能按照執行計劃執行，無法中途調整。
是以，動态執行計劃也成為目前很多資料庫優化器突破的方向，在執行過程中，根據執行過程中的統計資訊，不斷修正執行計劃，達到最佳的目的。
實際上，導航也與之類似，如果你根據目前的路況規劃好了導航，在行駛過程中，可能某些路段發生了變化（擁堵情況），靜态導航就無法修正這樣的問題，還是按一開始既定的線路行駛。而動态導航，可以根據實時路況進行修正，選擇下一跳。
在生産中有很多類似的例子，比如資料路由，負載均衡等等。
![spring data JPA中的主鍵政策[圖]](data:image/gif;base64,R0lGODlhAQABAIAAAP///wAAACwAAAAAAQABAAACAkQBADs=)