Simple Sudoku Solver Source

Here’s the code of a brute-force implementation of a recursive sudoku solver in python. An optimised version will be released after the homework deadline. I’m posting this in english just to be evil to my classmates. The important part is highlighted.

Read more and the source will be with you.

# -*- coding: utf-8 -*-

stKlicev = 0

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

def razlicne(lst):
    """
    Vrne True, ce se v seznamu lst pojavljajo sama razlicna stevila.
    Stevilo 0 pri tem ignorira.
    """
    lst = [x for x in lst if x > 0]
    return len(lst)==len(set(lst))

def veljavna(tab):
    """
    Vrne True, ce 2D tabela tab predstavlja veljavno delno resitev sudokuja
    (t.j. ce se v nobenem stolpcu, nobeni vrstici in nobenem od devetih
    3x3 kvadratov nobeno stevilo ne pojavi dvakrat.
    """
    vrsticeOk = all(razlicne(vrsta) for vrsta in tab)
    stolpciOk = all(razlicne(vrsta[i] for vrsta in tab) for i in range(9))
    kvadratiOk = all(
        razlicne(tab[i][j:j+3]+tab[i+1][j:j+3]+tab[i+2][j:j+3])
        for i in range(0,9,3) for j in range(0,9,3))
    return vrsticeOk and stolpciOk and kvadratiOk

def sudokuStr(tab):
    """
    Pretvori tabelo tab v string, primeren za izpis na ekran.
    """
    res = ""
    for y in range(9):
        if y==3 or y==6:
            res += '------+-------+------\n'
        res += ' | '.join(
            ' '.join(str(el) if el else '.' for el in tab[y][x:x+3])
            for x in range(0,9,3))
        res += '\n'
    return res
    
def resi(tab, m):
    """
    S tehniko sestopanja resi sudoku, podan s tabelo tab. Resevanje zacne z
    izpolnjevanjem tabele tab na m-tem polju.
    Funkcija vrne True, ce je uspesno postavila stevilo na m-to polje
    (in z rekurzivnimi klici tudi na vsa naslednja polja); False sicer.
    """
    global stKlicev
    stKlicev += 1
    
    if m == 81:
        return 1
    # pretvorimo zaporedno stevilko polja v koordinate v tabeli
    (x,y) = m//9, m%9
    if tab[x][y]:
        return resi(tab, m+1)
    for i in range(1,10):
        tab[x][y] = i
        # boljse preveriti veljavnost sudokuja pred klicem funkcije
        if veljavna(tab) and resi(tab, m+1):
            return 1
    tab[x][y] = 0
    return 0
    
print("Prej:"); print(sudokuStr(sudoku))
resi(sudoku, 0)
print("Potem:"); print(sudokuStr(sudoku))
print("Stevilo klicev:"); print(stKlicev)
Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

%d bloggers like this: