Questo sito utilizza cookies solo per scopi di autenticazione sul sito e nient'altro. Nessuna informazione personale viene tracciata. Leggi l'informativa sui cookies.
Username: Password: oppure
Grattacieli - Grattacieli C#
Forum - Grattacieli - Grattacieli C# - Pagina 2

Pagine: [ 1 2 3 ] Precedente | Prossimo
Avatar
Carlo (Member)
Guru


Messaggi: 1389
Iscritto: 29/01/2018

Segnala al moderatore
Postato alle 1:20
Domenica, 28/04/2024
Testo quotato

Postato originariamente da AldoBaldo:

Qualche domanda...

Quante sarebbero le soluzioni possibili in una griglia 9x9?
È lecito dire che non si tratta di un solutore ma di un archivio di soluzioni?
È fattibile un solutore che analizzi la situazione e trovi la soluzione "al volo"? Come?
In caso contrario, sarebbe proponibile precalcolare le soluzioni e inserirle in un file per non ripetere ogni volta il procedimento?


griglia 3x3 da una set di schemi disponibili su una griglia di lato 6, 6x6 = 36
griglia 4x4 da una set di schemi disponibili su una griglia di lato 24, 24x24 = 576
griglia 5x5 da una set di schemi disponibili su una griglia di lato 120, 120x120 = 14400
griglia 6x6 da una set di schemi disponibili su una griglia di lato 720, 720x720 = 518400
griglia 7x7 da una set di schemi disponibili su una griglia di lato 5040, 5040x5040 = 25401600
griglia 8x8 da una set di schemi disponibili su una griglia di lato 40320, 40320x40320 = 1625702400
griglia 9x9 da una set di schemi disponibili su una griglia di lato 362880, 362880x362880 = 131681894400

Il metodo adottato per risolvere lo schema si chiama brute force, dove si provano tutte le combinazoni possibili, l'unica intelligenza sta nel fatto che vengono scartati a priori gli schemi non congrui, limitando di fatto il numero delle iterazioni per arrivare alla soluzione.

Un algoritmo che arrivi alla soluzione in modo analitico sarà quasi sicuramente perseguibile, ed era quello cha hanno tentato di fare nel 2017 i signori che hanno partecipato infruttuosamente alla discussione sul forum proposto da maurizio74, tale approcio è fuori dalla mia portata.

Quando ho scritto il programma per trovare tutte le griglie possibili, non sapevo quando tempo avrebbe impiegato, e il pensiero di mettere le soluzioni in un file da ricaricare senza rigenerarle era nel cassetto. Visto che invece le griglie 4x4 vengono generate in una frazione di secondo, il file non è necessario. Tale approcio è ancora praticabile per griglie più grandi, ma anche il metodo di ricerca è migliorabile, infatti quando mi sono reso conto che gli schemi erano solo 576 non mi sono preoccupato di ottimizzare il codice di ricerca.

Come anticipato da Ultimo una volta generati gli schemi e salvati su file, per analizzarli si possono far partire 4 Thread ognuno che analizza la sua fetta, per esempio la griglia 5x5 con le sue 14400 combinazioni sarebbero analizzati dal thread1 da 0 a 3599, il thread2 da 3600 a 7199 il thread3 da 7200 a 10799 e il thread4 da 10800 a 14400.

Ritengo che con questo approcio trovare lo schema 5x5 corrispondente sia ancora quasi immediato. Per schemi più grandi bisognerà aspettare.

Ultima modifica effettuata da Carlo il 28/04/2024 alle 10:22


in programmazione tutto è permesso
PM Quote
Avatar
AldoBaldo (Member)
Guru


Messaggi: 708
Iscritto: 08/01/2015

Segnala al moderatore
Postato alle 2:08
Domenica, 28/04/2024
Il problema è che un file che contenga 130 e passa miliardi di combinazioni è ingestibile sia per spazio di archiviazione, sia per velocità di consultazione. Immagino poi il tempo che richiederebbe calcolarlo e scriverlo...

È curioso che uno schema di gioco possa essere risolto basandosi sull'intuizione in modo relativamente diretto, mentre addivenire alla stessa soluzione per via programmatica sia così pestifero! Se riesci a venire a capo di questa roba sei davvero un grande. Io non mi ci metto neppure.


ATTENZIONE! Sono un hobbista e l'affidabilità delle mie conoscenze informatiche è molto limitata. Non prendere come esempio il codice che scrivo, perché non ho alcuna formazione accademica e rischieresti di apprendere pratiche controproducenti.
PM Quote
Avatar
Carlo (Member)
Guru


Messaggi: 1389
Iscritto: 29/01/2018

Segnala al moderatore
Postato alle 10:30
Domenica, 28/04/2024
Testo quotato

Postato originariamente da AldoBaldo:
È curioso che uno schema di gioco possa essere risolto basandosi sull'intuizione in modo relativamente diretto, mentre addivenire alla stessa soluzione per via programmatica sia così pestifero!



Sono problemi NP, il più famoso è quello del commesso viaggiatore, chi li risolve si intasca un milione di dollari: https://matematica.unibocconi.eu/articoli/un-milione-di-dol ...


in programmazione tutto è permesso
PM Quote
Avatar
Ultimo (Member)
Guru


Messaggi: 891
Iscritto: 22/05/2010

Segnala al moderatore
Postato alle 11:16
Domenica, 28/04/2024
Ciao a tutti

Io faccio un calcolo delle permutazioni seguente:

Su una griglia 4 x 4

prima riga       = 4 x 3 x 2 x 1 = 24

seconda riga   =       3 x 2 x 1 = 6

terza riga       =             2 x 1 = 2

quarta riga    =                   1 = 1

si moltiplicano le permutazioni delle righe 24 x 6 x 2 x 1 = 288

ora come si vede le griglie univoche dovrebbero essere 288

se moltiplichiamo 288 per 2 il risultato è 576



If ok Then GOTO Avanza else GOTO Inizia

PM Quote
Avatar
Ultimo (Member)
Guru


Messaggi: 891
Iscritto: 22/05/2010

Segnala al moderatore
Postato alle 11:30
Domenica, 28/04/2024
Carlo i thread utilizzabili possono essere anche 1024, puoi utilizzarne anche di più,

anche per la ricerca delle griglie possibili puoi suddividerla su thread che eseguono una funzione o procedura.


If ok Then GOTO Avanza else GOTO Inizia

PM Quote
Avatar
Carlo (Member)
Guru


Messaggi: 1389
Iscritto: 29/01/2018

Segnala al moderatore
Postato alle 19:53
Domenica, 28/04/2024
Testo quotato

Postato originariamente da Ultimo:

Ciao a tutti

Io faccio un calcolo delle permutazioni seguente:

Su una griglia 4 x 4

prima riga       = 4 x 3 x 2 x 1 = 24

seconda riga   =       3 x 2 x 1 = 6

terza riga       =             2 x 1 = 2

quarta riga    =                   1 = 1

si moltiplicano le permutazioni delle righe 24 x 6 x 2 x 1 = 288

ora come si vede le griglie univoche dovrebbero essere 288

se moltiplichiamo 288 per 2 il risultato è 576



il ragionamento sembra valido, se fosse nei miei schemi ci devono essere delle ripetizioni, controllerò.
Una cosa che ho notato e che un quesito può avere due soluzioni per esempio:
Codice sorgente - presumibilmente Plain Text

  1. -----------------
  2.    1  2  2  4
  3. 1 40 30 20 10 4
  4. 2 30 10 40 20 2
  5. 2 20 40 10 30 2
  6. 4 10 20 30 40 1
  7.    4  2  2  1
  8. -----------------
  9.    1  2  2  4
  10. 1 40 30 20 10 4
  11. 2 30 40 10 20 2
  12. 2 20 10 40 30 2
  13. 4 10 20 30 40 1
  14.    4  2  2  1
  15. ----------------



EDIT: e 4 soluzioni:
Codice sorgente - presumibilmente Plain Text

  1. 256 ------------
  2.    2  1  3  2
  3. 2 20 40 10 30 2
  4. 1 40 10 30 20 3
  5. 3 10 30 20 40 1
  6. 2 30 20 40 10 2
  7.    2  3  1  2
  8.  
  9. 118 ------------
  10.    2  1  3  2
  11. 2 10 40 20 30 2
  12. 1 40 30 10 20 3
  13. 3 20 10 30 40 1
  14. 2 30 20 40 10 2
  15.    2  3  1  2
  16.  
  17. 258 ------------
  18.    2  1  3  2
  19. 2 20 40 10 30 2
  20. 1 40 20 30 10 3
  21. 3 10 30 20 40 1
  22. 2 30 10 40 20 2
  23.    2  3  1  2
  24.  
  25. 402 ------------
  26.    2  1  3  2
  27. 2 30 40 10 20 2
  28. 1 40 20 30 10 3
  29. 3 10 30 20 40 1
  30. 2 20 10 40 30 2
  31.    2  3  1  2



non ho trovato schemi ripetuti, il mio calcolo disponedo le griglie su un quadrato che le contiene è più accurato.

Ultima modifica effettuata da Carlo il 28/04/2024 alle 20:42


in programmazione tutto è permesso
PM Quote
Avatar
Ultimo (Member)
Guru


Messaggi: 891
Iscritto: 22/05/2010

Segnala al moderatore
Postato alle 19:13
Mercoledì, 01/05/2024
Ciao, col 6x6 l'algoritmo ricorsivo ha generato 812.850.000 griglie valide (dopo più di un ora )

ho verificato con una funzione non ci sono zeri, ne ripetizioni nelle righe e nelle colonne

se nella lista non ci sono griglie ripetute e sembra che non c'è ne siano questo è il numero esatto.



If ok Then GOTO Avanza else GOTO Inizia

PM Quote
Avatar
Carlo (Member)
Guru


Messaggi: 1389
Iscritto: 29/01/2018

Segnala al moderatore
Postato alle 20:48
Mercoledì, 01/05/2024
Testo quotato

Postato originariamente da Ultimo:

Ciao, col 6x6 l'algoritmo ricorsivo ha generato 812.850.000 griglie valide (dopo più di un ora )

ho verificato con una funzione non ci sono zeri, ne ripetizioni nelle righe e nelle colonne

se nella lista non ci sono griglie ripetute e sembra che non c'è ne siano questo è il numero esatto.




Hai messo tutte le griglie in una lista? credo di no.
il numero 812.850.000 non è esatto perchè con mod 10000 ti predi i conteggi, avresti dovuto ristampare conta.
Il numero esatto è 812.851.200, conteggio effettuato senza aggiungere le griglie in una lista.
Nelle mie prove ho verificato che a 64bit la lista riesce a contenere poco più di 134 milioni di schemi 6x6 composti da byte. :yup:

Resto ancora sorpreso dall'enorme differenza di schemi generabili tra griglia 5x5 e griglia 6x6 :om:




in programmazione tutto è permesso
PM Quote
Pagine: [ 1 2 3 ] Precedente | Prossimo