Deze opgave is gebaseerd op een opgave uit het herexamen van het academiejaar 2017-2018.

In deze opgave zul je alle leerstof en technieken uit de voorbije opgaves combineren om een Sudoku klasse te schrijven. Deze klasse bevat een aantal methoden bevatten om de sudoku in te vullen, maar ook hulpmethodes om deze op te lossen. Een volledige sudoku-solver zul je in deze opgave echter niet implementeren, aangezien dit buiten de scope van dit vak valt. Echter, als je alle hulpmethodes in deze klasse met elkaar combineert, is het mogelijk om een (weliswaar eenvoudige) solver te maken.

Sudoku

Als je reeds weet wat een Sudoku is en wat de regels zijn, kan je deze sectie overslaan.

Een sudoku is een Japanse cijferpuzzel, die bestaat uit een rooster van 81 vakjes (9 rijen x 9 kolommen). Deze 9 rijen en kolommen worden op hun beurt ook nog eens onderverdeeld per 3, zodanig dat het volledige rooster 9 blokken van 9 cijfers bevat. Om een sudoku op te lossen, moet in elk van deze 81 vakjes een cijfer van 1 tot 9 worden ingevuld, op zo’n manier dat aan al onderstaande regels tegelijk is voldaan.

Sudoku

Regels

Elk cijfer mag, per rij, maar 1 keer voorkomen

Correct
Fout

Elk cijfer mag, per kolom, maar 1 keer voorkomen

Correct
Fout

Elk cijfer mag, per blok, maar 1 keer voorkomen

Correct
Fout

Nummering

We maken volgende afspraken bij de nummering van rijen, kolommen en blokken:

Rijen
Kolommen
Blokken

Opgave

Maak een Java-klasse Sudoku. Deze klasse stelt een sudoku voor en moet minstens volgende constructor en methoden bevatten. Je bent volledig vrij om de nodige instantievariabelen te kiezen en het is ook toegelaten (en aangeraden!) om extra methodes toe te voegen, om je dubbel werk en hoofdpijn te besparen.

Constructor

De constructor van de Sudoku-klasse moet volgende signatuur hebben. De constructor bevat dus geen argumenten.

Sudoku();

Methodes

Deze methodes zijn alfabetisch gesorteerd, het is aangeraden om ze niét in deze volgorde te maken.

allowedValues()

int[] allowedValues(int row, int column);

Deze methode geeft een array terug van alle waarden die zijn toegelaten in de cel op rij row, kolom column. Het maakt niet uit of deze cel reeds is ingevuld of niet. Zie verder de isAllowed()-methode. De volgorde van de cijfers in deze array is niet belangrijk, de test zal deze toch sorteren.

equals()

boolean equals(Object other);

Deze equals()-methode geeft true terug als deze Sudoku gelijk is aan een ander object, dat al dan niet ook een Sudoku is. De definitie van deze equals()-methode is hetzelfde als in de Klassement (deel 1)1 opgave. Bij deze opgave staat uitgelegd hoe je deze methode moet implementeren, je kan deze kopiëren en aanpassen om hier te gebruiken.

getBlock()

int[] getBlock(int block);

Deze methode geeft een array terug van alle waarden in een gegeven blok, van links naar rechts, van boven naar onder. De lengte van deze array moet steeds gelijk zijn aan 9. Cellen die nog niet zijn ingevuld, worden voorgesteld door het cijfer 0. Hou rekening met de hierboven aangegeven nummering.

getCell()

int getCell(int row, int column);

Deze methode returnt het ingevulde cijfer in de cel op rij row, kolom column. Indien deze cel nog niet was ingevuld, moet deze methode 0 teruggeven.

getColumn()

int[] getColumn(int column);

Deze methode geeft een array terug van alle waarden in een gegeven kolom, van boven naar onder. De lengte van deze array moet steeds gelijk zijn aan 9. Cellen die nog niet zijn ingevuld, worden voorgesteld door het cijfer 0. Hou rekening met de hierboven aangegeven nummering.

getFirstEmpty()

int[] getFirstEmpty();

Deze methode geeft een array terug van lengte 2, die de eerste lege (niet ingevulde) cel in de sudoku voorstelt. Om de eerste lege cel te bepalen, wordt de sudoku rij per rij overlopen van boven naar onder, vervolgens van links naar rechts. Stel dat de eerste lege cel zich bevindt op de 5e rij, in de 2e kolom, dan zal deze methode de array [5, 2] teruggeven. Als de sudoku volledig is ingevuld (er zijn geen lege cellen), wordt de array [0, 0] teruggegeven.

getRow()

int[] getRow(int row);

Deze methode geeft een array terug van alle waarden in een gegeven rij, van links naar rechts. De lengte van deze array moet steeds gelijk zijn aan 9. Cellen die nog niet zijn ingevuld, worden voorgesteld door het cijfer 0. Hou rekening met de hierboven aangegeven nummering.

isAllowed()

boolean isAllowed(int row, int column, int value);

Deze methode geeft true terug wanneer het cijfer value in de cel op rij row, kolom column mag staan. Het is niet belangrijk of in deze cel al een cijfer staat of niet, het resultaat moet enkel false zijn wanneer niet voldaan is aan alle drie de regels.

isComplete()

boolean isComplete();

Deze methode geeft true terug wanneer alle cellen van de sudoku zijn ingevuld. Deze cellen mogen ongeldige waarden bevatten, zolang ze maar niet leeg zijn.

isSolved()

boolean isSolved();

Deze methode geeft true terug wanneer alle cellen van de sudoku zijn ingevuld én wanneer elke cel een waarde bevat die voldoet aan alle bovenstaande regels.

setCell()

void setCell(int row, int column, int value);

Deze methode vult het cijfer value in in de cel op rij row, kolom column. Deze methode moet niet controleren of deze waarde al dan niet toegelaten is in die cel. Wanneer deze cel reeds ingevuld was, moet deze simpelweg worden overschreven met de nieuwe waarde.

toString()

String toString();

Deze methode geeft een String-representatie terug van de sudoku, zoals in onderstaand voorbeeld. Cellen die nog niet zijn ingevuld, worden voorgesteld door een punt (.).

+-------+-------+-------+
| 5 3 . | . 7 . | . . . |
| 6 . . | 1 9 5 | . . . |
| . 9 8 | . . . | . 6 . |
+-------+-------+-------+
| 8 . . | . 6 . | . . 3 |
| 4 . . | 8 . 3 | . . 1 |
| 7 . . | . 2 . | . . 6 |
+-------+-------+-------+
| . 6 . | . . . | 2 8 . |
| . . . | 4 1 9 | . . 5 |
| . . . | . 8 . | . 7 9 |
+-------+-------+-------+

Lokaal testen

Je kan je geschreven methodes eenvoudig zelf testen door in de Sudoku-klasse een main() methode te schrijven, waarin je een nieuwe instantie van je Sudoku-klasse aanmaakt, wat cellen invult en controleert of het resultaat klopt. Deze methode zal door de test genegeerd worden, dus je kan dit gerust laten staan wanneer je indient. Voorbeeld:

public class Sudoku {
  // andere methodes van de Sudoku klasse
  // staan hierboven.
  public static void main(String[] args) {
    Sudoku s = new Sudoku();

    s.setCell(1, 1, 1);

    if(s.getCell(1, 1) == 1) {
      System.out.println("setCell en getCell werken :)");
    }
  }
}

Appendix: Sudoku solver

Zoals reeds eerder aangegeven heb je in deze opgave alle hulpmethodes geïmplementeerd om een sudoku solver te maken. Aangezien het schrijven van de solve-methode geen deel uitmaakte van deze opgave, krijg je deze hieronder gegeven voor de volledigheid. Deze methode kan eender welke sudoku oplossen in ongeveer 1 seconde. Het idee achter de werking is vrij eenvoudig, namelijk: Probeer op elke lege cel in de sudoku, elke toegelaten waarde.

public void solve() {
    // Zoek de eerste lege cel.
    int[] firstEmpty = this.getFirstEmpty();
    int row = firstEmpty[0];
    int column = firstEmpty[1];
    // Probeer enkel iets als er nog lege cellen zijn.
    if (firstEmpty[0] != 0) {
        // Probeer elke toegelaten waarde in te vullen op de eerste lege cel.
        for (int tryValue : this.allowedValues(row, column)) {
            // Vul een toegelaten waarde in.
            this.setCell(row, column, tryValue);
            // Roep de huidige methode nog eens op; nu zal de volgende lege cel worden
            // geprobeerd, aangezien er reeds een cel werd ingevuld op de bovenstaande
            // lijn. Op deze manier vullen we de volledige sudoku in.
            this.solve();
            
            if (this.isSolved()) {
                // Indien de sudoku opgelost zou zijn, zoek niet verder naar oplossingen.
                return;
            } else {
                // De sudoku is niet opgelost. Maak de huidige cel terug leeg en probeer
                // in de volgende iteratie de volgende toegelaten waarde.
                this.setCell(row, column, 0);
            }
        }
    }
}

Hierbij nog wat uitleg over de Dodona-testen voor deze oefening: