Newsgroup: it.hobby.enigmi
Titolo: Ne resta una

12 pedine numerate da 1 a 12, sono poste in circolo nel loro ordine 
naturale, come su un quadrante dell'orologio:
              12
           11    1
         10        2
         9          3
          8        4
            7    5
               6
Una mossa consiste nel sollevare una pedina e di spostarla in senso 
orario di tanti spazi quanti ne indica il suo valore, all'arrivo la 
pedina che ha effettuato la mossa, sostituisce quella nella casella di 
arrivo, che viene tolta dal gioco.
Se ad es. muovo la pedina 5, questa andrà a sostituire la pedina 10, 
lasciando questa situazione:
              12
           11    1
          5        2
         9          3
          8        4
            7    x
               6
Se ora muovessi la 3 mi troverei cosi' :
              12
           11    1
          5        2
         9          x
          8        4
            7    x
               3
Lo scopo è quello di rimanere con una sola pedina dopo 11 mosse.
ciao.

Il 04-10-2007, Dario Uri dice:







spoiler
Gioco la 11 per 11 volte e finisce da sola a mezzogiorno.
-- 
Saluti, Dalet

Dalet ha scritto:

anche la uno, se è per questo.

carmine ha scritto:

e anche la 5 e la 7

 
Naturalmente c'e' un'altra clausola:
Non e' possibile muovere la stessa pedina per 2 volte consecutivamente !

>spoiler


Anche la 5 e allora anche la 7... basta che non siano
divisori mi sembra.
-- 
Saluti, Dalet

 
infatti, l'avevo detto 4 minuti fa.

 Non e' possibile muovere la stessa pedina per 2 volte consecutivamente !
Arrivo a 12 mosse: 6,5,7,5,7,5,7,5,7,5,6,7
Ciao Dario!!!  :o)
Livio

 
Ciaooo Livio,
ci sei quasi !
Ne ho una sola in 11 e vorrei sapere se ne esistono altre.

Non e' possibile muovere la stessa pedina per 2 volte consecutivamente !
spoiler
 1- 2
 7- 2
 5-10
11-10
 7- 9
11- 9
 3- 6
 4- 8
 3- 9
 4-12
 3-12
-- 
Saluti, Dalet

Ne ho una sola in 11 e vorrei sapere se ne esistono altre.
M'e' sembrato obbligato perche' dal posto 9 non ho trovato
altro modo di toglierla che col 3.
L'arrivo e' infatto 1/2 obbligato: 6-12, 5-12, 4-12, 3-12
e allora a causa del 9 i 5,6 devono invece morire altrove.
-- 
Saluti, Dalet

 e allora a causa del 9 i 5,6 devono invece morire altrove
Ottimo!
Io avevo la sol. sotto che č essenzialmente la stessa.
Ciao
Spoiler
8,3,5,1,11,7,11,7,3,8,3.

8,3,5,1,11,7,11,7,3,8,3.
 1,7,5,11,7,11,3,4,3,4,3
voglio dire che da te l'8 si mangia il 4 e da me invece
il contrario.
Diverso sarebbe fare inversioni di tempi e mi sembra che
ce ne sia piu' d'una possibile.
-- 
Saluti, Dalet

Io avevo la sol. sotto che è essenzialmente la stessa.
Il mio PC, dopo 20 secondi di lavoro (e 2 ore di messa a punto),
sostiene che le soluzioni possibili sono 1816, e hanno tutte le
seguente particolarità:
- Non viene mai spostato il 12 (ovvio)
- Nessuna soluzione inizia con 2 o 6 o 10
- L'ultimo numero rimasto é sempre o 3 o 4 o 8 o 9 e rimane sempre
nella posizione delle ore 12.
A titolo di esempio vi trascrivo la prima e l'ultima soluzione trovata
(se volete le posto tutte):
1,3,4,5,7,11,7,11,3,4,3
,,,,,,
11,9,8,7,5,1,5,1,9,8,9
Ciao a tutti
-- 
Dano  

11,9,8,7,5,1,5,1,9,8,9
Complimenti! e non avrei mai pensato tante!
Hai postato proprio quelle col 5 e il 9 che si muovono,
che m'era sembrato di dover escludere... ma toglimi una
curiosita': c'entra con le classi resto il programma? perche'
avevo cominciato col pensarci, ma poi ho preferito tirare
avanti col brute force.
-- 
Saluti, Dalet

 11,9,8,7,5,1,5,1,9,8,9
Grande!
Se hai voglia di visitare il mio monitor con le tue soluzioni te ne 
sarei grato. grazie ciao.
dario

sarei grato. grazie ciao.
Ti ho inviato tutte le soluzioni al tuo indirizzo di posta.
Adesso però rilancio con un allargamento del problema.
Avendo N pedine numerate poste in circolo, per quali valori di N é
possibile trovare soluzioni con N-1 mosse?
Naturalmente N=2 é banale e scontato.
Ciao
-- 
Dano

avanti col brute force.
Ho usato la forza bruta con un po' di intelligenza usando la tecnica
del backtrace (se una strada é senza soluzione torno indietro di un
passo e provo una strada alternativa). 
In piů ho impostato il vincolo che quando sposto un numero questo deve
finire su una posizione occupata da un altro numero; questo permette
di trovare solo le soluzioni con 11 mosse.
Il programma é scritto in C; se interessa Te lo posso inviare.
Ciao
-- 
Dano

Il programma é scritto in C; se interessa Te lo posso inviare.
Si' grazie! e potresti postarlo se ti va direttamente qui?
tanto e' ascii.
-- 
Saluti, Dalet

tanto e' ascii.
Ti ho inviato il programma via email.
Per il momento preferisco non inviarlo qui perché sarebbe come dare la
soluzione alla generalizzazione che ho proposto :-))))
Ciao
-- 
Dano

Il 07-10-2007, Dano dice:



Ti ringrazio ma devi scusarmi che non son stato chiaro, ma
l'indirizzo email non va. Aspetto dopo la generalizzazione.
-- 
Saluti, Dalet

Naturalmente N=2 é banale e scontato.
Mi rispondo da solo perche mi sembra che nessuno abbia avuto tempo o
voglia da dedicare al problema.
In effetti cercare delle soluzioni senza l'uso di un qualche software
può risultare frustrante dato che non é facile trovare soluzioni e non
si sa nemmeno se ne esiste almeno una.
Lascio comunque un piccolo spoiler per chi volesse continuare in
proprio la ricerca.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
Quando con il mio PC ho provato a cercare soluzioni su un diverso
numero di pedine pensavo di trovarne parecchie su vari numeri, ma mi
sono dovuto ricredere.
Con il PC ho fatto la scansione completa finoa N = 18 e già con questo
valore sono necessarie più di 8 ore di tempo macchina, con N = 19 ho
stimato potrebbe essere necessario almeno un mese e ho rinunciati.
Gli unici valori che hanno soluzioni sono:
N =  2 ->    1 soluzione
N = 12 -> 1816 soluzioni
N = 15 -> 5504 soluzioni
Per il caso N = 15 riporto alcune delle soluzioni trovate (le prime e
le ultime:
1,4,1,4,11,14,11,9,14,9,5,9,5,9
1,4,1,4,11,14,11,9,14,9,10,9,10,9
1,4,1,4,14,11,14,6,11,6,5,6,5,6
1,4,1,4,14,11,14,6,11,6,10,6,10,6
1,4,1,11,4,11,14,9,14,9,5,9,5,9
.......
.......
14,11,14,4,11,4,1,6,1,6,10,6,10,6
14,11,14,11,1,4,1,9,4,9,5,9,5,9
14,11,14,11,1,4,1,9,4,9,10,9,10,9
14,11,14,11,4,1,4,6,1,6,5,6,5,6
14,11,14,11,4,1,4,6,1,6,10,6,10,6
Per chi fosse interessato posso inviare un file con tutte le
soluzioni.
Per soddisfare anche la richiesta di Dalet riporto in fondo il listato
del programma in C che ho utilizzato per la ricerca (compilato con
LCC).
Per proseguire la ricerca é necessario trovare qualche altra
scorciatoria che consenta di risurre i tempi di calcolo o meglio
determinare in modo analitico per quali valori esistono soluzioni.
Ciao, Dano
Ecco il listato; purtroppo le righe verranno spezzate in modo
disordinato, ma dopo un copia/incolla potranno essere ricostruite
facilmente.
Modificando il parametro PEDINE (ora fissato a 12) possono essere
scansionati tutti gli altri valori.
/*---------------------------------------------------------------------------*/
/* header files */
#include <stdlib.h>
#include <stdio.h>
#include <conio.h>
/*---------------------------------------------------------------------------*/
#define  VERO         (0 == 0)
#define  FALSO           !VERO
#define  PEDINE             12    /* Modificare secondo le pedine   */
/*---------------------------------------------------------------------------*/
/*     variabili globali */
int            schema[PEDINE][PEDINE+1];   /* Disposizione dei numeri
*/
unsigned long  num = 0;                    /* numero delle soluzioni
*/
FILE          *file;                       /* puntatore al file */
/*---------------------------------------------------------------------------*/
/*     prototipi di funzione */
void stampa   (void );
int  mossa    (int  );
void mostra   (void );
void fatal    (int  );
/*---------------------------------------------------------------------------*/
int main (void)
{
  int j, i = 0;
  char  nome[32];
  for(j = 0; j <= PEDINE ; ++j)
    schema[0][j] = j;
  sprintf(nome, "PEDINE_%02d.TXT", PEDINE);
  if ((file = fopen(nome,"wt")) == NULL) fatal(1);
  while(i >= 0)
  {
    if(mossa(i))                       /* Eseguo la mossa i-esima */
      ++i;                             /* se trovata passo alla
successiva     */
    else
      --i;                             /* se non trovata torno alla
precedente */
  }
  if (fclose(file) == EOF) fatal(1);
  return(0);
}
/*---------------------------------------------------------------------------*/
int mossa(int s)
{
  int i, j, k;
  i = schema[s][0];                    /* i e' uguale alla base per la
ricerca della mossa   */
  k = (s == 0) ? 0 : schema[s-1][schema[s-1][0]];   /* mossa fatta al
passo precedente       */
  while(VERO)
  {                                    /* ricerca una posizione nella
quale c'e' un numero   */
    do
      if(++i > PEDINE) return(FALSO);  /* se arriva alla fine ritorna
il FALSO               */
    while(schema[s][i] == 0 || schema[s][i] == k);
                                       /* il numero deve essere
diverso da 0 e diverso dalla */
                                       /* mossa precedente */
    j = schema[s][i] + i;              /* calcola la nuova posizione
*/
    if(j > PEDINE) j -= PEDINE;
    if(i != j && schema[s][j] != 0)    /* se la nuova posizione e'
vuota ne cerca un'altra   */
    {
      schema[s][0] = i;                /* se  no scrive nella
posizione 0 la mossa da fare   */
      if(s == PEDINE-2)                /* se e' OK controlle se e'
l'ultimo schema           */
      {
        stampa();                      /* ed esegue la stampa su file
della soluzione        */
        continue;                      /* poi continua la ricerca */
      }
      break;
    }
  }
  for(k = 1; k <= PEDINE ; ++k)      /* esegue la mossa scrivendo la
nuova situazione        */
    schema[s+1][k] = schema[s][k];   /* nello schema successivo s+i */
  schema[s+1][j] = schema[s+1][i];   /* scrive nella nuova posizione
il valore della vecchia */
  schema[s+1][i] = 0;                /* mette a zero la veccchia
posizione                   */
  schema[s+1][0] = 0;                /* mette a zero la mossa del
nuovo schema               */
  return(VERO);
}
/*---------------------------------------------------------------------------*/
void stampa(void)
{
  int i;
  ++num;
  for(i = 0; i < PEDINE-1; ++i)
    fprintf(file, "%d%c", schema[i][schema[i][0]], (i == PEDINE-2) ?
'\n' : ',');
 mostra();
}
/*---------------------------------------------------------------------------*/
void mostra(void)
{
  int i,j;
  gotoxy(1,1);
  printf("Soluzione %lu\n\n", num);
  printf("   ");
  for(j = 1; j <= PEDINE; ++j)
    printf("%2d ", j);
  printf("\n  ");
  for(j = 1; j <= PEDINE; ++j)
    printf(" --");
  printf("\n");
  for(i = 0; i < PEDINE-1; ++i)
  {
    printf("%2d|", i);
    for(j = 1; j <= PEDINE; ++j)
      printf("%2d ", schema[i][j]);
    printf(" Muovo %2d (%2d)\n", schema[i][0],
schema[i][schema[i][0]]);
  }
}
/*---------------------------------------------------------------------------*/
void fatal(int n)
{
  fprintf(stderr,"Errore accesso al file PEDINE.TXT\n");
  exit(1);
}

LCC).
TNX!! mo' me lo compilo, ma devo toglierci conio.h che
sono con Linux.
-- 
Saluti, Dalet