9

まず第一に、これは大学の課題であるため、誰かにコードを書いてもらうように頼んでいるわけではありません。正しい方向に向ける必要があるだけです。:)

では、任意のサイズの (解ける) 数独ボードを解くアルゴリズムを作成する必要があります。任意の 9x9 ボードをすばやく (~1ms) 解決できる再帰関数を作成しましたが、解決するのが難しい大きなボード (16x16) を実行すると苦労します.解決しそうにない。簡単な 16x16 のパズルや空白の 16x16 のボードを解くことができるので、問題は寸法ではないと思います.. 問題はアルゴリズムである可能性が高いと思います.

とにかく、これは私のプログラムの基本的なロジックです..

  • すべての正方形の可能な値を格納する 3D ベクトルがあります
  • 値が正方形に配置されると、周囲の正方形、行、および列の可能な値から削除されます。

次に、私の解決機能は基本的に次のとおりです。

bool solve() {

    if (there are no unfilled squares)
        return true

    if (the board is unsolvable - there are empty squares that have no possible values)
        return false

    while (there are empty squares)
    {
        int squaresFilled = fillSquaresWithOnlyOneChoice(); //this method updates the possible results vector whenever it fills a square

        if (squaresFilled == 0)
            break;
    }

    //exhausted all of the 'easy' squares (squares with only one possible choice), need to make a guess

    while (there are empty squares that have choices left) {

        find the square with the least number of choices

        if (the square with the least number of choices has 0 choices)
            return false; //not solvable.

        remove that choice from the 3D vector (vector that has the choices for each square)
        make a copy of the board and the 3D choices vector

        fill the square with the choice

        if (solve())
            return true; //we're done

        restore the board and choices vector 
        //the guess didn't work so keep looping and make a new guess with the restored board and choices -- the choice we just made has been removed though so it won't get made again.

    }

    return false; //can't go any further
}

これについて何か非効率的なことはありますか？うまく機能させる方法はありますか？16x16 のボードに非常に時間がかかるのは、ボードの決定木が非常に大きく、あまり埋められていないためだと思います。奇妙なことに、9x9 ボードは非常に速く解けるからです。

アイデアや提案は絶対に素晴らしいでしょう。私が見逃した情報があれば、私にも知らせてください！

4

6 に答える 6

6

数独を解くための高速なアルゴリズムは、Donald Knuth による Algorithm X です。数独を正確なカバー問題として表現し、アルゴリズム Xを使用して EC 問題を解決します。次に、アルゴリズム X の効率的な実装としてDLXを使用します。

ウィキペディアには、数独を解くために正確なカバーを適用する方法についての素晴らしい説明があります.

DLX は数独を解くのに非常に高速であり、最速のアルゴリズムで一般的に使用されていると言えます。

http://www.setbb.com/phpbb/index.php?mforum=sudokuは、おそらく最高の sudoku プログラマーにとって素晴らしいフォーラムです。

于 2011-10-08T12:43:21.857 に答える
4

1 つの選択肢だけでマスを埋めることと、ボード上で完全に再帰することの間に、実行できるより高度なアクションがあります。「領域」が 1 つの行、または 1 つの列、または 1 つの正方形の領域 (3x3 または 4x4) であるとしましょう。

戦術1

同一の K 個の数しかとれない領域に K 個の正方形がある場合 (たとえば、2 と 5 のみを取ることができる 2 つの正方形、または 1、7、8 のみを取ることができる 3 つの正方形)、その領域内の他のすべての正方形は「それらの特定の数値を取得します。「取られた」数字を取り除くために各領域を反復する必要があるため、論理的な選択肢が 1 つだけの正方形を見つけることができます (たとえば、2、4、5 の 3 番目の正方形は論理的に 4 しか取ることができず、1、3、 7 と 8 は、論理的には 3) しか取ることができません。

次の例を考えると、これは繰り返しで解決する必要があります。領域には、次の可能な数の正方形があります。

A: 1 2 3
B: 2 3
C: 2 3 4 5
D: 4 5
E: 4 5

アルゴリズムは、正方形 D と E が数字 4 と 5 を保持していることを検出する必要があるため、4 と 5 は領域内の他の正方形から除外されます。次に、アルゴリズムは、正方形 B と C が数字 2 と 3 を保持していることを検出し、それらを他の正方形から除外します。これにより、正方形 A には番号 1 のみが残ります。

戦術2

数字が 1 つの正方形のみの領域にある場合、論理的にはその正方形がその数字を保持します。

戦術3

戦術 1 と 2 は、戦術 3 の特殊なケースであり、K 個の同じ数字のみを持つ K 個の正方形があります。K 個の正方形と K 個の数字のセットを持つことができ、それらの K 個の正方形はそれらの K 個の数字の任意のサブセットを保持できます。次のリージョンの例を考えてみましょう。

A: 1 2
B: 2 3
C: 1 3
D: 1 2 3 4

正方形 A、B、および C は、数字 1、2、および 3 のみを保持できます。これは、K の K です。つまり、他の正方形はこれらの数字を論理的に保持できないことを意味し、正方形 D には数字 4 のみが残ります。

戦術 2 は、K = N - 1 の場合の戦術 3 の特殊なケースです。

戦術4

領域の重複を利用します。ある数が領域の特定の正方形にのみ存在できるとします。これらのすべての正方形が別の重複領域に属している場合、その数は、この他の領域内の他のすべての正方形から除外する必要があります。

戦術5

結果をキャッシュします。すべてのリージョンには、リージョンが最後に処理されてからリージョン内の何かが変更されたことを示す「ダーティ」フラグが必要です。このフラグが設定されていない領域を処理する必要はありません。

人間はこれらすべての戦術を使用しますが、後戻りは本当に苦痛なので、数字を推測することは本当に嫌いです. 実際、ボードの難易度は、ボードを解決するために必要な最小数の推測で測定されます。ほとんどの「極端な」ボードでは、1 つの適切な推測で十分です。

于 2011-10-08T12:09:12.307 に答える
1

このリンクを以前に見たことがあるかどうかはわかりません。また、単純な形式のバックトラッキングを使用するため、ダンシング リンク アルゴリズムとは比較にならない可能性があります。とにかくそれは動作します。それがあなたに役立つかどうか見てください！

また、「簡単な」正方形を解くために数行追加することもできます。 http://edwinchan.wordpress.com/2006/01/08/sudoku-solver-in-c-using-backtracking/

于 2011-10-08T09:56:05.200 に答える
0

可能な数が1つしかないセルを特別なものとして扱う必要はありません。あなたはすでに、最初に可能性の数が最も少ないセルにアクセスしています。

また、「3Dベクトルからその選択を削除」すると、同じ{row、columns、box}の他のセルからも削除できます。ビットマスクはおそらくうまく収まるでしょう。（ただし、バックトラックは少し難しくなります）

于 2011-10-08T12:40:27.547 に答える
0

@ralu が述べたように、数独を解く最速のアルゴリズムは DLX を使用することです。以下は私が過去に書いたプログラムです。4*4 数独を 1 秒以内に解くことができます。

入力が次のようになっているとします。

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

あなたは試すことができます:)

于 2012-12-30T02:22:31.923 に答える
0

あなたのアルゴリズムは問題ないようです。問題は、ブルート フォース アプローチを使用しているため、実行時間が (文字数)^(ボードのサイズ) であることです。つまり、9x9 の場合は 9^9=387420489 であり、16x16 の場合は実行時間は 16^ です。 16=18446744073709551616. 違いがわかります。

動的プログラミングのアプローチを見つけてみてください

  • あなたが 1 年生または 2 年生の場合は、自分の持っているものをそのまま使用してください (そして、正確性を確認してください)。先生はそれ以上期待しないでしょう。
于 2011-10-08T10:00:40.347 に答える