Generazione di un sudoku di una difficoltà desiderata?

Question

Quindi, ho fatto un bel po 'di lettura nella generazione di un puzzle di Sudoku. Da quello che posso dire, il modo standard per avere un puzzle di Sudoku di una difficoltà desiderata è generare un puzzle, e poi classificarlo in seguito, e ripetere fino a quando non si ha una valutazione accettabile. Questo può essere raffinato generando tramite backtracing usando alcuni dei più complessi schemi di risoluzione (ala XY, pesce spada, ecc.), Ma non è proprio quello che voglio fare qui.

Quello che voglio fare, ma non sono stato in grado di trovare alcuna risorsa reale, è generare un puzzle da un "valore di difficoltà" (valore 0-1.0, 0 è il più semplice e 1.0 è il più difficile).

Ad esempio, voglio creare un puzzle moderatamente difficile, quindi è selezionato il valore .675. Ora usando quel valore voglio essere in grado di generare un puzzle moderatamente difficile.

Qualcuno sa di qualcosa di simile? O forse qualcosa con una metodologia simile?

Answer 1

Non è elegante come quello che chiedi, ma è possibile simulare questo comportamento con il caching:

1. decidere quanti "secchi" che si desidera per i puzzle. Ad esempio, supponiamo che tu scelga 20. Quindi, i tuoi bucket conterranno puzzle di diversi livelli di difficoltà: 0-.05, .05-.1, .1-.15, .., .9-.95, .95- 1
2. generare un puzzle
3. Grade puzzle
4. Metti nel secchio appropriata (o buttare via quando il secchio è pieno)
5. Ripetere fino tuoi secchi sono "pieno". Le dimensioni dei contenitori e il loro luogo di conservazione saranno basati sulle esigenze dell'applicazione.

Quindi, quando un utente richiede un certo puzzle di difficoltà, dargli uno in cache dal bucket che sceglie. Potresti anche prendere in considerazione la possibilità di scambiare numeri e cambiare l'orientamento dei puzzle con difficoltà note per generare puzzle simili con lo stesso livello di difficoltà. Quindi ripeti quanto sopra quando necessario quando hai bisogno di riempire i tuoi secchi con nuovi puzzle.

Answer 2

Bene, non puoi sapere quanto sia complicato, prima di sapere come risolverlo. E il Sudoku che risolve (e quindi anche il livello di difficoltà) appartiene allo NP-C complexity class, il che significa che è (molto probabilmente) logicamente impossibile trovare un algoritmo che sia (asintoticamente) più veloce del proposto random-guess-and-check.

Tuttavia, se si può trovare uno, è stato risolto il P versus NP problem e dovrebbe cancellare un armadio per la Fields Medal ... :)

Answer 3

La difficoltà di sudoku è legato in un modo interessante per la (minima) quantità di informazioni necessarie per specificare una soluzione unica per una data griglia.

Suoni come la teoria dell'informazione, sì, anche qui ha applicazioni.

I puzzle di Sudoku dovrebbero avere una soluzione unica. Inoltre i puzzle di sudoku hanno certe simmetrie, cioè per riga, per colonna e per sotto-quadrato.

Queste simmetrie specificano il numero minimo di indizi (e la loro posizione più o meno) necessaria in modo che la soluzione sia univoca (cioè utilizzando un compilatore sudoku o un algoritmo come backtrack-search).

Questo sarebbe il livello di puzzle più difficile/difficile di sudoku (cioè il numero minimo necessario di indizi). Quindi tutti gli altri livelli di difficoltà, da quelli meno difficili a quelli facili, vengono generati consentendo più indizi rispetto all'importo minimo necessario.

Va notato che i livelli di difficoltà sono sudoku non di serie, come spiegato in precedenza, si può avere come molti o pochi livelli di difficoltà, come si vuole. Qual è lo standard è il numero minimo (e la posizione) di indizi (che è il livello più difficile e che è legato alle simmetrie di sudoku), allora si possono generare tanti livelli di difficoltà quanti ne si vogliono semplicemente permettendo di rendere visibili indizi extra/ridondanti anche.

Answer 4

Aggiunta di un'altra risposta per generare un sudoku della difficoltà desiderata al volo.

Ciò significa che, a differenza di altri approcci l'algoritmo esegue sola volta e restituisce una configurazione sudoku corrispondenza della difficoltà desiderato (con elevata probabilità di un intervallo o con probabilità = 1)

varie soluzioni per la generazione (e valutazione) una difficoltà di sudoku ha a che fare con human-based techniques and approaches, che può essere facilmente valutato.

Poi uno (dopo aver generato una configurazione sudoku) ri-risolve il sudoku con il risolutore di tipo umano e seconda delle tecniche del risolutore utilizzato (es coppie, x-ala, spada ecc.) viene anche assegnato un tasso di difficoltà.

problemi con questo approccio (e requisiti per il caso d'uso che ho avuto)

1. Per generare un sudoku con data difficoltà, con metodo precedente si ha la necessità di risolvere un sudoku due volte (una volta con l'algoritmo di base e una volta con il risolutore simile all'uomo).

2. Uno deve (pre) generare molti sudoku che possono essere valutati in base alla difficoltà dopo il risolutore di tipo umano. Quindi non è possibile generare immediatamente un sudoku desiderato al volo.

3. Il risolutore di tipo umano può essere complicato e nella maggior parte dei casi (se non tutti) è strettamente accoppiato a griglie di sudoku 9x9. Quindi nessuna facile generalizzazione ad altri sudoku (ad esempio 4x4, 16x16, 6x6 ecc.)

4. Il grado di difficoltà delle tecniche umane è molto soggettivo. Ad esempio, perché x-wing è considerato più difficile di single nascosti? (Personalmente hanno risolto molti difficili pubblicati puzzle Sudoku manualy e mai utilizzato tali tecniche)

Un altro approccio è stato utilizzato, che ha i seguenti vantaggi:

1. generalizza bene a sudoku arbitraria (9x9, 4x4, 6x6 16x16 ecc.
2. La configurazione di sudoku, con difficoltà desiderata, viene generata una volta e al volo
3. Il livello di difficoltà è oggettivo.

Come funziona?

Prima di tutto, il semplice fatto che il più difficile è il puzzle, più tempo ha bisogno di essere risolto.

Ma il tempo da risolvere è intimamente correlata sia numero di indizi (Givens) e alternative medi da investigare per cella vuota.

estendere il mio previous answer, è stato detto che per qualsiasi puzzle Sudoku il numero minimo di indizi è una proprietà oggettiva del puzzle (ad esempio for 9x9 grids the minimum number of clues for having a valid sudoku is 17)

Si può cominciare da lì e calcolare il numero minimo di indizi per difficoltà livello (correlazione lineare).

Inoltre in ogni fase del processo di generazione sudoku, si possono verificare le alternative medi (da investigare) per cella vuota è entro certi limiti (in funzione della difficoltà desiderata)

seconda che l'algoritmo usa backtrack o no (per il caso d'uso discusso l'algoritmo non fa retromarcia) la difficoltà desiderata può essere raggiunta sia con probabilità = 1 o con alta probabilità entro limiti (rispettivamente).

I test del sudokus generati con questo algoritmo e il livello di difficoltà basato sui precedenti approcci (risolutore umano) mostrano una correlazione tra i tassi di difficoltà desiderati e stimati, oltre a una maggiore capacità di generalizzazione di configurazioni arbitrarie di sudoku.

(hanno usato questo in linea sudoku solver (e anche this one) correlare i tassi difficoltà del sudoku di prova)

Il codice è disponibile gratuitamente on github sudoku.js (along with sample demo application), una versione in scala ridotta di un costruttore CrossWord.js cruciverba professionale in JavaScript, dallo stesso autore