Sudoku NRC

[snb]

Dag allen.

NRC plaatst dagelijks een Sudoku.
Het speciale van deze Sudoku is, dat er 4 extra ('grijze') vakken zijn toegevoegd, die ook aan de Sudoku-eis moeten voldoen: alle cijfers van 1 t/m 9 bevatten.
Nu carnaval voorbij is kunnen de geesten weer gescherpt worden.

Ik heb gemerkt dat het bedenken van efficiënte algoritmes voor het oplossen van zo'n Sudoku vele malen meer tijd kost dan het oplossen van deze sudoku's.
Het gebruik van VBA om alle mogelijke combinaties met brute kracht te testen beschouw ik daarbij niet als een efficiënt algoritme.

Daarom de volgende vraag:
- bedenk 1 of meer algoritmes (eventueel gecombineerd) om dit soort Sudoku's op te lossen
- beschrijf het principe (oplossingsconcept) van ieder algoritme
- gebruik daarbij niet meer dan 100 VBA regels ( zonder gebruik van : om diverse VBA-opdrachten op 1 lijn te zetten)
- probeer de doorlooptijd zoveel mogelijk te reduceren

In de bijlage een aantal Sudoku's, overgenomen uit NRC.
Met de spinbutton kun je een van de sudoku's uit gebied A26:I164 in gebied A1:I9 laten plaatsen.
Het is de bedoeling dat je oplossing in gebied A12:I20 terechtkomt; daar vindt controle op een correcte oplossing plaats.

De huidige Sudoku in A1:I9 is meteen ook de moeilijkste Sudoku uit de verzameling t/m rij 164.

 

[sylvester-ponte]

gaaf snb, dat is een zeer zware opgave.

 

[alphamax]

Voor oplossings strategien, zie https://www.sudokuwiki.org/Getting_Started

Een recursieve back-tracking bruto-force algoritme is ook niet makkelijk, zie https://www.helpmij.nl/forum/showth...e-solver-(brute-force-recursive-backtracking)

 

[snb]

Ik bedoel natuurlijk VBA-oplossingsstrategieën.
Het gaat juist om de manier waarop je het in VBA aanpakt.
Dat de Sudoku wordt opgelost is in dit geval secundair.

 

[Enigmasmurf]

Met een zekere vorm van genoegen gooi ik nog een beetje olie op het vuur
Lang geleden, toen Office nog moest uitgevonden worden (Windows overigens ook), heb ik al een Sudoku-oplosser ontwikkeld in het door 'specialisten' altijd zwaar onderschatte Basic. Die werkte enkel in full screen modus en mogen we rustig gedateerd noemen:d
Helaas heb ik in een vlaag van opruimwoede (al veel spijt van gehad) de oorspronkelijke code niet meer, maar nog enkel de exe-versie. Die hier toevoegen heeft geen enkele zin want oplossers zijn er voldoende te vinden, en het gaat in dit draadje uiteindelijk om code.
Ik heb mijn methode toch even losgelaten op de door snb getoonde moeilijkste NRC-opgave en in 0,06 sec. was de klus geklaard op een echt antieke (lees: uiterst trage) pc. In mijn nadeel spreekt wel het feit dat mijn code met zekerheid een stukje langer was dan het maximum aantal toegelaten regels code uit de openingspost.
Maar eerlijk gezegd, zó moeilijk vond ik dat niet ('k heb in diezelfde periode o.a. ook Tetris, Mastermind, Vier op een rij e.d. ontwikkeld, beide laatste om tegen de computer dan wel tegen een ander persoon te spelen).

De enige bedoeling van deze post is dus om zoveel mogelijk vba-ers aan te sporen zich er toch aan te wagen, misschien doe ik zelf ook wel mee...

 

[alphamax]

Deze puzzel heet een "Hyper Sudoku".
En waarom zijn de grijze vakken in het orgineel en jouw tekstuitleg in bericht#1, in jouw bestand oranje vakken?
Het maakt er alles niet duidelijker op.

 

[sylvester-ponte]

alphamax, in jouw vba oplossing mag je alle kleuren gebruiken en je mag de vakjes ook vierkant maken.
zet hem op.
in mijn toekomstige vba oplossing krijg je per sudokupunt 9 vakjes te zien dan zie je wat er nog toegestaan is in dat sudokupunt.

 

[E v R]

Nu draaiend met dezelfde insteek als van Sylvester hierboven, nog wat efficiënter maken (lees 250 regels minder :d ) alvorens hier te plaatsen

 

[snb]

@Enigma

Klinkt goed, edoch ook jouw oplossing blijft een raadsel.
De beoordeling van de gebruikte algoritmen is bovendien wat lastg.
Hopelijk vind je het een en ander terug op je computer of anders wel tussen de oren.
Zoals ik al aangaf is de snelhied secundair (tot op zekere hoogte natuurlijk)

@Alpha,
Zoals je kunt zien staat 'grijs' tussen aanhalingstekens. Dat betekent dat het weliswaar in de NRC om grijze vakken gaat, maar in mijn bestand is met een wat levendiger kleur aangegeven.
Dat het om de gebieden 2,2 .. 4,4; 2,6 .. 4,8; 6,2 ..8,4 en 6,6 .. 8,8 gaat is je waarschijnlijk inmiddels wel duidelijk.
In jouw verwijzing naar strategieën tref ik geen echte redeneringen aan.
Maar ik kan te oppervlakkig gelezen hebben

@sylv

Hoewel @EvR zegt dezelfde insteek te gebruiken is mij die nog niet echt duidelijk.
Misschien moet ik je eerste versie afwachten om te beoordelen of jij wellicht dezelfde aanpak hebt als ik, maar alleen anders noemt.

@EvR
Mooi !
Een suggestie: als je een van de andere voorbeeldsudoku's neemt kun je met minder algoritmes terecht. Zo ben ik tenminste begonnen, totdat ik een Sudoku trof die halverwege stokte, zodat er iets nieuws uit de hoge hoed getoverd moest worden.
De manier waarop ik zelf zo'n sudoku aanpak is opmerkelijk genoeg totaal anders dan wanneer ik het in VBA laat oplossen.
Ik ben beneiuwd of dat bij jullie ook zo is.

 

[E v R]

Ik werk deels "recursive", de wat makkelijkere hebben wat minder 'omloopjes' nodig.
Ik heb niet gekeken naar andere Sudoku-solvers, ben gaan bouwen hoe ik het zelf handmatig zou aanvliegen.
Nu nog 160 regels code minder alvorens hier te plaatsen.

 

[sylvester-ponte]

snb, ik ben niet zo snel, maar het aantal regels vindt ik minder boeiend.
ik ben ge interesseert in het algoritme van iedereen, niet in het aantal regels.
vele verschillende benaderingen hoop ik.

 

[snb]

@EvR

daar gaat het bij mij ook op uitdraaien.

@Sylv

Helemaal met je eens.
Maar zo gauw ik iets werkends heb, kan ik de vraag 'kan dat niet simpeler' niet weerstaan.
Ik vind het vaak fascinerend hoe hernieuwd kijken naar code tot vereenvoudiging kan leiden.
Maar ook daar zitten grenzen aan; mijn laatste 'vereenvoudiging' werkte zo vertragend, dat ik dat geen verbetering meer vond.
Ik ben nu bezig de door mij geprogrammeerde algoritmes in heldere, begrijpelijke taal uit te schrijven.
Is ook nog niet eens zo eenvoudig.

 

[snb]

Dag allen,

Zullen we een deadline afspreken om een aanvang te maken met de plaatsing van de diverse vormen van aanpak ?
Is 15 maart een geschikte datum of is er voorkeur voor de equinox op 21 maart ?

 

[alphamax]

Dit topic is automatisch gesloten omdat er sinds vier maanden niet meer op gereageerd is.

Indien gewenst kan de topicstarter een verzoek tot heropening indienen.

In ieder geval voor deze tijd

 

[snb]

Voor sommigen maken we altijd wel een uitzondering ....

 

[cow18]

domme vraag anders, is het niveau 2021/365 of verplicht lager (ivm. application.sort op matrices) ?
Tellen Sub ... en End Sub (of Function) mee als regels ?

 

[snb]

Wat mij betreft geen beperkingen.
Juist interessant om de voor-/nadelen van versies te beoordelen.

Zo vaak zullen die regels toch niet voorkomen ?
Dat wordt toch pas interessant onder de 10 regels, lijkt me

 

[sylvester-ponte]

Hallo, hier een eerste poging:
gebuikte namen:
Hor : horizontale lijn
Vert: verticale lijn
Blok: Gewoon blok van standaard sudoku (3*3) vakjes
BlokGr: grijs blok (3*3) vakjes

al deze vormen bevatten in hun naam ook de rij en kolom van het punt links boven in de vorm.

in mijn voorlopige opzet geeft het programma een aantal zeer eenvoudig te beredeneren volgende zetten weer.
als je op z'n zet (rechts van de uitgebreide sudoku ) klikt dan wordt er met die zet verder gewerkt.
alle zetten die weergegeven zijn zijn ok.

ps er zit in deze poging (nog) geen slimmigheid voor als het moeilijker gaat worden.
ondanks de niet zo intelligente poging lost hij de meeste al op.
als je liever hebt dat hij alle punten zelf invult, dan hoor ik dat wel. ik vond deze tot nu toe wel leuk om te laten zien.
op blad 2 staan alle sudokuus van snb

ik heb net ontdekt dat spel 13 meer iq vereist . daar ga ik nog aan werken. alle andere spellen lost hij op.

 

[cow18]

hierbij ook mijn eerste schot voor de boeg, Sudoku van rij 146 en de eerste zijn nog niet oplosbaar, maar dat is kwestie van dubbels or driedubbels op te zoeken en tegen elkaar af te schrappen.
Maar ik zeg net als Sylvester, werk voor morgen.
Voorlopig tik ik af op 64 regels, (er zijn wat kleurrijen bij en zo, dus is het een ruwe schatting), dus heb ik nog 36 regels om dat probleem te tackelen ....

Edit : waw Sylvester op 80 rijen :thumb:, maar ik heb hem nog niet geprobeerd ...

 

[snb]

@cow18

Het gaat mij om het aantal regels om de sudokun op te lossen, niet om de VBA om een bepaalde sucdoku te selectern
Ik tref in je code op diverse plaatsen de : aan. Die horen natuurlijk op aparte regels (zie derde gedachtenstreepje in mijn oorspronkelijke bericht.) Dat maakt vergelijking met andere vormen van aanpak beter mogelijk.

Nog een vraag: je gebruikt textjoin in de functie 'tellen'
Welke waarden kan variabele 's' daar aannemen ?