solver.py

import sys
import numpy as np
from datetime import datetime
from copy import deepcopy

def solve_sudoku(sudoku_array):
    # https://stackoverflow.com/questions/1697334/algorithm-for-solving-sudoku von:dominik von stack overflow
    # HIER ANJAS TEIL
    # Eingabe: Sudoku als mehrdimensionales Array (je Reihe ein Unter-Array),
    #          z.B: [[5, 3, 0, 0, 7, 0, 0, 0, 0], [6, 0, 0, 1, 9, 5, 0, 0, 0], ...]
    #          die Nullen entsprechen den leeren Sudoku-Feldern
    # Source: https://stackoverflow.com/a/35500280/3582159

    def output(a):
        sys.stdout.write(str(a))

    N = len(sudoku_array)

    def print_field(field):
        if not field:
            output("No solution")
            return
        for i in range(N):
            for j in range(N):
                cell = field[i][j]
                if cell == 0 or isinstance(cell, set):
                    output('.')
                else:
                    output(cell)
                if (j + 1) % 3 == 0 and j < 8:
                    output(' |')

                if j != 8:
                    output(' ')
            output('\n')
            if (i + 1) % 3 == 0 and i < 8:
                output("- - - + - - - + - - -\n")

    def read(field):
        """ Read field into state (replace 0 with set of possible values) """

        state = deepcopy(field)
        for i in range(N):
            for j in range(N):
                cell = state[i][j]
                if cell == 0:
                    state[i][j] = set(range(1, 10))

        return state

    def done(state):
        """ Are we done? """

        for row in state:
            for cell in row:
                if isinstance(cell, set):
                    return False
        return True

    def propagate_step(state):
        """ Propagate one step """

        new_units = False

        for i in range(N):
            row = state[i]
            values = set([x for x in row if not isinstance(x, set)])
            for j in range(N):
                if isinstance(state[i][j], set):
                    state[i][j] -= values
                    if len(state[i][j]) == 1:
                        state[i][j] = state[i][j].pop()
                        new_units = True
                    elif len(state[i][j]) == 0:
                        return False, None

        for j in range(N):
            column = [state[x][j] for x in range(N)]
            values = set([x for x in column if not isinstance(x, set)])
            for i in range(N):
                if isinstance(state[i][j], set):
                    state[i][j] -= values
                    if len(state[i][j]) == 1:
                        state[i][j] = state[i][j].pop()
                        new_units = True
                    elif len(state[i][j]) == 0:
                        return False, None

        for x in range(3):
            for y in range(3):
                values = set()
                for i in range(3 * x, 3 * x + 3):
                    for j in range(3 * y, 3 * y + 3):
                        cell = state[i][j]
                        if not isinstance(cell, set):
                            values.add(cell)
                for i in range(3 * x, 3 * x + 3):
                    for j in range(3 * y, 3 * y + 3):
                        if isinstance(state[i][j], set):
                            state[i][j] -= values
                            if len(state[i][j]) == 1:
                                state[i][j] = state[i][j].pop()
                                new_units = True
                            elif len(state[i][j]) == 0:
                                return False, None

        return True, new_units

    def propagate(state):
        """ Propagate until we reach a fixpoint """
        while True:
            solvable, new_unit = propagate_step(state)
            if not solvable:
                return False
            if not new_unit:
                return True

    def solve(state):
        """ Solve sudoku """

        solvable = propagate(state)

        if not solvable:
            return None

        if done(state):
            return state

        for i in range(N):
            for j in range(N):
                cell = state[i][j]
                # Do not solve if solving takes more than 1/30secs.
                curtime = datetime.now()
                #print((curtime - starttime).microseconds)
                if (curtime - starttime).microseconds > (1000000/3):
                    print("jumped solving because took too long")
                    return None

                if isinstance(cell, set):
                    for value in cell:
                        new_state = deepcopy(state)
                        new_state[i][j] = value
                        solved = solve(new_state)
                        if solved is not None:
                            return solved
                    return None


    starttime = datetime.now()
    print("started solving")
    res = None
    # do not solve sudokus with less than 5 known numbers (of 81)
    if(np.count_nonzero(sudoku_array) >= 5):
        state = read(sudoku_array)
        res = solve(state)
        if res is not None:
            print("solved")
        else:
            print("could not solve")
        #print_field(res)
    else:
        print("jumped solving because less than 5 known numbers")

    # Ausgabe: gelöstes Sudoku in der gleichen Struktur oder wenn unlösbar: original-sudoku
    return res if res else sudoku_array