Rompimuro

[giobimbo]

Nel primo computer modello Macintosh, il 128K, c’era un giochino chiamato “Rompimuro”. Ogni suo livello iniziale presentava il fondo dello schermo occupato da un muro di nxn mattoni impilati uno sull’altro, con l’ultima pila, l’ultima colonna, formata da mattoni col numero n, con n che aumentava di 2 man mano che si passava di livello. Bisognava numerare tutti gli altri in modo che una pallina, cadendo dall’alto li distruggesse tutti, lasciando in piedi solo l’ultima colonna. Le regole erano semplici:
1. Ogni fila di mattoni era formata da numeri diversi;
2. Ogni fila di mattoni conteneva i numeri da 1 a n;
3. Ogni fila era diversa dalle altre.
4. Se la pallina cadeva sul numero n allora Game Over, partita persa.

La pallina cadendo colpiva un qualsiasi mattone con numero minore di n – poniamo che fosse p – disintegrandolo e rimbalzando (SEMPRE verso destra, eventualmente uscendo dallo schermo e rientrandovi da sinistra) faceva un salto di m mattoni. Cadeva, supponiamo sul mattone numero q, distruggendolo e facendo poi un salto di q mattoni, e così via.

Un esempio con solo 2 file di un muro 11x11:
01 02 06 03 05 10 07 04 08 09 11
01 02 09 05 03 04 07 10 08 06 11

dalla prima fila vengono eliminati (pallina che cade su 04 per esempio):
04 01 02 03 07 06 08 10 05 09
prima fila eliminata e la pallina con un salto di 09 mattoni cade ora sul numero 10, per cui dalla seconda fila vengono eliminati in successione:
10 07 09 01 02 05 08 04 06 03
e anche la seconda fila viene eliminata. Provando con mattoni con numero diverso da 04 si vedrà che succede sempre la stessa cosa.

Problema 1 (facile). Numerare il muro del livello 1, che ha n=8
Problema 2 (meno facile). Numerare il muro del livello 2, con n=10

[Quelo]

Ciao Giobimbo,
se ho capito bene, perché ogni fila sia cancellata completamente partendo da un mattone qualsiasi, l'ultimo salto deve riportare al mattone di partenza (candendo poi sulla fila sottostante)
Questa condizione implica che la somma di tutti i salti deve essere multipla di n

$\displaystyle \frac{(n-1)n}{2}\equiv 0 \pmod{n}$

Ciò accade solo per i numeri dispari (se n è dispari, n-1 è pari)

Con n pari non trovo nessuna soluzione in cui l'ultimo salto riporta al mattone di partenza
Con n dispari invece si trovano diverse soluzioni:
per n = 3 è una sola: (1,2,3)
per n = 5 sono due: (1, 2, 3, 4, 5) e (2, 4, 1, 3, 5)
per n = 7 sono 14
per n = 9 sono 78
per n = 11 sono 838

In alcuni casi come per n = 5, 11, 13, 19, 29 la sequenza di numeri in ordine da 1 a n è una soluzione
La cosa curiosa è che i numeri che ammettono questa soluzione sono tutti numeri primi (almeno per n<100000)

[giobimbo]

Hai ragione Quelo, siccome stavo lavorando su diversi problemi devo aver fatto confusione.
Le soluzioni da trovare vanno riscritte così:

Problema 1 (facile). Numerare il muro del livello 1, che ha n=7
Problema 2 (meno facile). Numerare il muro del livello 2, con n=9

La stranezza dei casi in cui n è primo mi pare abbia una semplice spiegazione. Non essendoci divisori “tutte” le file sono una soluzione e nella parola “tutte” sono comprese anche quelle formate da numeri consecutivi.

[Quelo]

7 è un numero primo ma (1, 2, 3, 4, 5, 6, 7) non è una soluzione, stesso discorso per 17, 23, 31, ecc...

Non tutti i numeri primi ammettono una sequenza ordinata come soluzione
Nessun numero composto ammette una sequenza ordinata come soluzione

Codice: Seleziona tutto

3 ok [1, 2, 3]
5 ok [1, 2, 3, 4, 5]
7 no
11 ok [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
13 ok [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13]
17 no
19 ok [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19]
23 no
29 ok [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29]
31 no
37 ok [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32, 33, 34, 35, 36, 37]
41 no
43 no
47 no
53 ok 
59 ok 
61 ok 
67 ok 
71 no
73 no
79 no
83 ok 
89 no
97 no

[giobimbo]

Scusa Quelo, ma tu sei riuscito a costruire un muro 7x7 che risolve il Problema 1? Non son certo di capire cosa intendi per “soluzione”.

[franco]

Una soluzione del 7x7 potrebbe essere questa?

Rompimuro7x7.PNG (13.42 KiB) Visto 160905 volte

(non sono sicurissimo di aver capito il gioco)

[giobimbo]

Giusto, Franco, bravo. Nonostante la tua insicurezza hai risolto il Problema 1. Ovviamente ci sono molte-issime soluzioni possibili. Ora aspetto per il Problema 2.

[Quelo]

Per soluzione intendo una sequenza di numeri che permette di cancellare la fila intera (permutazione valida dei numeri da 1 a n-1)

Per il 7 esistono solo 14 permutazioni valide
[1, 3, 5, 2, 6, 4, 7]
[1, 4, 2, 6, 3, 5, 7]
[2, 3, 6, 4, 1, 5, 7]
[2, 4, 1, 5, 3, 6, 7]
[2, 4, 6, 1, 3, 5, 7]
[2, 6, 3, 1, 4, 5, 7]
[3, 1, 5, 2, 4, 6, 7]
[3, 4, 6, 1, 5, 2, 7]
[4, 1, 3, 5, 6, 2, 7]
[4, 1, 5, 2, 6, 3, 7]
[4, 2, 5, 6, 1, 3, 7]
[4, 6, 1, 2, 5, 3, 7]
[5, 1, 2, 4, 6, 3, 7]
[5, 2, 6, 1, 3, 4, 7]
Nessuna di queste ha i numeri in ordine (la più elegante è [2, 4, 6, 1, 3, 5, 7])

Complessivamente danno luogo a $\displaystyle \binom{14}{7}=3432$ possibili combinazioni per il muro 7x7 (escludendo le permutazioni delle file di mattoni che sono 7!=5040 per ogni combinazione)

Non le ho postate prima perché le ho trovate provando tutte le combinazioni con un programma, lo stesso per n=9 (78 permutazioni valide, 182 miliardi di combinazioni 9x9)

[franco]

Giusto, Franco, bravo. Nonostante la tua insicurezza hai risolto il Problema 1. Ovviamente ci sono molte-issime soluzioni possibili. Ora aspetto per il Problema 2.

Ottimo,

Onestamente, devo dire che non ho fatto grandissimi ragionamenti ... sono andato banalmente per tentativi trovando molto facilmente la prima riga (che partiva con un 1).
A quel punto ho provato a partire con 2, poi con 3 ... e ci ho messo poco tempo a trovare soluzioni per le prime 5 righe.
Le ultime due mi hanno fatto penare un pochino di più (del resto, col 6 non potevo certo cominciare!) ma comunque non è stato particolarmente impegnativo.

Il 9x9 mi sembra abbastanza più tosto.
Magari potrebbe essere più divertente provare a scrivere un programmino come ha fatto Quelo e lasciar fare i tentativi al PC

[giobimbo]

A scrivere programmi purtroppo non sono capace, ma dei ragionamenti sono possibili pensando in generale, ma ne parlerò più tardi, non vorrei dare troppi indizi che aiuterebbero a risolvere un prossimo gioco ancora in preparazione.
Grazie Quelo per le soluzioni di n=7, io manualmente ne avevo trovate solo 12, provvederò ad aggiornarmi. Per il Problema 2 ne avevo trovate 9, tante quante richieste.

[Quelo]

Inizialmente ho scelto un attacco di "forza bruta", cioè provare tutte le permutazioni per vedere quelle che rispettano i criteri
Per fortuna esistono algoritmi già pronti che producono tutte le permutazioni di un insieme (negli esempi di Decimal Basic c'è la routine PERMUTAT.BAS)
Quindi ho dovuto scrivere solo il codice di test (simulazione del movimento della pallina)
Con questo metodo, che ha una complessità computazionale abbastanza alta (le permutazioni di n elementi sono n!), arrivo agevolmente fino a 21x21 (cioè 21 righe diverse di lunghezza 21)

A questo punto ho ragionato su un algoritmo che replica quello che si potrebbe fare manualmente:
Mi posiziono sul primo mattone (la scelta è indifferente perché la sequenza deve essere valida con qualsiasi partenza), scelgo un numero, questo mi porta in una nuova posizione, qui ho solo alcune opzioni, perché devo scartare tutte quelle che mi portano sul primo mattone, sull'ultimo mattone o su uno già occupato.
Se ad un certo punto non ho più opzioni, torno indietro e faccio un'altra scelta, finché non trovo una sequenza valida.

Faccio un esempio con n=9

Sul primo mattone posso mettere tutti i numeri tranne l'8, perché 1+8=9, quindi finirei sull'ultimo mattone
Scelgo il 7, la nuova posizione è 8
Qui non posso mettere 1, perché andrei sul 9, né 2 perché andrei a 1 (8+2=10; 10 mod 9 = 1)
Scelgo il 3, la nuova posizione è 2
Scelgo l'1, la nuova posizione è 3
Qui non posso mettere 1,3,7 (già usati) né 6 che mi porta a 9
Scelgo il 2, la nuova posizione è 5
Qui non posso mettere 1,2,3,7 (già usati) né 4, 5, 6 che mi portano a 9 o su posizioni occupate
Scelgo l'8, la nuova posizione è 4
Qui mi fermo perché 4,5,6 non si possono mettere

Codice: Seleziona tutto

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
-------------------------------------
  7  ---------------------------> 3
      1	<--------------------------
      --> 2 ----> 8
              ✗ <--

Torno indietro di due passi e al posto del 2 metto il 4, la nuova posizone è 7
Qui non posso mettere 1,3,4,7 (già usati) né 2, 5 che mi portano a 9 o su posizioni occupate
Scelgo il 6, la nuova posizione è 4
Da qui le scelte sono obbligate
Scelgo il 2, la nuova posizione è 6
Scelgo l'8, la nuova posizione è 5
Il 5 in posizione 5 riporta a 1 e chiude il cerchio
La sequenza è valida

Codice: Seleziona tutto

| 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
-------------------------------------
  7  ---------------------------> 3
      1	<--------------------------
      --> 4 ------------> 6
              2 <----------
              ------> 8
                  5 <--
  ✓  <-------------

Con questo algoritmo arrivo facilmente a 49x49

Vi lascio anche una solouzione per 9x9

[7, 1, 4, 2, 5, 8, 6, 3, 9]
[7, 1, 4, 2, 6, 8, 3, 5, 9]
[7, 1, 4, 2, 8, 5, 3, 6, 9]
[7, 2, 4, 8, 1, 5, 3, 6, 9]
[7, 4, 1, 6, 2, 8, 5, 3, 9]
[7, 4, 2, 6, 8, 1, 5, 3, 9]
[7, 4, 2, 8, 5, 1, 6, 3, 9]
[7, 4, 2, 8, 6, 1, 3, 5, 9]
[7, 5, 1, 2, 6, 8, 3, 4, 9]
[7, 5, 2, 8, 1, 4, 6, 3, 9]

[giobimbo]

Ho visto che Decimal Basic ora è anche disponibile per Macintosh, vedrò di scaricarlo e cercare di capirci qualcosa.
L'idea di Rompimuro è vecchia, cercavo una soluzione usando i quadrati latini ma senza risultato, poi rilassando le regole, lasciando una fila intera invece di distruggere tutto il muro, mi è venuto fuori questo.

[Quelo]

Ho sempre programmato in Basic (a partire da quello del C=64 fino a Visual Studio), quindi l'approccio a Decimal Basic (scoperto grazie a questo forum) è stato naturale.
Il linguaggio è semplice e orientato alla matematica, quindi ti permette di fare cose che in altri linguaggi sono più laboriose.
C'è anche un'ottima guida in PDF che ho caricato qui https://sc476224442.files.wordpress.com ... c-help.pdf
Da un paio di anni sono passato a Python, molto più potente e versatile.
Ha il vantaggio di non avere limitazioni alla dimensione delle variabili, l'unico limite è la quantità di memoria installata, se ad esempio ho 1GB posso creare una stringa con 1 miliardo di caratteri o un numero con un miliardo di cifre.
Inoltre la maggior parte di ciò che ci serve è già stato pensato e realizzato da qualcuno ed esiste come libreria che si può aggiungere, come ad esempio per combinazioni e permutazioni.
Se si ha dimestichezza con il Basic non si fa fatica ad imparare le basi di Python.

A titolo d'esempio vi lascio il codice per Rompimuro

Codice: Seleziona tutto

from itertools import permutations as pms
for n in range(7,31,2):
    a = 0
    m = [[] for _ in range(n)]
    for i in range(1,n):
        m[i]=list(range(1,n))
        m[i].pop(n-1-i)
    r = []
    o = m.copy()
    r.append(o)
    s = []
    t = [0]*n
    p = 1
    while True:
        if m[p]==[]: break
        v = m[p].pop(0)
        q = p + v
        q %= n
        if q!=0 and t[q]==0:
            o = [x.copy() for x in m]
            r.append(o)
            for i in range(n):
                if v in m[i]: m[i].remove(v)            
            s.append(v)
            t[p] = v
            p += v
            p %= n
        else:
            if q==1 and len(s)==n-2:
                u = t.copy()
                u[p]=v
                u.pop(0)
                u.append(n)
                print(u)
                a += 1
            while len(m[p])==0:
                t[p] = 0
                m = r.pop(-1)
                if s==[]: break
                v = s.pop(-1)
                p -= v
                p %= n
        if n>9 and a==n: break