Sudoku


Spielregeln: In der Standardvariante müssen in einem 9x9 Gitter die Zahlen 1 bis 9  derart in die Felder gesetzt werden, dass in jeder Zeile und jeder Spalte alle Zahlen genau einmal vorkommen. Zudem wird das Gitter in 9 Untergitter mit 3x3 Feldern aufgeteilt, wobei auch in diesen die Zahlen genau einmal auftreten müssen. Zu Beginn des Spiel ist bereits eine bestimmte Anzahl der Zellen besetzt. Bei idealer Spielvorgabe sollte es genau eine Lösung geben.

Für die grafische Darstellung eignet sich ein GameGrid hervorragend, da das Spiel eine Gitterstruktur aufweist. Die Vorgabezahlen zeichnest du als TextActor schwarz ein, die eingesetzten Zahlen sind rot. In folgender Spielimplementierung ist eine Funktion isValid(state) eingebaut, die überprüft, ob ein bestimmter Spielzustand state die Spielregeln befolgt.

 

# Sudoku.py

from gamegrid import *

def pressEvent(e):
    loc = toLocationInGrid(e.getX(), e.getY())
    if loc in fixedLocations:
        setStatusText("Location fixed")
        return
    xs = loc.x // 3
    ys = loc.y // 3
    x = loc.x % 3
    y = loc.y % 3
    value = startState[ys][xs][y][x]
    value = (value + 1)  % 10
    startState[ys][xs][y][x] = value
    showState(startState)
    if isValid(startState):
        setStatusText("State valid")
    else:
        setStatusText("Invalid state")

def showState(state):
    removeAllActors()
    for ys in range(3):
        for xs in range(3):
            for y in range(3):
                for x in range(3):
                    loc = Location(x + 3 * xs, y + 3 * ys)
                    value = state[ys][xs][y][x]
                    if  value != 0:
                        if loc in fixedLocations:
                            c = Color.black
                        else:
                            c = Color.red
                        digit = TextActor(str(value), c, Color.white, 
                                Font("Arial", Font.BOLD, 20))
                        addActorNoRefresh(digit, loc)
    refresh()

def isValid(state):
    # Check lines
    for ys in range(3):
        for y in range(3):
            line = []
            for xs in range(3):
                for x in range(3):
                    value = state[ys][xs][y][x]
                    if value > 0 and value in line:
                        return False
                    else:
                        line.append(value)    
    # Check rows
    for xs in range(3):
        for x in range(3):
            row = []
            for ys in range(3):
                for y in range(3):
                    value = state[ys][xs][y][x]
                    if value > 0 and value in row:
                        return False
                    else:
                        row.append(value)    

    # Check subgrids
    for ys in range(3):
        for xs in range(3):
            subgrid = state[ys][xs]
            square = []
            for y in range(3):
                for x in range(3):
                    value = subgrid[y][x]
                    if value > 0 and value in square:
                        return False
                    else:
                        square.append(value)
    return True

makeGameGrid(9, 9, 50, Color.red, False, mousePressed = pressEvent)
show()
setTitle("Sudoku")
addStatusBar(30)
visited = []
setBgColor(Color.white)
getBg().setLineWidth(3)
getBg().setPaintColor(Color.red)
for x in range(4):
    getBg().drawLine(150 * x, 0, 150 * x, 450) 
for y in range(4):
    getBg().drawLine(0, 150 * y, 450, 150 * y) 

stateWiki = [[[[0, 3, 0], [0, 0, 0], [0, 0, 8]],
              [[0, 0, 0], [1, 9, 5], [0, 0, 0]],  
              [[0, 0, 0], [0, 0, 0], [0, 6, 0]]], 
             [[[8, 0, 0], [4, 0, 0], [0, 0, 0]],
              [[0, 6, 0], [8, 0, 0], [0, 2, 0]],
              [[0, 0, 0], [0, 0, 1], [0, 0, 0]]],
             [[[0, 6, 0], [0, 0, 0], [0, 0, 0]],
              [[0, 0, 0], [4, 1, 9], [0, 0, 0]],
              [[2, 8, 0], [0, 0, 5], [0, 7, 0]]]]   
startState = stateWiki

fixedLocations = [] 
for xs in range(3):
    for ys in range(3):
        for x in range(3):
            for y in range(3):
                if startState[ys][xs][y][x] != 0:
                    fixedLocations.append(Location(x + 3 * xs, y + 3 * ys))

showState(startState)
Programmcode markieren (Ctrl+C kopieren, Ctrl+V einfügen)


Erklärungen zum Programmcode:
In der Funktion isValide() muss man die 9 Zeilen und 9 Spalten, sowie die 9 quadratischen Blöcke überprüfen. Die bereits vorhandenen Zahlen werden in eine Liste values aufganommen. Kommt die Zahl bereits darin vor, so handelt es sich um einen illegalen Spielzustand. Das Resultat wird in der Statusbar ausgeschrieben.

Ein Sudoku-Programm, in dem der Computer selbst Lösungen sucht, finden Sie unter programmierkonzepte.ch.