Recentemente mi sono imbattuto in una variante speciale del Sudoku e ora sto lottando per risolverlo efficacemente in modo programmatico.

Considera la seguente griglia iniziale 6x6:

Leregole

Ilpuntointerrogativorossodovrebberappresentarelanostracifrasegreta.Lacifrasegretasicomportacomeunanormalecifra.Valeadire,haunvalorerealetra1e6,maquestovalorenonvienerivelatoalgiocatore.Inquestotipodigioco,secreiamounacollisione,lanuovacifrainseritadiventeràunelementoneutrochepuòesserevistocomeunjoker,nonincollisioneconnessun'altracifra.Adesempio,selacifrasegretafosseeffettivamenteuna6eabbiamoinseritoun6nellasuariga,essadiventerebbeunelementoneutro(econciòsapremmoanchequalèlacifrasegreta).Possiamogenerareunmassimodiunelementoneutro(nelsensochepossiamocrearesolounacollisione),unasecondacollisionerenderebbeirrisoltalagriglia.
Notaamargine:Naturalmente,questotipodigiocointerattivononlofahasensoesserestampatosuunpezzodicarta;sarebbeades.richiedeun'infrastrutturaclient-serverperilsegretodanonrivelarealgiocatore.

Analisi

Poichélacifrasegretasegueleregoledibase,possiamodedurrechenonpuòessereun4nellagrigliadiesempio,maognialtracifrapotrebbeesserepossibile.Possiamoanchevederechenonesisteunasoluzioneunica;infatti,disolitocisonocentinaiadipossibilisoluzioni.Inunagrigliainiziale6x6,c'èsempreunacifrasegretae6cifrechesonoposizionateinmodocasualenellagriglia(senzascontrarsil'unaconl'altra).Ciòsignificacheilsegretopotrebbeessereespostofindasubito,maelimineremoilcasobanaledalmomentochenonèaffattodivertente:)

Risoluzionedellastrategia

Lastrategiapiùpromettentesarebbequelladiscoprirelacifrasegretailpiùrapidamentepossibile.Cioè,inseriremmocifrenellasuariga,colonnaoscatolafinchénonsiesaurirebbeognipossibilità,ocreeremmounacollisione.Nonappenasappiamoqualèilsegreto,possiamorisolverel'enigmacomeunnormale(ignorandosemplicementel'elementoneutrosepresente).

Ilproblema

Voglioscrivereunalgoritmochetrovilacifrasegretasenzacreareunaschedairrisolvibile.
Hoscrittounprogrammapiuttostosmussatocheiniziaidentificandoicampinellariga,colonnaeriquadrodelsegretoconilminornumerodibloccanti.Quindiinseriscecifreinqueicampi,inunordinedalnumerominoredibloccantiallamaggiorpartedeibloccantifinoaquandoilsegretopuòesserededottodallacollisioneodall'esaurimento.Nellagrigliadiesempio,farebbequalcosadelgenere:

Le cifre blu verranno posizionate in ordine crescente (iniziando con 1 ). Il mio attuale alogritmo produce un consiglio irrisolvibile circa il 20% delle volte, il che è inaccettabile per me. Ed è per questo che sto facendo la domanda:
Quale sarebbe un approccio più intelligente, riducendo al minimo o addirittura eliminando la possibilità di creare un puzzle irrisolvibile?

P.S.: Apprezzo ogni tipo di risposta; la prosa teoretica, lo pseudo-codice o il codice reale in un linguaggio popolare va bene, voglio semplicemente ottenere l'essenza di quali campi / cifre selezionare per la strategia di partenza.