algoritmo xy-chain
Condividi:
+ Rispondi alla Discussione
Risultati da 1 a 10 di 10

Discussione: algoritmo xy-chain

  1. #1
    Junior Member
    Data Registrazione
    Mar 2015
    Messaggi
    5

    algoritmo xy-chain

    Sapete dirmi dove posso trovare l'algoritmo della xy-chain ?
    mi serve per un software in VB6.
    Grazie

  2. #2
    Senior Member
    Data Registrazione
    Sep 2010
    Località
    Roma
    Messaggi
    543
    Ciao Tommaso, vedi mio msg privato,

    Sergio

  3. #3
    Junior Member
    Data Registrazione
    Mar 2015
    Messaggi
    5
    sei molto gentile, grazie

  4. #4
    Senior Member
    Data Registrazione
    Oct 2014
    Messaggi
    168
    Ciao Tommaso

    Le varie tecniche con nomi più o meno strani trovano tutte origine dall'esame di doppie possibilità suddivisibili in 2 tipologie:
    a) celle con 2 soli candidati
    b) singoli candidati in 2 sole celle
    Solo così ho risolto il problema a monte ignorando tutte le denominazioni possibili (X wing - XY wing - XY Chain - Color - Scrapecolor ecc ecc )
    L'algoritmo da me usato (sempre in VB6) si basa sulla lettura di un "contatore di divieti" per candidato/cella dopo la "simulazione" per singola possibilità (quelle sopra elencate).
    I candidati con doppio divieto (contatore = 2) sono da eliminare a tutto vantaggio della ricerca della soluzione.
    Se poi nelle celle rettificate rimane un solo candidato, si può parlare di numero certo dovuto a doppia conferma.

    Spero di esserti stato d'aiuto almeno in parte e, comunque, sono a tua disposizione per approfondimenti.

    vittorio

  5. #5
    Junior Member
    Data Registrazione
    Mar 2015
    Messaggi
    5
    Vittorio ti ringrazio moltissimo per la tua gentilezza.
    Io pensavo che indispensabile fosse solo la condizione a), sei sicuro che il procedimento è estensibile anche alla condizione b) ?
    (ma se in una riga (o colonna o zona) ho solo 2 celle con 2 candidati è già ovvio che posso eliminare gli altri candidati presenti nelle 2 celle quindi la condizione b) quando è che si verifica?)


    Quindi prima mi faccio una mappatura di tutte le celle con 2 soli candidati
    Poi trovo le coppie di celle (in riga,colonna o zona) che sono impegnate obbligatoriamente da 2 candidati (2 candidati in 2 celle)
    su questi ultimi eseguo l'indagine con la nuova tecnica.

    Lo svolgimento dell'indagine parte dalla forzatura di un candidato e seguo l'effetto fino a che la catena non si spezza o si chiude contando i morti? e lo stesso per l'altro candidato della stessa cella di partenza.
    Alla fine conto i candidati cancellati 2 volte che potranno essere eliminati definitivamente; è così?

    la presenza certa (con cancellature 0) si riferisce al caso b), vero?

    Grazie dell'attenzione
    Tommaso
    Ultima modifica di tommaso; 08-03-15 alle 10:07

  6. #6
    Senior Member
    Data Registrazione
    Oct 2014
    Messaggi
    168
    Ciao Tommaso
    Ti confermo che il procedimento è applicabile ad entrambi i casi a) e b)
    Poiché dalle tue domande percepisco di non essere stato sufficientemente chiaro ti mostro un esempio.

    Il caso a) si riferisce a qualsiasi cella dello schema in cui i candidati possibili sono solo due.
    Ciò vale anche se, nella riga/colonna/quadro (anche diagonale per la variante sudoku cross), restano solo due celle da definire.
    Il caso b) si riferisce a qualsiasi candidato che in una riga/colonna/quadro ecc ha a disposizione due sole celle.

    fig a b .JPG

    Nell'esempio la colonna 7 mi fornisce lo spunto per una dimostrazione di entrambi i casi.

    Caso a)
    La cella con cornice azzurra è quella su cui applichiamo la procedura ai due candidati e che ci porterà allo stesso risultato nella cella con cornice verde.
    Ipotizzando il 4 nella cella di partenza otteniamo direttamente [3 in r8c7] e quindi la cancellazione del 3 in r7c9 (contatore=1)
    Ipotizzando invece il 3 (con un giro più largo) otteniamo [9 in r2c9] [9 in r3c3] [3 in r7c3] e quindi ancora la cancellazione del 3 in r7c9 (contatore=2)
    Poiché nella cella di arrivo rimane un solo candidato, possiamo affermare che i due candidati della cella di partenza rendono entrambi certo l'8.

    Caso b).
    Senza ripetere la descrizione, puoi vedere che in colonna 7 i due candidati 4 (testati singolarmente) oppure i due candidati 3 portano al medesimo risultato del caso a).

    Se ti vuoi divertire, puoi scoprire che ottieni ugualmente lo stesso risultato prendendo in esame i due candidati 3 della riga 2, i due candidati 9 della riga 3, i due candidati 6 della colonna 2 e mi fermo qui per non farti passare tutto il pomeriggio dietro questo schema.

    Per ultimo, quello che tu chiami candidato a cancellazioni zero non è da considerare numero certo se non nel caso di cella con unico candidato residuo.

    Se hai bisogno di altro, sono qua

    Buon pomeriggio
    vittorio

  7. #7
    Junior Member
    Data Registrazione
    Mar 2015
    Messaggi
    5
    Ciao Vittorio, grazie dell'attenzione.
    Trovo molto chiara la spiegazione che mi hai dato; è perfetta e chiara.

    Noto però qualcosa che non mi soddisfa e quindi chiedo la tua opinione

    Ipotizzando che sia il 4 il numero certo nella cella di partenza e non conoscendo dove dovrò fermarmi, sono portato a inserire tutti i numeri certi che incontro.
    A un certo punto mi accorgo che in una cella non ha più candidati e quindi è chiaro che il 4 non può essere il numero certo della casella di partenza.
    Poi provo con il numero 3 e arrivo a completare il gioco coprendo tutte le caselle.
    Ma questo significa risolvere il sudoku per tentativi.
    Certamente questo è dovuto allo schema che è molto semplice.
    Con esempi pliù complessi potrebbe aversi il caso di un successivo blocco che mi ferma ancora l'indagine
    In questo caso quando non so più andare avanti potrei confrontare le due vie e vedere quali numeri in ogni caso sono da eliminare.
    (e questo sarebbe il chain).
    In sostanza ci vorrebbe qualche concetto guida che consigli sul proseguire o meno la catena di tentativo.

    Io, come detto all'inizio, cerco l'algoritmo del chain per un software. se seguo il tuo concetto vado diritto alla soluzione per tentativo.
    Dimmi la tua opinione.
    Ciao

  8. #8
    Senior Member
    Data Registrazione
    Oct 2014
    Messaggi
    168
    Ciao Tommaso
    Riconoscere al volo l'opportunità di applicare una tecnica evoluta che ti consenta di depennare uno o più candidati non è di per se facile e diventa oneroso istruire il processore al riconoscimento caso per caso (tempi di elaborazione/difficoltà progettuali).

    Come già accennato, tutte le tecniche evolute si basano sull' esame di casi di doppia possibilità (di cui una è sicuramente errata) e potrebbero anche essere definite come tecniche per "tentativi" se la "simulazione" la manteniamo fino a fine corsa.
    L'algoritmo che ti ho indicato porta a saltare piè pari le difficoltà di riconoscimento di singole configurazioni (xy wing, xy chain, ecc) e ti offrono nell'immediato l'indicazione di uno o più candidati "impossibili" in determinate celle.
    Tutto ciò aiuta a portare a termine lo schema (sfoltendo l'esercito dei candidati) e può diventare intervento risolutivo se, mirando prima ad una cella con due soli candidati e utilizzando poi i casi a) e b) presenti altrove, otteniamo su quella cella un contatore = 2 per uno dei candidati.
    Non occorre arrivare fino alla fine del percorso delle due ipotesi iniziali (una sola ti darà errore), ma basta controllare se gli effetti investono con percorso breve la cella presa di mira.
    Nell'esempio che ti ho fornito, mantenedo sempre fermo l'obbiettivo sulla cella r7c9, se la cella di partenza fosse risultata visibilmente incapace di influenzare la cella destinataria, mi sarei allontanato gradualmente e avrei scoperto che anche una cella lontana (la r2c2) mi offriva risultato concreto in quella di destinazione.

    Non riuscendo ad immaginare in quale contesto intendi scrivere il codice dell'algoritmo che cerchi, non riesco a darti ulteriori indicazioni se non di tipo generico.
    Stai creando un risolutore? un generatore di schemi complessi? un help di supporto?

    Comunque sia, conta pure sul mio aiuto (fin quando sono capace).
    vittorio

  9. #9
    Junior Member
    Data Registrazione
    Mar 2015
    Messaggi
    5
    Ciao Vittorio, sei molto gentile a offrirmi la tua disponibilutà.
    Ho realizzato un risolutore a tecniche differenziate per chiarirmi il concetto nei casi difficili e imparare meglio la applicazione delle varie tecniche nel procedimento manuale.
    Mi trovo bene per esaminare gli schemi che non riesco a fare.
    Il sofware è in VB6.
    Ho introdotto le tecniche di tipo wing
    Mi mancano le tecniche avanzate di tipo Chain
    Cercavo qualche algoritmo ma non ne ho trovati.
    Mi hai dato l'idea del contatore di eliminazioni che credo potrà essermi utile.
    Ci devo lavorare su.
    Grazie ancora
    Tommaso

  10. #10
    Senior Member
    Data Registrazione
    Oct 2014
    Messaggi
    168
    Buon lavoro, Tommaso
    Se ti può essere utile, potrei inviarti tramite e-mail alcune immagini relative alle possibilità che il mio software (VB6) offre ad un utente (principiante o esperto) e da cui potresti eventualmente cogliere spunti per il tuo progetto.
    Solo se sei d'accordo, inviami un messagio privato col tuo indirizzo.

    Buona serata
    vittorio

+ Rispondi alla Discussione

Permessi di Scrittura

  • Tu non puoi inviare nuove discussioni
  • Tu non puoi inviare risposte
  • Tu non puoi inviare allegati
  • Tu non puoi modificare i tuoi messaggi
  • Il codice BB è Attivato
  • Le faccine sono Attivato
  • Il codice [IMG] è Attivato
  • Il codice HTML è Disattivato