Newsgroup: it.hobby.enigmi
Titolo: La scacchiera del Reversi

Ciao a tutti.
Non escludo che l'argomento sia già stato trattato, ma sinceramente non mi 
ricordo e non ho fatto ricerche approfondite in merito. Mi è stato 
recentemente proposto da un amico. Non è particolarmente difficile, ma 
sempre meglio di niente... :-)
Abbiamo una generica scacchiera NxM. Su ogni casella è posta una pedina del 
Reversi-Othello, con la faccia nera rivolta verso l'alto. Una mossa consiste 
nel capovolgere una pedina e con essa tutte le pedine che si trovano nella 
sua riga e nella sua colonna.
Qual è il numero minimo di mosse per avere tutte le pedine con la faccia 
bianca rivolta verso l'alto?
Ciao
Giorgio

 bianca rivolta verso l'alto?
Sinceramente non escluderei che l'argomento sia stato gia trattato qui
su ihe...
Il gioco non mi suona nuovo ma non sapevo la soluzione e quindi mi ci
sono cimentato:
S
P
O
I
L
E
R
Se almeno uno tra M ed N è dispari rivoltiamo tutte le pedine su una
riga/colonna dispari. Naturalmente se sia N che M sono dispari
scegliamo il lato più corto.
Se sia N che M sono pari una soluzione banale consiste nel rivoltarle
tutte una volta. Sinceramente non mi vengono in mente metodi più
efficaci :-(
Ciao,
Gabriele

 efficaci :-(
Ciao Gabriele!
Anch'io ho dato la stessa risposta e mi è stata confermata come giusta. 
Naturalmente con almeno un lato dispari non avevo dubbi: si vede a occhio! 
:-)
Con entrambi i lati pari, pur sembrandomi non esserci una soluzione 
migliore, rimane il fatto che non l'ho ancora giustificata come soluzione 
ottimale (a dire il vero non ci sono nemmeno messo più di tanto). Forse con 
qualche ragionamento sulla parità si dovrebbe riuscire a dimostrare che non 
ci sono soluzioni più corte. Ci vuoi provare tu? ;-)
Ciao!
Giorgio 

 sua riga e nella sua colonna...
A me viene in mente che questa frase potrebbe essere tradotta cosě:
"Una mossa consiste nel capovolgere una pedina e con essa tutte le
pedine che sarebbero raggiungibili con la mossa della Torre."
Ora, sostituendo "Torre" con gli altri pezzi degli scacchi, si possono
ottenere vari problemi analoghi, forse interessanti.
Ciao!!!  :o)
Livio

"Che nickname ha costui?"

Ciao Livio! :-)
Certo! Perché no?
Tra l'altro ho dato un'occhiata all'archivio di IHE e ho trovato un thread 
intitolato Matrici Luminose (introdotto da te!) in cui si tratta lo stesso 
problema con la mossa della "Torre corta" o del "Re retto" :-). Te ne 
ricordavi? ;-) Io per niente, ma ho la scusa di non avervi partecipato...
Per ora do il mio contributo alla tua proposta: in una scacchiera 3x3 con la 
mossa della Regina č sufficiente una mossa! :-)
Ciao!
Giorgio

 con la mossa della Regina è sufficiente una mossa! :-)
Anche con la mossa del Re :o)
Anzi, la mossa del Re dev'essere quella che risolve le scacchiere
rettangolari con il minor numero di mosse.
La 3x3 è anche l'unica che finora son riuscito a risolvere con
il cavallo, ma ce ne saranno pur altre. Se domenica piove...
Ciao!!!  :o)
Livio

 rettangolari con il minor numero di mosse.
Non tutte.
Ciao!!!  :o)
Livio

 Non tutte.
Invece, penso proprio di si: con la mossa del re ci troviamo esattamente 
come nel caso delle matrici luminose con l'accensione a croce.
Ciao
Gianni

"Giovanni Ravesi"

Credo che Livio intendesse dire che non in tutte le scacchiere la mossa del 
Re fornisce la soluzione migliore. Se infatti prendiamo una scacchiera 3x12, 
sono sufficienti 3 Torri (come da problema originario), mentre di Re ne 
occorrono 4.
E' comunque vero che con i Re si risolvono tutte le scacchiere, utilizzando 
un numero di mosse pari a ceiling(N/3) x ceiling(M/3), dove ceiling(x) è 
l'arrotondamento a intero per eccesso di x. E il tutto ribaltando ogni 
pedina una sola volta, senza quindi sovrapposizioni.
Sempre che non abbia preso abbagli...
Ciao
Giorgio 

 Sempre che non abbia preso abbagli...
Non mi pare!
Ciao
Gianni

 che non ci sono soluzioni più corte. Ci vuoi provare tu? ;-)
se ci provo io fa lo stesso?
Ho cominciato a scrivere questo post una decina di volte, e pur avendo le 
idee chiare su quello che dovevo dire, non riuscivo a farlo in modo chiaro. 
Ho capito che la colpa è della formulazione. Se dico che una pedina viene 
capovolta un certo numero di volte, non si capisce se sto dicendo che l'ho 
scelta un tot di volte come pedina "pivot" oppure se l'ho girata un certo 
numero di volte perché si trovava nella stessa riga o colonna della pedina 
scelta come pivot.
Quindi preciso meglio la formulazione di mossa:
Una mossa consiste nello "SCEGLIERE" una pedina, copovolgendo quella pedina 
e con essa tutte
le pedine che si trovano nella sua riga e nella sua colonna.
Alla fine ogni pedina sarà stata SCELTA un tot di volte. In realtà conta 
solo la parità, e quindi ci si potrebbe limitare a sgeglierla 0 o 1 volta. 
Ma non è importante.
Scriviamo in ogni casella il numero delle volte in cui la pedina viene 
scelta. Otterremo una matrice MxN che chiameremo matrice delle scelte:
0 1 0 1 1 0
0 1 1 0 0 1
1 1 1 1 0 0
0 1 0 1 0 1
Il colore finale di ogni pedina dipende da quante volte viene capovolta. Una 
pedina è capovolta ogni volta che viene scelta o quando viene scelta una 
pedina della stessa fila o colonna. Quindi il colore della pedina non è 
altro che la parità totale delle M caselle "*" della sua riga e delle (N-1) 
caselle "+" della sua colonna.
Per la casella (0,0) sommando i termini "*" e i termini "+"
* * * * * *
+ . . . . .
+ . . . . .
+ . . . . .
il risultato, se vogliamo che la pedina alla fine sia girata rispetto 
all'inizio, deve essere DISPARI
La stessa cosa vale per la casella (1,2)
* * * * * *
. + . . . .
. + . . . .
. + . . . .
quindi tutte le semicolonne di "+" hanno la stessa parità.
Ma allora la regione di "+" qui sotto ha parità totale PARI, perché somma di 
un numero pari di termini della stessa parità.
* * * * * *
+ + + + + +
+ + + + + +
+ + + + + +
La parità totale dell'intera matrice delle scelte deve essere PARI, perché 
ogni SCELTA gira M+N-1 pedine, che è dispari (9 nel nostro esempio), ed alla 
fine le pedine girate sono MxN, pari.
Quindi se ne deduce che la parità della prima riga è PARI.
Ma per ogni riga, o colonna, vale la stessa cosa.
Ma allora, guardando lo schema di prima dove tutte le semicolonne di tre "+" 
avevano la stessa parità
* * * * * *
+ + + + + +
+ + + + + +
+ + + + + +
si deduce che tutti i termini "*" della prima riga hanno la stessa parità. 
Di più: tutti i termini di qualsiasi riga o colonna hanno la stessa parità. 
TUTTI i termini della matrice hanno la stesa parità. Con tutti pari non si 
muove una paglia. Con tutti dispari si risolve, come già detto.
-- 
Ciao, Silv:o)

 Certo! Perché no?
Ho provato con la mossa del Cavallo, che mi sembra abbastanza
interessante. Sotto spoiler metto qualche soluzione per scacchiere
da 3x3, 3x4, 3x5, 3x6, 4x4 e 4x5 che non garantisco *minime*.
Per scacchiere più grandi dovrò tagliare qualche ramo secco.
Ma chissà cosa farete voi coi vostri pc turbo e i vostri C++++!
Ciao!!!  :o)
Livio
|
|
|
|
|
|
|
|
|
|
|
|
spoiler
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
111
111
111
0000
1111
0000
00011
11111
00011
110011
111111
110011
1001
0110
0110
1001
11111
01110
01110
11111

 Ma chissà cosa farete voi coi vostri pc turbo e i vostri C++++!
Però, tanto per incoraggiarvi, vi do la soluzione del Cavallo sulla
scacchiera classica 8x8, che dovrebbe anche essere minima.
Qui, più che tagliare i rami secchi, ho abbattuto direttamente
l'albero con l'accetta.
Ciao!!!  :o)
Livio
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
spoiler
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
10000001
01000010
00111100
00111100
00111100
00111100
01000010
10000001

 quindi tutte le semicolonne di "+" hanno la stessa parità.
[cut]
Sinceramente a questo punto mi blocco, perchè tutte le semicolonne
devono avere la stessa parità?
Ciao,
Gabriele

 devono avere la stessa parità?
Con un esempio si chiariscono meglio le cose.
Supponiamo di avere una matrice delle scelte fatta così:
1 1 0 1 1 0
1 1 1 0 0 1
1 0 1 1 0 1
1 0 0 0 1 1
Partiamo dalla casella in alto a sinistra.
1 1 0 1 1 0
1 . . . . .
1 . . . . .
1 . . . . .
Dopo aver girato tutte le pedine, quella in alto a sinistra pedina
risulterà girata 4 volte assieme a tutta la prima riga (se stessa
compresa) e 3 con la prima colonna (se stessa esclusa).
Alla fine quindi risulterà bianca perché 7 è dispari.
Veniamo alla casella successiva:
1 1 0 1 1 0
. 1 . . . .
. 0 . . . .
. 0 . . . .
Il bilancio è 4+1, ancora dispari perché le caselle della semicolonna
danno ancora contributo dispari, cosa non vera per la terza
semicolonna. Quindi la terza pedina della prima riga resterebbe nera.
Tentiamo di aggiustare le cose includendo un'altra padina della terza
colonna
1 1 0 1 1 0
1 1 1 0 0 1
1 0 1 1 0 1
1 0 1 0 1 1
Adesso la prima riga risulta alla fine tutta bianca, perchè l'intera
riga viene capovolta 4 volte e le semicolonne tutte un numero dispari
di volte.
Non è difficle continuare come dicevo nel post precedente: la somma di
tutta la scacchiera deve essere pari, la somma di tutte le semicolonne
private della prima riga è pari perchè somma di sei termini omogenei
(in questo caso dispari), quindi la prima riga dovrebbe avere - per
differenza - somma pari. Anche la prima colonna deve avere somma pari,
per ragioni analoghe, e così tutte le colonne. Ma se le semicolonne
sono tutte della stessa parità, e le colonne sono tutte pari, allora
la prima riga deve essere costituita da tutti numeri della stessa
parità. Tutta la matrice deve essere fatta di numeri della stessa
parità!
Probabilmente si può saltare qure qualche passaggio, semplificando
ancora.
-- 
Ciao, Silv:o)

 Con un esempio si chiariscono meglio le cose.
Ok, grazie mille.
Con calma ma ci arrivo pure io...
Ciao Silvio!
Gabriele

 ottenere vari problemi analoghi, forse interessanti.
Ho provato con l'alfiere ma sembra fin troppo facile, non ho ancora
trovato una scacchiera che non si possa completare facilmente.
Sicuramente è sempre possibile per scacchiere 1xN e 2xN. Anche le 3xN
sembrano sempre "ribaltabili" (ho provato fino alla 3x6) anche se non
ho ancora individuato uno schema ripetibile, facilmente si fanno anche
tutte le NxN.
Ciao,
Gabriele