Kategorier
Python

Lös sudoku med Python

Sudoku är ett japanskt pusselspel som nu för tiden går att hitta i varenda tidning. Här presenteras en lösning för dig som har tröttnat på den gamla vanliga papper och penna-metoden.

Jag fick ett mejl av min morfar igår. Han hade fastnat i ett klassiskt sudokupussel och efterfrågade vägledning. Rimligast hade förstås varit om jag slog mig ner med papper och penna, gnuggat geniknölarna och försökt komma fram till vilken strategi jag kunde delge morfar. Det gjorde jag inte. Istället slog tanken mig om ett Pythonprogram som automatiskt kan lösa alla möjliga sudokupussel. Så blev det.

Skärmdump på mejl där hjälp med sudoku efterfrågas.
Expressens kluriga sudoku. Kan vi lösa det med Python?

Vad är ett sudoku?

Jag misstänker att de flesta vet hur ett sudoku ska lösas – åtminstone i teorin. Men en snabb repetition kan nog ändock vara på sin plats. Ett sudokupussel består av 3 x 3 lådor, som i sin tur innehåller 3 x 3 celler. Hela spelplanen består således av 81 celler fördelade på 9 rader och 9 kolumner. Tanken med spelet är att du ska placera ut siffrorna 1-9 så att varje rad, kolumn och låda innehåller varje siffra exakt en gång.

Backtracking-baserad algoritm

En snabb sökning visar att det finns flera etablerade algoritmer för att lösa de flesta sudokupussel på några få sekunder. Jag kommer använda backtracking som strategi, mest eftersom det är en tämligen lättbegriplig algoritm som enkelt kan omsättas i kod.

Backtracking kan liknas vid en typ av totalsökning och innebär att vi provar att fylla i de tomma cellerna en efter en med tillåtna siffror. Om vi når en cell där ingen av siffrorna 1-9 är tillåtna, backar vi ett steg och väljer nästa tillåtna siffra.

Tillvägagångssättet kan beskrivas i följande steg:

  1. Hitta en tom cell.
  2. Tilldela cellen det lägsta tillåtna värdet.
  3. Gå vidare till nästa tomma cell.
  4. Om du når en cell som inte kan tilldelas något tillåtet värde måste någonting vara fel. Gå då tillbaka till föregående cell och tilldela den nästa tillåtna värde istället.
  5. När inga tomma celler finns kvar är pusslet löst.

Från algoritm till kod

Vi börjar med att importera de moduler och bibliotek vi kommer använda oss av. Jag har valt att använda mig av NumPy, som är ett populärt bibliotek för vetenskapliga beräkningar. NumPy låter oss strukturera data i array-objekt, vilket underlättar när vi senare vill referera till specifika delar av spelplanen. Dessutom resulterar det i en tydligare utskrift av spelplanen.

import numpy as np
import time

Morfars pussel representeras här av en lista med listor. Värdet 0 betyder att cellen ännu inte har någon siffra.

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

Vi skapar en klass vid namn Sudoku och skapar en instans av klassen genom att skicka med spelplanen ovan. Vi kan nu hitta värdet i en specifik cell med hjälp av koordinaterna i rutsystemet. Till exempel ger self.board[1][3] värdet tre, eftersom det är värdet i cellen belägen på den andra raden och fjärde kolumnen. Observera att:

  • Y-värdet anges inom första hakparenteserna, och sedan x-värdet i andra.
  • Vi börjar räkna från det övre vänstra hörnet.
  • Vi börjar räkna från 0. Koordinaterna (0, 8) avser alltså övre högra hörnet.
class Sudoku:
    def __init__(self, board):
        self.board = np.array(board)
        
sudoku = Sudoku(puzzle)

Klassen ska berikas med fem metoder:

  1. print_board()
  2. find_empty_cell()
  3. get_box()
  4. is_valid()
  5. solve()

Ingen vidare förklaring behövs till print_board(), som helt enkelt skriver ut spelplanen i terminalen. Här finns uppenbara utvecklingsmöjligheter.

    def print_board(self):
        print(self.board)

Metoden find_empty_cell() går igenom spelplanen och returnerar koordinaterna till den första tomma cell som hittas.

    def find_empty_cell(self):
        for row_number, row in enumerate(self.board):
            for column_number, cell in enumerate(row):
                if cell == 0:
                    return (row_number, column_number)
        return None

För att kunna avgöra vilka siffror som är tillåtna i en given cell, måste vi kunna ta reda på vilka siffror som redan finns i den låda som cellen är belägen i. Kom ihåg: en låda är den struktur om 3 x 3 celler i vilken varje siffra bara får förekomma en gång.

Först beräknar vi lådans koordinater genom att dividera cellens y- respektive x-koordinater med 3, och avrundar resultatet nedåt till närmaste heltal. Om cellen är belägen vid (1, 3) blir således koordinaterna till lådan (0, 1), det vill säga den mittersta lådan på övre raden.

De värden som hör till lådan i fråga får vi genom att börja räkna vid det index som fås när vi multiplicerar respektive koordinat med 3, och sedan räknar 3 index framåt.

    def get_box(self, y, x):
        box = (y // 3, x // 3)
        return self.board[box[0]*3:box[0]*3+3,box[1]*3:box[1]*3+3]

Nu kan vi implementera is_valid(), som kontrollerar om en viss siffra (n) är ett giltigt värde för en given cell (y, x).

Kontrollen består av tre enkla delar. Först kollar vi om n redan finns i raden y, sedan om n redan finns i kolumnen x. Till sist kollar vi, med hjälp av get_box(), om värdet finns i den låda cellen är placerad i.

    def is_valid(self, y, x, n):

        #Check for n in row y
        if n in self.board[y]:
            return False

        #Check for n in column x
        if n in self.board[:,x]:
            return False

        #Check for n in box
        if n in self.get_box(y, x):
            return False

        return True

Slutligen implementerar vi logiken för själva backtracking-algoritmen i metoden solve(). Vi hämtar en tom cell och går igenom siffrorna 1-9. När vi hittar en siffra som är ett tillåtet värde i cellen så tilldelar vi cellen det värdet. Vi anropar sedan samma metod vi befinner oss i igen, för att fylla i nästa tomma cell. Om ingen av siffrorna 1-9 är tillåtna i den nya cellen så sätter vi den ursprungliga cellen till 0 igen och backar ett steg.

    def solve(self):
        empty_cell = self.find_empty_cell()
        if not empty_cell:
            return True
        else:
            y, x = empty_cell

        for n in range(1,10):
            if self.is_valid(y, x, n):
                self.board[y][x] = n

                if self.solve():
                    return True

                self.board[y][x] = 0

        return False

Kör programmet och lösningen ges på ett par sekunder:

start = time.perf_counter()
sudoku.solve()
end = time.perf_counter()

print(f'Solved in {end - start:0.2f} seconds:')

sudoku.print_board()
Solved in 1.74 seconds:
[[7 4 5 2 8 6 1 3 9]
 [8 9 1 3 5 4 6 7 2]
 [6 3 2 7 9 1 5 8 4]
 [1 5 4 6 7 8 9 2 3]
 [3 2 7 9 4 5 8 1 6]
 [9 8 6 1 3 2 7 4 5]
 [5 1 3 8 2 9 4 6 7]
 [2 6 9 4 1 7 3 5 8]
 [4 7 8 5 6 3 2 9 1]]

Sen hur mycket det här hjälper morfar låter jag vara osagt.

Hela koden

# coding: utf8
import numpy as np
import time

class Sudoku:

    def __init__(self, board):
        self.board = np.array(board)

    def solve(self):
        empty_cell = self.find_empty_cell()
        if not empty_cell:
            return True
        else:
            y, x = empty_cell

        for n in range(1,10):
            if self.is_valid(y, x, n):
                self.board[y][x] = n

                if self.solve():
                    return True

                self.board[y][x] = 0

        return False

    def get_box(self, y, x):
        box = (y // 3, x // 3)
        return self.board[box[0]*3:box[0]*3+3,box[1]*3:box[1]*3+3]

    def is_valid(self, y, x, n):

        #Check for n in row y
        if n in self.board[y]:
            return False

        #Check for n in column x
        if n in self.board[:,x]:
            return False

        #Check for n in box
        if n in self.get_box(y, x):
            return False

        return True

    def find_empty_cell(self):
        for row_number, row in enumerate(self.board):
            for column_number, cell in enumerate(row):
                if cell == 0:
                    return (row_number, column_number)
        return None

    def print_board(self):
        print(self.board)

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

sudoku = Sudoku(puzzle)

start = time.perf_counter()
sudoku.solve()
end = time.perf_counter()

print(f'Solved in {end - start:0.2f} seconds:')

sudoku.print_board()

Lämna ett svar

E-postadressen publiceras inte. Obligatoriska fält är märkta *