Newsgroup: it.hobby.enigmi
Titolo: closed tour

Prendiamo una scacchiera quadrata NxN ed una torre (intesa come pezzo degli
scacchi), non è difficile trovare (per N pari) un giro della scacchiera
fatto dalla torre in modo che questa passi una ed una sola volta per tutte
le N^2 caselle e torni al punto di partenza (chiamiamolo "closed tour").
Consideriamo ora una scacchiera 3x3, eliminando una casella opportuna è
univocamente determinato un closed tour da parte della torre, per esempio:
 (X indica la casella eliminata)
 _ _ _
|X|2|3|
|8|1|4|
|7|6|5|
Per la scacchiera 4x4, per determinare un univoco closed tour, dobbiamo
eliminare almeno 2 caselle, per esempio nel modo seguente:
 _ _ _ _
|X|_|_|X|
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
Quante caselle dobbiamo eliminare, al minimo, da una scacchiera NxN per
determinare in maniera univoca un closed tour di una torre?
Si potrebbe cominciare ad analizzare per N piccoli, 5-6-7...
GaS

Forse ho capito male io, ma per una 4x4 esiste un closed tour che tocca
tutte le 16 caselle:
01 16 15 14
02 07 08 13
03 06 09 12
04 05 10 11
Ste

"Stefano Bragaglia" wrote:

Si, certo, ma non è unico. Quello che cercavo era questo: tolgo p caselle da
una scacchiera NxN in modo che sia possibile un *unico* closed tour (nella
4x4 tutta intera avremo molte altre possibilità). Qual è il più piccolo p
per N=5,6,7,8....?
Spero di essermi spiegato,
GaS

Ok, adesso ho capito...
Permettimi solo di aggiungere che si deve tener conto delle simmetrie...
cioè nel caso 3x3 la casella tolta può essere una qualsiasi delle 4
angolari... nel caso 4x4 si possono togliere le due caselle esterne di ogni
lato, ecc...
secondo me se si "allarga" la scacchiera, si allarga lo spazio percorribile
in tanti modi diversi... quindi diventa sempre più grande il bisogno di
togliere caselle...
il problema è fortemente esponenziale... occorre trovare un "metodo" perchè
non è possibile andare per tentativi quando la complessità diventa
abbastanza grande!
Ste

 abbastanza grande!
Sinceramente non ho nessun metodo generale, non penso che esista. Infatti
chiedevo di analizzare  valori bassi di N (5, 6, 7, 8....), chi lo fa si
ritroverà una bella sorpresa :o)
Allora? Neanche una soluzione per la facilissima 5x5? E la 6x6?
Ciao,
GaS

Se tieni conto delle simmetrie fai meno fatica: una volta che trovi una
soluzione aggiungi all'insieme delle soluzioni anche le sue equivalenti cosě
non ci si sforza a doverle trovare ancora...
A parole non vuol dire niente, ma se lo intendi nel contesto di un programma
semplifica la vita! Questo accorgimento potrebbe in linea teorica accelerare
di 4 volte il tempo richiesto dall'algoritmo per ottenere la risposta...
Lo so, sono considerazioni un po' cosě... ma il problema che proponi č
troppo oneroso per me! ;)
Ciao,
  Ste

 troppo oneroso per me! ;)
Ma guarda che per N=5,6 č abbastanza facile. Neanche un tentivo di sorta?
Non c'č bisogno di computer, a mano si riesce a fare.
GaS

 Si potrebbe cominciare ad analizzare per N piccoli, 5-6-7...
N = 5
   _ _ _ _ _    _ _ _ _ _    _ _ _ _ _
  |_|_|X|_|_|  |_|_|X|_|_|  |_|_|X|_|_|
  |_|_|X|_|_|  |_|_|X|_|_|  |_|_|_|_|_|
  |_|_|X|_|_|  |_|_|_|_|_|  |_|_|_|_|_|
  |_|_|_|_|_|  |_|_|_|_|_|  |_|X|X|_|_|
  |_|_|_|_|_|  |_|_|X|_|_|  |_|_|_|_|_|
N = 6
   _ _ _ _ _ _
  |_|_|X|_|_|_|
  |_|_|_|_|_|_|
  |_|_|_|_|_|_|
  |_|_|X|_|_|_|
  |_|_|_|_|X|_|
  |_|_|X|_|_|_|
        Mauro

 N = 6
[cut]
Bravo Mauro, si comincia a muovere qualche cosa.
Proviamo a ricapitolare, sia N la dimensione della scacchiera e p il numero
minimo di caselle da togliere:
N  |  p
---|----
2  |  0
3  |  1
4  |  2
5  |  3
6  |  4
.. | ...
Qualcuno vuole provare a continuare? ;-)
Notiamo intanto che, sicuramente, N e p devono avere la stessa parita.
Gabriele