Sudoku oplossen?

Tegenwoordig heeft bijna iedereen wel eens een Sudoku puzzel gezien. Eenvoudig samengevat is een Sudoku “een puzzel bestaande uit negen bij negen vakjes die gegroepeerd zijn als negen blokken van drie bij drie vakjes. In de vakjes moeten de cijfers 1 tot en met 9 ingevuld worden op zo’n manier dat in elke horizontale lijn en in elke verticale kolom en in elk van de negen blokjes de cijfers 1 tot en met 9 één keer voorkomen” (bron: Wikipedia).

Soduko als voorbeeld van een CSP

Sudokus zijn voorbeelden van een subcategorie AI-zoekproblemen die bekend staan als CSP (Constraint-Satisfaction Problems). Zo’n probleem bestaat uit variabelen met mogelijke waarden in domeinen en beperkingsregels op de waardetoekenningen. Een oplossing voor een dergelijk probleem wordt gevonden door iedere variabele te voorzien van een domeinwaarde, waarbij tegelijkertijd aan alle beperkingsregels wordt voldaan. Bekende problemen in deze categorie zijn het achtdamesprobleem, het “Australian Map Colouring Problem” en diverse rooster-  en planningsproblemen.

Milco: “Zelf kwam ik dit soort probleem tegen in “Classic Computer Science Problems in Python” van David Kopec (Manning, 2019). Het hoofdstuk uit dit boek over CSPs is ook verschenen als artikel op de website van Manning. In het boek (en het artikel) wordt een framework beschreven om deze categorie problemen generiek op te kunnen lossen, waarbij de uitdaging vooral ligt in het correct beschrijven van de variabelen, domeinen en beperkingen. Het framework is beschikbaar op de Github repository van David Kopec’s boek.”

Microsoft Rules

Vroeger kon het opzetten van een ontwikkelomgeving nog wel wat tijd kosten, door uitdagingen met verschillende versies van compilers/interpreters, isolatie van bibliotheken en wat dies meer zij. Those were the days. Maar die zijn gelukkig nu over, want het opzetten van een ontwikkelomgeving kan tegenwoordig zo veel gemakkelijk dank zij … Microsoft. Een aantal jaar geleden ben ik – aanvankelijk schoorvoetend – steeds meer gebruik gaan maken van Visual Studio Code als ontwikkeltool, aanvankelijk naast geïntegreerde ontwikkelomgevingen als Oracle JDeveloper, JetBrains IntelliJ en PyCharm, maar tegenwoordig ben ik eigenlijk om en gebruik ik nagenoeg alleen nog maar Code. En ja, het is een “editor”, geen “IDE”, maar tegenwoordig is er zo’n overvloed aan plugins beschikbaar, dat het verschil nauwelijks meer merkbaar is.

Een van de grote voordelen van Code boven de “Community Editions” van JetBrains is het feit dat Code direct al zelf “Remote Development” ondersteunt. Hierbij krijg je een perfecte isolatie van je projecten en libraries, omdat je voor ieder project afzonderlijk een container kunt inrichten om in te ontwikkelen. Hierdoor kun je eenvoudig je projecten en al hun vereisten en afhankelijkheden gescheiden houden, zodat ze elkaar niet langer in het vaarwater zitten. Het enige wat je hiervoor lokaal moet installeren, is VS-Code (met het Remote Development Extension Pack) en Docker met WSL (maar je kunt ook op een echte remote server ontwikkelen – en als alternatief kun je met codespaces ook volledig in de Cloud werken):

Afbeelding uit Microsoft documentatie https://code.visualstudio.com/docs/remote/remote-overview

Setup

Om lokaal te kunnen beginnen, is het voldoende om een projectfolder te maken. Als je hierin een .devcontainer folder maakt, met een devcontainer.json configuratiebestand, dan weet Code genoeg om een ontwikkelcontainer te kunnen bouwen en opspinnen voor je werk. Met het onderstaande voorbeeld wordt een container aangemaakt voor Python 3.11, waarbij direct mijn favoriete Code extensies worden geïnstalleerd:

• Python Language Server voor VS-Code
• Flake (Style Guide Enforcer)
• Black (opinionated Source Code Formatter)

{ 
 "name": "Python 3", 
  "image": "mcr.microsoft.com/devcontainers/python:1-3.11-bullseye", 
  "customizations": { 
    "vscode": { 
      "extensions": [ 
        "ms-python.black-formatter", 
        "ms-python.flake8", 
        "ms-python.vscode-pylance", 
         "ms-python.python" 
      ] 
    } 
  } 
}

Bij het openen van de projectfolder wordt een nieuwe ontwikkelcontainer aangemaakt en wordt (handig!) voorgesteld om je projectdirectory direct beschikbaar te maken in de nieuwe container, zodat je alles bij de hand hebt!

Implementatie

Zoals gezegd, de uitdaging voor dit soort problemen zit vooral in het modelleren van het probleem; aangezien het probleem al kan worden opgelost met het generieke CSP-framework, is het enige resterende probleem het definiëren van de beperkingsregels die moeten gelden voor een Sudoku puzzel:

• ieder cijfer van 1 tot en met 9 moet precies één keer voorkomen:
  • in iedere rij
  • in iedere kolom
  • in ieder blok van 3×3 cellen, bestaande uit combinaties van rij/kolom 1-3, 4-6, 7-9

Hiernaast bestaan er nog andere varianten Sudokus, bijvoorbeeld de Sudoku die in het NRC wordt gepubliceerd:

Hierbij moet niet alleen aan de “normale” Sudoku regels worden voldaan, maar moet ook in de grijs gearceerde blokken (rij/kolom 2-4 & 6-8) ieder cijfer precies één keer voorkomen. Ongetwijfeld bestaan er nog veel meer varianten …

Door iedere cel te representeren als een variabele, kan er een set met beperkingsregels worden opgesteld tussen de variabelen. Zo wordt voor iedere rij voor iedere cel een beperkingsregel aangemaakt tussen die cel en alle cellen ter rechterzijde van de desbetreffende cel, aangezien deze beperkingsregels symmetrisch zijn (wat geldt voor x m.b.t. y geldt ook voor y m.b.t. x – dus ieder paar (x,y) komt slechts een keer voor). Naar analogie wordt eenzelfde set beperkingsregels opgelegd voor de kolommen en voor de ‘blokken’, waarbij deze in “NRC-modus” nog worden aangevuld met de beperkingsregels voor de grijs gearceerde blokken. Ten slotte heeft iedere beperkingsregel een methode ‘satisfied’, die aangeeft of er vanuit het oogpunt van deze beperkingsregel is voldaan aan de restrictie:

De methode satisfied controleert of gegeven de huidige waardetoekenningen in het probleem (assignment dictionary) hier voor zichzelf en de beperkende cel dezelfde waarde voorkomt. Zo niet, dan wordt (voorlopig) aan deze beperkingsregel voldaan.

At our Service

De service wordt beschikbaar gemaakt als REST API, zodat er geen aparte front-end gebouwd hoeft te worden. In Python zijn vele API frameworks beschikbaar, hier is gekozen voor FastAPI. Deze API stelt één enkel eindpunt beschikbaar, waarbij een verzoek moet worden gedaan met een JSON-representatie van de invoer; de invoer kan hier worden opgegeven als array van strings:

Sudoku van de dag (sudokuonline.nl)

Invoer als lijst van tekstregels

Invoer als ‘sparse dictionary’ – alleen de gevulde cellen

Dockerizing

De ultieme oplossing is natuurlijk een API die als service wordt aangeboden in een container, zodat deze op allerlei platforms is uit te voeren: volledig geïsoleerd van andere componenten, met zijn eigen set aan afhankelijkheden al voorgeïnstalleerd. Allereerst is hiervoor een Dockerfile nodig om een Docker image te kunnen bouwen; de service wordt gebouwd op basis van een Python 3.11 basis image, waarbij de Python afhankelijkheden worden geïnstalleerd en de service onder beperkte gebruiker (‘appuser’) wordt aangeboden door de service te starten op container poort 8080 (context /sudoku):

FROM python:3.11-slim as build
LABEL Author="Milco Numan" REPO="https://github.com/mnuman/sudocku" Language="Python"
COPY ./app app
WORKDIR /app
RUN set -ex \
    # Create a non-root user
    && addgroup --system --gid 1001 appgroup \
    && adduser --system --uid 1001 --gid 1001 --no-create-home appuser \
    # Install dependencies
    && pip install -r requirements.txt --no-cache-dir
CMD ["uvicorn", "main:app", "--host", "0.0.0.0", "--port", "8080"]
USER appuser
EXPOSE 8080

Met deze configuratie kan allereerst lokaal een Docker image worden gebouwd en getest voordat dit wordt geautomatiseerd.

Github Actions

Binnen Github bestaat de mogelijkheid om aan bepaalde gebeurtenissen automatisch acties te verbinden; zo’n gebeurtenis kan bestaan uit een issue dat wordt opgevoerd waar het ontwikkelteam actie op moet ondernemen, maar bijvoorbeeld ook uit het beschikbaar maken van nieuwe of aangepaste code in de repository. Hiermee kan ook het proces om een Docker image te bouwen en te publiceren naar een container-dump worden geautomatiseerd. Binnen Github worden hiervoor YAML files gebruikt die in de .github subdirectory van de Github-repository moeten staan:

name: Github action flow to create and push a docker image upon committing to the master branch

on:
  push:
    branches: [ "master" ]

jobs:
  build-and-push:
    runs-on: ubuntu-latest
    steps:
    - name: Check out the repo
      uses: actions/checkout@v3
    - name: Login to Docker Hub
      uses: docker/login-action@v2
      with:
        username: ${{ secrets.DOCKERHUB_USERNAME }}
        password: ${{ secrets.DOCKERHUB_TOKEN }}
    - name: Build and push Docker image
      uses: docker/build-push-action@v4
      with:
        file: ./Dockerfile
        push: true
        tags: >
          ${{ secrets.DOCKERHUB_USERNAME }}/${{ vars.DOCKER_IMAGE_NAME }}:latest, 
          ${{ secrets.DOCKERHUB_USERNAME }}/${{ vars.DOCKER_IMAGE_NAME }}:${{ github.sha }}

De bovenstaande pipeline definitie wordt actief zodra er code wordt gepusht naar de master branch van de repository. Vervolgens wordt er een ubuntu builder-image aangevraagd, waarop allereerst de code van de Github repository wordt uitgecheckt. Hierna wordt er ingelogd in Docker (gebruik makend van een geheim token – opgeslagen als repository secret met de naam DOCKERHUB_TOKEN) en wordt het Docker image gebouwd.

Als de bouw van het image succesvol is afgerond, dan wordt het image voorzien van de juiste tags (onder andere de commit identificatie) en naar de container repository gepusht, in dit voorbeeld is Docker Hub gebruikt.

The proof of the Pudding …

Hiervoor moet allereerst een docker container worden gestart, op basis van het gemaakte docker image:

Docker image wordt gestart, port 8080 wordt gemapt naar de container port (ook 8080)

Met behulp van Postman kunnen eenvoudig REST-verzoeken worden ingeschoten op een API; in het onderstaande voorbeeld wordt de Sudoku uit NRC opgelost, de aanvullende restricties worden gecommuniceerd door middel van de request parameter “mode” met waarde nrc:

Hiermee wordt het oplossen van Sudoku’s een makkie:

Oplossing van de Sudoku