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 gioco - Grattacieli gioco

Grattacieli gioco

Sommario | Admin | Forum | Bugs | Todo | Files

Avatar
Carlo (Member)
Guru


Messaggi: 1388
Iscritto: 29/01/2018

Segnala al moderatore
Postato alle 17:26
Martedì, 30/04/2024
Programma C# per giocare al rompicapo Grattacieli su griglie 2x2 3x3 4x4 5x5, con possibilità di aiuto.

Il gioco consiste nel posizionare i grattacieli da 10, 20, 30, 40 o 50 piani, in modo da rispettare cosa vede le vedette (caselle bianche).

I grattacieli con più piani coprono i più bassi.
Nella stessa riga o colonna i grattacieli non si ripetono.
Se sullo schema 4x4 la vedetta vede 1 grattacielo significa che in prima posizione abbiamo il grattacielo con 40 piani.
Non sappiamo quali siano i grattacieli in seconda, terza e quarta posizione, si deve desumere dalle altre vedette.
Se la vedetta vede 4 grattacieli, è certo che la disposizione è: 10, 20, 30, 40.

In base alla griglia scelta cliccando le caselle gialle con il mouse destro, i numeri 10, 20, ... , e vuoto si susseguono."
Cliccando le caselle gialle con il mouse sinistro, i numeri ... , 20, 10 e vuoto si susseguono."

Clicca [aiuto] se non riesci, l'aiuto viene dato sulla prima casella vuota.

Se vuoi un aiuto per una casella specifica, riempi provvisoriamente le precedenti.

Combinazioni risultanti schemi.
2x2 = 2, immediato.
3x3 = 12, immediato.
4x4 = 576, frazione di secondo.
5x5 = 161280, generate in un secondo.

A questo punto o abbiamo tralasciato qualcosa per calcolare le combinazioni, oppure il mio algoritmo genera dei duplicati e/o ne tralascia qualcuna.

Ultima modifica effettuata da Carlo il 30/04/2024 alle 17:37


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


Messaggi: 891
Iscritto: 22/05/2010

Segnala al moderatore
Postato alle 18:44
Martedì, 30/04/2024
Ciao Carlo, prova a inserire una funzione che per ogni griglia trovata ne controlla la correttezza, se rispetta i parametri
non ci sono zeri e non è ripetuta.
l'algoritmo ricorsivo è interessante


If ok Then GOTO Avanza else GOTO Inizia

PM Quote
Avatar
Carlo (Member)
Guru


Messaggi: 1388
Iscritto: 29/01/2018

Segnala al moderatore
Postato alle 22:17
Martedì, 30/04/2024
Testo quotato

Postato originariamente da Ultimo:

Ciao Carlo, prova a inserire una funzione che per ogni griglia trovata ne controlla la correttezza, se rispetta i parametri
non ci sono zeri e non è ripetuta.
l'algoritmo ricorsivo è interessante



La griglia viene controllata e validata con la funzione valida, due vettori che rappresentano una riga e una colonna, vengono confrontati con le altre posizioni.

Non so se le permutazioni in combinazioni inaspettate possano generare due griglie uguali, ma verificando gli schemi prodotti dalle griglie 3x3 e 4x4 sembra proprio di no.

Nel tuo calcolo per esempio conti le permutazioni come se le righe fossero indipendenti, ma così non è, le righe vanno ripermutate anche in verticale.

Il calcolo con i fattoriali ne deve tenere conto (le parentesi solo per evidenziare i due fattoriali V-H):

Griglia 2x2 = (2*1)*(2*1) = 4
Griglia 3x3 = (3*2*1)*(3*2*1) = 36
Griglia 4x4 = (4*3*2*1)*(4*3*2*1) = 576
Griglia 5x5 = (5*4*3*2*1)*(5*4*3*2*1) = 14400
Griglia 6x6 = (6*5*4*3*2*1)*(6*5*4*3*2*1) = 518400

Questo significa che devo modificare l'algoritmo per la generazione che va benissimo a 4x4, ma salta degli schemi con griglie più piccole e duplica con griglie più grandi.

Ultima modifica effettuata da Carlo il 30/04/2024 alle 22:21


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


Messaggi: 891
Iscritto: 22/05/2010

Segnala al moderatore
Postato alle 23:13
Martedì, 30/04/2024
L'ho provato a 6 x 6 e ha superato 24 milioni di griglie, ho dovuto mettere un limite per uscire prima
non so a quanto potrebbe arrivare

Ultima modifica effettuata da Ultimo il 01/05/2024 alle 0:03


If ok Then GOTO Avanza else GOTO Inizia

PM Quote
Avatar
maurizio74 (Normal User)
Pro


Messaggi: 117
Iscritto: 30/03/2009

Segnala al moderatore
Postato alle 11:48
Mercoledì, 01/05/2024
C

Ultima modifica effettuata da maurizio74 il 01/05/2024 alle 13:13
PM Quote
Avatar
Carlo (Member)
Guru


Messaggi: 1388
Iscritto: 29/01/2018

Segnala al moderatore
Postato alle 19:11
Mercoledì, 01/05/2024
Testo quotato

Postato originariamente da Ultimo:

L'ho provato a 6 x 6 e ha superato 24 milioni di griglie, ho dovuto mettere un limite per uscire prima
non so a quanto potrebbe arrivare



a 6x6 supera la capacità della List, anche a 64bit.
Cercavo di capire se il mio algoritmo genera dei duplicati ma sembra di no, mi aiutate?
Ho semplificato l'algoritmo perché alcuni controlli che facevo sono risultati inutili

Qui un codice che genera e salva in un file testo, tutte le idee e commeti sono graditi.

Codice sorgente - presumibilmente C++

  1. using System;
  2. using System.Windows.Forms;
  3.  
  4. namespace Griglie
  5. {
  6.     public partial class Form1 : Form
  7.     {
  8.         int LatoGriglia = 5;  // cambiare a piacere 6 supera la capacità della lista
  9.  
  10.         System.Collections.Generic.List<sbyte[,]> listGrid = new System.Collections.Generic.List<sbyte[,]>();
  11.         int iterazioni = 0;
  12.         public Form1()
  13.         {
  14.             InitializeComponent();        
  15.         }
  16.  
  17.         private void Form1_Shown(object sender, EventArgs e)
  18.         {
  19.             this.Refresh();
  20.             sbyte[,] grid = new sbyte[LatoGriglia, LatoGriglia];
  21.             int size = grid.GetLength(0);
  22.             labInfo.Text = "generazione griglie per schema " + LatoGriglia.ToString() + "x" + LatoGriglia.ToString();
  23.             labInfo.Refresh();
  24.             risolviCell(grid, 0, 0, size);
  25.             string nomeFile = System.IO.Path.Combine(Application.StartupPath, size.ToString() + "x" + size.ToString() + ".txt");
  26.             labIterazioni.Text = "Iterazioni n. " + iterazioni.ToString();
  27.             labValide.Text = "Valide n. " + listGrid.Count.ToString();
  28.             labInfo.Text = "scrittura file in: " + nomeFile;
  29.             this.Refresh();
  30.             using (System.IO.StreamWriter sw = new System.IO.StreamWriter(nomeFile))
  31.             {
  32.                 for (int nlist = 0; nlist < listGrid.Count; nlist++)
  33.                 {
  34.                     sw.Write(nlist.ToString("00000000") + " | ");
  35.                     for (int i = 0; i < size; i++)
  36.                     {
  37.                         for (int j = 0; j < size; j++)
  38.                         {
  39.                             sw.Write(listGrid[nlist][i, j] * 10 + " ");
  40.                         }
  41.                         sw.Write("| ");
  42.                     }
  43.                     sw.WriteLine();
  44.                 }
  45.             }
  46.             labInfo.Text = "file salvato in: " + nomeFile;
  47.         }
  48.  
  49.         // *************** GENERAZIONE GRIGLIE VALIDE ****************  
  50.         public void risolviCell(sbyte[,] grid, int r, int c, int size)
  51.         {
  52.             iterazioni++;
  53.             if (iterazioni % 1333 == 0) { labIterazioni.Text = iterazioni.ToString(); labIterazioni.Refresh(); }
  54.             if (r == size)
  55.             {
  56.                 sbyte[,] clonedGrid = (sbyte[,])grid.Clone();
  57.                 listGrid.Add(clonedGrid); // aggiungo la griglia valida alla lista              
  58.                 if (listGrid.Count % 1333 == 0) { labValide.Text = listGrid.Count.ToString(); labValide.Refresh(); }
  59.                 return;
  60.             }
  61.  
  62.             if (c == size)
  63.             {
  64.                 risolviCell(grid, r + 1, 0, size);
  65.                 return;
  66.             }
  67.  
  68.             for (sbyte i = 1; i <= size; i++)
  69.             {
  70.                 if (valida(grid, r, c, i, size))
  71.                 {
  72.                     grid[r, c] = i;
  73.                     risolviCell(grid, r, c + 1, size);
  74.                     grid[r, c] = 0;
  75.                 }
  76.             }
  77.         }
  78.  
  79.         static bool valida(sbyte[,] grid, int r, int c, int num, int size)
  80.         {
  81.             for (int i = 0; i < size; i++)
  82.             {
  83.                 if (grid[r, i] == num || grid[i, c] == num)
  84.                 {
  85.                     return false;
  86.                 }
  87.             }
  88.             return true;
  89.         }
  90.     }
  91. }



Dubbi:
è vero che la griglia 6x6 sia così mostruosamente più grande della griglia 5x5?
è vero che non vengono generati duplicati?
come si dovrebbero calcolare tutte le combinazioni possibili?

Ultima modifica effettuata da Carlo il 01/05/2024 alle 19:25


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


Messaggi: 891
Iscritto: 22/05/2010

Segnala al moderatore
Postato alle 19:20
Mercoledì, 01/05/2024
Ciao, ho risposto nell'altro thread, sembra che sia tutto ok, il problema è trovare la formula giusta per il calcolo esatto.

dopo allego il codice che ho fatto.


Ultimo ha allegato un file: Screenshot (23).png (175015 bytes)
Clicca qui per guardare l'immagine

Ultima modifica effettuata da Ultimo il 01/05/2024 alle 19:23


If ok Then GOTO Avanza else GOTO Inizia

PM Quote
Avatar
Carlo (Member)
Guru


Messaggi: 1388
Iscritto: 29/01/2018

Segnala al moderatore
Postato alle 21:14
Mercoledì, 01/05/2024
Testo quotato

Postato originariamente da Ultimo:

Ciao, ho risposto nell'altro thread, sembra che sia tutto ok, il problema è trovare la formula giusta per il calcolo esatto.

dopo allego il codice che ho fatto.



Letto, grazie, allega.

Pensi che sarà possibile lo schema 6x6 :-?
Per ora a me sembra di no :blush:

Ultima modifica effettuata da Carlo il 01/05/2024 alle 21:15


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


Messaggi: 1388
Iscritto: 29/01/2018

Segnala al moderatore
Postato alle 10:36
Sabato, 04/05/2024
Testo quotato

Postato originariamente da Ultimo:

Quando troviamo una griglia, in realtà sono 4, nord sud est ovest

se permutiamo i valori, per esempio il 6 con 1, da una griglia ne troviamo un altra.


Bingo... grazieee. :rotfl:

Era quello che mi serviva, avevo in mente di prendere le prime 50.000 griglie valide per gli schemi più grandi di 4x4, ma prendendo solo le prime avrei avuto sempre la prima riga uguale in tutti gli schemi, e anche la seconda e la terza sullo schema 9x9. Ora ogni schema generato lo ruoto due volte e ci ottengo 3 griglie, con questo metodo le griglie sono variegate, ne genero 60.000, più che sufficienti per non annoiarsi e per evitare che qualcuno le impari a memoria.

Ho pubblicato la versione 1.0.0.2 del gioco rompicapo Grattacieli, griglie 2x2 3x3 4x4 5x5 6x6 7x7 8x8 9x9.
A mio avviso le griglie da 6x6 in su sono irrisolvibili, per questo ho introdotto la possibilità di rivelare qualsiasi casella cliccandola con il tasto centrale del mouse, la casella diventa rosa ed il contatore degli aiuti si incrementa.
Ultimo rigrazie per la dritta. :k:


in programmazione tutto è permesso
PM Quote