Sudoku-backtracking-Algorithmus

Schnell algorhitm für die Lösung von sudoku ist der Algorithmus X durch Donald Knuth. Sie repräsentieren Lösung des sudoku als exakte Abdeckung problem, und verwenden Sie dann Algorithmus X für die Lösung der EG-problem. Dann nutzen Sie DLX als effiziente Implementierung des Algorithmus X.

Gibt es tolle Erklärung auf wikipedia, wie die genaue Abdeckung für die Lösung von sudoku.

Ich kann Ihnen sagen, dass DLX ist extrem schnell fost Lösung des sudoku-in wird Häufig verwendet, in der schnellsten algorhitm.

http://www.setbb.com/phpbb/index.php?mforum=sudoku ist tolles forum, mit wahrscheinlich der besten sudoku-Programmierer.

Du bist Algorithmus sieht gut aus. Das problem ist, dass Sie mit einer brute-force-Ansatz, und daher Ihre Laufzeit ist (Anzahl der Zeichen)^(Größe des Verwaltungsrats) - also für 9x9 es gibt 9^9=387420489 und für 16x16 die Laufzeit ist auf 16^16=18446744073709551616. Sie können den Unterschied sehen.

Versuchen Sie finden eine Dynamic programing Ansatz

• Wenn Sie einen ersten\zweite Jahr-student, bleiben Sie einfach mit, was Sie haben (und überprüfen Sie die Richtigkeit). Ihre Lehrer nicht mehr erwarten.

als @ralu erwähnt, den schnellsten Algorithmus zu lösen Sudokus mithilfe von DLX. unten ist ein Programm, das ich schrieb in der Vergangenheit. kann es lösen 4*4 sudoku innerhalb von 1 Sekunde.

angenommen, die Eingabe ist wie:

--A----C-----O-I
-J--A-B-P-CGF-H-
--D--F-I-E----P-
-G-EL-H----M-J--
----E----C--G---
-I--K-GA-B---E-J
D-GP--J-F----A--
-E---C-B--DP--O-
E--F-M--D--L-K-A
-C--------O-I-L-
H-P-C--F-A--B---
---G-OD---J----H
K---J----H-A-P-L
--B--P--E--K--A-
-H--B--K--FI-C--
--F---C--D--H-N-


#include <iostream>
#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <algorithm>
using namespace std;

const int INF=1<<30;
const int N=4;
const int MAXR=N*N*N*N*N*N+10;
const int MAXC=N*N*N*N*4+10;
const int SIZE=MAXR*MAXC/N/N;

int n,m;
int mat[MAXR][MAXC],r,c,ans;
int L[SIZE],R[SIZE],U[SIZE],D[SIZE],S[MAXC],C[SIZE],RH[SIZE],O[MAXC];
int a[MAXR];
char b[MAXR];
char s[N*N+10][N*N+10];
int head,cnt;

int node(int up,int down,int left,int right) {
    U[cnt]=up;D[cnt]=down;L[cnt]=left;R[cnt]=right;
    D[up]=U[down]=L[right]=R[left]=cnt;
    return cnt++;
}

void init() {
    cnt=0;
    head=node(0,0,0,0);
    for (int i=1;i<=c;i++) {
        C[i]=node(cnt,cnt,L[head],head);
        S[i]=0;
    }
    for (int i=1;i<=r;i++) {
        int rowh=-1;
        for (int j=1;j<=c;j++) if (mat[i][j]) {
            if (rowh==-1) {
                rowh=node(U[C[j]],C[j],cnt,cnt);
                RH[rowh]=i;
                C[rowh]=C[j];
                S[j]++;
            }
            else {
                int k=node(U[C[j]],C[j],L[rowh],rowh);
                RH[k]=i;
                C[k]=C[j];
                S[j]++;
            }
        }
    }
}

void remove(int col) {
    L[R[col]]=L[col];
    R[L[col]]=R[col];
    for (int i=D[col];i!=col;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 col) {
    for (int i=U[col];i!=col;i=U[i])
        for (int j=L[i];j!=i;j=L[j]) {
            S[C[j]]++;
            U[D[j]]=j;
            D[U[j]]=j;
        }
    L[R[col]]=col;
    R[L[col]]=col;
}

bool dfs(int k) {
    if (R[head]==head) {
        ans=k;
        return true;
    }
    int mins=INF,cur=0;
    for (int i=R[head];i!=head;i=R[i])
        if (S[i]<mins) {
            mins=S[i];
            cur=i;
        }
    remove(cur);
    for (int i=D[cur];i!=cur;i=D[i]) {
        O[k]=RH[i];
        for (int j=R[i];j!=i;j=R[j])
            remove(C[j]);
        if (dfs(k+1)) return true;
        for (int j=L[i];j!=i;j=L[j])
            resume(C[j]);
    }
    resume(cur);
    return false;
}

void makegraph() {
    r=0;
    for (int i=0;i<N*N;i++)
        for (int j=0;j<N*N;j++) {
            int t=(i/N)*N+(j/N);
            int p=i*N*N+j;
            if (s[i][j]=='-') {
                for (int k=1;k<=N*N;k++) {
                    r++;
                    mat[r][i*N*N+k]=1;
                    mat[r][N*N*N*N+j*N*N+k]=1;
                    mat[r][2*N*N*N*N+t*N*N+k]=1;
                    mat[r][3*N*N*N*N+p+1]=1;
                    a[r]=p;
                    b[r]='A'+k-1;
                }
            }
            else {
                int k=s[i][j]-'A'+1;
                r++;
                mat[r][i*N*N+k]=1;
                mat[r][N*N*N*N+j*N*N+k]=1;
                mat[r][2*N*N*N*N+t*N*N+k]=1;
                mat[r][3*N*N*N*N+p+1]=1;
                a[r]=p;
                b[r]=s[i][j];
            }
        }
}

int main() {
    freopen("sudoku.txt","r",stdin);
    freopen("sudoku_sol.txt","w",stdout);
        for (int i=0;i<N*N;i++)
            scanf("%s",s[i]);
        memset(mat,0,sizeof(mat));
        makegraph();
        c=N*N*N*N*4;

        init();
        ans=INF;
        dfs(0);
        for (int i=0;i<ans;i++)
            for (int j=i+1;j<ans;j++)
                if (a[O[i]]>a[O[j]]) swap(O[i],O[j]);

        for (int i=0;i<ans;i++) {
            printf("%c",b[O[i]]);
            if ((i+1)%(N*N)==0) printf("\n");
        }
    fclose(stdin);
    fclose(stdout);
    return 0;
}

u können einen Versuch haben 🙂