Newsgroup: it.hobby.enigmi
Titolo: [MA] Solitario generalizzato

Sopra una scacchiera MxN sono collocate MN pedine, una per casella.
Elimino una qualsiasi pedina, poi gioco al classico solitario.
Una mossa consiste in una "mangiata"; una pedina ne salta un'altra 
finendo nella casella vuota al di la' della pedina saltata che viene 
eliminata. I salti sono permessi solo ortogonalmente.
Lo scopo e' di rimanere con una sola pedina.
La scelta della prima casella vuota non e' banale, difatti non tutte le 
posizioni portano ad una possibile soluzione.
Quando una soluzione e' possibile, il gioco puo' terminare con l'ultima 
pedina su diverse caselle ,ma non tutte sono possibili.
Quali sono le leggi che governano questi solitari?
Un esempio di gioco su scacchiera 4x3:
01 02 03 04
05 06 07 08
09 10 11 12
Inizio con la casella 01 vuota.
3,1 - 11,3 - 4,2 - 9,11 - 5,7 - 1,3 - 12,4,2 - 11,3 - 2,4.
Come si vede la 01, puo' essere una casella di partenza (CP)
e la 04 puo' essere una casella di arrivo (CA).
Non e' possibile ed es. terminare nella casella 10.

 Quali sono le leggi che governano questi solitari?
Ho provato, senza successo, a definire una condizione sufficiente di 
impossibilità di una particolare configurazione. Vediamo cosa ho provato a 
fare, magari qualcuno prende spunto e ci riesce.
Sono partito cercando una colorazione di due colori della scacchiera in 
maniera tale che, ponendo un numero pari su un colore ed uno dispari 
sull'altro, ogni mossa lasciasse invariata la parità totale. Purtroppo 
niente da fare ma mi sono reso conto che occorrono tre *colori diversi*.
La configurazione più utile mi sembra quella a scacchiera:
ABCABCABC...
BCABCABCA...
CABCABCAB...
............
Non è scelta a caso, quello che succede è che due caselle che distano 3 sono 
*equivalenti* (nel senso che si mostrerà tra poco) tra di loro.
Ho provato, poi, ad assegnare ad ogni colore (lettera) un diverso valore in 
modo tale che ogni mossa lasci invariata una qualche proprietà globale, 
chiamiamola PG, sul prodotto dei valori di ogni casella. Per esempio la PG 
potrebbe essere la parità o il fatto di essere multiplo di qualcosa +/- 
qualcos'altro.
Per far questo, rispetto alla PG, devono essere equivalenti A^2, B^2, C^2 e 
ABC.
Ma, arrivato fin qua, non so proprio come proseguire, comunque ho il 
sospetto che potrebbe essere utile associare numeri complessi ad ogni 
casella.
Qualcuno ha altre idee? Riesce a sviluppare i miei due centesimi?
Approfitto per fare (in ritardo, lo so) gli auguri di Buon Natale a tutti 
voi.
Per compensare faccio gli auguri di Buon Anno in anticipo :o)
(3 giorni di ritardo e 3 di anticipo mi sembra che nessuno si possa 
lamentare :o)
Ciao,
Gabriele 

 e ABC.
O meglio devono essere equivalenti A con BC, B con AC e C con AB.
Pensavo che queste condizioni fossero strettamente incluse nelle precedenti 
ma mi sono accorto che non è cosi.
Devo dire, però, che non riesco a cavare proprio niente di buono, non lo so 
se questa strada porti a qualcosa di buona.
Ciao,
Gabriele 

 *equivalenti* (nel senso che si mostrerà tra poco) tra di loro.
Possiamo considerare il numero di pedine nei vari colori mod 2 (cioe`
per ogni colore: 0 = numero pari di pedine, 1 = numero dispari di
pedine).
Ogni mossa toglie una pedina da due colori e ne aggiunge una al terzo
colore, quindi inverte la parita` di tutti i colori.
La posizione finale vincente e` del tipo: 100 (oppure 010 o 001 ma il
discorso non cambia).  La penultima deve essere per forza 011, la
terzultima 100, ...
Una condizione necessaria (ma non sufficiente) per arrivare alla
soluzione e` quindi che la posizione iniziale sia del tipo 100 oppure
110, cioe` due pari e una dispari oppure due dispari e una pari.
Se si parte con 3 pari o 3 dispari non c'e` soluzione.
La casella di arrivo (se c'e`) e` nel gruppo che ha parita` diversa
dagli altri (e mantiene la diversita` dall'inizio alla fine).
Esempio (4x4):
  A B C A
  B C A B
  C A B C
  A B C A
La scacchiera contiene 6 A, 5 B e 5 C. 
Dobbiamo togliere una pedina per cominciare, abbiamo 3 casi:
- togliamo una A, rimangono 5, 5, 5 -> 111 -> impossibile
- togliamo una B, rimangono 6, 4, 5 -> 001 -> forse possibile
- togliamo una C, rimangono 6, 5, 4 -> 010 -> forse possibile
Possiamo eliminare le caselle A:
  X . . X
  . . X .
  . X . .
  X . . X
Lo stesso discorso si puo` fare con la colorazione "alternativa"
  A B C A
  C A B C
  B C A B
  A B C A
e rimangono come possibili caselle di partenza le caselle intermedie
del bordo esterno (o):
  X o o X
  o X X o
  o X X o
  X o o X
Se la scacchiera contiene 3n caselle (n, n, n), tutte le caselle
portano a una posizione (n-1, n, n) con parita` buona, e quindi non
possiamo scartare nessuna casella di partenza (almeno con questo
metodo).
        Mauro