Discussion :

[Arbraz]

Ci joint une fonction Python récursive qui donne une solution pour une grille de Sudoku.
Cette fonction peut être améliorée, mais là n'est pas le propos.

Le programme s'arrête après avoir trouvé une solution.
Je souhaite :
- compter le nombre de solutions ;
- conserver chaque solution s'il y en a plusieurs.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
def PositionValide(position):
    if position == 81:
        return True
    ligne = position // 9
    colonne = position % 9
    if (Grille[ligne][colonne]) != 0:
        return PositionValide(position + 1)
    for nombre in range(0, 10):
        if absentDeCase(Grille, nombre, ligne, colonne):
            Grille[ligne][colonne] = nombre
            if PositionValide(position + 1):
                return True
    Grille[ligne][colonne] = 0
    return False

Des idées ? Merci

[Sve@r]

Des idées ?

Bonjour
Tout d'abord il ne faut pas que ta fonction s'arrête dès qu'elle est en position 81 (ok, tout le monde a bien compris que "position=81" signifie que tu as trouvé la 81° case donc que t'as rempli ta grille) mais que justement là elle incrémente un compteur et mémorise la position courante. Puis elle remonte à l'étape précédente et repart explorer une autre branche.
Bien entendu le tableau des positions à mémoriser et le compteur seront transmis d'appel en appel (encore que le compteur ait peu d'intérêt puisqu'il correspond au nombre de positions mémorisées).

Maintenant question utilité je pense que c'est faible. Parce que si tu pars d'une grille avec des nombres déjà placés alors généralement il n'y a qu'une solution (et dans ce cas en plus ton test position == 81 ne pourra pas être vrai donc tu ne la trouveras pas) et si tu pars d'une grille vide alors le nombre de solutions est connu (il est assez grand mais il reste fixé et invariant).