Newsgroup: it.hobby.enigmi
Titolo: Le 8 Regine

     perň  ce l'ha fatta!
A chi interessa, ho un programma che scrissi diverso tempo fa (sotto
DOS :-) per la risoluzione del problema delle n regine (n a piacere),
che scova tutte le soluzioni. Comunque, č un problema stranoto, sono
sicuro che anche in rete si trovano programmi di risoluzione.
-- 
Topoldo  
www.pianetalinux.com
(Grazie a Dio, sono ateo)

 che scova tutte le soluzioni.
Il problema sta nella ottimizzazione del programma. Ad es. quanti
secondi impiega per trovare le sol per n=17, che sono 11.977.939 ? E'
buono se sta sotto i 10.000 secondi. Fammi sapere.
:) dario

buono se sta sotto i 10.000 secondi. Fammi sapere.
No, non sta sotto. Con un po' di impegno mi potrei mettere a guardare
se esistono delle tecniche di ottimizzazione, ma non saprei per adesso
da dove cominciare e dove informarmi. Immagino comunque che sia un
problema ampiamente affrontato nello studio degli algoritmi.


No, non sta sotto.
10.000 sarebbe 10 secondi o 10mila secondi?
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
ZOOGE

 10.000 sarebbe 10 secondi o 10mila secondi?
10mila.
Il programma di Francesco Balena, piuttosto ottimizzato (vedi MC
Microcomputer 131 agosto 1993) impiegava per la scacchiera 17*17 appunto
9540 secondi su un 486/66 MHz.
Con lo stesso programma ho contato proprio ieri le sol. per il 18*18.
Sono 28.693.992.
Mi avventuro per il 19*19. Le sol. dovrebbero essere piu' di
300.000.000. Stimo un tempo di circa 60mila secondi. Appena finito ti
sapro' dire.
ciao :) dario

 ciao :) dario
Ho riesumato un mio programma per le N regine scritto tanti anni fa per
scopi
ludico-didattici che allego volentieri. Calcola le soluzioni per 17 regine
in circa 38.000 secondi su un Pentium II-333. Le soluzioni sono però
95.815.104. Queste sono tutte le posizioni diverse guardando la scacchiera
da un unico punto di vista, incluse quindi le disposizioni speculari e
ruotate che sicuramente il programma cui Dario fa riferimento rimuove.
(Probabilmente avrete già discusso della rimozione delle posizioni speculari
e ruotate, ma purtroppo - vedi P.S. a fine messaggio - non ho più traccia
dei messaggi inviati prima del 20 luglio scorso.)
Il mio programma quindi trova tutte le soluzioni e non è particolarmente
ottimizzato ma è interessante perché è ricorsivo e come ogni programma
ricorsivo è elegante, essenziale e "magicamente" funziona! Spero possa
interessare a qualcuno.
Ecco il listato in C:
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
typedef int BOOL;
#define FALSE 0
#define TRUE 1
#define N 8
int scac[N + 1];
long cont = 0;
void metti(int n, int pos);
BOOL vabene(int n, int pos);
void stampasol(void);
void metti(int n, int pos)
{
 int i;
 if (vabene(n, pos))
 {
  scac[n] = pos;
  if (n == N)
  {
   stampasol();
   cont++;
  }
  else
   for (i = 1; i <= N; i++)
    metti(n + 1, i);
 }
}
BOOL vabene(int n, int pos)
{
 int i;
 for (i = 1; i < n; i++)
  if (scac[i] == pos || n - i == abs(pos - scac[i]))
   return FALSE;
 return TRUE;
}
void stampasol()
{
 int i;
 for (i = 1; i <= N; i++)
  printf("%d ", scac[i]);
 printf("\n");
}
int main(int argc, char* argv[])
{
 int i;
 for (i = 1; i <= N; i++)
  scac[i] = 0;
 time_t starttime = time(NULL);
 for (i = 1; i <= N; i++)
  metti(1, i);
 printf("Tempo trascorso: %ld\n", time(NULL) - starttime);
 printf("Soluzioni trovate = %ld\n", cont);
 return 0;
}
Ciao Dario e ciao a tutti!
P.S. Ne approfitto per scusarmi per le eventuali risposte a miei messaggi
postati una quindicina di giorni fa a cui non è seguita da parte mia alcuna
replica. Sono infatti partito per le ferie poco dopo averli scritti e per 2
settimane sono rimasto (felicemente) isolato dal resto del mondo. :)