Aiuto su sudoku livello esperto!

Presente e passato di questo meraviglioso rompicapo

Aiuto su sudoku livello esperto!

Messaggioda bad_hunter » dom 11 nov 2012, 15:44

Ciao a tutti sono appena iscritto.

Sto facendo in questi giorni un programma per la risoluzione dei sudoku senza utilizzare alcun attacco brutale o soluzioni a tentativi, il programma in questo momento riesce a risolvere i sudoku a livello facile medio difficile e qualche volta esperto, proprio per riuscire a risolvere anche quei sudoku vi lascio un sudoku in cui il programma si blocca:

Immagine

Ovviamente questo non è uno screen del mio programma ma del sito da dove ho preso il sudoku, principalmente il problema è che il programma risolve i sudoku che anche io so risolvere e a quanto pare questo non è alla mia portata, quindi vi chiedo sapete dirmi il prossimo numero e sopratutto il perchè?
bad_hunter
 
Messaggi: 7
Iscritto il: dom 11 nov 2012, 0:48

Re: Aiuto su sudoku livello esperto!

Messaggioda gabriele » dom 11 nov 2012, 16:58

r1c1=59, r3c1=58, r9c1=89
tripla nuda
quindi r7c1=6

se cerchi aiuto prova a scaricare il mio solver
https://www.argio-logic.net/Sudoku_v5.zip
puoi trovare esempi di tecniche di soluzione, anche le più complicate.
Il genere umano è diviso in 10 specie: quella che capisce il binario e quella che non lo capisce
Avatar utente
gabriele
Amministratore
 
Messaggi: 4605
Iscritto il: dom 13 apr 2008, 11:27
Località: porto mantovano

Re: Aiuto su sudoku livello esperto!

Messaggioda emilio » dom 11 nov 2012, 17:08

Il Boss è sempre il Boss... giusto che mi abbia battuto sul tempo.
Ma ora controllo il proseguimento

:ciao
il Sudoku è un gioco che va meditato. Correte piano
EMILIO
Avatar utente
emilio
 
Messaggi: 3889
Iscritto il: dom 7 mar 2010, 19:24
Località: monza

Re: Aiuto su sudoku livello esperto!

Messaggioda emilio » dom 11 nov 2012, 17:23

niente da fare, lo schema, dopo l'inserimento del 6, mi rimane bloccato. Mi pare di intuire che debba essere applicata una di quelle cose strane ("colore" "chain") delle quali non ho mai capito il funzionamento, per cui ci metterei il tentativo, ma non è questo che ha chiesto il nostro nuovo affiliato.
:ciao
il Sudoku è un gioco che va meditato. Correte piano
EMILIO
Avatar utente
emilio
 
Messaggi: 3889
Iscritto il: dom 7 mar 2010, 19:24
Località: monza

Re: Aiuto su sudoku livello esperto!

Messaggioda bad_hunter » dom 11 nov 2012, 18:28

Grandioso, ho capito il concetto ora devo soltanto cercare di spiegarlo al programma, grazie mille vi terrò aggiornati!!
bad_hunter
 
Messaggi: 7
Iscritto il: dom 11 nov 2012, 0:48

Re: Aiuto su sudoku livello esperto!

Messaggioda gabriele » dom 11 nov 2012, 19:38

bad_hunter ha scritto:Grandioso, ho capito il concetto ora devo soltanto cercare di spiegarlo al programma, grazie mille vi terrò aggiornati!!

che linguaggio usi, cacciatore?
Il genere umano è diviso in 10 specie: quella che capisce il binario e quella che non lo capisce
Avatar utente
gabriele
Amministratore
 
Messaggi: 4605
Iscritto il: dom 13 apr 2008, 11:27
Località: porto mantovano

Re: Aiuto su sudoku livello esperto!

Messaggioda gabriele » dom 11 nov 2012, 19:45

lo schema viene definito per "esperti"-
In effetti si risolve con una xy-chain
Immagine
se
r3c2=3
allora
r3c8=5
r4c8=1
r4c5=8
quindi 8 o in r3c2 o in r4c5
8 non può stare in r4c2
nella riga 4 dunque sta in r4c5

MA NON BASTA
OCCORRONO ALTRE DUE CATENE
Immagine
Immagine

definirlo quindi per "esperti"
è un po' riduttivo!
Il genere umano è diviso in 10 specie: quella che capisce il binario e quella che non lo capisce
Avatar utente
gabriele
Amministratore
 
Messaggi: 4605
Iscritto il: dom 13 apr 2008, 11:27
Località: porto mantovano

Re: Aiuto su sudoku livello esperto!

Messaggioda bad_hunter » dom 11 nov 2012, 21:51

Lo sto facendo in una via di mezzo fra C e C++, in pratica a scuola dovevano insegnarci il C ma ci fanno usare qualche funzioncina del C++ per facilitarci la vita, come compilatore uso il Dev C++.

Per quanto riguarda il primo numero da trovare e cioè il 6 ho già tutto in mente, farò una funzione per le righe, una per le colonne e una per i quadrati per trovare quei casi, ho solo un dubbio su una cosa ma lo risolverò a forza di prove; invece per la catena al momento non ho alcuna idea ma nemmeno voglio pensarci ora, prima voglio fare le altre funzioni.
bad_hunter
 
Messaggi: 7
Iscritto il: dom 11 nov 2012, 0:48

Re: Aiuto su sudoku livello esperto!

Messaggioda bad_hunter » sab 17 nov 2012, 23:46

A quanto pare il tempo libero non è il mio forte in questo periodo!!

Oggi ho potuto finalmente aggiungere la funzione delle triple nude, l'ho fatta in modo che riconosca anche le quartine e le cinquine nude (in caso esistano), ha per ora un bug noto che devo risolvere che però non crea danni ma non mi fa funzionare la funzione in un caso particolare.

Il discorso della catena l'ho capito, devo farmi venire qualche idea in mente per implementarlo ma confido in me!
bad_hunter
 
Messaggi: 7
Iscritto il: dom 11 nov 2012, 0:48

Re: Aiuto su sudoku livello esperto!

Messaggioda gabriele » dom 18 nov 2012, 15:37

bad_hunter ha scritto:A quanto pare il tempo libero non è il mio forte in questo periodo!!

Oggi ho potuto finalmente aggiungere la funzione delle triple nude, l'ho fatta in modo che riconosca anche le quartine e le cinquine nude (in caso esistano), ha per ora un bug noto che devo risolvere che però non crea danni ma non mi fa funzionare la funzione in un caso particolare.

Il discorso della catena l'ho capito, devo farmi venire qualche idea in mente per implementarlo ma confido in me!

esistono anche le triple nascoste ( 3 candidati presenti solo su 3 celle insieme ad altri candidati)
la relazione tra gruppi nudi e nascosti è
: nascosto= N - nudo
dove N è il numero delle celle non note del dominio (righe, colonne, settori)
per cui le cinquine sono inutili
es: se in un dominio hai 9 celle vuote se esiste una cinquina nuda esiste anche una quartina nascosta
nel esempio proposto oltre alla tripla nuda 589 esiste anche la tripla nascosta 146
Il genere umano è diviso in 10 specie: quella che capisce il binario e quella che non lo capisce
Avatar utente
gabriele
Amministratore
 
Messaggi: 4605
Iscritto il: dom 13 apr 2008, 11:27
Località: porto mantovano

Re: Aiuto su sudoku livello esperto!

Messaggioda bad_hunter » dom 18 nov 2012, 23:35

Ho un problema, quella funzione ha funzionato col sudoku a livello esperto ma per qualche strano motivo fa danni con tutti gli altri sudoku, puoi farmi capire come si inseriscono i sudoku a mano col tuo programma in modo da aiutarmi a capire l'errore?

Edit: trovato l'errore, ora la funzione non fa danni!

Mi chiedevo, il discorso delle terzine e quartine vale solo per righe e colonne o anche per i quadrati?

Il discorso delle terzine nascoste francamente non l'ho capito.
bad_hunter
 
Messaggi: 7
Iscritto il: dom 11 nov 2012, 0:48

Re: Aiuto su sudoku livello esperto!

Messaggioda gabriele » lun 19 nov 2012, 9:11

bad_hunter ha scritto:Ho un problema, quella funzione ha funzionato col sudoku a livello esperto ma per qualche strano motivo fa danni con tutti gli altri sudoku, puoi farmi capire come si inseriscono i sudoku a mano col tuo programma in modo da aiutarmi a capire l'errore?

Edit: trovato l'errore, ora la funzione non fa danni!

Mi chiedevo, il discorso delle terzine e quartine vale solo per righe e colonne o anche per i quadrati?

Il discorso delle terzine nascoste francamente non l'ho capito.

vale anche per i quadrati
Il genere umano è diviso in 10 specie: quella che capisce il binario e quella che non lo capisce
Avatar utente
gabriele
Amministratore
 
Messaggi: 4605
Iscritto il: dom 13 apr 2008, 11:27
Località: porto mantovano

Re: Aiuto su sudoku livello esperto!

Messaggioda bad_hunter » ven 23 nov 2012, 23:14

Ok, non ci vorrà molto per implementare quella funzione per i quadrati, mi sto però scervellando per capire le catene, se ho ben capito si tratta di celle che al massimo hanno due candidati, i candidati in totale delle celle sono tanti quanto le celle e queste ultime possono trovarsi ovunque nel sudoku.

Hai per caso una spiegazione standard?
bad_hunter
 
Messaggi: 7
Iscritto il: dom 11 nov 2012, 0:48

Re: Aiuto su sudoku livello esperto!

Messaggioda gabriele » sab 24 nov 2012, 13:57

bad_hunter ha scritto:Ok, non ci vorrà molto per implementare quella funzione per i quadrati, mi sto però scervellando per capire le catene, se ho ben capito si tratta di celle che al massimo hanno due candidati, i candidati in totale delle celle sono tanti quanto le celle e queste ultime possono trovarsi ovunque nel sudoku.

Hai per caso una spiegazione standard?

puoi trovare qualche cosa qui
viewtopic.php?f=9&t=568
le catene di celle bivalori sono le più semplici e vengano chiamate xychain
ce ne sono di più complcate
ti suggerisco di andare nella nostra pagina dei download e scaricare il solver sudoku, che per ogni tecnica utilizzata da le spiegazioni.
https://www.argio-logic.net/?p=sudoku
Il genere umano è diviso in 10 specie: quella che capisce il binario e quella che non lo capisce
Avatar utente
gabriele
Amministratore
 
Messaggi: 4605
Iscritto il: dom 13 apr 2008, 11:27
Località: porto mantovano

Re: Aiuto su sudoku livello esperto!

Messaggioda bad_hunter » gio 17 gen 2013, 15:19

Alla fine durante le vacanze di natale ci sono riuscito!!!!

:b5 :bg :b5


Ecco gli screen del programma, il primo è il main e il secondo è la parte grafica fatta con la libreria graphics del borland e infatti è una merda):


Immagine

Immagine

:b2

Ho provato a fargli fare altri sudoku di quel sito e ho notato che alcuni li fa ed altri no, probabilmente ci sarà da aggiungere altre funzioni ma per ora mi accontento, devo ancora presentarlo a scuola tra l'altro!!

Se volete ve lo posso postare assieme al codice, ovvio non compete minimamente con quello di Gabriele ma visto che ho cominciato a muovere i primi passi da poco più di un anno penso di poter essere soddisfatto di me stesso.


Grazie per gli aiuti!!
bad_hunter
 
Messaggi: 7
Iscritto il: dom 11 nov 2012, 0:48


Torna a Tutto sul Sudoku

Chi c’è in linea

Visitano il forum: Nessuno e 3 ospiti

cron