Il problema delle otto regine

[ZioGiò]

Ciao a tutti!

Ecco un problemino abbastanza famoso e divertente di algoritmica:

Scrivere un programma che individui tutte le possibili soluzioni al seguente problema, detto delle "otto regine":
"si abbia una scacchiera 8 * 8 e otto regine ognuna ostile a tutte le altre; si trovi una posizione per ciascuna regina in modo che nessuna di esse possa essere mangiata dalle altre."

Qualcuno sa dirmi se si riesce anche a risolverlo con una funzione ricorsiva?

Saluti!

[Pasquale]

Questo è un programma in Decimal Basic che scrissi velocemente (senza badare alla perfezione) tempo fa, per la ricerca veloce di qualche soluzione al problema (almeno una) per scacchiere di lato n variabile (in rapporto all'accettabilità dei tempi di elaborazione, il programma accetta fino a scacchiere 13x13, a partire da 4x4).
Ogni soluzione è rappresentata da una riga di n numeri che indicano ciascuno la posizione di una regina su una riga, a partire dalla prima riga in alto e dalla prima casella di sinistra (es: nella soluzione 7 5 3 1 6 8 2 4, per scacchiera 8x8, 7 vuol dire settima casella da sinistra della prima riga dall'alto; 5 la quinta casella da sinistra della seconda riga dall'alto, ecc.)
Lancia il programma e appena vedi che inizia a scrivere, fai stop, perché una soluzione utile è uscita (il programma non ricerca tutte le soluzioni possibili).
Non ho mai studiato altro tipo di programma, passato il momento in cui mi interessava la cosa.

DO
INPUT PROMPT "inserisci lato scacchiera fra 4 e 13 -> ": l
LOOP WHILE l13
PRINT

dim a(l)
randomize
do
10
for m=1 to l
20
LET x=1 + int(rnd*l)

for n=1 to m-1
if a(n)=x then goto 20
next N
LET a(m)=x
if m<l then
for n=1 to m-1
if a(n)=x-m+n or a(n)=x+m-n then
mat a=zer
goto 10
end if
next N
else
for n=1 to m-1
if a(n)=x-m+n or a(n)=x+m-n then
mat a=zer
goto 10
end if
next N

end if
next M
for m=1 to l
print a(m);
next M
print
mat a=zer
loop

[ZioGiò]

Ciao!

Secondo me il problema ha 92 soluzioni...
Sono di fretta e non ho qui il sorgente che serve al calcolo (quando l'avevo risolto avevo utilizzato diverse librerie grafiche di visualbasic che complicano parecchio il codice.) Comunque se vuoi vedere l'effettone e dirmi se qualche soluzione combacia con la tua puoi trovare il mio programma a:
http://www.lyra.net/ottoregine.exe

Appena posso ti posto il sorgente (epurato dalla parte grafica)

Saluti!

[0-§]

In realtà le soluzioni sono 12,se non contiamo le otto soluzioni che cisacuna di esse produce via riflessioni e rotazioni(una di esse ne produce solo 4 per la sua simmetria interna,quindi 11*8+1*4=92 e la matematica é salva)
Ecco qui:

[0-§]

Le 12 scacchiere sono quelle più a sinistra(prego ignorare quei neri massicci montuosi sulla destra).
Per Panurgo:come fai a mettere le immagini a metà del messaggio,tra peezi di testo,e non in fondo?
Per Fabio:sto studiandomi il Ghersi,come promesso.E' più difficle del prevsito,quindi ci metterò un po'.Preparati...
Intendo postare comunque sul forum i problemi per ora mandati solo a ZioGiò,Fabio insomma:Zio,posso metterli qui o preferisci di no?
Saluti dal mottolerrimo
0-§

[Daniela]

vogliamo i problemi laidi e subito
anzi li pretendiamo - per favore

[ZioGiò]

Heilà!

Ecco il primo risultato:


Bello il discorso sui 12 risultati più le varie simmetrie... Hai messo in luce la differenza tra forza bruta e intelligenza matematica
A questo punto dovresti provare a scrivere un programma che fa meno cicli del mio (15398, un bel numerino... Ci mette 4 secondi a farli girare tutti) e restituisce le simmetrie. Così risparmi un bel po' di memoria...

sto studiandomi il Ghersi,come promesso.E' più difficle del prevsito,quindi ci metterò un po'.Preparati...

Tranqui... Io sto studiando il Ricci (di analisi), un libro scritto a mano. Farei volentieri scambio

Zio,posso metterli qui o preferisci di no?

Boh, fai un po' tu. Probabilmente si meritano un topic a parte. Qualcosa come "I problemi scacchistici di 0-§", oppure "Come farvi venire il mal di testa ogni volta che sentite la parola cavallo, alfiere, collina e scacchiera"

vogliamo i problemi laidi e subito anzi li pretendiamo - per favore

0-§ non vorrai deludere un pubblico così impaziente?

Saluti!

ZioGiò

[mathmum]

ZioGiò, il Ricci!!!!!
Mamma mia, si studia ancora "lì"????
Ma sei alla facoltà di Mate a Milano, o lo fai per diletto?
(però devo dire che per i controesempi, se non ricordo male, è abbastanza imbattibile!!!)
in bocca al lupo... sono due bei volumozzi (ancora grigi? la scrittura a mano e il grigio della copertina sono deprimenti)
ciao

[Ospite]

ZioGiò, il Ricci!!!!!

Sapevo che la cosa avrebbe colpito i più "anzianotti" del forum
un mio mitico professore di fisica del liceo è stato uno dei due che hanno passato l'esame di analisi 1 col Ricci a Fisica nel lontano NonSoCheAnno... E' da lui che l'ho sentito nominare per la prima volta.

Mamma mia, si studia ancora "lì"????

No, diciamo che l'ho preso per "diletto"... Il libro consigliato è assolutamente vago (non scrivo il titolo, prima di fare la fine del tuo allievo (a proposito, hai avuto un po' di clemenza?) e offendere qualcuno) e mi interessava approfondire alcuni argomenti come i numeri complessi. Ovviamente sono riuscito a provare a dimostrare un esercizio il cui risultato sul libro è sbagliato... E prima di affidarmi al calcolo di Derive c'ho messo un po' perchè pensavo di essere io a non aver capito niente... Vabbé!

sono due bei volumozzi (ancora grigi? la scrittura a mano e il grigio della copertina sono deprimenti)

Devo dire che, abituato come sono ai libri scritti al computer (o, al peggio, scritti a macchina) la prima volta che l'ho visto mi è venuto da sorridere... Mi sentivo come Fra Luca Bartolomeo de Pacioli tra le miniature medioevali...

Ma sei alla facoltà di Mate a Milano

No; la firma mi è stata riportata da un amico che bazzica da quelle parti. Sembra stia sulla porta di qualche professorone... Nella versione originale suonava come "Se sei qui per un problema e non hai la sua soluzione allora sei parte del problema"

Byez!

[ZioGiò]

Curioso.. Pensavo di essere loggato... Invece...
Misteri dell'informatica!

[delfo52]

ad uso e consumo di chi non so, presento alcuni testi di mate. che ho trovato in un recente trasloco. Tenetevi forte!
Mineo Chini: Corso speciale di matematiche con numerose applicazioni ad uso principalmente dei chimici e dei naturalisti. Giusti (Livorno) 1929-ottava edizioneProf. Enea Bortolotti: Geometria analitica e proiettiva-lezioni redatte per uso degli studenti (Università Firenze 1938) ed.Cedam
dello stesso autore: Geometria descrittiva-1939
Prog. G.Sansone:Lezioni di analisi matematica redatte per uso degli studenti (Università Firenze)ed Cedam -I vol:1934 II vol:1936

Sono disposto a mandarli in visione

[Daniela]

la geometria proiettiva non ha incontrato grandi fortune dopo la seconda guerra mondiale e se qualcuno e' appassionato del genere, quel testo potrebbe esseere ancora "attuale". Gli altri tre probabilmente dicono molto sull'evoluzione (evoluzione?) della scuola italiana degli ultimi sette decenni o giu' di li'. Raccontaci di piu'.
(Li vedrei molto volentieri ma non vorrei mai che qualchedue vivacissimi personaggi li riducessero irrimediabilmente a brandelli!!!!!!!!! Se qualcuno ha voglia di scannerizzarli...)
d.

[mathmum]

Sapevo che la cosa avrebbe colpito i più "anzianotti" del forum

ZioGiò io sul Ricci CI ho studiato, inteso come libro, non come prof! Pensavo che alla facoltà di Milano di Mate fosse ancora in uso...20 anni dopo di me! Okkio che se mi fai passare da anzianotta un'altra volta ti faccio le ossicine a pezzetti come quelle di M. !!!!

A proposito. Finisco ora un bel paio di ore di analisi col suddetto M. che si è presentato in versione multicolor davanti al mio ghigno hehehehehe ha ammesso la sua, come dire... pollaggine (siamo educati noi anzianotti GRRRRR). Comunque l'ho massacrato lo stesso. Problemi standard posti in modo non-standard, giusto per capire se aveva capito.... ma non ha capito.... perchè non ha studiato.... oggi mi sento una mateprof molto cattiva.

[Daniela]

Ma se il malcapitato davvero avesse capito, non avrebbe avuto ne' avrebbe mai piu' in futuro bisogno di studiare

[ZioGiò]

ZioGiò io sul Ricci CI ho studiato

Sì, l'avevo intuito
L'aneddoto sul mio prof. è giusto per sottolineare gli infiniti rimandi di un semplice nome... Sembra che per essere ammesso all'esame con Lui bisognasse superare una prova scritta di 2 ore e un colloquio di altre 2 ore con i suoi assistenti... Fatto questo al primo colpo (ci erano riusciti in 7) il mio mitico prof. si è visto segare, dopo un'ora di colloquio, dallo stesso Ricci in quanto aveva dimenticato una delle 5 ipotesi di non so quale teorema minore... L'autore del nostro libro preferito (?!) è certamente più cattivo di certe giovani mateprof

Pensavo che alla facoltà di Milano di Mate fosse ancora in uso

Beh, si sono aggiornati, credo. Basta utilizzare il Cateni-Bernardi che a farlo tutto bene è già pregevole...

Okkio che se mi fai passare da anzianotta un'altra volta ti faccio le ossicine a pezzetti come quelle di M.

Chiedo venia.... Basta cambiare sistema di riferimento e i giovani diventano infanti e gli anzianotti giovani :

Problemi standard posti in modo non-standard, giusto per capire se aveva capito.... ma non ha capito.... perchè non ha studiato....

Come sempre è solo questione di tempo... Quando diventerà un po' più anzianotto troverà i tuoi quesiti molto facili ma gliene veranno richiesti ben altri.

E dopo questa metafora pascolian-leopardiana della vita vi saluto!