sabato 30 gennaio 2010

C'è un giochino di cui non conosco il nome

C'è un giochino, di cui non conosco il nome, che funziona così: si deve riempire una griglia quadrata n×n con i numeri che vanno da 1 a n2, seguendo queste regole:

1) ci si può spostare in orizzontale o in verticale saltando due caselle,
2) ci si può spostare in diagonale saltando una casella.

Di solito si mette il numero 1 nella prima casella in alto a sinistra, ma non è obbligatorio.

Ai miei tempi era molto noto e si faceva sempre a scuola durante le, ehm, pause. Si parte, di solito, con n=5; i più temerari provano anche con n=10.

Qualche giorno fa uno studente me l'ha riproposto (lui non lo conosceva e lo considerava una novità (i corsi e ricorsi storici…)), e mi sono messo lì a compilare la mia griglia, tra un'interrogazione e un esercizio. Naturalmente anche gli altri studenti si sono interessati, e in breve è iniziata la gara.

“Prof, ma se entra la preside?”, diceva uno.

“Bè? Anche questa è matematica, no?”, rispondevo angelico.

“Massè”, interveniva quello che nella griglia 5×5 si era fermato al numero 9.

“Sì, vi dico. Provate, che poi ne parliamo”, insistevo.

“Prof, ma è ancora lì?”, domandava quello che aveva già riempito un foglio con le sue prove.

“Sono al numero 19, tu?”, rispondevo mentre con la matita segnavo puntini qua e là sulla mia griglia.

“Eh, io sono arrivato all'89 in uno, al 91 in un altro, al 94 in questo, ma non riesco ad arrivare a 100”.

“E allora cosa ridi? Io arrivo al 100 prima di te”.

Insomma, alla fine dell'ora io ero arrivato circa a metà schema, e la lezione successiva ho portato la griglia completa.

Eccola qua:


Provateci, poi ne parliamo.

14 commenti:

Massimo ha detto...

io non ero male a questo gioco. Se vuoi insegnare agli studenti le magie della ricorsione e del backtracking ho ancora un programmino perl che ho scritto nei primi '90 per risolverlo.

Massimo ha detto...

(le regole del mio sono un po' diverse, uso la mossa del cavallo, ma non dovrebbe essere difficile modificarlo)

zar ha detto...

Ecco, in realtà il backtacking non serve (questo sarà il succo del prossimo post sull'argomento...).

Anche io avevo fatto un programma simile al tuo, poi ho scoperto, leggendo McMicrocomputer, che esiste un altro modo.

[Uhm, rileggendomi forse è meglio che specifichi: il backtracking non serve con queste regole, mentre non so se l'altro metodo si possa usare con la mossa del cavallo, bisognerebbe provarci]

Massimo ha detto...

Ok, funziona anche con le tue regole:
Sun Jan 31 09:47:08 2010:Solution:102 after
----+---+---+---+---+---+---+---+---+---+
| 1| 66| 69| 16| 65| 38| 47| 56| 37| 40|
----+---+---+---+---+---+---+---+---+---+
| 75| 18| 3| 76| 45| 4| 35| 44| 5| 34|
----+---+---+---+---+---+---+---+---+---+
| 68| 15| 60| 67| 70| 59| 64| 39| 48| 57|
----+---+---+---+---+---+---+---+---+---+
| 2| 77| 74| 17| 78| 43| 46| 55| 36| 41|
----+---+---+---+---+---+---+---+---+---+
| 92| 19| 71| 93| 63| 29| 94| 58| 6| 33|
----+---+---+---+---+---+---+---+---+---+
| 81| 14| 61| 80| 73| 50| 79| 42| 49| 52|
----+---+---+---+---+---+---+---+---+---+
| 23| 96| 89| 28| 95| 88| 27| 54| 85| 10|
----+---+---+---+---+---+---+---+---+---+
| 91| 20| 72| 98| 62| 30| 99| 51| 7| 32|
----+---+---+---+---+---+---+---+---+---+
| 82| 13| 24| 83| 12| 25| 84| 11| 26| 53|
----+---+---+---+---+---+---+---+---+---+
| 22| 97| 90| 21|100| 87| 8| 31| 86| 9|
----+---+---+---+---+---+---+---+---+---+

zar ha detto...

Bello. Il sorgente perl è molto lungo? Sono curioso, il perl non lo conosco...

Massimo ha detto...

nel libro di kay su xmlt kay risolveva il problema con xmlt, cosa complicata dal momento che in quel linguaggio non sono possibili le assegnazioni. C'era ricorsione ma non backtracking, perché scegliendo ripetutamente la soluzione con meno mosse possibili si risolveva il problema a livello 8 senza backtrack.

Massimo ha detto...

Non è lungo. Va lanciato da dos. Mandami una email che te lo mando.

Massimo ha detto...

guarda il dm in ff

topor ha detto...

Rimpiango con grandissima nostalgia quando queste cose io e lo Zar le facevamo a mano (ehi, non pensate tutti subito male!) e ci passavamo giorni e giorni, oscillando fra 98 e 99....
Quando sono arrivata a 100 per la prima volta quasi la incorniciavo.
Devo specificare che c'è più di una soluzione o mi prendete a sportellate perchè secondo chissaquale teorema è talmente ovvio...?

zar ha detto...

Ehi, anche quello in figura è fatto a mano, eh. Ma esiste una tecnica per farlo "bene" al primo colpo.

Marco ha detto...

La cosa più bella da fare a mano è automatizzare i processi automatizzabili!!! Potresti scrivere qualche post al riguardo :)

zar ha detto...

Sì, l'idea era questa...

topor ha detto...

tempo fa, quando mio figlio lo scoprì, ne facemmo molti insieme, e avevo diviso lo schema in quattro parti concatenando la soluzione di un "25" all'altro ripetendo le stesse mosse.
Vale?

zar ha detto...

Se funziona, vale.