Scambio di diagonale

[giobimbo]

Un gioco dall'Argentina.
Sei pedine, numerate da 1 a 6, sono disposte sulla diagonale principale di una scacchiera, la pedina 1 sulla prima fila orizzontale di caselle, la pedina 2 sulla seconda fila e così via. Ogni pedina può muoversi orizzontalmente di tanti passi quanto è il suo numero, verso destra o sinistra, a scelta, ma quando la pedina m si muove di m passi a destra (o sinistra) altre m pedine si muovono di un passo in direzione contraria, sì che in ogni colonna della scacchiera ci sia sempre una pedina. Ogni mossa consiste quindi nello spostamento di (m+1) pedine.

Spostare le sei pedine sulla diagonale opposta col minor numero di mosse.

Nell'esempio sotto, la posizione iniziale, la posizione dopo la mossa 2D (cioè pedina 2 muove due passi a destra), la posizione dopo le mosse 2D e 3D, la posizione finale:

1...0...0...0...0...0 - 1...0...0...0...0...0 - 1...0...0...0...0...0 - 0...0...0...0...0...1
0...2...0...0...0...0 - 0...0...0...2...0...0 - 0...0...2...0...0...0 - 0...0...0...0...2...0
0...0...3...0...0...0 - 0...3...0...0...0...0 - 0...0...0...0...3...0 - 0...0...0...3...0...0
0...0...0...4...0...0 - 0...0...4...0...0...0 - 0...4...0...0...0...0 - 0...0...4...0...0...0
0...0...0...0...5...0 - 0...0...0...0...5...0 - 0...0...0...5...0...0 - 0...5...0...0...0...0
0...0...0...0...0...6 - 0...0...0...0...0...6 - 0...0...0...0...0...6 - 6...0...0...0...0...0

[delfo52]

se ho capito bene, il numero di pedine da muovere è fissato, e corrisponde al "nome" della pedina mossa di due posti.
Quali siano le pedine da muovere di una posizione in controtendenza, è lasciato alla discrezione del giocatore.

[giobimbo]

Quali siano le pedine da muovere di una posizione in controtendenza, è lasciato alla discrezione del giocatore.

Quando si muove la pedina m di m passi in una certa direzione, essa andrà a finire in una colonna dove c'è già la pedina l e questa si sposterà di un passo in direzione contraria.
Se l finisce in una colonna vuota la mossa è terminata, se l finisce in una colonna dove c'è già la pedina k questa si sposterà di un passo in direzione contraria a quella di m, e così via finché la pedina x capita in una colonna vuota.
Una volta mossa la pedina m i movimenti delle altre pedine sono obbligate, non c'è scelta a discrezione.

(Sono anche interessato alla soluzione per una scacchiera 4x4)

[infinito]

Non ho ben capito ...

Ma la pedina 6 si può muovere solo di 6 posti, e quindi può solo andare alternativamente a sinistra sulla prima colonna e poi sulla destra a ll'ultima, no?

Quindi mi pare che la risoluzione sia "banale":

Sposto tutte le pedine a sinistra, in ordine decrescente a partire adalla 6, ottenendo quello che cerco di riportare sotto (analogamente a quanto fatto da giobimbo, ma mettendo solo in rosso il numero principale spostato):


1···0···0···0···0···0 ___ 0···1···0···0···0···0 ___ 0···0···1···0···0···0 ___ 0···0···0···1···0···0 ___ 0···0···0···0···1···0 ___ 0···0···0···0···0···1

0···2···0···0···0···0 ___ 0···0···2···0···0···0 ___ 0···0···0···2···0···0 ___ 0···0···0···0···2···0 ___ 0···0···0···0···0···2 ___ 0···0···0···0···2···0

0···0···3···0···0···0 ___ 0···0···0···3···0···0 ___ 0···0···0···0···3···0 ___ 0···0···0···0···0···3 ___ 0···0···0···3···0···0 ___ 0···0···0···3···0···0

0···0···0···4···0···0 ___ 0···0···0···0···4···0 ___ 0···0···0···0···0···4 ___ 0···0···4···0···0···0 ___ 0···0···4···0···0···0 ___ 0···0···4···0···0···0

0···0···0···0···5···0 ___ 0···0···0···0···0···5 ___ 0···5···0···0···0···0 ___ 0···5···0······0···0 ___ 0···5···0···0···0···0 ___ 0···5···0···0···0···0

0···0···0···0···0···6 ___ 6···0···0···0···0···0 ___ 6···0···0···0···0···0 ___ 6···0···0···0···0···0 ___ 6···0···0···0···0···0 ___ 6···0···0···0···0···0


Il caso di 4x4 è analogo .... ma forse non ho capito bene il problema

[giobimbo]

Giustamente la pedina 6 muove di 6 posti (passi, caselle) quindi va a finire... fuori dalla scacchiera. La pedina 6 si muove sempre di un passo verso sinistra, quando vi viene costretta da una mossa di m passi di un'altra pedina con numero m diverso da 6.

Con riferimento all'esempio iniziale, posizione dopo 2D e 3D:
con terza mossa 4D le pedine 2, 3, 5 e 6 sono obbligate a spostarsi tutte a sinistra di un passo.

[giobimbo]

Correzione: la pedina 6 deve andare nella casella in fondo a sinistra, è vero, ma durante il viaggio può anche muovere a destra.

Per indicare la soluzione non occorre disegnare la scacchiera con la posizione delle pedine dopo ogni mossa, basta scrivere 2D, 3D, 1D, 2S, eccetera.

Mi è venuto il dubbio di non aver capito bene il senso della domanda di delfo52. Se per esempio la mossa iniziale è 2D, si muove la pedina 2 di due passi, ma poi bisogna muovere prima 3 e poi 4, oppure prima 4 e poi 3, oppure ambedue assieme? Qui la scelta è davvero libera, a discrezione.

[Sancho Panza]

Soluzione per il caso 4x4 (in 7 mosse)

2d
1d
2s
1d
3d
1d
2d

[Pasquale]

Con la soluzione di Sancho ho capito bene il problema, che evidentemente non avevo letto attentamente.
Bel problemino ed ecco la mia soluzione, a titolo di esercizio, per la scacchiera 3x3: 1D, 2D, 1D, 1D (per la scacchiera 2x2: 1D)

[giobimbo]

Ho aggiunto la scacchiera 4x4 perché lavorandoci sopra trovavo sempre soluzioni in 8 mosse; solo usando un certo ragionamento algebrico sono riuscito a farcela in 7 mosse, perciò vorrei sapere da Sancho Panza se il suo risultato l'ha ottenuto muovendo le pedine (nel qual caso è stato più bravo di me) o in altro modo.
Sette mosse sono il minimo

[Sancho Panza]

Ciao Giobimbo,
sulla scacchiera 4x4 il risultato l'ho trovato per tentativi
(non è difficile, è piuttosto piccola)

Per la scacchiera 6x6 ho studiato una strategia (forse non ottimale),
che permette di avere una soluzione in 17 mosse:

3d, 2d, 4d, 1d, 4s, 2s, 3s, 5d, 1d, 1d, 3d, 2d, 4d, 2d, 3d, 1d, 2d


Come ho detto prima non sono in grado di dire se sia la soluzione minima;
l’ho trovata nel seguente modo:

Con le prime 7 mosse scambio di posto il numero 1 con il numero 5 (sfruttando il più possibile la simmetria nelle mosse)
Successivamente sposto il 5 in fondo, in modo di muovere il 6
Porto con altre due mosse il numero 1 in fondo
Con le 7 mosse restanti, sposto i numeri a destra quanto basta per avere la diagonale desiderata.

Questa strategia l’ho trovata a livello intuitivo, ma mi pare comunque abbastanza buona.

Hasta la vista amigos,

Sancho Panza

[giobimbo]

Mi hai superato di nuovo, il mio record sulla scacchiera è di 18 mosse, però usando l'algebra come nel 4x4 arrivo a 16 mosse con una soluzione dalla struttura matematicamente mirabile.
Purtroppo il signor Poniachik dice che si può fare di meglio...

[Sancho Panza]

Ciao Giobimbo,
questo è l’ultimo risultato che sono riuscito a trovare:

1d
3d
1d
4d
1d
1d
2d
5d
3s
4s
1d
4d
2d
3d

(è una soluzione in 14 mosse, non riesco a trovare di meglio per cui spero che sia la minima)
Grazie per il problema, mi è piaciuto moltissimo!!!

Sancho Panza

[giobimbo]

Bravissimo Sancho, mi hai lasciato a bocca aperta con la tua soluzione (che ha il giusto numero di mosse).
Complimenti a te e grazie a Jaime P. per il problema.

[Pasquale]

Grande Sancho!
Una piccola osservazione che conduce ad una seconda soluzione, quale che sia in ogni scacchiera: provate un po' ad effettuare i vari spostamenti in senso inverso, partendo dalla coda della sequenza di ciascuna soluzione e ..... voilà!
Sarei curioso di vedere le soluzioni di Giobimbo con l'approccio algebrico.
Hasta luego Sancho!

[giobimbo]

Partiamo con la scacchiera 4x4. Nell'algebra c'è manipolazione di simboli per cui cominciamo a inventarne qualcuno. Indichiamo con P0 la posizione delle pedine all'inizio, con P1 la posizione dopo la prima mossa, con Pr la posizione dopo l'erresima mossa.
Scriviamo Pr=3 2 4 1 per dire che nella prima colonna della scacchiera c'è la pedina3, nella seconda colonna c'è la pedina2, nella terza colonna c'è la pedina4 e nell'ultima colonna la pedina1; in particolare avremo P0=1 2 3 4. Scrivo una soluzione trovata in otto mosse:
1 2 3 4
1 3 4 2
3 1 4 2
1 4 2 3
4 1 2 3
4 2 1 3
4 1 3 2
4 3 1 2
4 3 2 1

Come hai notato anche tu, Pasquale, tramite una riflessione orizzontale e una verticale questo insieme di otto permutazioni diventa un'altra soluzione in otto mosse, le scrivo affiancate con dei colori che serviranno per la spiegazione dopo:
1 2 3 4 - 1 2 3 4
1 3 4 2 - 2 1 3 4
3 1 4 2 - 2 3 1 4
1 4 2 3 - 3 1 2 4
4 1 2 3 - 3 2 1 4
4 2 1 3 - 3 2 4 1
4 1 3 2 - 2 4 1 3
4 3 1 2 - 2 4 3 1
4 3 2 1 - 4 3 2 1

E' possibile passare da una posizione della soluzione di sinistra a quella di destra in modo da eliminare dei passaggi? Da P2 in rosso a sinistra, con la mossa 2S salto a P4 in rosso a destra, ottenendo la Soluzione1 in sette mosse qua sotto (un'altra, chiamiamola Soluzione2, si ottiene da P4 in blu a sinistra a P6 in blu a destra, sempre con mossa 2S):
1 2 3 4
1 3 4 2
3 1 4 2
3 2 1 4
3 2 4 1
2 4 1 3
2 4 3 1
4 3 2 1

Scompongo Soluzione1 in tre blocchi di mosse, A=(P0, P1, P2), B=(P3, P4), D=(P5, P6, P7), ovvero in forma grafica:
1 2 3 4) A
1 3 4 2)
3 1 4 2)

3 2 1 4) B
3 2 4 1)

2 4 1 3) D
2 4 3 1)
4 3 2 1)

Allo stesso modo scompongo Soluzione2 in tre blocchi A, C e D, dove C corrisponde a:
1 4 2 3) C
4 1 2 3)

Il blocco A si trasforma nel blocco D tramite una riflessione verticale seguita da una riflessione orizzontale, il blocco B si trasforma nel blocco C allo stesso modo. Lo schema qua sotto dice che una soluzione si ottiene percorrendo la strada ABD e un'altra si trova percorrendo ACD. Se due blocchi con lo stesso colore hanno lettere diverse significa che uno può trasformarsi nell'altro tramite doppia riflessione, come appena specificato, lo stesso farò con la scacchiera 6x6.
A - A
B - C
D - D


Eccoci infine alle 6 pedine. Per sveltire la faccenda scrivo solo le posizioni di metà dei blocchi, l'altra metà si può ricavare tramite il codice dei colori, facendo la doppia riflessione:
1 2 3 4 5 6) A
1 2 4 5 6 3)
1 4 5 2 6 3)
1 4 5 6 3 2)
1 5 6 3 2 4)
5 1 6 3 2 4)

5 4 1 6 3 2) B

5 1 2 6 3 4) E

5 4 1 2 6 3) C
5 4 3 1 2 6)
5 4 2 3 1 6)

1 6 3 2 4 5) G

5 6 1 3 2 4) M

Comincio ad avere la lingua secca... ecco lo schema finale qua sotto. Le soluzioni non sono 4 ma il doppio, perché cominciando con ABC posso continuare con ABCDP oppure saltare ad ABCFP.
La bellezza è nell'occhio dell'osservatore.

A - A - A - A
B - E - G - M
C - C - H - H
D - F - L - N
P - P - P - P