Newsgroup: it.hobby.enigmi
Titolo: QUIZ DELLE 100 caselle

Il gioco č questo:
dovete riempire 100 caselle (10 x 10) con i numeri dall'1 al 100, ma
disponendoli cosě:
si parte da dove si vuole, ma il numero successivo deve essere distanziato
di due caselle se posto in orizzontale o in verticale, o di una se in
diagonale...
Se riuscite a fare questo rompicapo, non solo mi faccio prete, ma vorrei
anche che mi spediste la soluzione!!!
Eugenio
cicc...@iol.it

Eugenio
ciao
paolo


--
Posted from [208.163.206.2]
via Mailgate.ORG Server - 
http://www.mailgate.org


cicc...@iol.it
Effettivamente questo problemino mi ricorda tantissime ore in classe, ai bei
tempi delle superiori, passate a cercare di ingannare il tempo. Per quanto
mi riguarda puoi anche prendere i voti. Per ora accontentati di un indizio:
dividendo la matrice in quattro settori 5x5 in questo modo:
1   2
4   3
puoi risolvere in sottoprobelma con il seguente vincolo:
x  x  x  x  x
x  x  x  x  x
x  x  x  x  x
x  a  x  b x
x  x  x  x  x
dove "a" e "b" sono rispettivamente il primo e ultimo numero di quel settore
(i.e. nel primo settore, in alto a sinistra, saranno 1 e 25).
Come puoi vedere, è sempre possibile passare dalla "b" di un settore alla
"a" del successivo proseguendo in senso orario, e le soluzioni si ripetono
sempre uguali, tenendo presente che passando dal 2° al 3° settore la
soluzione sarà la simmetrica della precedente.
Prova a risolvere il problema ridotto, una semplice strategia di forza bruta
(backtrack) dovrebbe essere più che sufficiente. Se poi vorrai, ti invierò
la soluzione completa.
Ciao ciao.
    Andrea
~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
Contro la disinformazione, la superstizione e l'analfabetismo
                  matematico e scientifico in Italia.
http://www.valnet.it/cicap
¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤¤

 una nera puoi passare solo su altre caselle nere e ... non ti fai prete :-)
Paolo, ti ricordi??
questo problema piuttosto noto e' passato gia' un paio di volte.
Come dice Andrea considerando per primo un settore 5*5, diventa di
facile soluzione.
Ho ripescato una risposta data a suo tempo:
Utilizzando un metodo descritto per la prima volta da Eulero, e'
possibile saturare facilmente il quadrato 5x5, e poi derivare altre
soluzioni con le caselle di partenza e di arrivo in altre posizioni.
Questo permette di saturare il 10*10 utilizzando slittamenti o
riflessioni del 5*5 originario.
Ecco alcuni esempi:
-   -   -   -   -   -   -   -   -   -
-   -   -   -   -   -   -   -   -   -
-   -   -  75   -   -  76   -   -   -
-  51   -   -   -   -   -   -  100  -
-   -   -   -   -   -   -   -   -   -
-   -   -   -   -  3   16   11  4  19
-   -  50   -   -  22  6     1  23  9
-   -   -  26   -  14  25   20  15 12
-   -   -   -   -   2  17   10   5 18
-   -   -   -   -  21   7   13  24  8
Per i seguenti 5*5 vale lo stesso principio:
16  21  10  15  20
 1  16   6   11  17
21  13   3   20  23
 5  10  25   15   7
 2  19  22   12  18
 14   1   7   15    2
 25  11  19   22    5
 8   16   3   9    17
 13  21   6   12   20
 24  10  18   23    4
.... ne puoi trovare parecchi altri.
dario

Non solo l'ho risolto, ma ho anche scritto un algoritmo per
risolverlo! Lo trovate all'indirizzo:
http://www.geocities.com/Athens/Delphi/3636/mass.htm
P.S. Il metodo č quello di scegliere la casella che ha il MAGGIOR
(non il minore) numero di sbocchi!
Mariano Tomatis

 Mariano Tomatis
Ho scaricato il programma.
Come da richiesta, invio una mail di ringraziamento, assolutamente
doverosa.
Funziona benissimo
Restano aperti due quesiti.
1) Sebbene sia assolutamente evidente che dal 5 x 5 in poi il problema
e' sempre
risolubile, esiste una dimostrazione formale?
2) Su quali scacchiere rettangolari e' risolubile? Credo tutte quelle
che contengono
la 5 x 5; quindi il problema resta aperto per le 4 x n. Qualcuno ne sa
qualcosa?
Non ho avuto difficolta' con la 4 x 5:
  1  4   7  10  3
15 12 19 16 13
  6  9   2   5   8
20 17 14 11 18
La 4 x 6 e' appena piu' difficile.
Mi sembra probabile che lo schema si possa estendere.
Grazie e ciao
Mauro

