Linguaggi per implementare un sudoku

[Aa Il mantovano]

Ho una curiosità, provo a scrivere qui: in quali linguaggi
è possibile implementare un sudoku? Perché le possibili
disposizioni dei numeri sono 9^81, che è un numero di
60 e più cifre, mentre da una ricerca che ho fatto il totale
delle possibili valide disposizioni è un numero di 22 cifre:
si tratta di numeri che con il linguaggio java non sono
gestibili, e penso nemmeno con il C, che sono gli unici
due linguaggi che conosco (e il C molto meno del java).
Esistono linguaggi che arrivano a gestire numeri così
grandi? E se non esistono, come si può implementare un
algoritmo per il sudoku?

[rootkit]

Ho una curiosità, provo a scrivere qui: in quali linguaggi è possibile
implementare un sudoku? Perché le possibili disposizioni dei numeri sono
9^81, che è un numero di 60 e più cifre, mentre da una ricerca che ho
fatto il totale delle possibili valide disposizioni è un numero di 22
si tratta di numeri che con il linguaggio java non sono gestibili, e
penso nemmeno con il C, che sono gli unici due linguaggi che conosco (e
il C molto meno del java). Esistono linguaggi che arrivano a gestire
numeri così grandi? E se non esistono, come si può implementare un
algoritmo per il sudoku?

questo è stato un esercizio che ho proposto e discusso anni fa con dei
candidati ad un colloquio tecnico perché si presta bene a misurare la
capacità di analisi e la conoscenza base degli algoritmi. a giudicare da
quello che scrivi tu quel colloquio non l'avresti superato manco per
sogno.

tu hai una matrice 9x9 che devi riempire con 9 serie di numeri da 1 a 9
rispettando determinate regole. questo è l'obiettivo. visto che il numero
di possibili disposizioni è così elevato, il problema si presta ad un
approccio di tipo euristico. non solo, ma anche stocastico, dato che le
combinazioni valide sono tante e idealmente il tuo algoritmo dovrebbe
generarne ogni volta una diversa.

ti cerco io un po' di materiale da leggere:

http://users.encs.concordia.ca/~kharma/coen6321/Papers/SudokuGA%20(1).pdf
https://nidragedd.github.io/sudoku-genetics/

[enoquick]

Post by Aa Il mantovano
Ho una curiosità, provo a scrivere qui: in quali linguaggi
è possibile implementare un sudoku? Perché le possibili
disposizioni dei numeri sono 9^81, che è un numero di
60 e più cifre, mentre da una ricerca che ho fatto il totale
si tratta di numeri che con il linguaggio java non sono
gestibili, e penso nemmeno con il C, che sono gli unici
due linguaggi che conosco (e il C molto meno del java).
Esistono linguaggi che arrivano a gestire numeri così
grandi? E se non esistono, come si può implementare un
algoritmo per il sudoku?

Non proprio corretto
In java esiste nella lib std il bignumber
In c/c++ la libgmp sotto linux o mpr (che e' un porting di libgmp) sotto win
Inoltre per c++ boost ha i bignumber

[rootkit]

Ho una curiosità, provo a scrivere qui: in quali linguaggi è possibile
implementare un sudoku? Perché le possibili disposizioni dei numeri
sono 9^81, che è un numero di 60 e più cifre, mentre da una ricerca che
ho fatto il totale delle possibili valide disposizioni è un numero di
si tratta di numeri che con il linguaggio java non sono gestibili, e
penso nemmeno con il C, che sono gli unici due linguaggi che conosco (e
il C molto meno del java). Esistono linguaggi che arrivano a gestire
numeri così grandi? E se non esistono, come si può implementare un
algoritmo per il sudoku?

Non proprio corretto In java esiste nella lib std il bignumber In c/c++
la libgmp sotto linux o mpr (che e' un porting di libgmp) sotto win
Inoltre per c++ boost ha i bignumber

non capisco dove vedete la necessità di gestire numeri così abnormi per
risolvere questo problema. anche nelle soluzioni più fantasiose,
spiegatemelo perché veramente mi sfugge.
nel caso vi sia venuta l'insana idea di sviluppare tutte le soluzioni in
memoria vi informo che servirebbero, a cazzotto, svariati milioni di
petabyte di ram. fo per dirvelo, eh.

[enoquick]

Post by rootkit

Ho una curiosità, provo a scrivere qui: in quali linguaggi è possibile
implementare un sudoku? Perché le possibili disposizioni dei numeri
sono 9^81, che è un numero di 60 e più cifre, mentre da una ricerca che
ho fatto il totale delle possibili valide disposizioni è un numero di
si tratta di numeri che con il linguaggio java non sono gestibili, e
penso nemmeno con il C, che sono gli unici due linguaggi che conosco (e
il C molto meno del java). Esistono linguaggi che arrivano a gestire
numeri così grandi? E se non esistono, come si può implementare un
algoritmo per il sudoku?

Non proprio corretto In java esiste nella lib std il bignumber In c/c++
la libgmp sotto linux o mpr (che e' un porting di libgmp) sotto win
Inoltre per c++ boost ha i bignumber

non capisco dove vedete la necessità di gestire numeri così abnormi per
risolvere questo problema. anche nelle soluzioni più fantasiose,
spiegatemelo perché veramente mi sfugge.
nel caso vi sia venuta l'insana idea di sviluppare tutte le soluzioni in
memoria vi informo che servirebbero, a cazzotto, svariati milioni di
petabyte di ram. fo per dirvelo, eh.

Non devi chiederlo a me
Io ho solo risposto al fatto sui big
Se poi usarli o no sia utile non ho messo naso

[Una mamma]

Post by enoquick
Se poi usarli o no sia utile non ho messo naso

Ovvio. Tu non sapresti neanche da dove iniziare per risolvere un problema del genere. LOL :D

[rootkit]

Post by rootkit

Non proprio corretto In java esiste nella lib std il bignumber In c/c++
la libgmp sotto linux o mpr (che e' un porting di libgmp) sotto win
Inoltre per c++ boost ha i bignumber

non capisco dove vedete la necessità di gestire numeri così abnormi per
risolvere questo problema. anche nelle soluzioni più fantasiose,
spiegatemelo perché veramente mi sfugge.
nel caso vi sia venuta l'insana idea di sviluppare tutte le soluzioni
in memoria vi informo che servirebbero, a cazzotto, svariati milioni di
petabyte di ram. fo per dirvelo, eh.

Non devi chiederlo a me Io ho solo risposto al fatto sui big Se poi
usarli o no sia utile non ho messo naso

risposta del cazzo, quindi, visto che la domanda non era quella e
focalizzare su quello induce alla risposta sbagliata. è come se qualcuno
chiedesse "come faccio ad entrare in casa se abito al settimo piano e non
trovo scale a pioli abbastanza lunghe per arrivare al balcone?" e tu
rispondessi "esistono le scale dei pompieri" anziché "passa dalla porta".

premesso che fra l'altro non esiste in java nessun "bignumber" ma semmai
"biginteger", ma questo rientra nella cialtronaggine, te e l'accuratezza
siete su due pianeti diversi.

[Una mamma]

Post by enoquick
In java esiste nella lib std il bignumber

Dai, facci vedere come risolveresti quel problema usando la famosa classe "BigNumber".

[Una mamma]

Post by Aa Il mantovano
disposizioni dei numeri sono 9^81,

Sei sicuro?

Post by Aa Il mantovano
Ho una curiosità, provo a scrivere qui: in quali linguaggi
è possibile implementare un sudoku?

In qualunque linguaggio. Il numero di possibili disposizioni non c'entra nulla. Anche se fosse che volessi esplorare tutto lo spazio del problema, non sarebbe comunque necessario memorizzare quel numero. Semmai o ti finisce la memoria o il tuo brute force ci metter 3 secoli per finire. E` per questo che si studiano gli algoritmi, con le loro varie complessita`. Per il sudoku si puo` applicare un semplice algoritmo di backtracing.

[Marcoxxx]

Post by Aa Il mantovano
Ho una curiosità, provo a scrivere qui: in quali linguaggi
è possibile implementare un sudoku?

Magari ti hanno già risposto, ma credo che la risposta sia:

puoi usare un qualsiasi linguaggio.

Perché le possibili

Post by Aa Il mantovano
disposizioni dei numeri sono 9^81, che è un numero di
60 e più cifre, mentre da una ricerca che ho fatto il totale
si tratta di numeri che con il linguaggio java non sono
gestibili,

Nemmeno con altri. Non c'entra molto il linguaggio.
Credo sia più un problema di algoritmi.
Non conosco gli algoritmi che si possono usare per implementare il
sudoku, ma se usi degli algoritmi a complessità esponenziale
probabilmente non riesci a uscirne fuori con nessun linguaggio.
Se invece l'algoritmo che usi ha complessità inferiore puoi usare il
linguaggio che vuoi.

Altrimenti non potrebbero esistere ad esempio software che giocano a
scacchi o a go (a scacchi si stima che il numero di posizioni legali sia
dell'orgine di 10^43, il go ha probabilmente complessità molto maggiore).

e penso nemmeno con il C, che sono gli unici

Post by Aa Il mantovano
due linguaggi che conosco (e il C molto meno del java).

Molti software che giocano a scacchi sono implementati in C/C++,
anche quelli non basati su tecniche di AI (e la maggior parte dei
software esistenti per giocare a scacchi non è basato su AI).

Post by Aa Il mantovano
Esistono linguaggi che arrivano a gestire numeri così
grandi? E se non esistono, come si può implementare un
algoritmo per il sudoku?

è la complessità dell'algoritmo che conta, non il linguaggio.
Devi trovare un modo per risolvere il problema con un algoritmo di
complessità non esponenziale, poi lo implementi con qualsiasi
linguaggio. Però gli algoritmi per il sudoku non li conosco
(non so nemmeno esattamente cosa sia il sudoku. Me lo avevano
mostrato anni fa, ma me ne sono sempre altamente strafottuto).

Comunque da una semplice ricerca, ad esempio qui:

https://it.quora.com/Tutti-i-Sudoku-sono-risolvibili-con-un-algoritmo-o-codice#:~:text=Un%20algoritmo%20molto%20semplice%20(e,una%20soluzione%20accettabile%20del%20sudoku.

uno dice questa cosa (che non so che voglia dire perché nemmeno so
esattamente come funziona il sudoku):

"[..] Per risolvere (o creare) un sudoku basta un semplice algoritmo che
funziona così: parti dalla cella in alto a sinistra e se è piena vai
avanti, altrimenti posiziona un numero e vai avanti. Se non puoi
posizionare nessun numero (perché sono tutti già presenti nella riga,
colonna o quadrato) torna alla cella precedente e posiziona un altro
numero. Se hai finito le celle, hai riempito il sudoku. Questo algoritmo
funziona ricorsivamente piazzando un numero in una cella volta per volta
e verificando che la cella dopo sia riempibile. Se si arriva alla fine,
il sudoku è finito, altrimenti si torna indietro e si cambia numero e si
ritorna avanti. L'algoritmo funziona con ogni griglia (ammesso che non
sia già riempita male) indipendentemente da quanto sia già riempita"

[rootkit]

Post by Marcoxxx
"[..] Per risolvere (o creare) un sudoku basta un semplice algoritmo che
funziona così: parti dalla cella in alto a sinistra e se è piena vai
avanti, altrimenti posiziona un numero e vai avanti. Se non puoi
posizionare nessun numero (perché sono tutti già presenti nella riga,
colonna o quadrato) torna alla cella precedente e posiziona un altro
numero. Se hai finito le celle, hai riempito il sudoku. Questo algoritmo
funziona ricorsivamente piazzando un numero in una cella volta per volta
e verificando che la cella dopo sia riempibile. Se si arriva alla fine,
il sudoku è finito, altrimenti si torna indietro e si cambia numero e si
ritorna avanti. L'algoritmo funziona con ogni griglia (ammesso che non
sia già riempita male) indipendentemente da quanto sia già riempita"

per risolvere può andare bene, mentre per creare non è il più adatto
perché tendi a creare sempre lo stesso schema sulla base del numero di
partenza.
più adatto imho è un algoritmo genetico: in pratica popoli inizialmente la
griglia intera con le 9 serie di numeri disposti in modo random; ogni
iterazione (o generazione) applichi una mutazione scambiando due caselle,
quindi dai un punteggio alla nuova combinazione che dovrà essere
indicativo di quanto sei vicino alla soluzione. se il punteggio migliora
vai avanti con la generazione successiva, altrimenti riparti dalla
generazione precedente.
quello che non saprei come fare è, in fase di creazione, individuare
quante e quali caselle debbano essere rivelate per fare in modo che la
soluzione possibile sia solo quella generata.