DLX Algo

import numpy as np
import time as tm
import os

class Node(object):

    def __init__(self, left, right, top, bot, column_header, rowID):
        self.left = left
        self.right = right
        self.top = top
        self.bot = bot
        self.header = column_header
        self.rowID = rowID

    def __repr__(self):
        return 'node in column'+str(self.header)+'and row'+str(self.rowID)

class ColumnHeader(object):

    def __init__(self, size, name, left, right, top, bot):
        self.name = name
        self.size = size
        self.left = left
        self.right = right
        self.top = top
        self.bot = bot

    def __repr__(self):
        return 'CH ' + str(self.name) + '|size :' + self.size


class SparseMatrix(object):

    def __init__(self,matrix):
        self.m=np.copy(matrix)
        h,l=self.m.shape
        self.sm = np.vstack((np.empty((1,l), ColumnHeader),np.empty(self.m.shape, Node)))
        self.header=ColumnHeader(l,'header',None,None,None,None)

        self.createColumns()
        self.fillColumns()
        self.linkNodes()

    def createColumns(self):
        l=self.m.shape[1]

        self.sm[0,0]=ColumnHeader(0,'0',self.header,None,None,None)
        self.header.right=self.sm[0,0]

        for i in range(1,l):
            self.sm[0,i]=ColumnHeader(0,str(i),self.sm[0,i-1],None,None,None)
            self.sm[0,i-1].right=self.sm[0,i]

        self.header.left=self.sm[0,l-1]
        self.sm[0,l-1].right=self.header


    def fillColumns(self):
        h,l=self.sm.shape

        for j in range(0,l):
            column_size=0
            for i in range(1,h):
                if self.m[i-1,j]==1:
                    column_size+=1
                    self.sm[i,j]=Node(None,None,None,None,self.sm[0,j],i-1)
            self.sm[0,j].size=column_size


    def linkNodes(self):
        h,l=self.sm.shape

        for j in range(0,l):
            current_node=self.sm[0,j]
            for i in range(1,h):
                if self.sm[i,j]!=None:
                    current_node.bot=self.sm[i,j]
                    self.sm[i,j].top=current_node
                    current_node=self.sm[i,j]
            current_node.bot=self.sm[0,j]
            self.sm[0,j].top=current_node

        for i in range(1,h):
            k=0
            while self.sm[i,k] == None: k+=1
            current_node=self.sm[i,k]
            for j in range(k+1,l):
                if self.sm[i,j] != None:
                    current_node.right=self.sm[i,j]
                    self.sm[i,j].left=current_node
                    current_node=self.sm[i,j]

            current_node.right=self.sm[i,k]
            self.sm[i,k].left=current_node

    def coverColumn(self,column_header):
        column_header.left.right=column_header.right
        column_header.right.left=column_header.left

        row=column_header.bot
        while row!=column_header:
            node=row.right
            while node!=row:
                node.top.bot=node.bot
                node.bot.top=node.top
                node.header.size-=1
                node=node.right
            row=row.bot


    def uncoverColumn(self,column_header):
        row=column_header.top
        while row!=column_header:
            node=row.left
            while node!=row:
                node.top.bot=node
                node.bot.top=node
                node.header.size+=1
                node=node.left
            row=row.top

        column_header.left.right=column_header
        column_header.right.left=column_header

    def getSmallerColumn(self):
        c=self.header.right
        choice = c
        lowestsize = c.size
        while c.right != self.header:
            c=c.right
            if c.size< lowestsize:
                lowestsize = c.size
                choice = c
        return choice

    def __repr__(self):
        repr=""
        cur=self.header.right.bot
        while cur != self.header.right:
            repr += "row " + str(cur.rowID) + " \n"
            node = cur
            repr += "   -columns " + str(node.header.name) + "\n"
            node=node.right
            while node != cur:
                repr += "   -columns " + str(node.header.name) + "\n"
                node = node.right
            cur=cur.bot

        return repr


def XAlgorithm(sparse_matrix):
    solution = [None] * (sparse_matrix.header.size)
    sp=sparse_matrix

    def XAlgorithmRec(k):

        if sp.header.right==sp.header : return solution

        C=sp.getSmallerColumn()
        sp.coverColumn(C)

        row=C.bot
        while row!=C:
            solution[k]=row.rowID

            node=row.right
            while node!=row:
                sp.coverColumn(node.header)
                node=node.right

            keepSearching = XAlgorithmRec(k+1)
            if keepSearching :
                return True

            #Backing part
            node = row.left
            while node != row:
                sp.uncoverColumn(node.header)
                node=node.left

            row=row.bot

        sp.uncoverColumn(C)
        return False

    return XAlgorithmRec(0),solution


class Sudoku(object):

    def __init__(self,str,size=9): #str est une chaine de caractères, avec des 0 dans les cases vides/ size est la largeur du sudoku (9 std)
        self.matrix = []
        self.size=size
        assert (len(str)==size**2),"The string is not well sized"

        grid=self.list2dFromstr(size,str)
        for i in range(size):
            for j in range(size):
                v=grid[i][j]
                if v in range(1,size+1):
                    self.matrix.append(self.dlxRow(i,j,v)) #row of the matrix
                elif v==0:
                    for k in range(1,size+1):
                        self.matrix.append(self.dlxRow(i,j,k))


        self.sp=SparseMatrix(self.matrix)


    def solve(self):
        self.solution = XAlgorithm(self.sp)
        if not self.solution[0] :
            return False
        else:
            gridsolved=[ [None for _ in range(self.size)] for __ in range(self.size)]
            for x in self.solution[1]: #x is a row index part of the solution
                if x!=None:
                    row,col,val=self.dlx_row_to_rcv(self.matrix[x])
                    gridsolved[row][col]=val
            self.solved=np.array(gridsolved)
            return True

    def dlxRow(self,row,col,val):
        val-=1
        return self.encode(row,col)+self.encode(row,val)+self.encode(col,val)+self.encode(self.row_col_to_box(row,col),val)

    def list2dFromstr(self,size,str):
        grid=[ [None for _ in range(size)] for __ in range(size)]
        for i in range(size**2):
            grid[i//size][i%size]=int(str[i])
        return grid


    def row_col_to_box(self,row, col):
        #Return the index for the box that the given (r, c) sudoku coordinates fits into. Boxes go like this:
        #0 1 2    0 1
        #3 4 5    2 3
        #6 7 8
        d=int(np.sqrt(self.size))
        return (row - (row % d)) + (col // d)

    def encode(self,major, minor):
    #Build a list of 81 values, with a 1 in the spot corresponding to the value of the major attribute and minor attribute.
        out = [0] * self.size**2
        out [major*self.size + minor] = 1
        return out

    def dlx_row_to_rcv(self,dlxrow):
    #Pull (row,col,val) out from an encoded DLX list.
        d=self.size**2
        rowcol = dlxrow[0:d]
        rownum = dlxrow[d: 2*d]
        row,col = self.decode(rowcol)
        ignore,num = self.decode(rownum)
        return (row,col,num + 1)

    def decode(self,lst):
    #Take a list of 81 values with a single 1, decode two values out of its position. Return them in a tuple (major,minor).
        position = lst.index(1)
        minor = position % self.size
        major = position // self.size
        return (major,minor)


def Stats():
    strF=""


    strF+="###########################################\n"
    strF+="#Sudoku solver by A.Depasse, DLX algorithm#\n"
    strF+="###########################################\n"

    strF+="-------------------------------------------\n"
    strF+="Loading file \'toSolve.txt\' ...\n"
    t1=tm.clock()
    fichier=open('toSolve.txt','r')
    sudokus=fichier.read().split('\n')
    t2=tm.clock()
    strF+="File loaded in "+ str(t2-t1) +"s. \n"
    fichier.close
    strF+="-------------------------------------------\n"
    size,title=sudokus[0].split(',')
    strF+="File name : "+title+"\n"
    strF+="sudoku size : "+size+"\n"
    strF+="number of sudokus : "+ str(len(sudokus)-1) + "\n"
    strF+="-------------------------------------------\n"
    strF+="Starting solving process\n"
    deltatimes=[]
    for x in sudokus[1:]:
        t3=tm.clock()
        g=Sudoku(x,int(size))
        if not g.solve():
            strF+="Error : one sudoku cannot be solved. Interruption!\n"
            out=open("results.txt",'w')
            out.write(strF)
            out.close()
            return False
        t4=tm.clock()
        deltatimes.append(t4-t3)
    strF+="Sudokus solved ! \n"
    strF+="-------------------------------------------\n"
    strF+="Statistics : \n"
    totaltime=sum(deltatimes)
    avgtime=np.mean(deltatimes)
    strF+="Total time : "+str(totaltime)+"\n"
    strF+="Mean time for one puzzle : "+str(avgtime)+"\n"
    strF+="-------------------------------------------\n"
    out=open("results.txt",'w')
    out.write(strF)
    out.close()


Stats()