Newsgroup: it.hobby.enigmi
Titolo: "closed tour" il ritorno

Il gioco dell "full board" (bello!) mi ha fatto tornare in mente un gioco
che ho proposto più di un anno addietro:
---------------------------------------------------
Prendiamo una scacchiera quadrata NxN ed una torre, non è difficile trovare
(per N pari) un giro della scacchiera in modo che la torre passi una ed una 
sola volta per tutte
le N^2 caselle e torni al punto di partenza. Pare che gli anglofoni lo
chiamino "closed tour".
Consideriamo ora una scacchiera  3x3, eliminando una casella opportuna è
univocamente determinato un closed tour da parte della torre, per esempio:
(X rappresenta la casella eliminata)
 _ _ _
|X|2|3|
|8|1|4|
|7|6|5|
(in realtà, in questo caso, si poteva levare una qualsiasi casella ma non
divaghiamo troppo...)
Nella scacchiera  4x4, per determinare un univoco closed tour, dobbiamo
eliminare almeno 2 caselle, per esempio nel modo seguente:
 _ _ _ _
|X|_|_|X|
|_|_|_|_|
|_|_|_|_|
|_|_|_|_|
(ma esistono anche altre possibilità)
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...
------------------------------------------
Solo Mauro Casini propose delle soluzioni per N=5,6:
N = 5
   _ _ _ _ _    _ _ _ _ _    _ _ _ _ _
  |_|_|X|_|_|  |_|_|X|_|_|  |_|_|X|_|_|
  |_|_|X|_|_|  |_|_|X|_|_|  |_|_|_|_|_|
  |_|_|X|_|_|  |_|_|_|_|_|  |_|_|_|_|_|
  |_|_|_|_|_|  |_|_|_|_|_|  |_|X|X|_|_|
  |_|_|_|_|_|  |_|_|X|_|_|  |_|_|_|_|_|
N = 6
   _ _ _ _ _ _
  |_|_|X|_|_|_|
  |_|_|_|_|_|_|
  |_|_|_|_|_|_|
  |_|_|X|_|_|_|
  |_|_|_|_|X|_|
  |_|_|X|_|_|_|
Si potrebbe provare ora, a distanza di 16 mesi, ad estendere un po' i
risultati, sopratutto perchè,
udite udite!, il numero di caselle da togliere NON è sempre crescente con
N....
Chi mi trova qualche risultato per N=7,8,9 ?
Ciao,
GaS 

 divaghiamo troppo...)
E come fai se la casella eliminata
sta al centro di un lato?

   |_|_|X|_|_|_|
Non ho purtroppo molto tempo da dedicare allo svago...
Per quel che riguarda N=5 e N=6 ci sono anche
altre configurazioni oltre a quelle riportate sopra (salvo miei errori,
ovviamente), ad esempio, per N=5
   1  2 **  8  9
  22  3  6  7 10
  21  4  5 ** 11
  20 ** 16 15 12
  19 18 17 14 13
  **  1  2  5  6
  21 22  3  4  7
  20 19 **  9  8
  17 18 ** 10 11
  16 15 14 13 12
   1  2  3  6  7
  22 **  4  5  8
  21 20 ** **  9
  18 19 14 13 10
  17 16 15 12 11
e per N=6
   1  2  5  6  7  8
  32  3  4 11 10  9
  31 30 ** 12 13 **
  ** 29 28 ** 14 15
  25 26 27 20 19 16
  24 23 22 21 18 17
   1  2  3  6  7 **
  32 **  4  5  8  9
  31 24 23 20 19 10
  30 25 22 21 18 11
  29 26 ** 16 17 12
  28 27 ** 15 14 13
   1  2  3 ** 13 14
  32  5  4 11 12 15
  31  6  9 10 17 16
  30  7  8 ** 18 19
  29 28 ** 24 23 20
  ** 27 26 25 22 21
   1  2  3  4  5  6
  32 29 28 27 **  7
  31 30 25 26  9  8
  ** 23 24 ** 10 11
  21 22 17 16 13 12
  20 19 18 15 14 **
   1  2  3 ** 15 16
  32  5  4 ** 14 17
  31  6  9 10 13 18
  30  7  8 11 12 19
  29 28 25 24 21 20
  ** 27 26 23 22 **
Per N = 7 ho trovato questa con 7 ostruzioni
   1  2  5  6  7  8  9
  42  3  4 13 12 11 10
  41 40 ** 14 15 ** **
  ** 39 ** 17 16 25 26
  37 38 19 18 ** 24 27
  36 35 20 21 22 23 28
  ** 34 33 32 31 30 29
Piu' in la' non mi spingo.
Sotto ricopio un mio programmino in C veramente naive che puo' servire a 
controllare configurazioni piccole, diciamo max 7x7. Gli si devono 
passare sulla linea di comando le dimensioni (righe e  colonne) e le 
posizioni delle ostruzioni (numerate a partire da 0).
Per esempio se gli passo:  7 5 4 12 19
vuol dire 7 righe e 5 colonne e ostruzioni nelle posizioni 4, 12 e 19.
E mi stampa, per esempio,
   1 32 29 28 **
   2 31 30 27 26
   3  4 ** 24 25
   6  5 22 23 **
   7 20 21 16 15
   8 19 18 17 14
   9 10 11 12 13
Non so se a qualcuno puo' interessare per fare qualche prova, comunque 
ve lo copio sotto, visto che e' abbastanza breve, 40 linee.
(Il programma non fa controlli sulla correttezza dell'input e non va
assolutamente preso come esempio di come si deve programmare!!)
Ciao,
g.
#include<stdio.h>
#include<stdlib.h>
int N, M, nC, MN, *Q, *Flg, *Seq, *J;
void Vai(int x, int cnt)
{
   int i, y=x>>2;
   if ((Seq[y]=++cnt)==nC &&!(J[x]&&J[x+1]&&J[x+2]&&J[x+3]))
   { for (i=0; i<MN; i++)
    { if (Q[i]<0) printf(" **");  else printf(" %2d",Seq[Q[i]]);
      if ((i%N)==(N-1))printf("\n");  }
      printf("\n");
   } else {
   Flg[y]=1;
   for (i=0;i<4 && J[x+i]>=0; i++) if (!Flg[J[x+i]]) Vai(J[x+i]<<2,cnt);
   Flg[y]=0; }
}
int main(int argc, char *argv[])
{
   int i,m;
   M=atoi(argv[1]); N=atoi(argv[2]); MN=M*N;
   Q=calloc(MN,sizeof(int));
   Flg=calloc(MN,sizeof(int));
   Seq=calloc(MN+1,sizeof(int));
   for (i=3; i<argc; i++) Q[atoi(argv[i])]= -1;
   for (nC=i=0; i<MN; i++) if(Q[i]==0) Q[i]=nC++;
   J=calloc(MN<<2,sizeof(int));
   for (i=0; i<MN; i++)
    if ((m=Q[i])>=0)
     { m<<=2; J[m]=J[m+1]=J[m+2]=J[m+3]=-1;
       if ((i%N) && Q[i-1]>=0) J[m++]=Q[i-1];
       if (((i+1)%N) && Q[i+1]>=0) J[m++]=Q[i+1];
       if (i>=N && Q[i-N]>=0) J[m++]=Q[i-N];
       if (i<(MN-N) && Q[i+N]>=0) J[m++]=Q[i+N];
     }
   Vai(0,0);
   return 0;
}


Svista madornale, in origine avevo fatto una considerazione più lunga sulla 
parità delle caselle, poi però allungavo troppo il discorso e così ho tolto 
(quasi) tutto. Quella frase lasciata così risulta così completamente 
sbagliata.
Scusate,
GaS 

 controllare configurazioni piccole, diciamo max 7x7.
Interessante il programmino ma la parte interessante arriva sulla 8x8 :o)
Ciao,
GaS 

 Si puň fare di meglio...
5 ostruzioni
   1  2  3  4  5  6  7
  44 41 40 39 **  9  8
  43 42 ** 38 11 10 **
  ** 33 34 37 12 15 16
  31 32 35 36 13 14 17
  30 27 26 23 22 19 18
  29 28 25 24 21 20 **
ciao,
g.

 5 ostruzioni
Ciao Giovanni, ottima soluzione.
Quindi per N=7 abbiamo trovato una soluzione in cui servono 5 ostruzioni per 
definire univocamente un percorso.
Indovinate quante caselle bisogna togliere per definire un percorso unico 
nel caso di N=8?
:o)
Ciao,
GaS