Newsgroup: it.hobby.enigmi
Titolo: vicini e primi relativi

[letto su una lista di discussione argentina, segue una traduzione più o
meno letterale]
Partendo da una matrice NxN vogliamo riempirla con i numeri da 1 a N^2
seguendo i seguenti criteri:
- ciascun numero deve essere vicino al successivo
- tutti i numeri vicini devono essere primi relativi
Definiamo vicini due numeri che stanno in caselle con un lato in comune,
ricordiamo poi che due numeri sono detti primi relativi se non hanno
divisori in comune.
Facili gli esempi per N=2,3
1 2
4 3
1 2 3
6 5 4
7 8 9
Si richiedono soluzioni per N=4,5,6,7,....
Si può fare per tutte le N?
Gabriele

 Si richiedono soluzioni per N=4,5,6,7,....
per ora N=4
15 14 13 12
16 01 02 11
05 04 03 10
06 07 08 09
ciao
paolo

 Si può fare per tutte le N?
Non sono sicuro, ma un ragionamento *non troppo ortodosso* mi porta a pensare che oltre un certo
valore di N non sia più possibile.
Anzittutto una considerazione di parità: se consideriamo la matrice come una scacchiera, avremo
i numeri pari sul bianco e i dispari sul nero, o viceversa. Quindi nessun contatto tra due pari.
Cerco allora di valutare i possibili contatti tra numeri multipli di tre.
Prendiamo una matrice *abbastanza grande*, tale che si possa ritenere trascurabile l'influenza
delle caselle perimetrali.
Ciascun numero pari è a contatto con quattro numeri dispari.  Tra i numeri pari 1/3 sono
multipli di tre, idem per i dispari.
Quindi dal punto di vista *probabilistico* mi aspetto che tra i quattro vicini a un multiplo di
sei ce ne sia almeno uno multiplo di tre.
Se non c'è, vuol dire che la *densità* di multipli di tre in quella zona è diminuita, ma allora
la *densità* deve aumentare da un'altra parte, e aumenta di pari passo la *probabilità* di
contatto tra multipli di tre.
E' vero che la disposizione dei numeri non è casuale, ma non è nemmeno del tutto libera. I
vincoli dovuti al fatto che ciascun numero deve essere vicino al successivo, *forse* compensano
la *non casualità*. Inoltre si dovrebbe tener conto anche dei possibili contatti tra multipli di
5, 7, 11 ecc.
Penso anche (ma è solo una mia congettura) che oltre un certo N, anche eliminando quel vincolo,
e quindi *liberalizzando* del tutto la disposizione dei numeri, non sia possibile evitare la
vicinanza di numeri non primi relativi.
ciao
paolo

 Si può fare per tutte le N?
Per esercizio, a mano, alla ricerca di un metodo, cominciamo
con N=5:
03 02 15 16 17
04 01 14 25 18
05 12 13 24 19
06 11 10 23 20
07 08 09 22 21
Ci sara' un crivello? Bah! Ci penso ancora, neh...
Ciao!!!  ((^__^))'
Livio

>Si può fare per tutte le N?
Se non ho sbagliato il programmino, mi sembra che per N=6 non si possa
fare, mentre per N=7 si.
Ecco 5 soluzioni esemplificative, con il punto di partenza
differente:
---------------------
49  6  7  8  9 20 21
48  5  4  3 10 19 22
47 46 45  2 11 18 23
36 37 44  1 12 17 24
35 38 43 42 13 16 25
34 39 40 41 14 15 26
33 32 31 30 29 28 27
---------------------
  3  2  1 36 37 38 39
  4 15 16 35 34 33 40
  5 14 17 26 27 32 41
  6 13 18 25 28 31 42
  7 12 19 24 29 30 43
  8 11 20 23 48 47 44
  9 10 21 22 49 46 45
---------------------
39 40  3  2  1 20 21
38 41  4  9 10 19 22
37 42  5  8 11 18 23
36 43  6  7 12 17 24
35 44 49 48 13 16 25
34 45 46 47 14 15 26
33 32 31 30 29 28 27
---------------------
  3  2 37 38 39 40 41
  4  1 36 35 44 43 42
  5 24 25 34 45 46 47
  6 23 26 33 32 31 48
  7 22 27 28 29 30 49
  8 21 20 19 18 17 16
  9 10 11 12 13 14 15
---------------------
45 44 39 38 37 22 21
46 43 40  1 36 23 20
47 42 41  2 35 24 19
48  5  4  3 34 25 18
49  6 31 32 33 26 17
  8  7 30 29 28 27 16
  9 10 11 12 13 14 15
---------------------
ciao,
g.

 si possa fare, mentre per N=7 si.
Confermo il risultato, sul quale avevo qualche dubbio. Ho implementato
un backtrack e non ho trovato alcuna soluzione per la 6x6. Ma il
programma non e' molto efficiente, gia' impiega mezz'ora per trovarne
una da 7x7:
 39 40 41 42 43 44 45
 38 37 24 23 22 21 46
 01 36 25 26 27 20 47
 02 35 34 33 28 19 48
 03 08 09 32 29 18 49
 04 07 10 31 30 17 16
 05 06 11 12 13 14 15
Se riesco ad ottimizzarlo, provero' gli ordini superiori, se no
aspetto i tuoi risultati.  :o))))
Ciao!!!  ((^__^))'
Livio


Ho trovato cinque soluzioni per N = 8, dovrebbero essere le uniche, a parte
r&r.
03 04 05 06 07 08 61 60
02 01 12 11 10 09 62 59
15 14 13 20 21 64 63 58
16 17 18 19 22 51 52 57
27 26 25 24 23 50 53 56
28 33 34 35 36 49 54 55
29 32 39 38 37 48 47 46
30 31 40 41 42 43 44 45
15 16 17 18 19 20 61 60
14 13 24 23 22 21 62 59
01 12 25 36 37 64 63 58
02 11 26 35 38 51 52 57
03 10 27 34 39 50 53 56
04 09 28 33 40 49 54 55
05 08 29 32 41 48 47 46
06 07 30 31 42 43 44 45
09 10 11 12 13 14 61 60
08 07 06 17 16 15 62 59
03 04 05 18 19 64 63 58
02 01 24 23 20 51 52 57
27 26 25 22 21 50 53 56
28 33 34 39 40 49 54 55
29 32 35 38 41 48 47 46
30 31 36 37 42 43 44 45
60 59 58 57 56 55 46 45
61 62 63 52 53 54 47 44
10 09 64 51 50 49 48 43
11 08 01 02 03 40 41 42
12 07 06 05 04 39 38 37
13 18 19 24 25 34 35 36
14 17 20 23 26 33 32 31
15 16 21 22 27 28 29 30
15 16 21 22 27 28 29 30
14 17 20 23 26 33 32 31
13 18 19 24 25 34 35 36
12 07 06 01 02 39 38 37
11 08 05 04 03 40 41 42
10 09 64 51 50 49 48 43
61 62 63 52 53 54 47 44
60 59 58 57 56 55 46 45
Riguardo alle ottimizzazioni, si riducono enormemente i tempi di
elaborazione se si arresta l'analisi quando ci si accorge che nel quadrato
si sono formate "isole" di caselle vuote.
Ad esempio, nel caso di N = 3, una volta arrivati a questo punto:
0 1 0
0 2 0
0 3 0
o a questo:
1 2 0
0 3 4
0 0 0
č inutile continuare perché non si riuscirebbe in nessun caso a completare
il percorso.
Ciao :-)
Giorgio

 si sono formate "isole" di caselle vuote.
Ci avevo pensato ma non avevo avuto tempo di pensare a come
implementarla.
Tu come la realizzi ? (ogni quanto fai il test e come lo fai ?)
Sono curioso!
g.

"Giovanni Resta"

Sicuramente si può migliorare, ma già così dà degli ottimi risultati. Faccio
la verifica ogni volta che ho piazzato un numero valido n (potrei evitare
quando n < 3, ma al momento non faccio controlli su n), al che individuo
nella scacchiera una casella vuota (una qualunque), marco ricorsivamente
questa e tutte quelle vuote che ha attorno, conto quante sono poi confronto
questo valore con il numero totale delle caselle vuote (che è dato da
N*N-n). Se i valori sono diversi, abbandono il ramo.
Sembra dispendioso ma con N = 7 e con questa ottimizzazione trovo tutte le
soluzioni in meno di 15 secondi, mentre senza ottimizzazione ci vogliono più
di 6 minuti per trovare la prima.
Ciao :-)
Giorgio

 Cerco allora di valutare i possibili contatti tra numeri multipli di tre.
Vedendo meglio le cose, mi rendo conto che il ragionamento, basato solo sulle possibili
vicinanze di multipli di tre, non funziona.
Come controprova porto una NON soluzione per N=9; non è una soluzione perchè ci sono, per
esempio, contatti tra 10 e 15, e tra 22 e 33. Però nessun contatto tra multipli di tre.
01 06 07 12 13 18 19 24 25
02 05 08 11 14 17 20 23 26
03 04 09 10 15 16 21 22 27
52 51 46 45 40 39 34 33 28
53 50 47 44 41 38 35 32 29
54 49 48 43 42 37 36 31 30
55 60 61 66 67 72 73 78 79
56 59 62 65 68 71 74 77 80
57 58 63 64 69 70 75 76 81
Questo schema si può adottare per tutti gli N=3(mod 6), semplicemente disponendo N/3 struscie
orizzontali, alte 3 e larghe N, da percorrere a zig-zag come nell'esempio. Quindi si possono
avere N grandi quanto si voglia senza vicinanze tra multipli di tre.
In conclusione, rimango nel dubbio iniziale:
E' possibile per tutti gli N?
ciao
paolo

 Magari provo ad implementare il tuo test e vedo come si comporta.
Implementata ! Effettivamente e' molto piu' veloce di quello
che pensavo, visto che il costo ad ogni passo non e'
proprio piccolo. Evidentemente riesce a tagliare molte
strade morte.
Confermo le 5 soluzioni per N=8 (tutte in circa 9 minuti e 7 sec).
Ora vedo un po' per N=9, e N=10 ma mi sa che i tempi si allungano di
parecchio.
Considerando che per N=6 troviamo le 0 soluzioni in 0.18 secondi, per
N=7 troviamo tutte le soluzioni (che saranno una
trentina) in 9.6 secondi mentre per N=8 ci sono voluti 9 minuti e rotti,
potremmo (un po' a caso...)  estrapolare almeno 9 ore per N=9 ??
Lo lascio girare questa notte, poi domattina vediamo
se qualcuno ha trovato qualcosa :-)
ciao,
g.

 parecchio.
Penso anch'io che i tempi si allungheranno molto. Per ora con N = 9 ho
trovato che non dovrebbero esserci soluzioni mettendo l'1 nell'angolo.
Ciao :-)
Giorgio


confermo.
io posso dirti che non dovrebbero esserci nemmeno con l'1 nella
posizione (prima riga, seconda colonna)...
ciao,
g.

 ciao,
Dopo una notte di elaborazione non ho trovato soluzioni mettendo l'1 nelle
caselle contrassegnate da x, non so se ce ne siano partendo dalle caselle ?.
Il resto sono rotazioni e riflessioni.
x........
xx.......
xxx......
x???.....
?????....
.........
.........
.........
.........
Comunque ho interrotto l'elaborazione; aspetto i risultati completi da
Giovanni, che quasi sicuramente ha un computer piů veloce del mio.
Poi potremmo cominciare a considerare le matrici non quadrate, la partenza
da un numero diverso da 1, l'incremento non unitario, ecc. ecc... :-)
Ciao
Giorgio

 Giorgio
Penso che ci sia solo questa soluzione.
55 54 49 48 47 42 41 36 35
56 53 50  1 46 43 40 37 34
57 52 51  2 45 44 39 38 33
58 69 70  3  8  9 20 21 32
59 68 71  4  7 10 19 22 31
60 67 72  5  6 11 18 23 30
61 66 73 78 79 12 17 24 29
62 65 74 77 80 13 16 25 28
63 64 75 76 81 14 15 26 27
Per N=10 ho lasciato perdere.
Ciao,
g.

 ...
Ahhh...  non ti piace tassellare il piano, ma appena puoi usi i metodi
dei poliformisti!  :o)))  Questo, infatti, e' l'algoritmo usato dai solver
di polimini per tagliare i rami secchi.
Non solo! Ma, udite udite, il buco che resta deve essere... "passeggiabile"!!!
Se tu non avessi fatto tanto lo schizzinoso  :o))) e avessi sviluppato
un decente algoritmo per i polimini passeggiabili, a quest'ora
disporremmo di un database di polimini passeggiabili con cui
confrontare il buco restante. Se non e' un polimino passeggiabile,
inutile continuare!
Scherzi a parte, nonostante i miei mezzi un po' datati che non
raggiungono le vostre velocita', ho visto anch'io venir fuori le
soluzioni N=8 che prima del tuo algoritmo non volevano
saperne di vedere la luce.
Ho messo anche un test per vedere se il buco restante non fosse
passeggiabile. Una condizione sufficiente per dire che non e'
passeggiabile e' rilevare almeno tre caselle con almeno tre lati
sul perimetro del buco. Guadagna circa il 10% sul tempo per
N=7 e N=8. Non e' un gran che ma e' quasi gratis dal test di
Giorgio, se li' si fa una mappa booleana del buco per contarne
le caselle.
Ciao!!!  ((^__^))'
Livio


Certo che l'analisi della passeggiabilità porta a fare delle considerazioni
che potano i rami secchi in maniera brutale! Pensa solo a questa. Dopo aver
posizionato i primi 4 numeri in una matrice 9x9, ad esempio così:
12.......
*3.......
.4.......
.........
.........
.........
.........
.........
.........
si può facilmente osservare che, per poter completare tutto il percorso,
questo deve terminare per forza nella casella contrassegnata dall'asterisco.
Quindi in quella casella andrà a finire il numero 81, che è divisibile per 3
per cui questo inizio è da scartare. Attualmente i nostri programmi scartano
questo inizio dopo avere trovato un bel po' di isole!
Io oggi non ho tempo da dedicarci, se qualcun altro vuole provare a
implementare questa idea...
Ciao :-)
Giorgio


E invece non ho resistito e l'ho implementata. E pensare che oggi dovrei
lavorare a tutt'altro e mi sento un po' in colpa, soprattutto dopo che Livio
ha svelato che tutta questa roba alla fine altro non è che i soliti
polimini! ;-)
Comunque i tempi si sono ridotti di un ulteriore 30% circa! E questo è
dovuto al fatto che una metà delle volte in cui si forma un "corridoio", il
numero che dovrebbe andare a finire nella casella terminale ha la parità
sbagliata e quindi la soluzione non c'è, come nell'esempio che facevo
nell'altro post.
Ciao :-)
Giorgio

 ...
Ho perfezionato un po' la cosa.
Non ho ancora trovato un algoritmo che mi dica se un polimino
e' passeggiabile (aspettavo che mi arrivasse dal ng :o)). Pero'
ci sono dei criteri semplici per dire se *non e'* passeggiabile.
1) Non e' passeggiabile se ha almeno tre omini con tre lati perimetrali.
2) Non e' passeggiabile se ha due omini con tre lati perimetrali e
se l'ultima casella occupata non e' adiacente a uno di questi due.
Applicando queste due potature ottengo un miglioramento del
57% sui tempi, che comincia a non fare schifo.
Questi i miei dati:
Visual Basic 5.0 su Win98 su Pentium 733 (questo passa il convento).
Matrice N=8 con partenza fissa in (3,1)
- senza potature: ore...
- con potatura Giorgio: 11'11''
- con potatura Giorgio + i 2 test di passeggiabilita': 4'44''
Ciao!!!  ((^__^))'
Livio

 nell'altro post.
Allora provo ancora ad aggiungere qualche test, poi ti diro'.
Ciao Giorgio!!!  ((^__^))'
Livio

 Livio
Ciao!!!
Giorgio

 Allora provo ancora ad aggiungere qualche test, poi ti diro'.
L'aggiunta di questo test ai due precedenti non ha dato i risultati
sperati. In effetti, eliminati i casi di tre o piu' cul-de-sac, restano i
casi di un solo cul-de-sac in cui deve finire N*N, oppure il caso
di due cul-de-sac di cui uno adiacente all'ultima mossa, per cui ci
riconduciamo al caso precedente. In entrambi i casi si tratta di un
corridoio che porta all'ultima casella = cul-de-sac, la quale e' sempre
di parita' giusta, come empiricamente mi han mostrato due contatori
messi li' all'uopo. Nel caso poi di N=8, l'ultimo numero e' 64 che e'
potenza di due e che quindi va sempre bene. Nei casi di N=7 e N=9
il test interviene nell'1% dei casi non facendo risparmiare piu' tempo
di quello perduto nei calcoli.
Alla prossima!!!  ((^__^))'
Livio

 sperati. 
Il problema e' che il prossimo problema aperto e' per N=10,
(per N=9 mi sembra ci sia l'unica soluzione che ho postato questa
mattina)
Solo che per N=10 ci vuole qualcosa di piu' di un 30% per rendere le
cose fattibili. Naturalmente si potrebbe provare a prendere
un punto iniziale a caso ed avere fortuna, ma se non ci fossero
soluzioni la ricerca esaustiva penso porterebbe via ancora troppo
tempo.
ciao,
g.

 facendo risparmiare piu' tempo di quello perduto nei calcoli.
Mmmm... pero' ha trovato la sol. N=9 in 1'16'' con partenza fissa
(8,4). Sara' un caso?
 63 62 61 60 59 58 57 56 55
 64 65 66 67 68 69 52 53 54
 75 74 73 72 71 70 51 50 49
 76 77 78 05 04 03 02 01 48
 81 80 79 06 07 08 45 46 47
 14 13 12 11 10 09 44 43 42
 15 16 17 18 19 20 39 40 41
 26 25 24 23 22 21 38 37 36
 27 28 29 30 31 32 33 34 35
15:44:17 - 00:01:16


Non mi è chiaro perché tu dica che la casella cul-de-sac ha sempre la parità
giusta. Nel caso della 8x8, potrebbe presentarsi questa situazione:
x21.....
.3......
........
........
........
........
........
........
Qui l'unico cul-de-sac è in x, quindi lì dovrà andare il 64, che però non ha
la parità giusta. Infatti mi sono stupito la prima volta che l'ho fatto
girare con questo controllo che proprio con N=8 ci fossero dei miglioramenti
di velocità. Siccome non avevo considerato ancora la parità mi stupivo che
il 64 non fosse compatibile con i suoi vicini. Poi ho capito che non lo era
perché i suoi vicini erano pari!
Ciao :-)
Giorgio

 di quello perduto nei calcoli.
Non e' vero. Trattasi di banale errore di programmazione. Il guadagno
di tempo ulteriore e' del 27%. Il tempo impiegato ora e' meno di un
terzo di quello che impiegava prima dei vari test sulla passeggiabilita'.
Scusate!!!  ((^__^))'
Livio
 15 14 01 02 03 04 05 06
 16 13 12 11 10 09 08 07
 17 24 25 26 27 28 29 30
 18 23 36 35 34 33 32 31
 19 22 37 38 39 40 41 42
 20 21 64 51 50 49 48 43
 61 62 63 52 53 54 47 44
 60 59 58 57 56 55 46 45
18:10:36 - 00:03:26

 perché i suoi vicini erano pari!
Hai ragione. Mi sono sbagliato. E' che fino a ieri non avevo
mai considerato il divisore 2 nei test, tanto la parita' era sempre
giusta. Diverso discorso e' andare a vedere un cul-de-sac
qualunque. E' stato proprio uno svarione, corroborato dal
fatto che la subroutine che aveva preparato la matrice booleana
dei precalcoli ignorava il divisore 2, e chi se lo ricordava che
avevo fatto una maialata simile?  :o))
Ciao!!!  ((^__^))'
Livio


Ne sei sicuro? Mi pare che qui ci siano alcune differnze, forse significative:
diciamo che in questo caso ciascun numero potrebbe essere visto come un Polysex quadrato con i
quattro lati uguali
però noto che, per quanto riguarda le condizioni al confine, i Polisexes, o meglio i loro lati,
si possono classificare in due categorie:
- *neutri* (come i Sexominoes N o H),
- *sessuati* (come i Sexominoes M e F)
I primi hanno la caratteristica di essere *compatibili con se stessi*, ovvero si possono
accostare solo a lati della stessa specie. Per questi vale la proprietà transitiva: se A è
compatibile con B, e B è compatibile con C, allora A è compatibile con C.
Quelli sessuati non sono compatibili con se stessi, anzi ciascuno è compatibile *solo* con
quelli del sesso opposto. Per i sessuati non vale ovviamente la proprietà transitiva.
Nel problema in questione mi pare che i numeri non rientrino in nessuna delle due categorie. Per
esempio qui non esiste il concetto di *sesso opposto*, o comunque non è unico.
Non sara che i numeri sono dei grandi sporcaccioni?
:-)))
ciao
paolo

 .........
Sicuramenete per la 9x9 bisognava cercare, come punto iniziale, una casella
della stessa parità della casella d'angolo, ne segue che per 3 x sono stati
controlli inutili in partenza e 3 ? su 8 non porteranno sicuramente ad un
risultato utile. Certo per la 10x10 (la prossima candidata) non si possono
fare di queste considerazioni ma penso che siano da tenere in mente per il
futuro :o)
Un saluto,
Gabriele


Accidenti, è vero! :-)
Non ci avevo pensato. Aspetta che lo rispiego per quelli che (come me) non
lo dovessero capire subito. Siccome con N dispari, le caselle totali sono
dispari e quindi bisogna sistemare più numeri dispari che numeri pari,
questi (e in particolare l'1) dovranno occupare le celle "dispari" della
scacchiera, dove sono gli asterischi:
*-*-*
-*-*-
*-*-*
-*-*-
*-*-*
e quindi è inutile provare a partire da dove sono i trattini.
Ciao :-)
Giorgio

 ...
Ci sono ancora gli *ermafroditi* che complicano un po' le cose
soprattutto nei rovesciamenti, dove si differenziano dai *neutri*.
Ma non dimenticare Saffo, Sodoma, Gomorra, Kamasutra,
Tao, Zen...  ;o)
Per restare su un piano di concretezza fisica, potremmo
pensare a dei meccanismi, come a degli incastri scorrevoli.
Proviamo ad inventare un puzzle meccanico che risponda alle
regole di queste matrici, ad es. per N=5. I divisori comuni possono
essere solo 3, 5, 7 e 11, quindi facciamo 4 incastri per ogni lato,
maschi dove il numero d'ordine del pezzo ha quel divisore.
La regola del montaggio sara' solo quella di riuscire a mettere
i pezzi nella scatola, non importa se restano buchi (e' ammessa
la relazione saffica ma non quella sodomitica!  :o))
Per la regola che comtempla che i numeri in successione debbano
essere vicini, costruiamo 2 appendici rotanti per ogni pezzo
(eccetto l'1 e il 25 che ne hanno una sola) recanti delle chiavi
binarie, maschie per il numero seguente e femmine per il
precedente.
Il solito disegnino chiarira' le cose.
Ciao!!!  ((^__^))'
Livio
[FIDOCAD ]
LI 45 35 55 35
LI 55 35 55 30
LI 55 30 75 30
LI 75 30 75 35
LI 75 35 95 35
LI 115 30 115 35
LI 115 35 135 35
LI 135 35 135 30
LI 135 30 155 30
LI 155 30 155 35
LI 155 35 175 35
LI 175 35 175 30
LI 175 30 195 30
LI 195 30 195 35
LI 195 35 215 35
LI 215 35 215 30
LI 215 30 235 30
LI 235 30 235 35
LI 235 35 245 35
LI 245 35 245 45
LI 245 45 250 45
LI 250 45 250 65
LI 250 65 245 65
LI 245 65 245 85
LI 245 85 250 85
LI 250 85 250 105
LI 250 105 245 105
LI 245 105 245 125
LI 95 35 95 30
LI 95 30 115 30
LI 45 35 45 45
LI 45 45 40 45
LI 40 45 40 65
LI 40 65 45 65
LI 45 65 45 85
LI 45 85 40 85
LI 40 85 40 105
LI 40 105 45 105
LI 45 105 45 125
LI 155 75 165 75
LI 165 75 165 85
LI 165 85 160 85
LI 160 105 165 105
LI 165 105 165 115
LI 165 115 155 115
LI 155 115 155 110
LI 135 110 135 115
LI 135 115 125 115
LI 125 115 125 105
LI 125 105 130 105
LI 130 85 125 85
LI 125 75 135 75
LI 135 75 135 80
LI 155 80 155 75
LI 140 95 150 95
LI 145 90 145 100
SA 145 95
TY 135 80 6 3 0 0 0 * 3
TY 140 80 6 3 0 0 0 * 5
TY 145 80 6 3 0 0 0 * 7
TY 150 80 6 3 0 0 0 * 11
TY 135 100 6 3 0 0 0 * Pezzo 14
LI 135 80 145 80
LI 145 80 145 70
LI 145 70 150 70
LI 150 70 150 80
LI 150 80 155 80
LI 160 85 160 95
LI 160 95 170 95
LI 170 95 170 100
LI 170 100 160 100
LI 160 100 160 105
LI 155 110 145 110
LI 145 110 145 120
LI 145 120 140 120
LI 140 120 140 110
LI 140 110 135 110
LI 130 105 130 95
LI 130 95 120 95
LI 120 90 130 90
LI 130 90 130 85
LI 125 85 125 75
LI 120 95 120 90
LI 60 55 70 55
LI 65 50 65 60
SA 65 55
LI 100 55 110 55
LI 105 50 105 60
SA 105 55
LI 140 55 150 55
LI 145 50 145 60
SA 145 55
LI 180 55 190 55
LI 185 50 185 60
SA 185 55
LI 220 55 230 55
LI 225 50 225 60
SA 225 55
LI 60 95 70 95
LI 65 90 65 100
SA 65 95
LI 60 135 70 135
LI 65 130 65 140
SA 65 135
LI 100 135 110 135
LI 105 130 105 140
SA 105 135
LI 140 135 150 135
LI 145 130 145 140
SA 145 135
LI 180 135 190 135
LI 185 130 185 140
SA 185 135
LI 220 135 230 135
LI 225 130 225 140
SA 225 135
LI 220 95 230 95
LI 225 90 225 100
SA 225 95
LI 45 125 40 125
LI 40 125 40 145
LI 40 145 45 145
LI 245 125 250 125
LI 250 125 250 145
LI 250 145 245 145
TY 205 40 6 3 0 0 0 * Scatola 5x5
LI 215 115 210 115
LI 185 115 180 115
LI 205 95 195 95
LI 200 90 200 100
SA 200 95
LI 180 115 180 105
LI 215 115 215 105
LI 215 105 205 90
LI 205 90 195 90
LI 195 90 180 105
TY 195 105 6 3 0 0 0 * 4
LI 185 115 185 110
LI 185 110 190 110
LI 190 110 190 120
LI 190 120 205 120
LI 205 120 205 110
LI 205 110 210 110
LI 210 110 210 115
TY 175 125 6 3 0 0 0 * Chiave masc. 14
TY 185 105 6 3 0 0 0 * 1
TY 190 105 6 3 0 0 0 * 2
TY 200 105 6 3 0 0 0 * 8
TY 205 105 6 2 0 0 0 * 16
LI 75 75 80 75
LI 105 75 110 75
LI 110 75 110 85
LI 75 75 75 85
TY 80 80 6 3 0 0 0 * 1
TY 85 80 6 3 0 0 0 * 2
TY 90 80 6 3 0 0 0 * 4
TY 100 80 6 2 0 0 0 * 16
LI 80 75 80 80
LI 80 80 85 80
LI 85 80 85 70
LI 85 70 90 70
LI 100 80 100 70
LI 100 70 105 70
LI 105 70 105 75
TY 95 80 6 3 0 0 0 * 8
LI 90 70 90 80
LI 90 80 100 80
LI 100 100 110 85
LI 90 100 100 100
LI 75 85 90 100
LI 90 95 100 95
LI 95 100 95 90
SA 95 95
TY 70 60 6 3 0 0 0 * Chiave femm. 13

 Non ci avevo pensato...
I poliformisti... la prima cosa a cui pensano e' la parita'.  :o))))))))
Aggiungo qualche criterio.
Se l'ultimo (NxN) deve finire in un cul-de-sac, allora il penultimo
(NxN-1) ha la posizione segnata. Conviene controllarlo subito,
soprattutto per N=8 e N=10 perche' i penultimi sono divisibili
per 3. Proprio la migliore sol-1 che conosco per N=10 fallisce
per il 99:
 03 02 01 80  81 82 87 88 89 90
 04 75 76 79 100 83 86 93 92 91
 05 74 77 78  -- 84 85 94 45 44
 06 73 60 59  98 97 96 95 46 43
 07 72 61 58  57 56 55 48 47 42
 08 71 62 63  64 65 54 49 50 41
 09 70 69 68  67 66 53 52 51 40
 10 31 32 33  34 35 36 37 38 39
 11 30 29 28  27 26 25 24 23 22
 12 13 14 15  16 17 18 19 20 21       99
Applicata alla ricerca della solita N=8 con partenza fissa (3,1) che
uso come test, il tempo si abbassa ancora in modo sensibile.
Aggiorno il riassunto:
- senza potature: ore...
- con potatura Giorgio: 11'11''
- + i 2 test di passeggiabilita': 4'44''
- + il test dell'ultimo nel cul-de-sac: 3'26''
- + il test del penultimo: 2'21''
Ora, da bravo poliformista, ho colorato le soluzioni che abbiamo
per vedere se fosse saltata all'occhio qualche proprieta', come la parita'.
Salta all'occhio che ci sono dei numeri piu' facili e dei numeri piu'
difficili da piazzare. I piu' facili sono i jolly che si possono sempre
sistemare. Sono le potenze di 2 e i numeri primi >N/2. Quelli piu'
difficili sono quelli che hanno piu' divisori, il 3 e il 5 in testa.
Essi tendono a finire negli angoli, dove hanno meno confinanti.
Il 15, ad es., ha una grande densita' di presenze negli angoli.
Imponendo il backtrack se il 15 non finisce in un angolo ho
ottenuto sulla N=8 di test la soluzione in 8 secondi.  (!)
Questa notte ha girato una ricerca *quasi esaustiva* per N=10
imponendo il 15 e il 45 contemporaneamente negli angoli.
Non sono venute fuori soluzioni, pero' il metodo e' veloce e
potrebbero venirci altre idee simili.
Alla prossima!!!  ((^__^))'
Livio

 Un saluto a tutti, ho postato il problema e poi sono scomparso...
Ma gli Argentini, a che punto sono?
Ciao!!!  ((^__^))'
Livio

 ...
Se e' giusto, ancora meglio!  :o)
In realta' gli incastri devono essere simmetrici, se no non funziona.
Ciao!!!  ((^__^))'
Livio
[FIDOCAD ]
LI 20 30 30 30
LI 30 30 30 35
LI 30 35 40 35
LI 40 35 40 25
LI 40 25 45 25
LI 45 25 45 35
LI 45 35 50 35
LI 50 35 50 25
LI 50 25 55 25
LI 55 25 55 35
LI 55 35 65 35
LI 65 35 65 30
LI 65 30 75 30
LI 75 30 75 40
LI 75 40 70 40
LI 70 40 70 50
LI 70 50 80 50
LI 80 50 80 55
LI 80 55 70 55
LI 70 55 70 60
LI 70 60 80 60
LI 80 60 80 65
LI 80 65 70 65
LI 70 65 70 75
LI 70 75 75 75
LI 75 75 75 85
LI 75 85 65 85
LI 65 85 65 80
LI 65 80 55 80
LI 55 80 55 90
LI 55 90 50 90
LI 50 90 50 80
LI 50 80 45 80
LI 45 80 45 90
LI 45 90 40 90
LI 40 90 40 80
LI 40 80 30 80
LI 30 80 30 85
LI 30 85 20 85
LI 20 85 20 75
LI 20 75 25 75
LI 25 75 25 65
LI 25 65 15 65
LI 15 65 15 60
LI 15 60 25 60
LI 25 60 25 55
LI 25 55 15 55
LI 15 55 15 50
LI 15 50 25 50
LI 25 50 25 40
LI 25 40 20 40
LI 20 40 20 30
EV 45 55 50 60
TY 30 35 6 3 0 0 0 * 3
TY 35 35 6 3 0 0 0 * 5
TY 40 35 6 3 0 0 0 * 7
TY 45 35 6 2 0 0 0 * 11
TY 50 35 6 3 0 0 0 * 7
TY 55 35 6 3 0 0 0 * 5
TY 60 35 6 3 0 0 0 * 3

> ...
Ecco il gioco meccanico che Dario Uri non ha!  ;o))))
I tasselli questa volta sono formati da due meta' di un quadrato
di un certo spessore, tagliato lungo la diagonale, imperniate
tra di loro sull'asse blu. I pezzi, inoltre, sono rovesciabili.
Cosi' si realizza il puzzle della matrice N=5 e, volendo, con lo
stesso principio, anche gli ordini superiori.
Il perno si puo' sostituire con un'altra chiave binaria. In questo
modo il problema si puo' riportare a polimini puri, per la gioia
di Giorgio.  :o))))
Ciao!!!  ((^__^))'
Livio
[FIDOCAD ]
LI 85 55 85 60
LI 85 60 105 60
LI 105 60 105 50
LI 105 50 115 50
LI 115 50 115 60
LI 115 60 125 60
LI 125 60 125 50
LI 125 50 135 50
LI 135 50 135 60
LI 135 60 155 60
LI 155 60 155 55
LI 155 55 175 55
LI 175 55 175 75
LI 175 145 175 165
LI 65 55 85 55
LI 110 110 130 110 2
LI 120 100 120 120 2
LI 85 75 90 80 1
LI 95 85 130 120 1
LI 135 125 140 130 1
LI 65 165 175 55
LI 175 75 170 75
LI 170 75 170 95
LI 170 95 180 95
LI 180 95 180 105
LI 180 105 170 105
LI 170 105 170 115
LI 170 115 180 115
LI 180 115 180 125
LI 180 125 170 125
LI 170 125 170 145
LI 170 145 175 145
LI 115 180 125 180
LI 80 105 80 115
LI 65 80 65 55
LI 65 165 65 140
LI 90 165 65 165
LI 175 165 150 165
TY 85 60 7 4 0 0 0 *  3
TY 95 60 7 4 0 0 0 *  5
TY 105 60 7 4 0 0 0 *  7
TY 115 60 7 3 0 0 0 *  11
TY 125 60 7 4 0 0 0 *  7
TY 135 60 7 4 0 0 0 *  5
TY 145 60 7 4 0 0 0 *  3
TY 70 100 6 3 0 0 0 * 1
TY 70 95 6 3 0 0 0 * 2
TY 70 90 6 3 0 0 0 * 4
TY 70 85 6 3 0 0 0 * 8
TY 70 80 6 3 0 0 0 * 16
TY 70 115 6 3 0 0 0 * 1
TY 70 120 6 3 0 0 0 * 2
TY 70 125 6 3 0 0 0 * 4
TY 70 130 6 3 0 0 0 * 8
TY 70 135 6 3 0 0 0 * 16
TY 20 110 8 5 0 0 0 * femm.13
TY 20 105 8 5 0 0 0 * Chiave
LI 70 105 80 105
LI 80 115 70 115
LI 70 105 70 100
LI 70 100 60 100
LI 60 100 60 95
LI 60 95 70 95
LI 70 95 70 85
LI 70 85 60 85
LI 60 85 60 80
LI 60 80 65 80
LI 70 115 70 120
LI 70 120 60 120
LI 60 120 60 125
LI 60 125 70 125
LI 70 125 70 135
LI 70 135 60 135
LI 60 135 60 140
LI 60 140 65 140
TY 90 185 8 5 0 0 0 * Chiave masc. 14
LI 125 180 125 160
LI 115 160 115 180
LI 125 160 130 160
LI 130 160 130 170
LI 130 170 145 170
LI 115 160 110 160
LI 110 160 110 170
LI 110 170 95 170
LI 95 170 95 160
LI 95 160 90 160
LI 90 160 90 165
LI 145 170 145 160
LI 145 160 150 160
LI 150 160 150 165
LI 145 135 185 175 1
TY 185 175 7 4 0 0 0 * di un semipezzo sull'altro
TY 185 170 7 4 0 0 0 * Asse di rotazione di
TY 185 105 7 4 0 0 0 * Chiave NON-7
TY 185 110 7 4 0 0 0 * come divisore
TY 90 70 8 5 0 0 0 * PEZZO NR: 14
LI 45 30 85 30
LI 85 30 85 25
LI 85 25 115 25
LI 115 25 115 15
LI 115 15 125 15
LI 125 15 125 25
LI 125 25 155 25
LI 155 25 155 30
LI 155 30 195 30
LI 195 30 195 25
LI 195 25 225 25
LI 225 25 225 15
LI 225 15 235 15
LI 235 15 235 25
LI 235 25 265 25
LI 265 25 265 30
LI 285 50 290 50
LI 290 50 290 80
LI 290 80 300 80
LI 300 80 300 90
LI 300 90 290 90
LI 290 90 290 120
LI 290 120 285 120
LI 285 30 285 50
LI 265 30 285 30
LI 285 120 285 160
LI 285 160 290 160
LI 290 160 290 190
LI 45 30 45 25
LI 45 25 20 25
TY 240 35 8 5 0 0 0 * Scatola


Sono qui che non sto nella pelle!!!
Ciao :-)))))
Giorgio

 Ma gli Argentini, a che punto sono?
Italia-Argentina : 9-6
Si sono fermati dicendo che non esistono soluzioni per N=6
Forza Italia!
:o)
Gabriele

 Forza Italia!
E no... eh..
Un saluto.
Gianni
--
Socio fondatore del Luigino Fans Club. Tessera n° 001.
Aderite compatti al Luigino Fans Club (121 aderenti, finora).
"Perchè non venite a morire in Italia, magari mentre trombate qualche
compiacente segretaria bona?" [Cit.: S.B.].


E non è ancora finita!
Dopo il controllo sulle isole, ecco il controllo sulle penisole!!!
L'idea è questa: ogni volta che si mette un nuovo numero, può succedere che
questo formi delle "penisole".
E' sufficiente che l'ultimo numero messo si venga a trovare a distanza di 1
da una casella occupata o un muro e con la casella nel mezzo vuota per avere
due penisole.
Ad esempio, il 3 nella figura seguente forma, tra le altre, due penisole
collegate da x:
1..
23x
...
E' facile osservare che la casella in x si riempirà solo dopo che sarà stata
riempita completamente una delle due isole. Quindi già adesso posso fare i
conti di quale numero potrà andare a finire in x, basandomi sulla dimensioni
di ogni isola. Se entrambe le isole sono formate da un numero dispari di
caselle, non c'è soluzione (ho fatto un po' di studi sulla parità :-) ).
Negli altri casi dovrò vedere se il numero è compatibile con i vicini.
Con questa ulteriore ottimizzazione ho fatto una prova sulla 9x9 fermandomi
ai soli casi, senza soluzioni, con partenza 1,1. (Non ho ancora implementato
le ottimizzazioni di Livio sulla passeggiabilità e sul penultimo.)
Prima richiedeva 631 secondi, ora ne richiede solo 107!
Una riduzione di oltre l'80%!
Ora devo andare. Provo a lanciarlo per N=10 per vedere cosa succede. Sarò di
ritorno nel pomeriggio.
Ciao :-)
Giorgio

 avere due penisole.
   Non so se basta mica, sai: credo che sia necessaria una sequenza di tre 
vuoti tra la penisola e quello che le sta di fronte... Ci devo ancora 
pensare meglio... Poi provo ad implementarlo...
....cosi` come provo ad implemetare la ricerca all'indietro quando si crea 
un corridoio in cui deve andare l'ultimo numero disponibile, si puo` 
pensare di piazzarne ancora altri due, visto che avrebbero la direzione 
"obbligata"...
...per adesso devo ancora finire di implementare il test di 
passeggiabilita`: il mio programmillo ci mette circa una 30ntina di secondi 
per trovare le soluzioni della 7x7 usando il test sulle isole, quello sui 
corridoi e saltando i casi "impossibili" per parita`... Non l'ho ancora 
provato sulla 8x8... (C++ sul mio portatilino con un AMD Duron a 1GHz sotto 
Linux RedHat 7.2 con gcc 3.2.2)... 
Trovate le mie soluzioni 7x7 a:
http://www.pd.infn.it/~peluso/7x7.txt
Long Life & Prosper
Vh
-- 
                          | universi dissidenti, 
\|/ ____ \|/   \ ||_|     | ognuno con legislazione
"@'/ ,. \`@"    \|| |     | fisica autonoma.
/_| \__/ |_\ Vax Headroom |
   \__U_/                 |

 passeggiabilita`
   Fatto... Sulla 7x7 sono passato da circa 30 secondi a poco meno di 20, 
per trovare gli stessi risultati della "via lunga"...
rosario@nbzaphod:matrix > time ./prime 7 > 7x7.txt
real    0m19.791s
user    0m19.730s
sys     0m0.020s
   Adesso sto provando i tempi della 8x8...
Trovate il programmillo su:
http://www.pd.infn.it/~peluso/matrix.tar.gz
Consigli sono benvenuti...
Long Life & Prosper
Vh
-- 
                          |  Del resto mimporta 'nasega sai
\|/ ____ \|/   \ ||_|     |  Ma fatta bene
"@'/ ,. \`@"    \|| |     |  Del resto mimporta 'nasega sai
/_| \__/ |_\ Vax Headroom |  Ma fatta bene che non si sa mai
   \__U_/                 |  Che non si sa mai, che non si sa mai


Queste le ultime notizie: non ci sono soluzioni con partenza in 1,1 e 1,2. I
tempi sono ancora lunghini: circa 5 ore e mezza per questi due casi.
Ho aggiunto qualche ottimizzazione e ho migliorato un po' il codice. Dovrei
aver recuperato un altro 25%.
Faccio ripartire tutto e poi vi so dire.
Ciao :-)
Giorgio


Ho fatto ripartire il tutto e la situazione è questa: i tempi per escludere
soluzioni per 1,1 e 2,1 si sono ridotti a circa 1 ora e 45. Per escludere
soluzioni con 2,2 ci sono volute altre 10 ore e mezza! :-(
Allora ho avuto un'altra pensata: il controllo dei cul-de-sac forzati!
Prendiamo il seguente esempio:
x2y.....
.1......
ecc.
dopo aver messo il 2 si forma un cul-de-sac in x. Se il 3 finisce in x, il
cul-de-sac sparisce e tutto finisce lì. Per questo motivo non si può
propriamente definire un cul-de-sac, è in realtà un mezzo cul-de-sac, direi
quasi una chiapp-de-sac! :-)
Se invece il 3 lo metto in y, allora sì che x diventa un cul-de-sac e quindi
lì deve andare il numero N*N. Se, ad esempio, N=8 ci dovrebbe andare il 64
che per problemi di parità non può starci. Quindi posso concludere che la
mossa in x è forzata e abbandonare da subito l'analisi della mossa in y.
L'analisi è poi più complessa se si considera la contemporanea formazioni di
due o tre chiapp-de-sac, con conseguente ulteriore potatura dei rami. Se se
ne formano 2 e sono entrambi incompatibili, la cosa finisce lì. Se se ne
formano 3 (sarà possibile?), compatibili o no, la cosa finisce comunque lì.
Con questa e altre ottimizzazioni già apportate ieri ho ridotto i 107
secondi di cui parlavo ieri a 23! Tutta l'analisi completa, che porta a una
sola soluzione, della 9x9 viene fatta in meno di 17 minuti! Tutta la 8x8 in
65 secondi.
Ora faccio ri-ripartire tutto e poi si vedrà.
Ciao :-)
Giorgio


L'elaborazione non è ancora terminata, ma una soluzione c'è (dopo 11 ore)!
45 46 89 88 87 86 85 84 83 82
44 47 90 91 76 77 78 79 80 81
43 48 49 92 75 74 73 72 71 70
42 01 50 93 94 95 96 67 68 69
41 02 51 100 99 98 97 66 65 64
40 03 52 57 58 59 60 61 62 63
39 04 53 56 15 16 17 18 19 20
38 05 54 55 14 13 12 23 22 21
37 06 07 08 09 10 11 24 25 26
36 35 34 33 32 31 30 29 28 27
Ciao :-)
Giorgio

 36 35 34 33 32 31 30 29 28 27
Standing ovation per Giorgio, per la sua costanza e per le sue geniali
intuizioni. E pensare che, ad un certo punto di questa storia gia' pensavo
che la sol. per N=8 fosse praticamente impossibile.
Giorgio, non e' che ti viene in mente qualche nuova idea per i
polimini?  :o))))))  Ricordo che il mondo  :o)  sta ancora aspettando
una sol. per i decamini che, guarda a caso, e' un N=10 come questo.
Ciao e complimenti!!!  ((^__^))'
Livio

"Livio Zucca" wrote

Grazie Livio.
Ne approfitto per aggiornarvi sulle soluzioni della 10x10. Finora non ne ha
trovate altre. E' da parecchie ore alle prese con la partenza 5,3. Poi
mancano solo la 5,4 e la 5,5. Penso che ci vorranno ancora diverse ore.
Che cosa è questa soluzione per i decamini che il mondo sta aspettando?
Probabilmente, quando ne hai parlato, ero un po' distratto... :-)
Intendiamoci, lo chiedo solo per curiosità. Non ho alcuna intenzione di
mettermici! :-)
Ciao :-)
Giorgio


Dopo oltre 30 ore l'elaborazione è terminata. Confermo che questa è l'unica
soluzione trovata.
Ciao
Giorgio

 soluzione trovata.
Ciao Giorgio, i miei piů sentiti complimenti per i risultati ottenuti!
Gabriele


Ho fatto una mezza pensata sui polimini passeggiabili. Provo a proporre una
definizione di passeggiabile, di carattere ricorsivo e dicotomico. Prima
però introduco il concetto di "terminale" e di "istmo". Un terminale è un
omino che deve essere o un punto di partenza o un punto di arrivo; tipici
esempi di terminali sono i cul-de-sac. Un istmo è un omino che collega due
(o più) possibili isole, un omino, cioè, che se venisse rimosso
determinerebbe la formazione di due (o più) polimini separati tra loro.
Detto questo, un polimino è passeggiabile se e solo se:
supera tutti i test sul numero di terminali <= 2, supera i controlli di
conteggio delle caselle bianche e nere, supera i controlli di parità e di
colore sui terminali, ecc. e supera anche una "condizione speciale" di cui
parlerò dopo...
e,
qualora esista un istmo, anche i due polimini ottenuti dalla rimozione
dell'istmo, ai quali sia stato riaggiunto l'istmo stesso, attribuendogli
anche la connotazione di terminale, sono passeggiabili.
Un paio di esempi (gli istmi contrassegnati da x e i terminali da t);
***
***
**x**
  ***
  ***
In questo caso la prima serie di controlli viene superata e una volta
spezzato in due e ottenuto:
***
***
**t
e
t**
***
***
entrambi passano i controlli.
Quest'altro caso:
****
*x**
 x
*x**
*x**
 t
supera i primi controlli, lo spezzo in due e ottengo, ad esempio
****
*x**
 x
 t
che alla fine supera tutti i controlli, e questo
*t**
*x**
 t
che una volta spezzato ulteriormente, dà origine a
t
t
che va bene e
*t**
*t**
che li supera pur non essendo passeggiabile. Ecco che viene in soccorso la
"condizione speciale". Se un polimino ha due terminali e questi sono
adiacenti di lato e, considerati come un unico istmo, spezzano il polimino
in più isole allora il polimino non è passeggiabile.
Naturalmente la spezzettatura del polimino iniziale può avvenire in altri
modi ma si dovrebbe arrivare sempre alla stessa conclusione.
A occhio e croce mi sembra una definizione corretta, ma bisognerebbe
controllarla meglio, eventualmente limarla e affrontare anche questa
"condizione speciale" che non mi piace molto; sarebbe preferibile formularla
in altro modo o vedere di farla assorbire da altre condizioni più "belle".
L'implementazione è un po' laboriosa ma fattibile. Ne ho realizzata una, non
tanto per velocizzare ulteriormente il programma in questione perché in ogni
caso penso che affrontare la 11x11 sia fuori portata, ma per interesse fine
a se stesso. Mi sembra che funzioni, ma bisognerebbe testarla meglio e
sarebbe bello implementarla a parte e dotarla di un'interfaccia grafica e
fare test interattivi specifici. Io non credo proprio di avere il tempo per
farlo.
L'interesse vero è per la definizione di passeggiabilità in sé. Mi
piacerebbe che qualcuno verificasse, dal punto di vista teorico, se è
corretta o se si può migliorare o semplificare.
Rimane un sottoproblema che è sia di tipo implementativo che di tipo logico.
Per stabilire se un omino è un istmo, ricorro alla "famosa" ricerca delle
isole. Penso che si possa fare di meglio (e questo può andare a vantaggio
della velocità del programma in oggetto). Mi riferisco alla soluzione del
seguente problema:
dato un qualsiasi polimino, trovare un modo per stabilire se un determinato
omino è un istmo, analizzandone gli omini adiacenti. E' possibile? Io non mi
ci sono ancora messo, ma direi di sì. Penso che sia solo una questione di
valutare i vari casi.
Fatemi sapere se ho detto delle castronerie.
Ciao :-)
Giorgio
P.S. Visto che può darsi che questo thread ormai lo leggano in pochi, mi
sembra che possa valere la pena proporre a parte il problema della ricerca
dell'istmo. Vado ad aprire un nuovo thread.