So generieren Sie Sudoku-Boards mit einzigartigen Lösungen

Hier ist übrigens meine eigenen SuDoKu-Programm macht es:

1. starten Sie mit einem kompletten, gültig board (gefüllt mit 81 zahlen)

2. machen Sie eine Liste aller 81 cell Positionen und mische es zufällig

3. Solange die Liste nicht leer ist, nehmen Sie die nächste position aus der Liste aus und entfernen Sie die Nummer aus der zugehörigen Zelle

4. test Einzigartigkeit mit einem schnellen solver (mit backtracking falls erforderlich). Mein solver ist in der Lage zu zählen alle Lösungen, aber es Stoppt, wenn es mehr als 1 Lösung.

5. Wenn das aktuelle board hat nur eine Lösung, gehe zu Schritt 3 und wiederholen.

6. Wenn das aktuelle board hat mehr als eine Lösung, rückgängig die Letzte entfernen (Schritt 3), und weiter zu Schritt 3 mit der nächsten position aus der Liste

7. stoppen, wenn Sie getestet haben, alle 81 Positionen.

Dies gibt Ihnen nicht nur einen einzigartigen Brettern, aber boards, wo Sie nicht entfernen können, mehr zahlen, ohne die Zerstörung der Eindeutigkeit der Lösung.

Natürlich, dies ist nur die zweite Hälfte des Algorithmus. Die erste Hälfte ist zu finden, eine vollständige, gültige board-erste (zufällig gefüllt!) Es funktioniert sehr ähnlich, aber "in die andere Richtung":

1. beginnen Sie mit einem leeren Brett

2. fügen Sie eine zufällige Zahl in eine der freien Zellen (die Zelle wird nach dem Zufallsprinzip ausgewählt, und die Zahl wird nach dem Zufallsprinzip aus der Liste der Nummern, gilt für diese Zelle gemäß der SuDoKu-Regeln)

3. Verwenden Sie die backtracking-solver prüfen, ob der aktuelle Vorstand hat mindestens eine gültige Lösung. Wenn nicht, rückgängig zu Schritt 2 und wiederholen Sie mit einer anderen Nummer und Zelle. Beachten Sie, dass dieser Schritt möglicherweise produzieren voll gültig boards auf seine eigene, aber die sind in keiner Weise zufällig.

4. Wiederholen, bis das board ist komplett mit zahlen gefüllt

InformationsquelleAutor der Antwort Doc Brown

Es sei denn, P = NP, gibt es kein polynomial-Zeit Algorithmus für die Generierung von Allgemeinen Sudoku-Probleme mit genau einer Lösung.

In seiner master ' s thesis, Takayuki Yato definiert Die Andere Lösung Des Problems (ASP), bei denen das Ziel ist, eine problem-und eine Lösung zu finden, eine andere Lösung für dieses problem oder zeige, dass keiner existiert. Yato dann definiert ASP-Vollständigkeit, Probleme, für die es schwierig ist, nach einer Lösung zu suchen, und zeigte, dass Sudoku ist ASP-abgeschlossen. Da er beweist auch, dass die ASP-Vollständigkeit impliziert die NP-Härte, dies bedeutet, dass, wenn Sie erlauben, für eine beliebige Größe Sudoku-boards, es gibt keinen polynomial-Zeit-Algorithmus, um zu überprüfen, ob das puzzle, das Sie erstellt haben, eine eindeutige Lösung hat (es sei denn P = NP).

Sorry verwöhnen Ihre Hoffnungen auf einen schnellen Algorithmus!

InformationsquelleAutor der Antwort templatetypedef

Ich denke auch, dass Sie haben, um explizit zu überprüfen, Einzigartigkeit. Wenn Sie weniger als 17 vorgegebenen zahlen, eine einzigartige Lösung, die sehr unwahrscheinlich ist, aber: Keiner hat sich bislang nicht gefunden, obwohl es ist noch nicht klar, ob es existiert.)

Aber Sie können auch ein SAT-solver, im Gegensatz zum schreiben eines eigenen backtracking-Algorithmus. So, Sie kann in gewissem Maße regulieren, wie schwierig es sein wird, eine Lösung zu finden: Wenn Sie eine Einschränkung der Inferenz-Regeln, dass der SAT-solver verwendet, können Sie prüfen, ob Sie das Rätsel lösen leicht. Google einfach mal nach "SAT-solving sudoku".

InformationsquelleAutor der Antwort DaveFar

Diese Logik wird Ihnen einzigartige 9*9 sudoku jedes mal, wenn Sie es ausführen.
Es dauert 15 Minuten, 20 Minuten zum generieren eines eindeutigen sudoku.

import java.text.DateFormat;
import java.text.SimpleDateFormat;
import java.util.ArrayList;
import java.util.Date;
import java.util.Random;
//random numbers with incremental locations
//final solution for creating random sudoku
public class Sudoku {

    public static void main(String[] args) 
    {
        int b = 0;
        int Low = 1;
        int High = 10;
        boolean y=false;
        int[][] a= new int[9][9];
        Random r = new Random();
        int count1=0;
        int count2=0;
        int count3=0;
        long startTime = System.currentTimeMillis();
        long endTime;
        long totalTime; 
        int tc=0;

        //created 9*9 unique array 
        for(int i=0;i<9;i++) 
        {
            for(int j=0;j<9;j++) 
            {
                while(y==false)
                {
                b=(r.nextInt(High-Low) + Low);

                //check for duplicates horizontally 
                for(int x=0;x<9;x++)
                {
                        if(a[i][x]!=b)
                        {
                            ++count1;
                        }
                }

                //check vertically
                for(int d=0;d<9;d++)
                {
                        if(a[d][j]!=b)
                        {
                            ++count2;
                        }
                }

                //check for duplicates with in a 3*3 block
                int d=0;
                int e=0;

                for(int x1=0;x1<3;x1++) 
                {
                  for(int y1=0;y1<3;y1++) 
                  {

                    for(int i1=d;i1<d+3;i1++) 
                     {
                        for(int j1=e;j1<e+3;j1++) 
                        {
                            //System.out.print(a[i][j]+" ");

                            if(i==i1 && j==j1) 
                            {
                                for(int k=d;k<d+3;k++) 
                                 {
                                    for(int l=e;l<e+3;l++) 
                                    {
                                        if(b!=a[k][l]) {

                                            ++count3;
                                        }

                                    }
                                 }
                            }

                        }
                        //System.out.println();
                     }
                    e=e+3;
                    //System.out.println();
                  }
                  e=0;
                  d=d+3;
                  //System.out.println();
                }




                if(count1==9 && count2==9 && count3==9) 
                {
                    System.out.print(b+" ");
                    a[i][j]=b;
                    tc++;
                    y=true;
                    break;

                }
                else 
                {
                    y=false;
                }
                count1=0;
                count2=0;
                count3=0;
                endTime=System.currentTimeMillis();
                totalTime=endTime-startTime;


                if(totalTime>2000)
                {
                    System.out.println();
                    System.out.println("reset "+tc);
                    //System.out.println();
                    startTime=System.currentTimeMillis();
                    a=new int[9][9];
                    count1=0;
                    count2=0;
                    count3=0;
                    y=true;
                    b=0;
                    tc=0;
                    main(null);
                    break;
                }

                }
                y=false;
                if (i==8 && j==8)
                {
                    break;
                }
            }

            System.out.println();

        }

        //print the sudoku
        /*for(int m=0;m<9;m++)
        {
            for(int n=0;n<9;n++) 
            {
                System.out.print(a[m][n]+" ");
            }
            System.out.println();
        }*/
        for(int i=1;i<=9;i++) 
        {
            int t=i-1;
            for (int j=1;j<=9;j++)
            {
                if(j==1) {
                System.out.print("|");}
                int s=j-1;
                System.out.print(a[t][s]);

                if (j%3==0)
                System.out.print("|");
                else
                 System.out.print(",");

            }
            if(i%3==0 && i<9) {
                System.out.println();
                for (int j=1;j<=9;j++)
            {
                if(j==1) {
                System.out.print("|");}     
                if (j%3==0 &&j<9)
                System.out.print("-+");
                else if(j%3==0 && j==9)
                System.out.print("-|");
                else
                System.out.print("--");
            }
            }

            System.out.println();

        }
        DateFormat dateFormat = new SimpleDateFormat("yyyy/MM/dd HH:mm:ss");
        Date date = new Date();
        System.out.println(dateFormat.format(date)); //2016/11/16 12:08:43
        System.exit(0);

    }

}

InformationsquelleAutor der Antwort Ajay