Newsgroup: it.hobby.enigmi
Titolo: Minacce differenti

In una mia precedente risposta al "Ciao a tutti" di un amico proveniente
da it.hobby.scacchi, ho proposto un enigma che, penso sia passato
inosservato. Dato che invece lo considero interessante, lo riposto con
un titolo appropriato.
 ___ ___ ___
|   | Q |   |
|___|___|___|
| Q | Q |   |
|___|___|___|
| Q | Q |   |
|___|___|___|
 Su questa scacchierina 3x3, ho piazzato 5 Donne  in modo che ciascuna
Donna attacchi un numero
differente di caselle libere, difatti sostituendo a ciascuna donna il
numero di caselle libere minacciate dalla stessa, ottengo:
 ___ ___ ___
|   | 3 |   |
|___|___|___|
| 1 | 4 |   |
|___|___|___|
| 0 | 2 |   |
|___|___|___|
Qual e'  il massimo numero di Donne collocabili su una scacchiera nxn in
modo che ciascuna minacci un numero diverso di caselle libere?    
n=5,6,7,8....
:) ciao dario

 generalizzazione di "L'anno scorso a Mariembad".
Simpatica osservazione! ma penso solo ad una coincidenza. Per il momento
ho:
1,5,8,11,13,16.
Trovati a mano e probabilmente migliorabili (parlo degli ultimi 2)

 :) ciao dario
Ecco una soluzione di 14 Donne sulla scacchiera 6x6:
 ___ ___ ___ ___ ___ ___
| 0 | 1 |   | 6 |   |   |
|___|___|___|___|___|___|
| 2 | 4 | 10|   | 9 |   |
|___|___|___|___|___|___|
| 3 |   |   |   |11 |   |
|___|___|___|___|___|___|
| 5 |12 |   |   |   | 8 |
|___|___|___|___|___|___|
|   |   |   |13 | 7 |   |
|___|___|___|___|___|___|
|   |   |   |   |   |   |
|___|___|___|___|___|___|
Non garantisco che sia il massimo, perche' ho gia' dovuto
tagliare molti rami secchi che forse tanto secchi non erano.
Qui la brute force e' sempre meno bruta...
Per la 7x7 diventa insostenibile.
Suggerirei a Dario di pubblicare la sua 16 Donne, partendo 
da questa potrei cercare di superarla con una Darwin Machine.
Ciao a tutti
Livio
-- 
Posted from 
mta03-acc.tin.it
 [212.216.176.34] 
via Mailgate.ORG Server - 
http://www.Mailgate.ORG

:) ciao dario
.
.
.
.
.
.
.
.
.
.
.
Intatto incassa la soluzione per N=4 (non banale):
3 . 1 0
. 7 4 2
. . . 5
6 . . .
Poi ci risentiamo. 
Ci vorrebbe un PC solo per te!
Ciao   :o)   :o)
Livio
-- 
Posted from 
twingo.tiscalinet.it
 [195.130.224.85] 


:) ciao dario
.
.
.
.
.
.
spoiler
.
.
.
.
.
.
.
.
.
.
Ed ecco la soluzione per N=5:
 ___ ___ ___ ___ ___
| 0 | 2 |   |   | 3 |
|___|___|___|___|___|
| 1 | 7 | 6 | 9 |   |
|___|___|___|___|___|
| 5 |   |   |   | 8 |
|___|___|___|___|___|
| 4 |   | 10|   |   |
|___|___|___|___|___|
|   |   |   |   |   |
|___|___|___|___|___|
N=6 comincia ad essere lunga per il forzabrutista, pero'...
Abbiamo quindi:
1 donna su 4, 5 donne su 9, 8 su 16, 11 su 25, ...?
Mi sembra piu' la distribuzione di una festicciola in famiglia che una serie
matematica!
Eppure...
1,5,8,11,... mi dice qualche cosa...
ecco:
1,5,8,11,15,18,22,25,29,32,35,39,42,46,49,...
E' legata al gioco di Wythoff, che e' la generalizzazione del Nim, che e' la
generalizzazione di "L'anno scorso a Mariembad".
Fantasie?   :o)
Dammi un cenno.


me lo potreste spiegare con parole semplici?
anche le soluzioni, non ho capito niente

anche le soluzioni, non ho capito niente
.
Tutto subito mi son detto: 'cosa c'e' di incomprensibile?'
Poi ho riletto attentamente la mia posta e quella di Dario e mi e' venuto un
dubbio:
Valeria, quando noi diciamo "Donne" non intendiamo "Femmine del Genere
Umano" ma "Pezzi del Gioco degli Scacchi".
Sotto questa prospettiva, studiate le regole e le mosse dei vari pezzi, e'
tutto chiaro?
Cordialmente
Livio     :o)
-- 
Posted from 
laguna.tiscalinet.it
 [195.130.224.86] 


 da questa potrei cercare di superarla con una Darwin Machine.
 
  ___ ___ ___ ___ ___ ___ ___
 |   | 1 | 0 | 6 |   |   |   |
 |___|___|___|___|___|___|___|
 | 3 | 4 | 2 | 8 |   |   |   |
 |___|___|___|___|___|___|___|
 |   |   |   |11 |   |   |   |
 |___|___|___|___|___|___|___|
 | 5 | 9 |10 |13 |   |   |   |
 |___|___|___|___|___|___|___|   
 | 7 |   |   |   |15 |   |   |
 |___|___|___|___|___|___|___|
 |   |   |   |   |   |14 |   |
 |___|___|___|___|___|___|___| 
 |   |   |   |   |   |   |12 |
 |___|___|___|___|___|___|___|
Per correttezza devo dire che questa sol. e' stata trovata per primo
dall'argentino Hector San Segundo.
ciao :) dario

:) ciao dario
SCACCHIERA 7x7
==============
Esaminare tutte le possibili posizioni diventa
praticamente impossibile. Supponiamo di impiegare
1 microsecondo per analizzare una posizione, il
tempo necessario sarebbe di:
2^49*10-6/3600/24/365 =~ 18 anni
Tagliando molti rami secchi all'origine il tempo
puo' diminuire, ma piu' tagliamo, meno siamo
sicuri di aver provato tutte le combinazioni
'promettenti'.
Una Darwin Machine non ci aiuta molto perche' le
soluzioni sono 'isolate'. Provate ad immaginare
una collina n-dimensionale con in ascissa un 
iperspazio n-1 di tutte le variabili in gioco
e in ordinata le soluzioni. Queste
appariranno come picchi isolati. La Darwin
Machine dovra' fare salti da un massimo relativo
all'altro e sara' quindi comparabile ad una
Random Machine, senza trarre nessun vantaggio
dalla selezione. L'unica speranza di trovare
una soluzione in un tempo ragionevole e' che le
soluzioni siano tante, come succede in molti
puzzle geometrici (poliforme).
Ad esempio per n=7 le soluzioni di 16 Donne sono
probabilmente molte. Eccone infatti qualcuna:
 ___ ___ ___ ___ ___ ___ ___
| 0 | 3 |   |   |   | 4 | 2 |
|___|___|___|___|___|___|___|
| 1 | 7 | 9 |   |10 |   | 6 | 
|___|___|___|___|___|___|___|
| 8 |   |   |   |   |11 |   | 
|___|___|___|___|___|___|___|
| 5 |   |12 |16 |   |13 |   |
|___|___|___|___|___|___|___|
|14 |   |   |   |   |   |   | 
|___|___|___|___|___|___|___|
|   |   |   |   |   |   |   |
|___|___|___|___|___|___|___|
|   |   |   |   |   |   |   |
|___|___|___|___|___|___|___|
 ___ ___ ___ ___ ___ ___ ___
| 0 | 5 | 7 |   |   | 8 |   |
|___|___|___|___|___|___|___|
| 3 | 4 |   |13 |   |14 |   | 
|___|___|___|___|___|___|___|
|   |16 |   |   |   |   |   | 
|___|___|___|___|___|___|___|
|   |   |   |   |   |   |17 |
|___|___|___|___|___|___|___|
|   |   |   |   |18 |   |   | 
|___|___|___|___|___|___|___|
|11 |   |   |12 |   |   |   |
|___|___|___|___|___|___|___|
|   |   | 9 | 6 |   |10 |   |
|___|___|___|___|___|___|___|
 ___ ___ ___ ___ ___ ___ ___
| 0 | 5 | 3 |13 |   |   |   |
|___|___|___|___|___|___|___|
| 2 | 8 |   |   |   |   |11 | 
|___|___|___|___|___|___|___|
|   | 9 |   |   |17 |   |10 | 
|___|___|___|___|___|___|___|
|   |   |18 |   |   |   |   |
|___|___|___|___|___|___|___|
|14 |   |   |   |   |   |   | 
|___|___|___|___|___|___|___|
|7  |   |   |   |   |15 |   |
|___|___|___|___|___|___|___|
|   |   |   |   |12 |   | 4 |
|___|___|___|___|___|___|___|
SCACCHIERA 8x8
==============
Stesso discorso per n=8, esasperato nei numeri:
2^64*10^-6/3600/24/365 = 584942 anni.
Comunque ho una soluzione a 18 Donne, anche se
penso sia lontana dal top:
 ___ ___ ___ ___ ___ ___ ___ ___
| 0 | 6 |12 |   |   |   | 4 | 2 |
|___|___|___|___|___|___|___|___|
| 3 | 5 |   |   |10 | 7 | 8 |   |
|___|___|___|___|___|___|___|___|
|   |16 |   |   |   |14 |   |   |
|___|___|___|___|___|___|___|___|
|   |   |   |   |   |   |   |18 |
|___|___|___|___|___|___|___|___|
|   |   |   |   |23 |   |   |   |
|___|___|___|___|___|___|___|___|
| 9 |   |20 |   |   |   |   |   |
|___|___|___|___|___|___|___|___|
|13 |   |   |   |   |   |   |   |
|___|___|___|___|___|___|___|___|
|   |   |   |   |   |   |17 |   |
|___|___|___|___|___|___|___|___|
Ciao a tutti
Livio
[usare un carattere non proporzionale per vedere l'ascii-art]
-- 
Posted from 
twingo.tiscalinet.it
 [195.130.224.85] 


diverso di caselle libere?    
SCACCHIERA 8x8
==============
Questa Random Machine! La fai girare tutta la 
notte e 18 sembra la soluzione migliore che
riesca a trovare. Tempo di postarla e ne trova
una da 19 (!)
 ___ ___ ___ ___ ___ ___ ___ ___
| 6 |   |   |   |   |   |   |17 |
|___|___|___|___|___|___|___|___|
| 1 | 8 |   |   |16 |   |   |   |
|___|___|___|___|___|___|___|___|
| 0 | 3 |   |18 |   |   |   |   |
|___|___|___|___|___|___|___|___|
| 2 |11 |12 |   |   |   |   |   |
|___|___|___|___|___|___|___|___|
|   |   |   |   |   |   |21 |   |
|___|___|___|___|___|___|___|___|
| 7 |   |15 |   |   |   |   |   |
|___|___|___|___|___|___|___|___|
|   |   |14 |   |   |13 | 9 |   |
|___|___|___|___|___|___|___|___|
|   |   |   |   |10 | 5 |   |   |
|___|___|___|___|___|___|___|___|
Ciao
Livio


Stimolato dai messaggi di Dario Uri e Livio Zucca ho messo al lavoro
il mio PC e ho trovato parecchie soluzioni per 17 Donne su una
scacchiera 7x7. Ho fermato il mio programma dopo 450 soluzioni (credo
che il totale sia di qualche migliaio).
La prima trovata e' la seguente
 ___ ___ ___ ___ ___ ___ ___
|   |   |   |15 |   |   |   |
|___|___|___|___|___|___|___|
|   |16 |   |   |   |   |11 | 
|___|___|___|___|___|___|___|
|   |   |   |   |17 |   |   | 
|___|___|___|___|___|___|___|
|   |   |   |   |   |   |12 |
|___|___|___|___|___|___|___|
|   |   |14 |   |   |   |   | 
|___|___|___|___|___|___|___|
|10 | 5 |   | 8 | 9 |   |   |
|___|___|___|___|___|___|___|
| 0 | 4 | 1 | 3 | 2 | 7 | 6 |
|___|___|___|___|___|___|___|
Adesso sto cercando una soluzione per 20 Donne su una scacchiera 8x8;
vedremo se ci saranno novita'.
-- 
Ciao, Damiano

 che il totale sia di qualche migliaio).
...
Complimenti Damiano!
Io so cosa vuol dire rubare ore al sonno per far
girare questi parti della mente.
Mi stupiscono anche le tante soluzioni trovate.
Hai un metodo efficiente. Hai voglia di raccontarcelo
un po', metodo, linguaggio, PC?
Hai gia' provato con le poliforme?
Ciao
Livio
-- 
Posted from 
mta02-acc.tin.it
 [212.216.176.33] 


 che il totale sia di qualche migliaio).
Credo che si potrebbe aggiungere il vincolo che le minacce, oltre ad essere
*differenti* debbano essere *progressive*, da 0 a n-1. La soluzione
dell'argentino postata da Dario per la 7x7 con 16 donne, rispettava il
vincolo. Che ne dite?
Silv:o)

n=5,6,7,8....
Dopo qualche ora di lavoro con il mio PC, ho trovato alcune soluzioni
(30) per 20 Donne su una scacchiera 8x8.
La prima trovata é la seguente:
 ___ ___ ___ ___ ___ ___ ___ ___
|16 |   |   |   |   |   |   |12 |
|___|___|___|___|___|___|___|___|
|   |   |   |   |   |18 |   |   |
|___|___|___|___|___|___|___|___|
|   |19 |   |   |   |   |   |13 |
|___|___|___|___|___|___|___|___|
|   |   |   |   |   |   |   |   |
|___|___|___|___|___|___|___|___|
|   |   |   |   |   |17 |   |   |
|___|___|___|___|___|___|___|___|
|   |   |   |   |   |   |15 |   |
|___|___|___|___|___|___|___|___|
| 9 |10 |   |11 |14 |   | 8 |   |
|___|___|___|___|___|___|___|___|
| 0 | 6 | 7 | 3 | 1 | 2 | 5 | 4 |
|___|___|___|___|___|___|___|___|
Come potete vedere la disposizione e' *progressiva* come suggerito da
Silvio Sergio. In tutti i casi ci sono soluzioni di questo tipo. le
postero' prossimamente.
Ricapitolando:
Scacchiera 3x3 ->  5 Donne (   8 soluzioni)
Scacchiera 4x4 ->  8 Donne (   8 soluzioni)
Scacchiera 5x5 -> 11 Donne (  64 soluzioni)
Scacchiera 6x6 -> 14 Donne (4160 soluzioni)
Scacchiera 7x7 -> 17 Donne (forse centinaia di migliaia di soluzioni)
Scacchiera 8x8 -> 20 Donne (??????? soluzioni)
Naturalmente le soluzione sono complessive e comprendono anche le
possibili riflessioni e rotazioni.
Si nota facilmente che il numero massimo delle Donne aumenta di 3 ad
ogni aumento della dimensione della scacchiera.
C'e' qualche volontario che vuole trovare una disposizione di 23 Donne
su una scacchiera 9x9? Il mio PC ormai e' fuso :-))
Se a qualcuno interessa posso inviare tutte le soluzioni trovate.
-- 
Ciao, Damiano Scapeccia

Damiano,
complimenti per il risultato!
Hai fatto sicuramente un programma molto efficiente.
Ciao
Livio
-- 
Posted from 
mta16-acc.tin.it
 [212.216.176.47] 



Il mio PC e' ormai un po' vecchiotto, un Pentium 166 cloccato a 200
MHz, ma lavora ancora egregiamente. Ho scritto il programmma in C
compilato con Borland per DOS. 
L'algoritmo usato e' proprio forza bruta: uso un vettore di n^2
elementi, che rappresenta la scacchiera sviluppata linearmente; in
questo vettore indico con '1' le caselle occupate dalle Donne e con
'0' quelle vuote, quindi genero tutte le combinazioni possibili con un
mio metodo e per ognuna analizzo la distribuzione dei punteggi.
Fino alla scacchiera 5x5 é abbastanza veloce (meno di 2 minuti) mentre
per generare tutte le soluzioni di 14 Donne sulla 6x6 ho impiegato
circa 12 ore.
Non so proprio cosa siano le poliforme, io sono un programmatore
autodidatta che per passione ha imparato qualche linguaggio (in ordine
FORTRAN, BASIC, ASSEMBLER, C9 e mi appassionano gli algoritmi. Mi
potresti dare qualche informazione a proposito di queste poliforme?
Forse potrebbero interessarmi.
Se conosci il C e vuoi dare un'occhiata al mio programma scrivimi e ti
invio il sorgente per email.
-- 
Ciao, Damiano

vincolo. Che ne dite?
Ecco fatto!
Soluzione *progressiva* di 17 Donne su 7x7
 ___ ___ ___ ___ ___ ___ ___
|   |   |   |10 |   |   |   |
|___|___|___|___|___|___|___|
|   |   |   |14 |   |   |   | 
|___|___|___|___|___|___|___|
|   |   |   |   |   |16 |   | 
|___|___|___|___|___|___|___|
|   |   |15 |13 |   |   | 9 |
|___|___|___|___|___|___|___|
|12 |   |   |   |   |   |   | 
|___|___|___|___|___|___|___|
| 1 | 7 |   |11 |   |   |   |
|___|___|___|___|___|___|___|
| 0 | 3 | 2 | 5 | 8 | 6 | 4 |
|___|___|___|___|___|___|___|
Altre esempi di soluzioni *progressive* da 3x3 a 8x8 sono state gia'
postate.
Le soluzioni *progressive* sono:
Scacchiera 3x3  ->  5 Donne (   8 soluzioni *progressive*)
Scacchiera 4x4  ->  8 Donne (   8 soluzioni *progressive*)
Scacchiera 5x5  -> 11 Donne (  48 soluzioni *progressive*)
Scacchiera 6x6  -> 14 Donne (1232 soluzioni *progressive*)
Scacchiera 7x7  -> 17 Donne (  77 soluzioni *progressive* trovate)
Scacchiera 8x8  -> 20 Donne (   5 soluzioni *progressive* trovate)
Naturalmente come avevo gia' scritto non ho trovato tutte le soluzioni
per le scacchiere 7x7 e 8x8: credo che non basterebbe la mia vita.
Ciao, Damiano 

 complimenti per il risultato!
Mi associo. Ciao :) dario