Sudoku NRC

[snb]

@EvR

Dank voor je aanvulling.
Een pak van mijn hart.
We zijn blijkbaar weer veel te goed van vertrouwen geweest.
Kun je nagaan wat voor reputatie je hier hebt.

Ik heb mijn bestand aangepast.
De uitleg in de macromodule van het werkboek ook.
Ter illustratie van het onderscheid tussen binnenvakken en kadervakken heb ik gebied P12:X20 gebruikt.

Voor zover ik kan beoordelen zit er tot nog toe slechts 1 sudoku bij waarvoor routine 4 nodig is.
De andere zijn dus op te lossen zonder routine 4 (die 11 coderegels omvat).

 

[sylvester-ponte]

hier een beetje suf programma. hij voert steeds wat makkelijke zetten uit en als hij het niet meer weet dan probeert hij wat.
zo vind hij voor spel 15 meerdere oplossingen. in het groene vakje staat het aantal van de gevonden oplossingen. meestal maar 1

 

[cow18]

ik ben ook onder de indruk van de compactheid, zal nog even bezig zijn met alles na te lopen.
Ik heb even de oplossing door mijn "niet meer korte" versie, maar waarmee ik een beetje kan volgen wat/waar/wie/wat doet.
Iets analoogs zou in principe ook kunnen bepalen welke subroutine hoeveel oplost in de versie SNB.
Ik weet niet hoeveel blokken jij eigenlijk afloopt, ik kwam op 400, zie tabel in log kolommen G:Q en draaitabel in S1, kolom N zegt hoeveel cijfers er via die regel weggeschrapt werden.
Op hoeveel blokken zou jij komen ?
in de macro "mijn_dict" staat samengevat wat elk type voorstelt, dus dat zou overeenkomen met 1 van je 4 routines.

je hebt ons toch weer overklast :d

 

[sylvester-ponte]

cow, ik vind mijn oplossing niet zo bijzonder. het enige leuke vind ik dat je hem in 2 minuten ombouwt naar een gewone sudocu. of naar een kruis sudocu.
misschien moet ik daarvoor een knopje ofzo maken. ik hoor het wel als daar interesse voor is.
mijn opzet doet steeds zoveel mogelijk makkelijke zetten en als die op zijn, probeert hij de eerste probeerbare waarde,
daarna probeert hij weer makkelijke zetten . als er een fout ontstaat zet hij terug en probeert hij de volgende probeerbare zet.
als die makkelijke zetten allemaal goed gaan , dan probeert hij weer enz enz
in spel 15 moet hij alle variaties van 12 probeerbare zetten uitproberen. om uit te vinden dat er niets meer is.
in spel 13 is de probeer diepte maar 6 om er zeker van te zijn dat er maar 1 oplossing is.
omdat het programma zo suf is moet er best veel geprobeerd worden.
als ik het programma intelligenter zou maken dan hoeft hij niet zo veel te proberen.

EvR, van al die oplossingen is er maar 1 die op f3 een 6 heeft. (de laatste die hij vindt.)
dus inderdaad als je een 6 op f3 invult krijg je maar 1 oplossing.

 

[snb]

@cow

Kun je uitleggen wat de funktie is en het resultaat van :

sExclusief = Evaluate(Replace("=CONCAT(IF(ISERROR(SEARCH(ROW(A1:A9),TEXTJOIN("""",,#))),ROW(A1:A9),""""))", "#", Bereik2.Address))

 

[sylvester-ponte]

cow, wat is de definitie van blokken in "blokken aflopen" ?
als ik weet wat het is kan ik wel een tellertje inbouwen.

 

[snb]

In de bijlage een 'logboek' ingebouwd.
In kolom N krijg je te zien welke routine tot welk resultaat leidt.
Duidelijk wordt dat
- sommige sudoko's alleen gebruikmaken van routine 2 (de simpele sudoku's)
- de wat complexere sudoku's gebruiken ook routine 3
- slechts in 1 geval (nr.13) wordt gebruik gemaakt van routine 4

Zoals je ziet komt het aantal logboekregels overeen met het aantal lege cellen van de sudoku.

Inmiddels heb ik het verhaal ook op mijn website gezet:
https://www.snb-vba.eu/VBA_Sudoku.html

 

[sylvester-ponte]

snb, een kleine opmerking op je mooie uitleg:
je hebt het steeds over 36 elementen , ik tel er maar 31: 9 rijen , 9 kolommen, 9 standaard blokken en 4 grijze blokken.
verder zeg je dat elk punt een onderdeel is van 4 elementen, van de 81 punten zijn er 36 met 4 elementen verbonden en de rest met 3.

 

[snb]

@Sylv

Tot EvR mij erop attendeerde telde ik er ook maar 31.
Maar er zijn ook nog 5 'kader'vakken.
Zie de kleuren in gebied P11:X19 of het tweede plaatje in de webpagina.

 

[sylvester-ponte]

snb, nu snap ik het.
ik gebruik dat liever niet, omdat ik met de computer een gewone- of een kruis of een andere soort sudocu met het zelfde algoritme kan oplossen.
ik doe het zelfde als jij doet maar dan met minder blokken.
die laatste bijdrage van mij is een suf programmatje om te kijken of een sudocu slechts 1 oplossing heeft. voor ik er zelf aan begin.

 

[cow18]

@snb, het werkblad equivalent is
=TEKST.SAMENV(ALS(ISFOUT(VIND.SPEC(RIJ(A1:A9);TEKST.COMBINEREN("";;A11:C13)));RIJ(A1:A9);""))
=CONCAT(IF(ISERROR(SEARCH(ROW(A1:A9);TEXTJOIN("";;A11:C13)));ROW(A1:A9);""))
waarbij A11:C13 bijvoorbeeld die "#" voorstelde, dus eigenlijk een variabel bereik.
Dus eigenlijk op een benopte manier zoeken welke getallen 1-9 niet voorkomen in het bereik A11:A13
wel opletten, rij(A1:A9) is om een reeks 1-9 aan te maken en zou misschien beter met $ begeleid worden, maar 't is in VBA ...
Daarbij kan je je ook afvragen waarom ik zowel de functie Tekst.samenv als Tekst.combineren gebruik

Bon, een oplossing om op 1 VBA-regel iets te bekomen, dat je anders in een stuk of 5 zou moeten doen.
De vraag was niet om de leesbaarheid te bevorderen ...

 

[cow18]

@Sylvester Pointe, vooraf wordt er een dictionary aangemaakt, waarin alle bereiken worden aangemaakt. Die kan je eigenlijk consulteren in "Log" en eigenlijk zijn alleen de kolommen G:N interessant, waarbij ik nu zie dat de titels in H1 en I1 gewisseld zijn.
kolom G = key van de dictionary (niet interessant, enkel om uniek te maken)
vanaf H zijn het de items van de dictionary, waarbij de 1e, dus it(0), het volgnummer is dat gebruikt wordt in een matrix aOut om het het einde van de rit te weten via welke manier x cijfertjes gewist werden.

kolom H = een oplopend volgnummer
kolom I = type van bereiken (zie uitleg in macro Mijn_dict)
kolom J = (minder interessant) het 3*3 raster waarop je werkt
kolom K:N = de 2 of 3 bereiken waarop je werkt.

Nu is het wel zo dat alles in 1 loop afgelopen werd.
Het strookt niet met de vraag naar beknoptheid, maar je had anders een soort beslissingsboom kunnen maken.
1. je laat in 1e instantie alleen de types 1 en 4 toe = cel vergelijken met de andere 8 in het eigen raster
2. heb je een volledige loop doorlopen zonder iets aan te passen, dan laat je ook voor 1 cyclus de types 2-3 toe = cel vergelijken met de andere 8 van dezelfde rij/kolom en de volgende cyclus doe je weer enkel die eerste, etc
3. heb je weer een volledige cyclus met bovenstaande puntjes 1-2 zonder vervangen afgewerkt, dan laat je weer meer types toe, etc.
Bovenstaande omschrijving is enkel om te kijken welke "moeilijker" types nodig zijn om niet vast te lopen, terwijl je toch de meeste zaken met de eenvoudige probeert op te lossen.

dus moet je ergens iets in een dictionary of een array maken waarmee je definieert wat je op dat ogenblik doet en een tellertje

 

[cow18]

"Zoals je ziet komt het aantal logboekregels overeen met het aantal lege cellen van de sudoku."
eigenlijk heb ik nog niet nagekeken hoe je het gedaan hebt, maar ik kan me voorstellen dat je in een bepaalde cel de 1 wegschrapt volgens jouw routine 1 en de 5 bijvoorbeeld wegschrapt volgens een andere routine, dus in het slechtste geval heb je dus het aantal lege cellen * het aantal routines nodig als logboekregels, maar ik zal dat vanavond eens doornemen ...
Sorry als ik verkeerde conclusies trok !

 

[sylvester-ponte]

cow, in mijn laatste bijdrage heb ik maar 31 blokken. 9 horlijnen ,9 vertlijnen, 9 basisblokken en 4 grijze blokken.
ze worden in de sub Init aangemaakt. ik zal die 5 andere blokken ook eens toevoegen en kijken of de "probeer uit functionaliteit" veel minder gebruikt hoeft te worden.
ik zal hier later op terug komen.

 

[sylvester-ponte]

het gaat met die extra blokken een stuk sneller. (er hoeft minder diep geprobeerd te worden)
zet het blauwe celletje maar eens op nee (ja staat voor extrablokken gebruiken.)
in de rode cel staat hoe diep hij moest gaan met proberen, en terug zetten . om alle mogelijkheden bekeken te hebben.

 

[sylvester-ponte]

snb, ik vond het een leuke uitdaging. dank je wel. :thumb:

ik ben nog wel bezig met een algoritme dat zet voor zet aangeeft welke zet en waarom en,
als er geen zet is hoe en waarom hij sommige waarden uit het bord haalt om verder te komen.

maar dat valt buiten het kader van je vraag, dus daar zal ik jullie niet mee lastig vallen.

 

[snb]

@sylv,

Goed dat je er nog mee bezig bent.
Ik heb inmiddels ook nog een paar regels kunnen verminderen.
Jouw aanpak verschilt van de mijne in het aspekt dat jij mogelijkheden probeert en kijkt of/waar dat vastloopt.
Je zou het een 'intelligent brute force'- methode kunnen noemen.

Het idee achter de sudoku is dat je, op basis van de bekende gegevens, zoveel mogelijkheden kunt uitsluiten dat steeds 1 mogelijkheid resteert. Dat nieuwe gegeven beperkt vervolgens de mogelijkheden voor resterende lege cellen.
De volgorde waarin de sudoku wordt opgelost kan dan weliswaar verschillen, het resultaat is altijd slechts 1 oplossing.
Bij jouw benadering kan het voorkomen dat een uitgangspositie tot verschillende oplossingen kan leiden; maar dan niet door een volgtijdelijke uitsluitingsmethode.

Wat mij betreft blijf je de resultaten van je vervolgaktiviteiten gewoon hier plaatsen; ik blijf ze met belangstelling volgen.

 

[sylvester-ponte]

snb, alleen als er meer oplossingen mogelijk zijn zoals in spel 15 kan mijn benadering deze oplossingen vinden.
als er maar 1 oplossing mogelijk is, zal mijn methode nooit een extra oplossing vinden.

en als er meer oplossingen mogelijk zijn kun je met logisch nadenken nooit tot een oplossing komen.
er is immers ook een andere oplossing die de eerdere redenering onderuit haalt.
dat kan dan alleen door proberen.