Newsgroup: it.hobby.enigmi
Titolo: Quadrati cromatici

Supponiamo che ciascuna casella di una scacchiera n*n sia colorata di
bianco o di nero. Allora ogni quadrato 2*2,3*3,4*4....n*n  presente
nella scacchiera lo chiameremo cromatico se le caselle ai quattro angoli
sono dello stesso colore. Disegna una scacchiera 9*9 in cui tutti i 204
sottoquadrati sono NON cromatici.
:) dario

Dario Uri propose:

.
.
.
.
.
.
.
.
.
.
.
.
.
spoiler
.
.
.
.
.
.
.
Probabilmente ci sono molte soluzioni.
Io ho usato una Darwin Machine molto semplice.
A mano e' facile realizzare combinazioni di 
180..190 sottoquadrati non cromatici. Poi la
Darwin Machine pone delle mutazioni casuali
e accetta la mutazione se il risultato e' pari
o migliora. La convergenza e' rapida:
.XX..X.XX
..XX.X..X
X..XXXX..
XXX...XXX
..XXX...X
.X..XXX..
..XX..XX.
X...X..XX
XXXX.X..X
.X...XX.X
.XXXX....
..X..X.XX
X...X.XX.
..XXX.X.X
XX.X.X.X.
X.XX.X.X.
X.X..XX..
.X.X..XXX
X.X..X.X.
X.X.XX..X
X..XX..XX
XX..X.X..
.X.X..X.X
..XX.XX.X
XXX....XX
.X..XXXX.
..XXX....
Ciao alla prossima  :o)
Livio
-- 
Posted from 
mta21-acc.tin.it
 [212.216.176.74] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

in cui tutti i 204 sottoquadrati sono NON cromatici.
.
.
.
Visto come la mia Darwin Machine si trova a suo agio
con questo problema, l'ho spinta a cercare soluzioni
per i 285 sottoquadrati della scacchiera 10x10 e per
i 506 della scacchiera 12x12.
Se l'e' cavata egregiamente con lo stupore per primo
dell'autore. Considerate che la solita brute force si
sarebbe arresa molto prima.
2^144=~10^43 che x 1 microsec =~ 10^27 secoli
10x10 -> 285:
X X X X . . . X . .
. . . X X . X . . X
. X . . . X X X . X
. X X . X X . . . X
. . X . . X X . X .
X X . . X . . . X X
X . . X X . X X . .
. X . X . . . X X .
X . X X . X . . X .
X X X . . X X X . X
12x12 -> 506:
. . . X . . . X X X X X
X . X X X . X X . . . X
X . X . . . X . . X X .
. X . X . X X . X X . .
. . X X X X . . . . X X
X X X . . . . X X X X .
. X . . X X X X . . . .
. X X X X . . . X X . X
. . X . . . X X X . . X
X . . . X X X . X X . .
. X . X . . X X . X X X
X X . . . X . . X . X .
Bah!    :o|?
Livio
-- 
Posted from 
pop09-acc.tin.it
 [212.216.176.72] 


 sarebbe arresa molto prima.
Ho implementato la tua Darwin Mascin: fantastica!!!
Per ottenere i migliori risultati ho dovuto lavorare un po' di "fine
tuning". Ho messo un contatore di insuccessi, ed uno stack con le mosse
fatte. Quando il contatore supera una certa soglia, allora scatta il
backtrack, perché č inutile incaponirsi sui rami secchi. Un valore che mi č
parso adatto č n^2, e c'era da aspettarselo: vuol dire che mediamente ho
provato tutte le caselle, senza miglioramenti. Per valori di n piccoli
converge piů rapidamente se si permettono mutazioni che lasciano inalterato
il numero dei quadrati cromatici, per n superiori al dieci c'č bisogno del
massimo rigore. Ecco una soluzione con n=13, con n=14 in dieci minuti il
numero dei cromatici non č mai sceso sotto i 15, ed i vicoli ciechi
evidenziati dai passi indietro sono frequentissimi.
X X . . X . . . X . . X .
. . X . . X X X X . X X .
. X . . X X . X . . X X .
X . X X X . . X . X X . .
X X . X . . X . . X X . X
X . . X . X X X X . . . .
. X . . X . X . X X . X .
. . X X X . . . X . X . X
X X X . . X X . . X . . X
. . X X . . . X X . . X X
X X . . . X . . X X . . X
X . . . X X . X . . X . X
. . . X X . X . . X . X X
Ciao, Silv:o)

 sceso sotto i 15
Dopo qualche minuto sono andato a dare un'occhiata, e c'era una soluzione.
Peccato che č bacata :((( Ci sono un sacco di quadrati cromatici, devo aver
toppato qualche indice, vedo di aggiustarla. Cosě com'č piů che a madre
natura somiglia alla mucca pazza.
Silv:o)

 natura somiglia alla mucca pazza.
Sistemata, credo. Ho trovato diverse soluzioni con n=12, ma con n=13 non č
mai scesa sotto i 4 quadrati cromatici.
n=12 (tempo 00:03 - caso fortunatissimo, altre volte dopo dieci minuti la
resetto)
. X . X . . X X . X X X
X X . . X X . . . X . .
X . . X X . . X X . . X
. X . . X X X . . . X X
X X . X . . . . X X X .
X . . . . X X X X . . .
. . X X X X . . . . X X
X X X . . . . X X X X .
X . . X X . X X . . . .
. . X X . . X . . X X .
. X X . . X X X X X . .
X X . . X X . . . X . X
Ciao, Silv:o)

Guardando alcune soluzioni
mi sono chiesto se se ne puo'
trovare una a trama regolare.
Una cosa del genere?
quadrati da 5 6 7 8 si eliminano
per via delle righe 4B 4N
quadrati da 2 3 4 si eliminano
per via delle colonne....
xxxx....xxxx.
...xxxx....xx
xx....xxxx...
.xxxx....xxxx
....xxxx....x
xxx....xxxx..
..xxxx....xxx
x....xxxx....
sandro.san
mu...@ifsi.rm.cnr.it
elena.ifsi.rm.cnr.it
Non sono paranoico. se pensate che io sia paranoico, vaffanculo

Ho messo piu' colonne del necessario
per rendere comprensibile la trama.
Non riesco a capire se e' giusto e
se puo' funzionare, come trama,
fino ad ordini superiori. C'entra
qualcosa la periodicita' ...
bho.
ale

mai scesa sotto i 4 quadrati cromatici.
[cut]
.
Ho visto un -3 (647 quadrati per la 13x13)
.
.
.
Comunque mi stupisco molto di piu' che la Darwin Machine abbia
trovato soluzioni per la scacchiera 12x12 piuttosto che non ne 
abbia trovate per quella 13x13.
Il rapporto tra le due complessita' e' 
2^(12x12)/2^(13x13) =~ 1 : 33.000.000
e sulla 12x12 gia' giustamente arrancava.
Non riesco ad avere delle idee precise sul problema, pero' 
tento questo approccio:
 N   S_Q   2^(N*N)    Prob.      N_sol.
 2   1     16          .875      14 (14)
 3   5     512         .512      262 (276)
 4   14    65536       .154      10106 (10980)
 5   30    3.35E+7    1.82E-02   610930
 6   55    6.87E+10   6.46E-04   4.44E+7
 7   91    5.62E+14   5.28E-06   2.97E+9
 8   140   1.84E+19   7.60E-09   1.40E+11
 9   204   2.41E+24   1.47E-12   3.57E+12
 10  285   1.26E+30   2.96E-17   3.76E+13
 11  385   2.65E+36   4.71E-23   1.25E+14
 12  506   2.23E+43   4.52E-30   1.01E+14
 13  650   7.48E+50   2.01E-38   1.51E+13
 14  819   1.00E+59   3.19E-48   3.20E+11
 15  1015  5.39E+67   1.37E-59   7.41E+8
 16  1240  1.15E+77   1.23E-72   1.42E+5
 17  1496  9.94E+86   1.75E-87   1.74
 18  1785  3.41E+97   3.05E-104  1.04E-06
 19  2109  4.69E+108  4.95E-123  2.32E-14
 20  2470  2.58E+120  5.75E-144  1.48E-23
N       dimensione scacchiera da 2x2 a 20x20
S_Q     numero sottoquadrati
2^(N*N) num. combinazioni colori, rotazioni e specularita' comprese
Prob.   probabilita' ~ che una configurazione casuale abbia solo
        quadrati non cromatici = (14/16)^S_Q
N_Sol.  numero probabili soluzioni. Tra () verificate.
Le cifre parlano da sole. Per N=13 comincia il declino
della fortuna dei quadrati non cromatici: il num. delle
combinazioni sale di 8 ordini mentre il num. delle probabili
soluzioni scende di un ordine di grandezza.
La probabilita' che esista una scacchiera 20x20 completamente
non-cromatica e' praticamente nulla e per trovare quell'una o
due della 17x17 bisognera' attendere qualche generazione di PC.
(Come cercare un atomo nell'universo noto, altro che ago nel
pagliaio!)
Le cifre sono trocate e con beneficio d'inventario.
Ciao  :o)
Livio
-- 
Posted from 
mta13-acc.tin.it
 [212.216.176.44] 



Dario ha chiesto la soluzione per n=9, e tu trovi una bella soluzione
*regolare* per n=8. Non credo sia un caso, e da 9 in su le trame regolari
penso siano destinate a fallire.
Mentre è ovvio che tutti i pattern, quale che sia la loro forma o
dimensione, non possono formare matrici arbitrariamente estese completamente
acromatiche, non mi e' del tutto chiaro perche' il limite all'utilizzo dello
schema a righe shiftate è 8*8.
Silv:o)


E' vero, manca una riga. Il fatto di aver messo piu'
colonne mi ha tratto in inganno.
Ciao

Spulciando nel sempre interssante sito di Torsten Sillke
(
http://www.mathematik.uni-bielefeld.de/~sillke/
) mi sono imbattuto in un
problema che abbiamo discusso da poco, i quadrati cromatici proposti da
Dario. Noi avevamo trovato diverse soluzioni con n=12 con metodi random. Non
ho ne la voglia ne la capacità di tradurre, accontentatevi del copincolla.
_____________
no monocromatic (aligned) squares:
colors = 2: maximal n*n grid found so far is n=13.
Robert Israel, Chris Thompson
        0001101010110
        0101011000011
        1100001101110
        0110101011000
        0101100001101
        0000110101011
        1011101100001
        0110000110111
        0011010101100
        1010110000110
        1000011011101
        1101110110000
        1011000011010
This 13*13 (0,1) square *does* satisfy the condition, having no
i x i and i x (13-i) rectangles with four corners the same.
----
che mi pare sia più di quanto noi cercassimo.
La cosa notevole è che sandro.san aveva visto giusto, con la sua proposta di
griglia regolare
----
As a matter of fact, there *is* something odd going on.  A close look at
this solution shows that all the rows are cyclic permutations of
001101a101100, where "a" is either 0 or 1, each row being displaced 5
places to the left from the previous one.  If you write one of these
13-tuples as <c_i>_{i=0..12}, it satisfies the condition that for all
i and 1 <= j <= 12, c_i, c_{i+j}, c_{i+5j} and c_{i+6j} are not all the
same (considering the subscripts mod 13).  Thus such a 13-tuple generates
a square that works (with periodic boundary condition).  The only 13-tuples
for which this works are these two and those obtained from them by cyclic
permutation and interchanging 1 and 0.  I also tried shifts other than 5
(so for some b, 1<=b<=12, you want c_i,c_{i+j},c_{i+bj} and c_{i+(b+1)j}
never to be all the same).  No more examples except for b=8 (which is
equivalent to b=5 by left<->right symmetry).  Unfortunately, there are no
14-, 15-, 16- or 17-tuples with the analogous properties either.
It really looks as thought there ought to be some significance in the fact
that 001101a101100 is the pattern of quadratic residues mod 13 (a at the
point 0 mod 13), and in the fact that 5 and 8 are the square roots of -1
mod 13. But naive attempts to use the same rules for larger primes don't
work. (They do work for N=5, 01a10 shifted 2 for each new row.)
----
Ciao, Silv:o)