Résoudre le sudoku le plus difficile au monde avec plsql (moins de 1 ms)

Wzy0623 2021-08-19 21:07:15 阅读数:861

soudre le sudoku le difficile

        Les deux codes suivants sont utilisés séparémentOracleEtPostgreSQLSolution anonyme de bloc“Le sudoku le plus dur du monde”,Le Code de déclaration a été écrit par quelqu'un d'autre,Ce n'est qu'à titre d'intérêt et d'apprentissage.

        OracleLe Code vient dehttp://www.itpub.net/thread-1071946-2-1.html,Temps de résolution des problèmes120MS.

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 Le Code est réécrit par un autre grand Dieu OracleDe,Temps de résolution des problèmes800MS.

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$$;

Cent millisecondes, c'est trop lent , Un grand sacrifice ,1 Terminé en millisecondes .

1. CompilationC Le programme réalise sudoku DLXAlgorithmes

Le code suivant a été réécrit de “SuDoKu_DLX_9*9”,Parce que ça va marcher.PGPour appeler.( Dans mon environnement ,PGAppel moyenC La fonction est plus C L'exécution du programme est rapide 3-4X).Fichier sourcesudu.cIl se lit comme suit::

#include "postgres.h"
#include "fmgr.h"
#define XSIZE 3
#define SIZE (XSIZE * XSIZE) //3*3=9
#define MAX_C (SIZE * SIZE * 4) // Colonne maximale 9*9*4=324
#define MAX_R (SIZE * SIZE * SIZE) // Ligne maximale 9*9*9=729
#define MAX_SUDOKU (SIZE * SIZE) // Taille de la matrice sudoku 9*9
#define MAX_LINK (MAX_C * MAX_R) // Plage maximale de la liste de liens 324 * 729
int L[MAX_LINK],R[MAX_LINK],U[MAX_LINK],D[MAX_LINK]; // Liste des liens abstraits
int C[MAX_LINK],O[MAX_LINK],S[MAX_C],H[MAX_R]; //C&O Colonne représentative &D'accord,S Nombre de noeuds par colonne ,H Le premier noeud de chaque ligne
int NodeNumber,RecordNumber; // Pour pointer vers le noeud
int state[MAX_SUDOKU],ans[MAX_SUDOKU],record[MAX_SUDOKU];
bool input(char *buf);
char *ret;
//Dancing LinksModèle//
void init(void); //Dancing Links Initialisation de la liste des liens abstraits pour
void insert(int,int); // Ajouter un marqueur à un endroit de la liste
void removedata(int); //Supprimer une colonne, Supprimer également les lignes de cette colonne
void resume(int); // Restaurer une colonne , Restaurer les lignes dans cette colonne en même temps
//Dancing LinksModèle//
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 LinksModèle//
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);//Attention!
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. Installationpostgresql12Kit de développement

yum -y install postgresql12-devel

3. Créer créer créer SQLFichier de la fonction

sudu.sql.inLe contenu du document est le suivant::

create function sudu(text)
returns varchar
as 'MODULE_PATHNAME','sudu'
language C strict;

4. CréationMakeDocumentation

MakefileLe contenu du document est le suivant::

MODULES = sudu
DATA_built = sudu.sql
PG_CONFIG = /usr/pgsql-12/bin/pg_config
PGXS := $(shell $(PG_CONFIG) --pgxs)
include $(PGXS)

5. Compiler l'installationCProcédure

# Compiler
make
# Installation
make install

6. CréationSQLFonctions

psql -d test -f sudu.sql

7. AvecSQL Interroger la fonction d'appel et formater la sortie

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;

Voici le moment de témoigner d'un miracle :

Copyright:Cet article est[Wzy0623]Établi,Veuillez apporter le lien original pour réimprimer,remercier。 https://fra.fheadline.com/2021/08/20210819210711943A.html