Newsgroup: it.comp.lang.visual-basic
Titolo: [?] Le 8 regine

Un mio collega mi ha detto che all'università gli fu dato da realizzare un
software che gestisse la posizione su una scacchiera di otto regine in modo
che nessuna potesse essere mangiata dall'altra.
Mi piacerebbe impostare il
problema insieme a qualcuno di voi, chi vuole cimentarsi?
La scacchiera
potrebbe essere una matrice 8x8 dove 0 indica cella vuota e 1 cella con
regina....
--------------------------------
Inviato via 
http://usenet.iol.it

 regina....
Mi piace un sacco. Chiedo 50 euro l'ora. Dimmi quando...
Sto scherzando (ma non troppo).
In qualche momento di fusione ci penserò, giusto per svagarmi dal solito VB
gestionale.


Scusate ma non ci starebbe bene un bel [OT] su questo thread?

>Scusate ma non ci starebbe bene un bel [OT] su questo thread
ok,
scusa.


>Scusate ma non ci starebbe bene un bel [OT] su questo thread
ok,
scusa.



Perche', non e' un NG di programmazione? Mi pare un problema simpatico...
Claudio Valerio
Analista Programmatore
XXI.it S.r.l.
www.xxi.it

 Perche', non e' un NG di programmazione? Mi pare un problema
simpatico...
Infatti! Il problema e' simpatico, ma questo e' un newsgroup che si
occupa di visual basic, non di programmazione o di algoritmi in genere.
Un bel diversivo insomma, ma nel rispetto del manifesto (questo
sconosciuto) =))))
Lokar
----------
Sito Comune: 
http://www.it-lang-vb.net/
Manifesto: 
http://www.it-lang-vb.net/docs/Manifesto.txt

 ha scritto nel messaggio
news:213Z26Z221Z98Y1...@usenet.iol.it...

Volentieri, peccato che so già la soluzione
dato che è un classico insieme con
a) Problema del commesso viaggiatore
b) Problema del cavallo
c) Torre di Hanoi
d) Problema dei matrimoni misti
        (per chi non conoscesse il problema del cavallo
         consiste nel trovare il percorso da far compiere ad
         un cavallo sulla scacchiera in modo da ricoprire
        tutte le caselle senza ripassare su una casella già visitata
        ovviamente con la mossa classica del cavallo)
                                        danilo


=> In un NG su Visual Basic non si puo' parlare di programmazione o
algoritmi in genere? Mah... lo trovo limitativo... e di che si parla, solo
della sintassi?
Ciao


la cosa che mi incuriosisce è che lui dice che fondamentalmente si risolve
con una funzione ricorsiva di un paio di righe



A questo punto posso SOLO re-invitare ad una lettura del manifesto.
Happy Coding =)
Lokar.LeggiFirmaConAttenzione(True)


>Manifesto: 
http://www.it-lang-vb.net/docs/Manifesto.txt
Letto, trovato molto interessante, ma non cambio opinione. Tenere fuori la
programmazione da un NG su un linguaggio di programmazione sarebbe come fare
una crostata senza la farina.


 regina....
CUT
è roba da laureandi......bravissimi in queste cose...e con un sacco di tempo
da perdere....
anzi....la soluzione è a
http://webservices.polito.it/matdid/3ing_inf_N2172_TO_0/lucidi/55
insieme ad altra roba (interessante da un punto di vista didattico)
ed è in C ....linguaggio molto adatto a fare le ricorsioni in maniera
velocissima (prova a farle in VB e vedi!)...cmq...dai...scrivine una
versione ottimizzata per vb6....e chi per net???...la aspettiamo!
Ciauz!

 una crostata senza la farina.
Tua liberissima opinione. Senza voler creare un flame da un simpatico
spunto di dialogo (8 regine), comunque [OT] secondo manifesto, su questo
NG *non* si tiene affatto fuori la programmazione.
Gli algoritmi che risolvono il problema delle 8 regine sono fondalmente
2:
- Ricerca "banale" ed esaustiva delle possibili soluzioni;
- Ricerca "intelligente" mediante backtracking.
Interessante, pertinente ed anche didattico sarebbe cimentarsi a
sviluppare i due algoritmi in VB.
La ricerca dell'algoritmo, invece, esula dagli scopi del ng e pertanto
puo' essere solo marcata [OT], *indipendentemente* dal fatto che sia
*comunque* un simpatico spunto di discussione per *gran parte* del ng
(lo e'?).
Qualche notiziola: il problema delle 8 regine, proposto per la prima
volta nel 1848, ha 12 soluzioni distinte che con rotazioni e riflessioni
diventano 92.
Lo presenta anche Martin Gardner su "Le Scienze" N°51 del nov.1972 e nel
suo libro "Enigmi e Giochi Matematici".
Happy Coding a tutti =)
Lokar

 regina....
meglio bool e' + veloce
il bello adesso verra' sull'ottimizzazione del codice di ricerca :
vediamo in VB chi riesce a creare il codice + veloce che sia in grado di
trovare le prime 10 combinazioni del problema delle 8 regine ?
PS: breve spiegazione sul problema delle 8 regine :
bisogna riuscire a posizionare 8 regine su una normale scacchiera in modo
che non si intralcino a vicenda , cioe' in modo tale che ogni regina non ne
abbia un altro sulla sua verticale , sulla sua orizzontale e sulle sue
oblique !
Buona Programmazione e non cercate indizi in giro mi raccomando o vi metto
un bel 3 ( scusate deformazione professionale )

 con una funzione ricorsiva di un paio di righe
bhe aspe'... contando anche che si deve inserire "next var" le righe
diventano 5 ^_-

 regina....
Ammetto che possa essere un bel problema, pa perchè SPRECARE delle righe di
codice per risolvere un problema unico?
Insomma ogni volta che avvierò il mio programma mi verrà data la medesima
soluzione per lo stesso problema.
Perchè non cimentarsi in un programma che sviluppi un po' di intelligenza
artificiale? Chessò restando in tema di scacchi magari fare un programma che
sposti la regina e il re sulla scacchiera evitando lo scacco matto da parte
dell'utente.
Altrimenti sarebbe come fare un programma che mi risolva la somma di 3 + 2
con quanti più modi possibili.

 [...] chi vuole cimentarsi?
Eqqueqqua! Come ha detto giustamente Lokar, le soluzioni sono 92. La
visualizzazione avviene nella finestra di Debug e alla fine c'è un MsgBox
del totale.
Per trovarle tutte, ci mette molto meno di un secondo sul mio Pc, ma il
codice sarebbe ulteriormente ottimizzabile.
Aprire un progetto nuovo, piazzare nella form di default il seguente codice
(ocio agli eventuali a_capo non voluti), e mandare in esecuzione.
Option Explicit
Private Type tPosizioniRegine
   PosX As Integer
   PosY As Integer
End Type
Dim aArrayPosizioniRegine(1 To 8) As tPosizioniRegine
Dim lTotaleSoluzioni As Long
Private Function StessaXDiUnAltraRegina(ByVal x As Integer) As Boolean
   Dim r As Integer
   For r = 1 To 8
      If aArrayPosizioniRegine(r).PosX = x Then
         StessaXDiUnAltraRegina = True
         Exit For
      End If
   Next
End Function
Private Function StessaYDiUnAltraRegina(ByVal y As Integer) As Boolean
   Dim r As Integer
   For r = 1 To 8
      If aArrayPosizioniRegine(r).PosY = y Then
         StessaYDiUnAltraRegina = True
         Exit For
      End If
   Next
End Function
Private Function StessaDiagonaleDiUnAltraRegina(ByVal x As Integer, _
            ByVal y As Integer) As Boolean
   Dim r As Integer
   Dim iDifferenza As Long
   For r = 1 To 8
      If aArrayPosizioniRegine(r).PosX > 0 Then
         If aArrayPosizioniRegine(r).PosY > 0 Then
            If (Abs(aArrayPosizioniRegine(r).PosY - y) = _
               Abs(aArrayPosizioniRegine(r).PosX - x)) Then
                  StessaDiagonaleDiUnAltraRegina = True
                  Exit For
            End If
         End If
      End If
   Next
End Function
Private Sub MostraPosizione()
   Dim r As Integer
   Dim sRiga As String
   Dim sSoluzione As String
   For r = 1 To 8
      sRiga = String$(8, "O")
      Mid$(sRiga, aArrayPosizioniRegine(r).PosX, 1) = "X"
      sSoluzione = sSoluzione & sRiga & vbCrLf
   Next
   Debug.Print sSoluzione
End Sub
Private Sub CalcolaPosizione(ByVal iIndiceCorrente As Integer)
   Dim x As Integer
   Dim y As Integer
   y = iIndiceCorrente
   If Not StessaYDiUnAltraRegina(y) Then
      For x = 1 To 8
         If Not StessaXDiUnAltraRegina(x) Then
            If Not StessaDiagonaleDiUnAltraRegina(x, y) Then
               aArrayPosizioniRegine(iIndiceCorrente).PosX = x
               aArrayPosizioniRegine(iIndiceCorrente).PosY = y
               If iIndiceCorrente < 8 Then
                  CalcolaPosizione iIndiceCorrente + 1
                  aArrayPosizioniRegine(iIndiceCorrente + 1).PosY = 0
                  aArrayPosizioniRegine(iIndiceCorrente + 1).PosX = 0
               Else
                  MostraPosizione
                  lTotaleSoluzioni = lTotaleSoluzioni + 1
               End If
            End If
         End If
      Next
   End If
End Sub
Private Sub Form_Load()
   CalcolaPosizione 1
   MsgBox "Trovate " & lTotaleSoluzioni & " soluzioni"
End Sub
Ciao
*Roby*

 codice sarebbe ulteriormente ottimizzabile.
Ecco, infatti la chiamata a StessaYDiUnAltraRegina per esempio non serve a
niente.
Comunque ho rimodificato un po' il codice. Se interessa il numero minimo di
righe-colonne-regine che generano delle soluzioni valide è 4 (2 soluzioni,
ovviamente una speculare all'altra). Con 10 righe-colonne-regine si
ottengono 724 soluzioni e i tempi sono ancora accettabili. Salendo, le
soluzioni e i tempi aumentano esponenzialmente.
Potrebbe forse essere interessante fare esperimenti su scacchiere
rettangolari con numeri di regine pari alla dimensione maggiore, ma il tempo
a disposizione per cazzeggiare oggi è terminato. ;-)
Ciao
*Roby*