Newsgroup: it.lavoro.informatica
Titolo: Linguaggi per implementare un sudoku

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?


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:
 
https://www.youtube.com/watch?v=Pulvn4Dmpnw
 
http://users.encs.concordia.ca/~kharma/coen6321/Papers/SudokuGA%20(1).pdf
 
https://nidragedd.github.io/sudoku-genetics/
 

Il 09/02/23 14:32, Aa Il mantovano ha scritto:

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.
 
 
 
 

Il 10/02/23 05:21, rootkit ha scritto:

Non devi chiederlo a me
Io ho solo risposto al fatto sui big
Se poi usarli o no sia utile non ho messo naso
 
 
-- 
|___|
 

 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

 è 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.

 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.

 In java esiste nella lib std il bignumber 
 
Dai, facci vedere come risolveresti quel problema usando la famosa classe "BigNumber".

Il 09/02/2023 21:32, Aa Il mantovano ha scritto:
 > 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
 > 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,
 
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
 > 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).
 
 > 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"
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
-- 
Questa email è stata esaminata alla ricerca di virus dal software antivirus Avast.
www.avast.com
 

 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.