Génération de grilles de sudoku à partir de quelques valeurs pré remplies.

Adapté de la technique dite d'écrasement des fonctions d'ondes. (Wave function collapse Click to know more)

Fonctionnel pour la génération (mais à reprendre un peu). Pour obtenir une grille à jouer : il manque une méthode pour vider proprement la grille et ne laisser qu'une seule solution possible.

#!/usr/bin/python
# coding: UTF-8
""" Sudoku grid generator """
import time
from random import choice,randint
from numpy import array,zeros
from matplotlib.pyplot import plot,subplots,savefig,show,xlim,ylim
 
class Grid(object):
 
    def __init__(self, cells=zeros((9,9), dtype=int)):
        self.init()
        self.init_cells = cells
        self.cells += cells
        self.update_mask()
 
    def __repr__(self):
        return str( self.cells )
 
    def init(self):
        self.cells = zeros((9,9), dtype=int)
        self.mask  = array([ [ 0 ]*9 ]*9, dtype=object )
        for i in range(9):
            for j in range(9):
                self.mask[i,j] = list(range(1,10))
 
    def count(self):
        return sum([ self.cells[i,j]!=0 for i in range(9) for j in range(9) ])
 
    def find_next(self,i,j):
        if self.cells[i,j] != 0: return
        p = list(range(1,10))
        for ii in range(9):
            for k in p:
                if k not in self.mask[i,ii]:
                    p.remove(k)
                if k in p and k not in self.mask[ii,j]:
                    p.remove(k)
 
        i0 = i-i%3
        j0 = j-j%3
        for ii in range(i0,i0+3):
            for jj in range(j0,j0+3):
                for k in p:
                    if k not in self.mask[ii,jj]:
                        p.remove(k)
 
        if len(p) == 0:
            return
        v = choice( p )
        print( f"-- choice {v}" )
        self.cells[i,j] = int(v)
        self.mask[i,j]  = [ int(v) ]
 
 
    def set_cell(self, i,j,v):
        if v not in self.mask[i,j]: return
        for ii in range(9):
            if ii!=i and v in self.get_row(ii):
                return
            if ii!=j and v in self.get_col(ii):
                return
 
        self.cells[i,j] = v
 
    def get_row(self, i):
        return self.cells[i,:]
 
    def get_col(self, i):
        return self.cells[:,i]
 
    def get_box(self,i,j):
        i0 = i-i%3
        j0 = j-j%3
        return self.cells[i0:i0+3,j0:j0+3].flatten()
 
    def update_mask_from(self,i,j):
        if self.cells[i,j]!=0:
            self.mask[i,j] = [ int(self.cells[i,j]) ]
 
    def update_mask(self):
        for i in range(9):
            for j in range(9):
                if self.cells[i,j] == 0 or len(self.mask[i,j])==1: continue
                self.update_mask_from(i,j)
 
    def update_cell_from(self,i,j):
        if len(self.mask[i,j])==1:
            self.cells[i,j] = int(self.mask[i,j][0])
 
    def update_cells(self):
        for i in range(9):
            for j in range(9):
                self.update_cell_from(i,j)
 
 
    def update(self):
        unique   = self.update_mask()
        complete = self.update_cells()
        return unique or complete
 
    def is_empty_line( self, line ):
        return ( line==0 ).all()
 
    def is_valid_line( self, line ):
        v = list(range(1,10))
        return all([ v.count(x)==1 and len(line[line==x])==1 for x in line if x!=0 ])
 
    def is_complete(self):
        return not (self.cells==0).any()
 
    def empty_duplicates(self,line):
        line = list(line)
        for i,v in enumerate(line):
            if line.count(v) > 1:
                line[i] = 0
        return line
 
    def is_valid(self):
        for i in range(9):
            rowi = self.get_row(i)
            coli = self.get_col(i)
            if not self.is_valid_line( rowi ):
                self.cells[i,:] = self.empty_duplicates ( rowi )
                # print(f"-- row {i}: {self.get_row(i)} ")
                return False
            if not self.is_valid_line( coli ):
                self.cells[:,i] = self.empty_duplicates ( coli )
                # print(f"-- col {i}: {self.get_col(i)} ")
                return False
            i0 = i-i%3
            for j in range(9):
                j0 = j-j%3
                if not self.is_valid_line( self.get_box(i,j) ):
                    self.cells[i0:i0+3,j0:j0+3] = array(self.empty_duplicates ( self.get_box(i,j) )).reshape((3,3))
                    # print(f"-- box {i},{j}: {self.get_box(i,j)} ")
                    return False
        return True
 
 
    def propagate_from(self,i,j):
        cell = int(self.cells[i,j])
        if cell != 0: self.mask[i,j] = [int(cell)]
        # print( f"-- Propagate from {i},{j}" )
        for n in range(9):
            if len(self.mask[i,n])>1 and self.mask[i,n].count( cell ):
                self.mask[i,n] = [ c for c in self.mask[i,n] if c != cell ]
        for n in range(9):
            if len(self.mask[n,j])>1 and self.mask[n,j].count( cell ):
                self.mask[n,j] = [ c for c in self.mask[n,j] if c != cell ]
 
        i0 = i-i%3
        j0 = j-j%3
        for ii in range(i0, i0+3):
            for jj in range(j0,j0+3):
                if len(self.mask[ii,jj])>1 and self.mask[ii,jj].count( cell ):
                    self.mask[ii,jj] = [ c for c in self.mask[ii,jj] if c != cell ]
 
    def propagate(self):
        for i in range(9):
            for j in range(9):
                self.propagate_from(i,j)        
        return self.update()
 
    def pick_next(self):
        next_steps = [ [[i,j], len(self.mask[i,j])] for i in range(9) for j in range(9) if len(self.mask[i,j])>1 ]
        next_steps = sorted(next_steps, key=lambda x: x[1])
 
        if len(next_steps)==0: return
 
        # keep only lowest entropy
        nmin = min([ x[1] for x in next_steps ])
        next_steps = [ x for x in next_steps if x[1]==nmin ]
 
        for k in range( len(next_steps) ):
            [i,j],n = choice(next_steps)
            if self.cells[i,j] == 0: break
 
        self.cells[i,j] = int( choice( list(self.mask[i,j]) ) )
        self.mask[i,j]  = [ self.cells[i,j] ]
        self.propagate_from(i,j)
        # self.propagate()
        # self.update()
 
    def plot( self, save=False ):
        print( "--- Plot grid" )
 
        fig,ax = subplots()
 
        lw = 1
        for i in range(9):
            for j in range(9):
                if i%3==0: lw = 3
                else: lw =0.5
                plot( [i, i], [0,9], 'k-', lw=lw )
                plot( [0,9], [i, i], 'k-', lw=lw )
                if self.cells[i,j] != 0:
                    ax.text( j+0.5,9-(i+0.5),self.cells[i,j], ha='center', va='center')
 
        plot( [9,9], [0,9], 'k-', lw=3)
        plot( [0,9], [9,9], 'k-', lw=3 )
 
        xlim((0,9))
        ylim((0,9))
        ax.axis('square')
        ax.xaxis.set_visible(False)
        ax.yaxis.set_visible(False)
        filename = f"sudoku-{int(time.time())}.png"
        if save: 
            savefig( filename )
            print( f"--- Saved grid {filename}" )
        show()
 
    def solve(self, plot=False, save=False):
        n = 0
        r = 0
        t = time.time()
        while not self.is_complete():
            n += 1
            # self.update()
            self.propagate()
            self.pick_next()
            # self.update()
            self.propagate()
            if self.is_complete() and not self.is_valid():
                r += 1
                self = Grid( self.init_cells )
 
        t = time.time()-t
 
        print( self )
 
        if self.is_complete() and self.is_valid():
            print( f"--- Solved in {t:.3f} seconds ({n} iterations / {r} resets)" )
        if plot:
            self.plot( save=save )

Pour générer une grille:

# import du code ci-dessous sous le nom Sudoku.py
from Sudoku import Grid
 
# grille d'initialisation arbitraire
g0 = zeros((9,9), dtype=int)
 
# par exemple, 1ere colonne de 1 à 9
g0[:,0] = r_[ range(1,10) ]
 
# instance de grille en utilisant l'état initial g0
g = Grid( g0 )
 
# résolution
g.solve()

Pour vider la grille (pas nickel du tout mais ça aboutit):

g0 = zeros((9,9), dtype=int)
 
g0[:,0] = r_[ range(1,10) ]
 
g = Grid( g0 )
 
print(g)
 
g.solve( save=0, plot=0 )
 
solution = array(g.cells)
 
for n in range(60):
    i,j = randint(0,8),randint(1,8)
    v = g.cells[i,j]
    if v == 0: continue
    g.cells[i,j] = 0
    if v not in g.mask[i,j]: g.mask[i,j].append( v )
 
u = Grid( array(g.cells) )
 
print( g )
print( g.mask )
 
g.solve()
 
if (solution == g.cells).all():
    u.plot()