Disposizione di regine su una scacchiera

Sancho Panza · Messaggio da **Sancho Panza** » ven apr 20, 2007 10:23 pm

Vi propongo un altro problema che ammette soluzione con struttura in funzione di (N modulo 6)
Questo problema è decisamente più semplice del precedente riguardante le biglie numerate.

Problema: Disposizione di regine
Su una scacchiera NxN (con N>3) disporre N regine in modo tale che non ci siano regine che si diano scacco a vicenda.
La soluzione deve essere valida per qualsiasi N>3

La soluzione che ho trovato io è in funzione di (N modulo 6), cioé:
- ho una struttura valida per N multiplo di 6
- ho una struttura valida per (N Modulo 6) = 1
- ho una struttura valida per (N Modulo 6) = 2
- ho una struttura valida per (N Modulo 6) = 3
- ho una struttura valida per (N Modulo 6) = 4
- ho una struttura valida per (N Modulo 6) = 5

Spero di confrontarmi presto con le vostre soluzioni.

Hasta luego,

Sancho Panza

Jumpy94 · Messaggio da **Jumpy94** » sab apr 21, 2007 7:24 pm

Non mi azzecco neppure a questo problema, in quanto sarebbe al di sopra delle mia capacità, ma voglio precisare una cosa, che forse può essere utile: in giergo scacchistico è assurdo dare scacco (o scacco matto!!!) alla regina

. Forse tu intendi (anzi è così), che le regine non sono in grado di prendersi a vicenda. Questa è solo una precisazione, dato che di scacchi un pochino me ne intendo.

jepa · Messaggio da **jepa** » dom apr 22, 2007 3:11 pm

Spero di aver bene interpretato il problema, la soluzione che propongo è valida per ogni N, basta mettere la regine consecutivamente una all'altra muovendole con la mossa del cavallo. In pratica partendo dall'angolo in alto a sinistra della scacchiera metto la prima, poi la seconda va 2 posizioni in avanti e una in basso e così via fino alla fine della riga.
Quando non ce ne stanno più nella riga vado a capo

cioè riparto una riga sotto all'ultima regina posizionata, nella seconda colonna e si ricomincia.

Immagine

jepa · Messaggio da **jepa** » dom apr 22, 2007 3:14 pm

Mmmm,ma volevi dire che sulla stessa scacchiera per esempio prendendo una sottoscacchiera 4x4 deve essere risolto il problema?
Ci ho pensato ora.
Il mio sistema vale se tu crei una qualunque NxN e disponi così le regine.

jepa · Messaggio da **jepa** » dom apr 22, 2007 3:23 pm

Ah tra l'altro il mio sistema vale x N > 4, per la 4x4 si deve saltare una riga dopo la seconda regina!

Sancho Panza · Messaggio da **Sancho Panza** » dom apr 22, 2007 3:40 pm

Nel tuo esempio, Jepa, la prima e l'ultima regina sono sulla stessa diagonale.

Forse riesci a visualizzarlo meglio tramite la figura qui sotto:

jepa · Messaggio da **jepa** » dom apr 22, 2007 3:52 pm

Hai ragione sancio, e tra l'altro ho notato che in effetti il mio è stato un esempio sfortunato perchè il mio sistema è valido se si escludono le scacchiere con N multiplo di 4. In effetti mi ero accorto che col 4 non andava ma non avevo fatto caso che è un problema che si ripete con tutti i suoi multipli

jepa · Messaggio da **jepa** » dom apr 22, 2007 4:02 pm

Scusate ecco l'immagine

ZioGiò · Messaggio da **ZioGiò** » dom apr 22, 2007 5:33 pm

Se ho ben capito è una generalizzazione del problema delle 8 regine.
https://www.base5forum.it/viewtopic.php? ... tto+regine
Quindi, in questo caso, N è una variabile, non una costante generica ma fissata...
Insomma si cerca l'algoritmo che permetta, in funzione di N di posizionare le regine.
Non riuscirei neanche a dire se all'aumentare di N il n° di soluzioni possibili (per N=8 sono 92) aumenti o diminuisca... Sembrerebbe aumentare, ma non è detto che sia monotono...

@Jumpy94
Anche "minacciarsi" a vicenda andrebbe bene

Ciauz!

Sancho Panza · Messaggio da **Sancho Panza** » lun apr 23, 2007 10:20 pm

Mi spiace Jepa, ma il tuo sistema non solo non è valido per N multiplo di 4,
ma non è valido neppure per qualsiasi N pari o multiplo di 3.

Il tuo sistema vale solo per (N modulo 6 =1) o (N modulo 6 = 5).
Nella figura qui sotto ti dimostro che non funziona se N è pari o multiplo di 3:

Jumpy94 · Messaggio da **Jumpy94** » mar apr 24, 2007 7:56 pm

Visto che siamo in tema di scacchi....

Due giocatori (di scacchi) hanno a disposizione chi 3 e chi 5 regine. La scacchiera è del formato 5X5. Quante disposizioni possiamo avere affinché le regine dei due giocatori non si possano "minacciare"(anche se questo termine mi pare che viene usato in altre situzaioni particolari.....mi pare

)

jepa · Messaggio da **jepa** » mar apr 24, 2007 9:52 pm

Mmmm eh si già già già...
Hai ragione Sancho!!
Tu sei riuscito a trovare un sistema migliore?
Io non riesco a ipotizzare di meglio.

giobimbo · Messaggio da **giobimbo** » mer apr 25, 2007 5:54 pm

Ho appena finito di disegnare quello che penso sia la soluzione, devo ricontrollare e poi mettere tutte le tabelle sotto forma di testo, comunque il procedimento è questo: divido la scacchiera in due, orizzontalmente, poi adeguo la posizione delle regine in modo lineare rispetto alla crescita, così che in ogni ingrandimento si possa riconoscere la configurazione di partenza.

Per n = 4 + 6k e n = 6 +6k divido le scacchiere in metà.

Per n = 8 + 6k la parte superiore è alta 6 + 3k, quella inferiore 2 + 3k.

Per n = 5 + 6k e n = 7 + 6k la parte superiore è alta (n + 1)/2, quella inferiore (n - 1)/2.

Per n = 9 + 6k la parte superiore è alta (n - 1)/2, quella inferiore (n + 1)/2.

A domani.

Dunque, domani è arrivato oggi ma ha portato brutte nuove: errore nella costruzione di scacchiere del tipo n = 8 + 6k e n = 9 + 6k. Per il momento passo palla.

Ultimo aggiornamento di giovedì: dividendo le scacchiere dispari in 3 parti e quelle pari in 2 mi mancano solo le scacchiere del tipo 8 + 6k

Sancho Panza · Messaggio da **Sancho Panza** » gio apr 26, 2007 10:54 pm

Per Giobimbo
Giobimbo, spero che tu riesca a sistemare la tua soluzione
perché l'idea era giusta e confido nelle tue ottime capacità.

Per ZioGio
Ho provato a verificare quante soluzioni possibili ci siano al variare di N.
Questi sono i risultati trovati fino a N=14,
(le mie limitate capacità di programmatore non mi permettono di andare oltre)

Per N = 4 si hanno 2 soluzioni possibili
Per N = 5 si hanno 9 soluzioni possibili
Per N = 6 si hanno 4 soluzioni possibili
Per N = 7 si hanno 40 soluzioni possibili
Per N = 8 si hanno 92 soluzioni possibili
Per N = 9 si hanno 352 soluzioni possibili
Per N = 10 si hanno 724 soluzioni possibili
Per N = 11 si hanno 2680 soluzioni possibili
Per N = 12 si hanno 14200 soluzioni possibili
Per N = 13 si hanno 73712 soluzioni possibili
Per N = 14 si hanno 365596 soluzioni possibili

Jumpy94 · Messaggio da **Jumpy94** » ven apr 27, 2007 7:28 pm

mmmmmm......
Credo che il mio quesito sia stato respinto forse perché troppo semplice

......comunque, per far finta che qualcuno abbia risposto, mi do da solo una soluzione.
Ma non credete di scamparla, aprirò un topic dove metterò uno schema abbastanza difficile........

Ciao!!!