Ecco il problema, posto solo con un disegno, senza parole.
- Problema irrisolto 7.png (15.57 KiB) Visto 48243 volte
La soluzione è più avanti.
- Visitare caselle 5x5.png (10.9 KiB) Visto 48243 volte
La soluzione è solo una traccia di un possibile percorso.
Il 2 e il 5 non hanno soluzione, tutti gli altri punti di partenza di ottengono per simmetria e rotazione
7. Domande in cerca di risposta
Il problema ha sempre soluzione per n pari?
La risposta è sì.
Prendiamo il caso 2x2 la cui soluzione è banale e aggiungiamo un bordo 2 su due lati, sarà sempre possibile visitare tutte le caselle del bordo terminando sull'esterno
.
- Visitare caselle 4x4.png (5.88 KiB) Visto 48243 volte
con lo stesso sistema possiamo passare a 6x6, 8x8 e così via.
Dato uno schema 2nx2n e una posizione di partenza, sarà possibile individuare un nucleo 2x2 da espandere a 4x4, 6x6, ecc... fino all'angolo più vicino e poi completare tutto lo schema
.
- Visitare caselle 6x6.png (23 KiB) Visto 48243 volte
Gli schemi con lato dispari sono risolvibili solo per alcuni punti di partenza, cioè quelli con riga e colonna pari o riga e colonna dispari (le caselle bianche nell'immagine)
Questo perché lo schema 3x3 ha soluzioni solo per le partenze sulle diagonali e questo difetto si propaga in tutti gli schemi con lato dispari
.
- Visitare caselle scacchi.png (6.08 KiB) Visto 48243 volte
Se la griglia, fosse rettangolare anziché quadrata?
A intiuto direi che se il lato minore è pari, tutti i punti di partenza hanno soluzione, se il lato minore è dispari solo alcuni punti di partenza hanno soluzione (come per i quadrati con lato dispari)
Ci devo ancora lavorare
Aggiornamento:
Tutte le griglie che abbiano un lato pari sono risolvibili per ogni partenza, questo risponde anche alla domanda precedente (senza scomodare l'induzione)
Una tecnica semplice è la seguente:
1. dal punto di partenza raggiungere il lato pari più vicino
2. dirigersi verso l'altro lato dalla parte dove le caselle sono dispari
3. muoversi a serpentina tra il bordo e la casella di partenza inclusa
4. tornare indietro nello setsso modo e completare lo schema
Vediamo il caso 6x5
.
- Visitare caselle 6x5.png (12.55 KiB) Visto 48239 volte
Tutte le griglie che hanno entrambi i lati dispari sono risolvibili solo per partenze "a scacchiera", cioè riga e colonna dispari (1,1; 1,3; 3,3; ecc...) o pari (2,2; 2,4; 4,4; ecc...)
Vediamo il caso 7x5
.
- Visitare caselle 7x5.png (54.47 KiB) Visto 48236 volte