用PLSQL解决世界最难数独（不到1毫秒）
用PLSQL解决世界最难数独（不到1毫秒）
用户1148526
发布于 2021-12-07 12:46:29
发布于 2021-12-07 12:46:29
以下两段代码分别用Oracle和PostgreSQL匿名块解“世界最难数独”，声明代码是别人写的，这里只作为兴趣记录与学习。
Oracle代码出自http://www.itpub.net/thread-1071946-2-1.html，解题用时120毫秒。
DECLARE
TYPE t_num IS TABLE OF NUMBER INDEX BY BINARY_INTEGER;
TYPE t2_num IS TABLE OF t_num INDEX BY BINARY_INTEGER;
TYPE t_str IS TABLE OF VARCHAR2(10) INDEX BY BINARY_INTEGER;
s t_str;
used_c t2_num; --- in this column whether the number has been used
used_r t2_num; --- in this row whether the number has been used
used_a t2_num; --- in this area whether the number has been used
area t2_num; ---- mapping from row, column to area
v_cnt NUMBER :=0;
slot_value t2_num;
slot_r t_num;
slot_c t_num;
v_cnt2 NUMBER :=0;
v_idx NUMBER;
slot_value_idx t_num;
i NUMBER;
j NUMBER;
k NUMBER;
BEGIN
s(1):= '8 ';
s(2):= ' 36 ';
s(3):= ' 7 9 2 ';
s(4):= ' 5 7 ';
s(5):= ' 457 ';
s(6):= ' 1 3 ';
s(7):= ' 1 68';
s(8):= ' 85 1 ';
s(9):= ' 9 4 ';
FOR i IN 1..9 LOOP
FOR j IN 1..9 LOOP
used_c(i)(j) := 0;
used_r(i)(j) := 0;
used_a(i)(j) := 0;
area(i)(j) := (CEIL(i/3)-1)*3 + CEIL(j/3);
END LOOP;
END LOOP;
FOR i IN 1..9 LOOP
FOR j IN 1..9 LOOP
k := TO_NUMBER(TRIM(SUBSTR(s(i),j,1)));
IF k>0 THEN
used_c(j)(k) :=1;
used_r(i)(k) :=1;
used_a(area(i)(j))(k) :=1;
END IF;
END LOOP;
END LOOP;
FOR i IN 1..9 LOOP
FOR j IN 1..9 LOOP
IF SUBSTR(s(i),j,1)=' ' THEN
v_cnt := v_cnt+1;
v_cnt2 :=0;
FOR k IN 1..9 LOOP
IF used_c(j)(k) = 0 AND used_r(i)(k) = 0 AND used_a(area(i)(j))(k) = 0 THEN ---- possible value found for this slot
v_cnt2 := v_cnt2 +1;
slot_value(v_cnt)(v_cnt2) := k;
END IF;
END LOOP;
IF v_cnt2 = 0 THEN
RAISE_APPLICATION_ERROR(-20001,'invalid sudoku at '||i||','||j);
END IF;
IF v_cnt2 = 1 THEN ---- there's only one value for this slot, it's the answer
k := slot_value(v_cnt)(1);
used_c(j)(k) :=1;
used_r(i)(k) :=1;
used_a(area(i)(j))(k) :=1;
v_cnt := v_cnt - 1;
s(i) := SUBSTR(s(i),1,j-1) ||k|| SUBSTR(s(i),j+1);
ELSE
slot_r(v_cnt) := i; ---- position of this slot
slot_c(v_cnt) := j;
END IF;
END IF;
END LOOP;
END LOOP;
---- initialize the value indexes of slots
v_idx := slot_value.FIRST;
WHILE v_idx IS NOT NULL LOOP
slot_value_idx(v_idx) := slot_value(v_idx).FIRST;
-- DBMS_OUTPUT.PUT_LINE(v_idx||','||slot_value(v_idx).FIRST);
v_idx := slot_value.NEXT(v_idx);
-- DBMS_OUTPUT.PUT_LINE(v_idx||','||slot_value.NEXT(v_idx));
END LOOP;
v_idx := slot_value.FIRST;
WHILE v_idx IS NOT NULL LOOP
WHILE slot_value_idx(v_idx) IS NOT NULL LOOP ---- try all values for this slot
i := slot_r(v_idx);
j := slot_c(v_idx);
k := slot_value(v_idx)(slot_value_idx(v_idx));
IF used_c(j)(k) = 0 AND used_r(i)(k) = 0 AND used_a(area(i)(j))(k) = 0 THEN ---- possible value found for this slot
used_c(j)(k) := 1;
used_r(i)(k) := 1;
used_a(area(i)(j))(k) :=1;
EXIT;
END IF;
slot_value_idx(v_idx) := slot_value(v_idx).NEXT(slot_value_idx(v_idx));
-- DBMS_OUTPUT.PUT_LINE(v_idx||','||slot_value_idx(v_idx)||','||slot_value(v_idx).NEXT(slot_value_idx(v_idx)));
END LOOP;
IF slot_value_idx(v_idx) IS NULL THEN ---- all values tried but none is the answer
slot_value_idx(v_idx) := slot_value(v_idx).FIRST; --- reset the index of this slot
-- DBMS_OUTPUT.PUT_LINE(v_idx||','||slot_value(v_idx).FIRST);
v_idx := slot_value.PRIOR(v_idx); --- go back and release the last slot
IF v_idx IS NULL THEN ----- no anwer found
DBMS_OUTPUT.PUT_LINE('No Answer Found!');
EXIT;
END IF;
i := slot_r(v_idx);
j := slot_c(v_idx);
k := slot_value(v_idx)(slot_value_idx(v_idx));
used_c(j)(k) := 0;
used_r(i)(k) := 0;
used_a(area(i)(j))(k) :=0;
slot_value_idx(v_idx) := slot_value(v_idx).NEXT(slot_value_idx(v_idx));
ELSE
v_idx := slot_value.NEXT(v_idx);
IF v_idx IS NULL THEN ----- all slots tried and found an answer
v_idx := slot_value.FIRST;
WHILE v_idx IS NOT NULL LOOP
i := slot_r(v_idx);
j := slot_c(v_idx);
k := slot_value(v_idx)(slot_value_idx(v_idx));
s(i) := SUBSTR(s(i),1,j-1) || k || SUBSTR(s(i),j+1);
v_idx := slot_value.NEXT(v_idx);
END LOOP;
DBMS_OUTPUT.PUT_LINE('Answer Found:');
FOR i IN 1..9 LOOP
DBMS_OUTPUT.PUT_LINE(s(i));
END LOOP;
EXIT;
END IF;
END IF;
END LOOP;
END;
/PG的代码是另一位大神改写Oracle的，解题用时800毫秒。
DO $$DECLARE
i int;
j int;
k int;
s _varchar(10);
used_c int[][]:=array_fill(0,array[9,9]); --- in this column whether the number has been used
used_r int[][]:=array_fill(0,array[9,9]); --- in this row whether the number has been used
used_a int[][]:=array_fill(0,array[9,9]); --- in this area whether the number has been used
area int[][]:=array_fill(0,array[9,9]); ---- mapping from row, column to area
v_cnt int :=0;
slot_value int[][]:=array_fill(0,array[100,100]);
slot_r int[];
slot_c int[];
v_cnt2 int :=0;
v_idx int;
slot_value_idx int[]=array_fill(1,array[60]);
BEGIN
s[1]:= '8 ';
s[2]:= ' 36 ';
s[3]:= ' 7 9 2 ';
s[4]:= ' 5 7 ';
s[5]:= ' 457 ';
s[6]:= ' 1 3 ';
s[7]:= ' 1 68';
s[8]:= ' 85 1 ';
s[9]:= ' 9 4 ';
FOR i IN 1..9 LOOP
FOR j IN 1..9 LOOP
area[i][j] := (CEIL(i::numeric/3::numeric)-1)*3 + CEIL(j::numeric/3::numeric);
END LOOP;
END LOOP;
FOR i IN 1..9 LOOP
FOR j IN 1..9 LOOP
k := (case when TRIM(SUBSTRing(s[i],j,1))='' then '0' else TRIM(SUBSTRing(s[i],j,1)) end)::int;
IF k>0 THEN
used_c[j][k] :=1;
used_r[i][k] :=1;
used_a[area[i][j]][k] :=1;
END IF;
END LOOP;
END LOOP;
FOR i IN 1..9 LOOP
FOR j IN 1..9 LOOP
IF SUBSTRing(s[i],j,1)=' ' THEN
v_cnt := v_cnt+1;
v_cnt2 :=0;
FOR k IN 1..9 LOOP
IF used_c[j][k] = 0 AND used_r[i][k] = 0 AND used_a[area[i][j]][k] = 0 THEN ---- possible value found for this slot
v_cnt2 := v_cnt2 +1;
slot_value[v_cnt][v_cnt2] := k;
END IF;
END LOOP;
IF v_cnt2 = 0 THEN
RAISE EXCEPTION '-20001,invalid sudoku at %,%',i,j;
END IF;
IF v_cnt2 = 1 THEN ---- there's only one value for this slot, it's the answer
k := slot_value[v_cnt][1];
used_c[j][k] :=1;
used_r[i][k] :=1;
used_a[area[i][j]][k] :=1;
v_cnt := v_cnt - 1;
s[i] := SUBSTRing(s[i],1,j-1) ||k|| SUBSTRing(s[i],j+1);
ELSE
slot_r[v_cnt] := i; ---- position of this slot
slot_c[v_cnt] := j;
END IF;
END IF;
END LOOP;
END LOOP;
v_idx := slot_value[1][1];
WHILE slot_value[v_idx][1] <>0 LOOP
WHILE slot_value_idx[v_idx]<>0 LOOP ---- try all values for this slot
i := slot_r[v_idx];
j := slot_c[v_idx];
k := slot_value[v_idx][slot_value_idx[v_idx]];
IF used_c[j][k] = 0 AND used_r[i][k] = 0 AND used_a[area[i][j]][k] = 0 THEN ---- possible value found for this slot
used_c[j][k] := 1;
used_r[i][k] := 1;
used_a[area[i][j]][k] :=1;
EXIT;
END IF;
slot_value_idx[v_idx] := case when slot_value[v_idx][slot_value_idx[v_idx]+1] = 0 then 0 else slot_value_idx[v_idx]+1 end;
END LOOP;
IF slot_value_idx[v_idx]=0 THEN ---- all values tried but none is the answer
slot_value_idx[v_idx] := slot_value[1][1]; --- reset the index of this slot
v_idx := v_idx-1; --- go back and release the last slot
IF slot_value[v_idx][1] =0 THEN ----- no anwer found
raise notice 'No Answer Found!';
EXIT;
END IF;
i := slot_r[v_idx];
j := slot_c[v_idx];
k := slot_value[v_idx][slot_value_idx[v_idx]];
used_c[j][k] := 0;
used_r[i][k] := 0;
used_a[area[i][j]][k] :=0;
slot_value_idx[v_idx] := case when slot_value[v_idx][slot_value_idx[v_idx]+1] = 0 then 0 else slot_value_idx[v_idx]+1 end;
ELSE
v_idx := v_idx+1;
IF slot_value[v_idx][1] =0 THEN ----- all slots tried and found an answer
v_idx := slot_value[1][1];
WHILE slot_value[v_idx][1] <>0 and v_idx<>61 LOOP
i := slot_r[v_idx];
j := slot_c[v_idx];
k := slot_value[v_idx][slot_value_idx[v_idx]];
s[i] := SUBSTRing(s[i],1,j-1) || k || SUBSTRing(s[i],j+1);
v_idx := v_idx+1;
END LOOP;
raise notice 'Answer Found:';
FOR i IN 1..9 LOOP
raise notice '%',s[i];
END LOOP;
EXIT;
END IF;
END IF;
END LOOP;
END$$;百毫秒太慢了，祭出大招，1毫秒以内完成。
1. 编写C程序实现数独的DLX算法
以下代码是我改写自“SuDoKu_DLX_9*9”，因为要用PG来调用。（在我的环境中，PG中调用C函数比原始的C程序执行还快3-4倍）。源文件sudu.c内容如下：
#include "postgres.h"
#include "fmgr.h"
#define XSIZE 3
#define SIZE (XSIZE * XSIZE) //3*3=9
#define MAX_C (SIZE * SIZE * 4) //最大列 9*9*4=324
#define MAX_R (SIZE * SIZE * SIZE) //最大行 9*9*9=729
#define MAX_SUDOKU (SIZE * SIZE) //数独矩阵大小 9*9
#define MAX_LINK (MAX_C * MAX_R) //链表最大范围 324 * 729
int L[MAX_LINK],R[MAX_LINK],U[MAX_LINK],D[MAX_LINK]; //抽象链表
int C[MAX_LINK],O[MAX_LINK],S[MAX_C],H[MAX_R]; //C&O代表列&行，S每一列的节点数，H每一行的第一个节点
int NodeNumber,RecordNumber; //用来指向节点
int state[MAX_SUDOKU],ans[MAX_SUDOKU],record[MAX_SUDOKU];
bool input(char *buf);
char *ret;
//Dancing Links模版//
void init(void); //Dancing Links的抽象链表初始化
void insert(int,int); //在链表的一个位置中添加标记
void removedata(int); //删除一列，同时删除这一列中的行
void resume(int); //恢复一列，同时恢复这一列中的行
//Dancing Links模版//
void add(int,int,int);
void build(void);
bool dfs(int);
void output(void);
PG_MODULE_MAGIC;
PG_FUNCTION_INFO_V1(sudu);
Datum
sudu(PG_FUNCTION_ARGS)
{
char *t = PG_GETARG_CSTRING(0);
char *databuf = (char *)VARDATA(t);
VarChar *funcValue = (VarChar *)palloc(MAX_SUDOKU + VARHDRSZ);
SET_VARSIZE(funcValue, MAX_SUDOKU + VARHDRSZ);
ret = (char *)VARDATA(funcValue);
input(databuf);
init();
build();
dfs(0);
output();
PG_RETURN_VARCHAR_P(funcValue);
}
bool input(char *buf)
{
int i;
for(i=0;i<MAX_SUDOKU;i++)
{
state[i]=buf[i]-'0';
}
return true;
}
//Dancing Links模版//
void init(void)
{
for(int i=0;i<=MAX_C;i++)
{
L[i]=i-1;
R[i]=i+1;
U[i]=i;
D[i]=i;
C[i]=i;
O[i]=0;
}
L[0]=MAX_C;
R[MAX_C]=0;
NodeNumber=MAX_C+1;
memset(S,0,sizeof(S));
memset(H,0,sizeof(H));
}
void insert(int i,int j)
{
if(H[i])
{
L[NodeNumber]=L[H[i]];
R[NodeNumber]=H[i];
L[R[NodeNumber]]=NodeNumber;
R[L[NodeNumber]]=NodeNumber;
}
else
{
L[NodeNumber]=NodeNumber;
R[NodeNumber]=NodeNumber;
H[i]=NodeNumber;
}
U[NodeNumber]=U[j];
D[NodeNumber]=j;
U[D[NodeNumber]]=NodeNumber;
D[U[NodeNumber]]=NodeNumber;
C[NodeNumber]=j;
O[NodeNumber]=i;
S[j]++;
NodeNumber++;
}
void add(int i,int j,int k)
{
int row=i*MAX_SUDOKU+j*SIZE+k;
insert(row,i*SIZE+j+1);//注意
insert(row,i*SIZE+k+MAX_SUDOKU);
insert(row,j*SIZE+MAX_SUDOKU*2+k);
insert(row,(i/XSIZE*XSIZE +j/XSIZE)*SIZE+MAX_SUDOKU*3+k);
}
void build(void)
{
int pos;
for(int i=0;i<SIZE;i++)
for(int j=0;j<SIZE;j++)
{
pos=i*SIZE+j;
if(state[pos]!=0)
{
add(i,j,state[pos]);
}
else if(state[pos]==0)
{
for(int k=1;k<=SIZE;k++)
{
add(i,j,k);
}
}
}
}
void removedata(int c)
{
L[R[c]]=L[c];
R[L[c]]=R[c];
for(int i=D[c];i!=c;i=D[i])
{
for(int j=R[i];j!=i;j=R[j])
{
U[D[j]]=U[j];
D[U[j]]=D[j];
S[C[j]]--;
}
}
}
void resume(int c)
{
for(int i=U[c];i!=c;i=U[i])
{
for(int j=L[i];j!=i;j=L[j])
{
U[D[j]]=j;
D[U[j]]=j;
S[C[j]]++;
}
}
L[R[c]]=c;
R[L[c]]=c;
}
bool dfs(int k)
{
int count=~(1<<31),c=0;
if(!R[0])
{
RecordNumber=k;
return true;
}
for(int i=R[0];i;i=R[i])
{
if(S[i]<count)
{
count=S[i];
c=i;
if(count==1)
break;
}
}
removedata(c);
for(int i=D[c];i!=c;i=D[i])
{
for(int j=R[i];j!=i;j=R[j])
{
removedata(C[j]);
}
record[k]=O[i];
if(dfs(k+1))
return true;
for(int j=L[i];j!=i;j=L[j])
{
resume(C[j]);
}
}
resume(c);
return false;
}
void output(void)
{
int i,j,k=0;
for(i=0;i<RecordNumber;i++)
{
ans[(record[i]-1)/SIZE]=(record[i]-1)%SIZE+1;
}
for(i=0;i<SIZE;i++)
{
for(j=0;j<SIZE;j++)
{ret[k]='0' + ans[i*SIZE+j]; k=k+1;}
}
}2. 安装postgresql12开发包
yum -y install postgresql12-devel3. 建立创建SQL函数的文件
sudu.sql.in文件内容如下：
create function sudu(text)
returns varchar
as 'MODULE_PATHNAME','sudu'
language C strict;4. 创建Make文件
Makefile文件内容如下：
MODULES = sudu
DATA_built = sudu.sql
PG_CONFIG = /usr/pgsql-12/bin/pg_config
PGXS := $(shell $(PG_CONFIG) --pgxs)
include $(PGXS)5. 编译安装C程序
# 编译
make
# 安装
make install6. 创建SQL函数
psql -d test -f sudu.sql7. 用SQL查询调用函数并格式化输出
with t as (select sudu('800000000003600000070090200050007000000045700000100030001000068008500010090000400') a)
select substr(a,1,9) from t
union all
select substr(a,10,9) from t
union all
select substr(a,19,9) from t
union all
select substr(a,28,9) from t
union all
select substr(a,37,9) from t
union all
select substr(a,46,9) from t
union all
select substr(a,55,9) from t
union all
select substr(a,64,9) from t
union all
select substr(a,73,9) from t;下面是见证奇迹的时刻：
本文参与 腾讯云自媒体分享计划，分享自作者个人站点/博客。
原始发表：2021-07-27 ，如有侵权请联系 cloudcommunity@tencent.com 删除
评论
登录后参与评论
推荐阅读