Come generare tavole di Sudoku con soluzioni uniche

Come si genera una tavola di Sudoku con una soluzione unica? Quello che pensavo era di inizializzare una scheda a caso e quindi rimuovere alcuni numeri. Ma la mia domanda è: come posso mantenere l’unicità di una soluzione?

Facile:

  1. Trova tutte le soluzioni con un efficiente algoritmo di backtracking.
  2. Se c’è una sola soluzione, hai finito. Altrimenti se hai più di una soluzione, trova una posizione in cui la maggior parte delle soluzioni differiscono. Aggiungi il numero in questa posizione.
  3. Vai a 1.

Dubito che tu possa trovare una soluzione che sarebbe molto più veloce di questa.

Ecco come funziona il mio programma SuDoKu:


  1. Inizia con una scheda completa e valida (piena di 81 numeri).

  2. Crea una lista di tutte le 81 posizioni di cella e mescola casualmente.

  3. Finché l’elenco non è vuoto, prendi la posizione successiva dall’elenco e rimuovi il numero dalla cella correlata.

  4. Prova l’unicità utilizzando un solver backtracking veloce. Il mio risolutore è – in teoria – in grado di contare tutte le soluzioni, ma per testare l’unicità, si fermerà immediatamente quando troverà più di una soluzione.

  5. Se la scheda corrente ha ancora una soluzione, vai al passaggio 3) e ripeti.

  6. Se la scheda corrente ha più di una soluzione, annullare l’ultima rimozione (passaggio 3) e continuare il passaggio 3 con la posizione successiva dall’elenco

  7. Fermati quando hai testato tutte le 81 posizioni.


Questo ti dà non solo tabs uniche, ma tabs in cui non puoi rimuovere più numeri senza distruggere l’unicità della soluzione.

Naturalmente, questa è solo la seconda metà dell’algoritmo. Il primo semestre consiste nel trovare prima una scheda valida completa (riempita a caso!) Funziona in modo molto simile, ma “nella direzione opposta”:


  1. Inizia con una tavola vuota.

  2. Aggiungi un numero casuale in una delle celle libere (la cella viene scelta casualmente e il numero viene scelto in modo casuale dall’elenco di numeri valido per questa cella in base alle regole SuDoKu).

  3. Utilizzare il risolutore di backtracking per verificare se la scheda corrente ha almeno una soluzione valida. In caso contrario, annullare il passaggio 2 e ripetere con un altro numero e una cella. Si noti che questo passaggio potrebbe produrre tabs complete valide da sole, ma quelle non sono in alcun modo casuali.

  4. Ripeti fino a quando la scacchiera è completamente piena di numeri.

Puoi imbrogliare. Inizia con una tavola di Sudoku già esistente che può essere risolta per poi giocarci.

Puoi scambiare qualsiasi riga di tre blocchi 3×3 con qualsiasi altra riga. Puoi scambiare qualsiasi colonna di tre blocchi 3×3 con un’altra colonna. All’interno di ogni riga di blocco o colonna di blocchi è ansible scambiare singole righe e singole colonne. Infine puoi permutare i numeri in modo che ci siano numeri diversi nelle posizioni riempite finché la permutazione è coerente su tutta la scacchiera.

Nessuna di queste modifiche renderà irrisolvibile una scheda risolvibile.

A meno che non sia P = NP, non esiste un algoritmo tempo-polinomiale per generare problemi generali di Sudoku con esattamente una soluzione.

Nella sua tesi di laurea, Takayuki Yato ha definito L’altro problema di soluzione (ASP), in cui l’objective è, dato un problema e qualche soluzione, trovare una soluzione diversa a tale problema o mostrare che nessuno esiste. Yato ha quindi definito la completezza dell’ASP, problemi per i quali è difficile trovare un’altra soluzione e ha dimostrato che Sudoku è ASP-completo. Poiché dimostra anche che la completezza di ASP implica la durezza NP, questo significa che se si accettano tabs di Sudoku di dimensioni arbitrarie, non esiste un algoritmo tempo-polinomiale per verificare se il puzzle generato ha una soluzione unica (a meno che P = NP).

Mi spiace viziare le tue speranze per un algoritmo veloce!

Non è facile dare una soluzione generica. Devi sapere alcune cose per generare un tipo specifico di Sudoku … per esempio, non puoi build un Sudoku con più di nove gruppi vuoti di 9 numeri (righe, 3×3 blocchi o colonne). Si ritiene che i numeri minimi forniti (cioè “indizi”) in un Sudoku a soluzione singola siano 17, ma le posizioni numeriche per questo Sudoku sono molto specifiche se non sbaglio. Il numero medio di indizi per un Sudoku è circa 26, e non sono sicuro, ma se lasci i numeri di una griglia completata fino ad avere 26 e li lasci in un modo simmetrico, potresti avere un Sudoku valido. D’altra parte, puoi semplicemente smettere casualmente i numeri dalle griglie completate e testarli con CHECKER o altri strumenti finché non viene visualizzato un OK.

Penso anche che dovrai controllare esplicitamente l’unicità. Se hai meno di 17 givens, una soluzione unica è molto improbabile, tuttavia: nessuno è stato ancora trovato, sebbene non sia ancora chiaro se possa esistere.)

Ma puoi anche usare un solutore SAT, invece di scrivere un proprio algoritmo di backtracking. In questo modo, in una certa misura puoi regolare quanto sarà difficile trovare una soluzione: se limiti le regole di inferenza utilizzate dal SAT-solver, puoi verificare se è ansible risolvere facilmente il puzzle. Basta google per “SAT solving sudoku”.

Ecco un modo per creare un classico puzzle di sudoku (puzzle di sudoku con una sola soluzione, i quadrati pre-riempiti sono simmetrici attorno al quadrato centrale R5C5).

1) iniziare con una griglia completa (utilizzando il riempimento di gruppo più lo spostamento circolare per ottenerlo facilmente)

2) rimuovere il numero (i) da due quadrati simmetrici se i quadrati eliminati possono essere dedotti usando gli indizi rimanenti.

3) ripetere (2) fino a quando tutti i numeri sono controllati.

Usando questo metodo puoi creare un puzzle di sudoku molto semplice con o senza programmazione. Puoi anche usare questo metodo per creare più complessi puzzle di Sudoku. Potresti voler cercare “crea classic sudoku” su YouTube per avere un esempio passo dopo passo.

Questa logica ti darà un unico sudoku 9 * 9 ogni volta che lo esegui. Potrebbero essere necessari da 15 minuti a 20 minuti per generare un sudoku unico.

 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;i12000) { 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); } }