Dovete riempire una matrice 5×5 con i numeri da 1 a 25, seguendo però una regola ben specifica: tranne 1 e 2 per ovvie ragioni, ciascun numero è la somma di due tra i suoi “vicini” (valgono anche quelli in diagonale: quindi una casella che non sta sui lati ha otto vicini. I numeri da 1 a 9 e quelli da 20 a 25 sono stati posizionati. Riuscite a mettere gli altri 10?
(un aiutino lo trovate sul mio sito, alla pagina http://xmau.com/quizzini/p447.html; la risposta verrà postata lì il prossimo mercoledì. Problema tratto da Math StackExchange.)
A me la sequenza di numeri è venuta in questo modo: 16 e 17 obbligatori, 10\12 in alternativa, poi 14 (e a questo punto 12 e 10), poi 15 e solo a quel punto 11. Di conseguenza non sono riuscito a sfruttare l’aiutino.
La tabella? Per righe orizzontali:
19 11 15 20 21
13 06 05 04 17
23 07 01 03 14
16 09 08 02 12
25 24 18 10 22
Bello!
raramente c’è un unico modo per risolvere un problema: l’aiutino è come l’ho fatto io :-)
Effettivamente il grado di libertà che viene concesso potrebbe lasciare spazio a più soluzioni; mentre ci provavo, e prima di leggere l’aiutino, avevo notato subito le posizioni obbligate per i primi numeri, e di seguito ho completato le caselle con le, poche, combinazioni accettabili, ma una volta trovata quella risolutiva non ho approfondito quante altre fossero disponibili :-)
Con quella trovata, i primi e gli ultimi quattro numeri della griglia sono, rispettivamente,
19 – 18 – 15 – 20 – …
e
… – 24 – 11 – 10 – 22
(facendo il confronto con la soluzione già pubblicata, sembra che lo scambio tra 11 e 18 sia l’unica variante visibile).
Ok, ritratto tutto :-) l’11 in alto e il 18 in basso, come nella soluzione già pubblicata, altrimenti il 15 non può essere generato correttamente.
Scrivere a matita, senza usare la gomma, può dare qualche inconveniente nel trascrivere i risultati, sorry…
Sembra che ci sia un’unica soluzione, quella postata.
Almeno, il PC non ne trova altre :) .
perdona la curiosità di un ignorantone in materia (che sarei io): come si procede a programmare il pc per la soluzione di un problema come questo?
in un caso come questo, dove ci sono 10 numeri e quindi qualche decina di milioni di combinazioni possibili, io sarei pigro e userei la forza bruta.
In generale si usano algoritmi di backtracking, In pratica si prova a mettere ordinatamente i numeri, e quando ci si accorge di essere arrivati a un vicolo cieco si ritorna indietro.
Anch’io ho usato semplice forza bruta.
Gia’ ho faticato cosi’ … a scrivere lo script, dico. ;)
Dopo aver inserito 16,17,10,12 restano solo 6 caselle da riempire.
Per cui ho fatto verificare in sequenza tutte le possibilita’.
Prima calcolo tutte le permutazioni dei 6 numeri.
Poi per ogni permutazione inserisco i 6 numeri 6 numeri inseriti, cercando una eventuale coppia di numeri vicini compatibile.
Scusate … alla fine doveva essere:
Per ogni permutazione inserisco i 6 numeri e per ognuno cerco una coppia di numeri vicini adatta, esaminando tutte le coppie di numeri vicini.
Se non trovo i numeri vicini adatti, passo alla prossima permutazione dei 6 numeri.
Se troviamo la coppia di numeri vicini per tutti e 6 i numeri inseriti, abbiamo una soluzione.
… E pare che ce ne sia solo una. :)
Mah … Credevo di aver trovato delle posizioni obbligate per 10 e 12.
Ma pare non sia cosi’.
Ho provato a cercare le soluzioni senza aver inserito 10 e 12.
Ed e’ venuta fuori un’altra soluzione:
19 11 15 20 21
13 06 05 04 17
23 07 01 03 18
16 09 08 02 14
25 24 10 12 22
Sempre se non ci sono errori
Infatti c’e’ un errore.
Come non detto.