Visualizzazione dei risultati da 1 a 5 su 5
  1. #1

    [C] Algoritmo di Backtraking per 8 Regine

    Salve, il problema che mi si e' posto difronte e' quello di implementare un algoritmo per il posizionamento di N regine su una scacchiera NxN evitando che esse si tengano sotto scacco.
    Ho approntato uno pseudocodice, ma c'e' qualcosa che non mi torno... so che il problema non e' dei piu' semplici e ringrazio tutti quelli che mi vorranno dare una mano.

    Size = Numero di regine
    Riga = Indice di riga
    Col = Indice di colonna

    N.B. La funzione sara' ricorsiva quindi bisogna tenere ben presente come si utlizza lo stack in questi casi.

    Int IdxColV; //Indice di colonna della regina precendente.

    if (Riga < Size)
    .{
    ...if ( Col < Size )
    ....if ( Valido ) //Controlla se la regina posizionata in quella cella e' sotto scacco oppure no
    .....{
    .......Mark //Funzione che setta a +1 tutte le celle guardate dalla regina posizionata
    .......Richiamo su Riga+1 e IdxColV = Col
    .....}
    ....else
    ......Richiamo sulla stessa riga incrementando Col di 1
    ...else
    ....{
    ......UnMark //Decrementa di 1 le celle guardate dalla regina in posizione IdxColV
    ......Richiamo su stessa Riga ma con Col+1
    ....}
    ...Non ci sono soluzioni
    ..}
    else
    .Ho trovato una soluzione.


    Il dubbio che mi sorge e' il seguente:
    con una strutturazione del genere le soluzione create saranno tutte?

    Ecco alcuni risultati di cio' che si deve ottenere:
    Num Regine = 1 Soluzioni = 1
    Num Regine = 2 Soluzioni = 0
    Num Regine = 3 Soluzioni = 0
    Num Regine = 4 Soluzioni = 2
    Num Regine = 5 Soluzioni = 10
    Num Regine = 6 Soluzioni = 4
    Num Regine = 7 Soluzioni = 40
    Num Regine = 8 Soluzioni = 92
    Num Regine = 9 Soluzioni = 352
    e così via dicendo. Il problema ha soluzioni che crescono di numero in modo esponenziale.
    Grazie a tutti.

  2. #2
    E' una guerra vero? Anche io sto combattendo in altra direzione, ma ce la faremo!
    MondoLibero: Informazione Libera, Varia ed Eventuale
    Sito di informazione varia ed eventuale. Quando ho voglia scrivo di ciò che mi pare. Pubblico guide, recensioni, notizie, critiche e tutto ciò che mi passa sotto mano e che penso sia interessante.

  3. #3
    Proprio tu non mi dovevi rispondere smanettone del cavolo
    pensa al tu delay di stampa.... io intanto ho tanto di quel materiale per la relazione che non ne hai neanche idea... solo per la mia funzione posso riempire qualcosa come 6 pagine.... senza mettere grafici.

    Altri aiuti ?

  4. #4
    Originariamente inviato da LarsSalazar
    Proprio tu non mi dovevi rispondere smanettone del cavolo
    pensa al tu delay di stampa.... io intanto ho tanto di quel materiale per la relazione che non ne hai neanche idea... solo per la mia funzione posso riempire qualcosa come 6 pagine.... senza mettere grafici.

    Altri aiuti ?
    Delay risolto con la mia testa Ora sono alle prese con altri problemi di standard con linux, sto facendo dei test di stabilità e compilazione....Sorry per l'Off Topic tra amici.
    MondoLibero: Informazione Libera, Varia ed Eventuale
    Sito di informazione varia ed eventuale. Quando ho voglia scrivo di ciò che mi pare. Pubblico guide, recensioni, notizie, critiche e tutto ciò che mi passa sotto mano e che penso sia interessante.

  5. #5
    Moderatore di Programmazione L'avatar di alka
    Registrato dal
    Oct 2001
    residenza
    Reggio Emilia
    Messaggi
    23,871

    Moderazione

    Il forum non è una chat: utilizzate un servizio di messaggistica istantanea per le chiacchiere, o una banale email, che secondo me sono strumenti più appropriati.
    MARCO BREVEGLIERI
    Software and Web Developer, Teacher and Consultant

    Home | Blog | Delphi Podcast | Delphi Succinctly (e-book)

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2020 vBulletin Solutions, Inc. All rights reserved.