Binaire puzzel oplossen recursief

Een andere manier is om recursief te werken met backtracking. Je gaat gewoon controleren of het invullen van een bepaalde waarde in een vakje een oplosbare puzzel oplevert. Indien niet, dan moet de andere waarde ingevuld worden.

Om te weten of deze puzzel oplosbaar is gaan we eerst kijken of er een leeg vakjes is.

Als we een leeg vakje vinden, dan gaan we gokken. We gaan dit systemtisch doen, dat wilt zeggen, we gaan eerst proberen met een 0 en als dat niet lukt proberen we met 1.

We gaan ten eerste kijken of we de gok mogen invullen. En daarbij gaan we kijken naar de drie regels:

• Er mogen horizontaal of verticaal geen 3 opeenvolgende vakjes dezefde waarde bevatten. Kort gezegd, we mogen geen trio's krijgen.

• Er mogen in een rij of een kolom niet meer dan de helft van de vakjes dezelfde waarde bevatten.

• Er mogen geen identieke rijen of kolommen zijn.

We moeten natuurlijk wel controleren of het invullen van deze waarde leidt tot een oplosbare puzzel.

We gaan hiervoor geen nieuwe functie schrijven, maar gewoon de functie zichzelf laten aanroepen. 

Het aanroepen van een vanuit vanuit diezelfde functie word recursie genoemd.

We gaan dus terug op zoek naar een leeg vakje, en als er een leeg vakje is gaan we gokken.

Eerst kijken of we een 0 mogen invullen. Dit is niet het geval want dan krijg ik verticaal 3 keer een 0.

Daarna controleren of een 1 toegestaan is.

Dit mag wel, dus gaan we deze waarde invullen. 

Waarna we gaan kijken of de bekomen oplosbaar is.

We gaan deze functie dus weer recursief oproepen.

We gaan voor het groene vakje weer controleren of er een 0 mag ingevuld worden. Dit is niet het geval, want dan krijg ik horizontaal 3 keer een 0, wat niet toegestaan is.

Vullen we een 1 in, dan krijgen we verticaal drie keer een 1, wat ook niet toegestaan is.

Deze puzzel is dus niet oplosbaar.

Dit is dan ook de waarde die gaat teruggegeven worden aan de functie aanroep.

In het bruine vakje hebben we al een 0 en een 1 geprobeerd. Ofwel mag deze waarde niet ingevuld worden, of het invullen van de waarde leidt niet tot een oplosbare puzzel.

Er schiet geen andere mogelijkheid meer over. Dus deze puzzel is niet oplosbaar, en daarom wordt ONWAAR teruggegeven aan functie-aanroep.

De vorige gok (grijze vakje) gaat moeten gewist worden, en we gaan, indien beschikbaar, een andere waarde moeten gokken.

We kunnen proberen of 1 mag ingevld wordenen leidt tot een oplosbare puzzel.

Een 1 mag ingevuld worden, en de volgende stap is controleren of dit een oplosbare puzzel is.

• Er is een leeg vakje

• We kunnen geen 0 invullen want dan hebben we verticaal 3 keer een 0

• We kunnen wel een 1 invullen.

We vullen een 1 in, en gaan kijken of deze puzzel oplosbaar is.

• Er is een leeg vakje (groen)

• We kunnen een 0 invullen, dus we gaan dit doen en controleren of de puzzel oplosbaar is

• Er is een leeg vakje (blauw)

• We kunnen een 0 invullen, dus we gaan dit doen en controleren of de puzzel oplosbaar is