TAGS :Viewed: 14 - Published at: a few seconds ago

[ Python sudoku solver stops in the middle ]

So, I decided to write a Sudoku solver using Backtrack method to solve a sudoku. It seemed to me that I got it working, but it doesn't. It seems to me that when it has to move back to the previous ROW it cannot handle it, it can only move back in the same row it seems to me. Feel free to ask more questions, the code is the following (sorry that it's not in English):

import sys

rida = 0
veerg = 0
maatriks = []

# Loeb failist maatriksi sisse ja teeb temast listide listi.
def looMaatriks(sisendfail, maatriks):
    fail = open(sisendfail)
    for line in fail:
        line = line.strip()
        if line != "":
            rida = line.split(" ")
            for i in range (0, 9):
                if rida[i] != "-":
                    rida[i] = int(rida[i])
                else:
                    rida[i] = 0
            print(line.split(" "))
            maatriks.append(rida)
    return maatriks

maatriks = looMaatriks('sisend1.txt', maatriks)
#print(maatriks)

# Kontrollib, kas antud ruudukeses on number juba või mitte.
def numberOlemas(maatriks, rida, veerg):
    print(rida)
    print(veerg)
    if maatriks[rida][veerg] != 0:
        return True
    else:
        return False

print(numberOlemas(maatriks, 1,0))

# Kontrollib, kas arv sobib antud ruutu.
def kasSobib(maatriks, rida, veerg, arv):
    for i in range (0, 9):
        if arv == maatriks[rida][i]:
            return False
    for i in range (0, 9):
        if arv == maatriks[i][veerg]:
            return False
    return True

def prindiMaatriks(maatriks):
    for i in range (0, 9):
        print(maatriks[i])
    print("")

def lahendaRuut(maatriks, rida, veerg):
    prindiMaatriks(maatriks)

    if numberOlemas(maatriks, rida, veerg) == True:
        print("juba olemas")
        if veerg > 7:
            print("yolo2");
            rida = rida + 1
            if rida > 8:
                print("DONE!")
                sys.exit()
            veerg = -1        
        lahendaRuut(maatriks, rida, veerg + 1)
    else:
        for i in range (1, 10):
            if kasSobib(maatriks, rida, veerg, i):
                maatriks[rida][veerg] = i
                if veerg > 7:
                    print("yolo");
                    rida = rida + 1
                    if rida > 8:
                        print("DONE!")
                        sys.exit()
                    veerg = -1
                lahendaRuut(maatriks, rida, veerg + 1)
            print("ei sobi")

    prindiMaatriks(maatriks)
lahendaRuut(maatriks, rida, veerg)

Answer 1


The problem is that you never remove the wrong numbers. The sudoku is gradually being filled with wrong numbers in random places.

def lahendaRuut(maatriks, rida, veerg):
    prindiMaatriks(maatriks)

    if numberOlemas(maatriks, rida, veerg) == True:
        print("juba olemas")
        if veerg > 7:
            print("yolo2");
            rida = rida + 1
            if rida > 8:
                print("DONE!")
                sys.exit()
            veerg = -1        
        lahendaRuut(maatriks, rida, veerg + 1)
    else:
        for i in range (1, 10):
            if kasSobib(maatriks, rida, veerg, i):
                maatriks[rida][veerg] = i
                if veerg > 7:
                    print("yolo");
                    rida = rida + 1
                    if rida > 8:
                        print("DONE!")
                        sys.exit()
                    veerg = -1
                lahendaRuut(maatriks, rida, veerg + 1)
            print("ei sobi")

         #=========================
         # very important line of code
         # resets the cell before the algorithm backtracks
         maatriks[rida][veerg] = 0 
         #=========================


    prindiMaatriks(maatriks)