Ricerca algoritmo per Sudoku

[Gianluigi]

Il sudoku ha regole semplici, si gioca su una tabella di nove per nove caselle (9×9) in ognuna delle quali si deve inserire una cifra, da uno a nove.
Ogni riga e ogni colonna deve contenere tutte le cifre, da uno a nove, senza ripetizioni.
Ulteriore condizione anche ogni blocco di caselle tre per tre (3×3), contrassegnato da linee più marcate, deve contenere le nove cifre, senza ripetizioni. Il sudoku si presenta con una parte delle cifre già inserite in alcune caselle da un minimo di 20 a un massimo di 35.
Per essere un vero sudoku, deve inoltre avere una soluzione unica.
Ah e naturalmente deve poter essere risolto.
Se ho capito bene quello che ho letto, per avere una soluzione unica sembrerebbe  che i numeri minimi da mostrare siano 17 poiché pare sia stato provato che inserendone 16, le soluzioni possibili risulterebbero già 2 e il numero aumenterebbe esponenzialmente diminuendo tale cifra . Normalmente i numeri inseriti nello schema sono da 20 a 35 più basso è il numero delle cifre già inserite più la soluzione del gioco dovrebbe secondo logica essere difficile.
Invero ho anche letto che essendo un gioco di logica e non matematico la difficoltà è data dalla disposizione dei numeri dati e non dalla quantità.
A proposito di disposizione pare che sia stato dimostrato che per avere una soluzione univoca occorre che almeno un valore sia presente all’interno dell’area mostrata nell’immagine allegata.
Queste due caratteristiche, e cioè sopra i 17 valori esposti con almeno uno all’interno dell’area, ci aiutano a escludere parecchi schemi sicuramente non univoci ma non ne garantiscono l’unicità che sembra meglio ottenuta attraverso il metodo dei Dancing Links. Vedi ( https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X )

Qualcuno conosce l’algoritmo, magari lo ha già tradotto in gambas?

Qui visto che si parte da una griglia completa, vale a dire da un sudoku già compilato forse basta anche meno, ma non mi riesce proprio di capire come posso fare per scoprire se la soluzione data sia l’unica.
Qualcuna ha voglia di cimentarsi in questo rompicapo?

Allego la prima parte del codice di sudoku quella in cui si crea una griglia completa e via via nei vari passaggi commentati nel codice si affina la soluzione per poi passare al mostrare il gioco al giocatore, mentre si stampa la soluzione in console.

Come detto manca ancora l’algoritmo per sapere se la soluzione è unica, manca anche e tutto il resto che qui è solo in parte accennato, siamo solo all’inizio.

Grazie a chiunque voglia dare il proprio parere anche solo al codice già scritto.
La mia matematica è elementare pertanto vogliate scusare le ingenuità... siete i ben venuti a correggerle.

 

[cogier]

C'è questo nella 'Farm'.

https://gambas.one/gambasfarm/?id=519&action=search

[Gianluigi]

Si conosco, conosco anche l'autore che è membro di questo forum.
Purtroppo l'algoritmo che cerco non c'è (o forse non lo vedo).

[dex]

A parte che non conosco il sudoku e non posso aiutarti, la mia è più una curiosità.
ma tu cerchi un algoritmo che inserisca da solo i numeri giusti oppure uno che ti risolva il gioco?

[Gianluigi]

A parte che non conosco il sudoku e non posso aiutarti, la mia è più una curiosità.
ma tu cerchi un algoritmo che inserisca da solo i numeri giusti oppure uno che ti risolva il gioco?

Ma il programma Sudoku-PrimaParte allegato alla domanda (topic) lo hai scaricato?
Il codice mi sembrava ben commentato e, a modo suo, carica un gioco (puzzle) di cui da anche la soluzione in console.
In verità il gioco si forma a partire dalla soluzione che tiene conto delle regole dette nel topic, devo ancora pensare come essere assolutamente certo di almeno una cifra in area scura, ma questo non è un grosso problema.
Quello che cerco è l'algoritmo X tradotto in Gambas per vedere se può, come si dice in giro, garantirmi l'unicità della soluzione.
Pensavo anche a questo: ma se nei numeri (fra 20 e 35) mostrati faccio in modo che ci siano tutte e 9 le cifre, questo non dovrebbe garantire l'unicità della soluzione?
Insomma, se parte da una soluzione vuol dire che il puzzle è risolvibile, se negli indizi si mostrano tutte le cifre non dovrebbe significare che non c'è altra soluzione che quella da cui il puzzle parte? 

Purtroppo siccome vedo che il sudoku è molto discusso nei problemi algebrici, temo che non sia così semplice. 

Mannaggia l'ignoranza...

[cogier]

Ho dato un'occhiata a 'MySudoku'. C'è un problema perché crea numeri ripetitivi.



Ho scritto del codice che crea un puzzle completo. Crea numeri diversi ogni volta che la routine viene chiamata.



È questo quello che stai cercando?

[Gianluigi]

Ho dato un'occhiata a 'MySudoku'. C'è un problema perché crea numeri ripetitivi.
...

Ho scaricato il tuo programma e ti farò sapere, ma tu hai scaricato il mio (Sudoku-PrimaParte-0.0.1.tar.gz) presente nel primo post?
Perché non hai lavorato su quello?

[Gianluigi]

Ciao cogier,

ho guardato il tuo algoritmo di compilazione del puzzle, sembra molto buono.
Vedo che si tratta di un vecchio studio del 2002, è la traduzione di un altro algoritmo?
Potresti gentilmente spiegarne i passaggi, purtroppo sono troppo ignorante per capirlo da solo 

 

P.S. Comunque il problema dell'unicità della soluzione rimane.

[cogier]

Ciao Gianluigi,

L'idea di base è che ci sia un array per ogni colonna e riga.

Codice: [Seleziona]

byRow0 As New Byte[] byRow1 As New Byte[] byRow2 As New Byte[] byRow3 As New Byte[] byRow4 As New Byte[] byRow5 As New Byte[] byRow6 As New Byte[] byRow7 As New Byte[] byRow8 As New Byte[]
byCol0 As New Byte[] byCol1 As New Byte[] byCol2 As New Byte[] byCol3 As New Byte[] byCol4 As New Byte[] byCol5 As New Byte[] byCol6 As New Byte[] byCol7 As New Byte[] byCol8 As New Byte[]

Viene creato un insieme casuale di numeri.

Codice: [Seleziona]

byNumbers = [1, 2, 3, 4, 5, 6, 7, 8, 9]
byNumbers.Shuffle()

Si cerca di aggiungere il primo numero alla riga e alla colonna in questione, a condizione che non esista già. Poi il successivo fino a quando non si adatta o non fallisce. This creates one of the 9 blocks of 9.

Codice: [Seleziona]

If Not oAllRows[byRow + byNextWorkRow].Exist(byNumbers[byCounter]) And If Not oAllCols[byCol + byNextWorkCol].Exist(byNumbers[byCounter]) Then..

Questa operazione fallirà molte volte e il tentativo verrà interrotto. Il processo ricomincia da capo.

Codice: [Seleziona]

Repeat
    byLines.Clear
    ClearAll
    CreateArray
    Inc iTimes
  Until bItWorks = True

Ho appena creato 5 nuove soluzioni e i tentativi sono stati 19, 216, 257, 64 e 3 prima che l'intero processo fosse completato con successo. Durante il processo una Stringa[9,9] viene riempita e poi restituita.

The attempts are printed in the Console. '464 arrays of 81 numbers were created before a solution was found'  (Prima di trovare una soluzione sono state create 464 matrici di 81 numeri)

Spero che questo aiuti.

Non capisco esattamente cosa state cercando. Forse potrebbe spiegarlo in un altro modo. Non parlo italiano, quindi il suo punto di vista potrebbe essersi perso nella traduzione.

[Gianluigi]

Ciao cogier,

Grazie ora ho capito 

...
Non capisco esattamente cosa state cercando. Forse potrebbe spiegarlo in un altro modo. Non parlo italiano, quindi il suo punto di vista potrebbe essersi perso nella traduzione.

I started by creating a simple and orderly basic puzzle which then through various steps and various cycles creates the definitive puzzle to be masked to present it to the player.

This, apart from my poor math skills, I find it useful for creating puzzles of various difficulties, less cycles = easier game (maybe).

Unfortunately, your beautiful method is not controllable, you need a way to understand if the puzzle is easy, medium or difficult.

I, however,  I have passed the phase (valid or not) of the realization of the puzzle.

At this point the necessary algorithm is the one that from the masked puzzle (i.e. the puzzle ready to play) can check that there is only one valid solution.

This algorithm, as long as I understand correctly what I read, is Knuth's X algorithm: https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X , and I asked if there was someone who already had it done.

I think Tobias Boege has done something approaching X with gb.data Trie and TriePrefix ( http://gambaswiki.org/wiki/comp/gb.data ) but I'm too ignorant to understand anything 

Tradotto:

io ho iniziato con la creazione di un puzzle base semplice e ordinato che poi attraverso vari passaggi e vari cicli crea il puzzle definitivo da mascherare per presentarlo al giocatore.

Questo, a parte le mie scarse capacità matematiche, lo ritengo utile per creare puzzle di varie difficoltà, meno cicli = gioco più facile (forse).

Il tuo bel metodo purtroppo non è controllabile, occorre un modo per poter capire se il puzzle è facile, medio o difficile.

Io comunque la fase (valida o meno che sia) della realizzazione del puzzle l'ho superata.

A questo punto l'algoritmo necessario è quello che dal puzzle mascherato (vale a dire il puzzle pronto per giocare) può controllare che ci sia una sola soluzione valida.

Questo algoritmo, sempre che io abbia capito bene quello che ho letto, è l'algoritmo X di Knuth: https://en.wikipedia.org/wiki/Knuth%27s_Algorithm_X , e io chiedevo se c'era qualcuno che lo aveva già fatto.

Credo che Tobias Boege abbia fatto qualcosa che si avvicina a X con gb.data Trie e TriePrefix ( http://gambaswiki.org/wiki/comp/gb.data ) ma io sono troppo ignorante per capirci qualcosa.

[cogier]

..ma io sono troppo ignorante per capirci qualcosa.

Non siete soli.