main?urlpath=git-pull%3Frepo%3Dhttps%253A%252F%252Fgithub.com%252Fmp2i-info%252Fmp2i-info.github.io%26urlpath%3Dlab%252Ftree%252Fmp2i-info.github.io%252F4_c%252Ftp%252F8_sudoku.ipynb%26branch%3Dmain)

Un sudoku est une grille $9\times 9$ pouvant contenir des entiers de $0$ à $8$, dont certains sont remplis. Le but est de remplir les cases manquantes de façon à ce que chaque ligne, colonne et carré de taille $3\times 3$.
Voici un exemple de sudoku (à gauche) avec une solution (à droite) :

In [1]:

int m_ex[9][9] = {
    { -1, 3, -1, -1, -1, -1, 0, 6, 8 }, 
    { -1, -1, 1, -1, -1, 7, -1, 4, 3 }, 
    { -1, -1, 5, -1, -1, 4, -1, -1, 7 }, 
    { -1, 7, -1, -1, 6, -1, 8, 0, -1 }, 
    { -1, 4, -1, -1, 8, -1, -1, 2, -1 }, 
    { -1, 0, 8, -1, 5, -1, -1, 3, -1 }, 
    { 2, -1, -1, 3, -1, -1, 6, -1, -1 }, 
    { 4, 6, -1, 0, -1, -1, 1, -1, -1 }, 
    { 8, 1, 7, -1, -1, -1, -1, 5, -1 }
}
int m_ex[9][9] = {
    { -1, 3, -1, -1, -1, -1, 0, 6, 8 }, 
    { -1, -1, 1, -1, -1, 7, -1, 4, 3 }, 
    { -1, -1, 5, -1, -1, 4, -1, -1, 7 }, 
    { -1, 7, -1, -1, 6, -1, 8, 0, -1 }, 
    { -1, 4, -1, -1, 8, -1, -1, 2, -1 }, 
    { -1, 0, 8, -1, 5, -1, -1, 3, -1 }, 
    { 2, -1, -1, 3, -1, -1, 6, -1, -1 }, 
    { 4, 6, -1, 0, -1, -1, 1, -1, -1 }, 
    { 8, 1, 7, -1, -1, -1, -1, 5, -1 }
}

In [2]:

int m_ex_solved[9][9] = {
    { 7, 3, 4, 5, 2, 1, 0, 6, 8 },
    { 6, 2, 1, 8, 0, 7, 5, 4, 3 },
    { 0, 8, 5, 6, 3, 4, 2, 1, 7 },
    { 5, 7, 2, 4, 6, 3, 8, 0, 1 },
    { 3, 4, 6, 1, 8, 0, 7, 2, 5 },
    { 1, 0, 8, 7, 5, 2, 4, 3, 6 },
    { 2, 5, 0, 3, 1, 8, 6, 7, 4 },
    { 4, 6, 3, 0, 7, 5, 1, 8, 2 },
    { 8, 1, 7, 2, 4, 6, 3, 5, 0 }
};
int m_ex_solved[9][9] = {
    { 7, 3, 4, 5, 2, 1, 0, 6, 8 },
    { 6, 2, 1, 8, 0, 7, 5, 4, 3 },
    { 0, 8, 5, 6, 3, 4, 2, 1, 7 },
    { 5, 7, 2, 4, 6, 3, 8, 0, 1 },
    { 3, 4, 6, 1, 8, 0, 7, 2, 5 },
    { 1, 0, 8, 7, 5, 2, 4, 3, 6 },
    { 2, 5, 0, 3, 1, 8, 6, 7, 4 },
    { 4, 6, 3, 0, 7, 5, 1, 8, 2 },
    { 8, 1, 7, 2, 4, 6, 3, 5, 0 }
};

Vérification¶

Ici, on veut vérifier qu'une grille contient bien tous les entiers de $0$ à $8$. Pour cela, on code un sous-ensemble $S$ de $\{0, ..., 8\}$ par un entier dont la représentation binaire vaut $1$ en position $i$ si $i \in S$ (comme pour le TP 1, le revoir si nécessaire).

Exercice

Écrire une fonction int to_set(int) convertissant un entier $i$ en l'ensemble $\{i\}$ (c'est-à-dire $1\underbrace{0...0}_i = 2^i$).

Solution

In [3]:

int to_set(int n) {
    if(n == -1)
        return 0;
    return 1 << n;
}
int to_set(int n) {
    if(n == -1)
        return 0;
    return 1 << n;
}

Écrire une fonction bool full(int) telle que, si s est un entier représentant un ensemble, full(s) détermine si s contient tous les entiers entre $0$ et $8$ (c'est-à-dire : teste si s est égal à $\underbrace{111111111}_9 {}_2$).

Solution

In [4]:

bool full(int s) {
    return s == 511;
}
bool full(int s) {
    return s == 511;
}

Écrire une fonction int line(int m[9][9], int) telle que, si m est un sudoku, line(m, i) renvoie l'ensemble des chiffres apparaissant sur la ligne i de m. Par exemple, line(m_ex, 0) doit renvoyer $101001001_2 = 2^0 + 2^3 + 2^6 + 2^8 = 329$ (correspondant à l'ensemble $\{0, 3, 6, 8\}$ des chiffres apparaissant sur la première ligne de m_ex).

Solution

In [7]:

int line(int m[9][9], int i) {
    int l = 0;
    for(int j = 0; j < 9; j++)
        l |= to_set(m[i][j]);
    return l;
}

line(m_ex, 0)
int line(int m[9][9], int i) {
    int l = 0;
    for(int j = 0; j < 9; j++)
        l |= to_set(m[i][j]);
    return l;
}

line(m_ex, 0)

Out[7]:

Exercice

Écrire une fonction int column(int m[9][9], int) telle que, si m est un sudoku, column(m, j) renvoie l'ensemble des chiffres apparaissant sur la colonne j de m. Par exemple, column(m_ex, 0) doit renvoyer $100010100_2 = 2^2 + 2^4 + 2^8 = 276$ (correspondant à l'ensemble $\{2, 4, 8\}$ des chiffres apparaissant sur la première colonne de m_ex).

Solution

In [8]:

int column(int m[9][9], int j) {
    int c = 0;
    for(int i = 0; i < 9; i++)
        c |= to_set(m[i][j]);
    return c;
}

column(m_ex, 0)
int column(int m[9][9], int j) {
    int c = 0;
    for(int i = 0; i < 9; i++)
        c |= to_set(m[i][j]);
    return c;
}

column(m_ex, 0)

Out[8]:

Exercice

Écrire une fonction int square(int m[9][9], int) telle que, si m est un sudoku, square(m, k) renvoie l'ensemble des chiffres apparaissant sur le carré numéro k (avec la numérotation sur la figure de l'exemple) de m. Par exemple, square(m_ex, 1) doit renvoyer $010010000_2 = 2^4 + 2^7 = 144$ (correspondant à l'ensemble $\{4, 7\}$ des chiffres apparaissant sur le carré numéroté $1$ de m_ex).

Solution

In [9]:

int square(int m[9][9], int k) {
    int i_square = k/3;
    int j_square = k%3;
    int s = 0;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++) 
            s |= to_set(m[3*i_square + i][3*j_square + j]);
    return s;
}

square(m_ex, 1)
int square(int m[9][9], int k) {
    int i_square = k/3;
    int j_square = k%3;
    int s = 0;
    for(int i = 0; i < 3; i++)
        for(int j = 0; j < 3; j++) 
            s |= to_set(m[3*i_square + i][3*j_square + j]);
    return s;
}

square(m_ex, 1)

Out[9]:

Exercice

Écrire une fonction valid déterminant si un sudoku est correctement rempli.

Solution

In [10]:

bool valid(int m[9][9]) {
    for(int i = 0; i < 9; i++)
        if(!(full(line(m, i) & column(m, i) & square(m, i))))
            return false;
    return true;
}

!valid(m_ex) && valid(m_ex_solved)
bool valid(int m[9][9]) {
    for(int i = 0; i < 9; i++)
        if(!(full(line(m, i) & column(m, i) & square(m, i))))
            return false;
    return true;
}

!valid(m_ex) && valid(m_ex_solved)

Out[10]:

true

Résolution¶

On veut maintenat résoudre un sudoku. Pour cela, on va utiliser un algorithme de backtracking :

Pour chaque case $c$ non remplie du sudoku dans l'ordre (par exemple de gauche à droite et de haut en bas) :

Calculer l'ensemble $S$ des numéros autorisés pour $c$ (on pourra utiliser les fonctions précédentes pour ça)
Pour chaque numéro $k$ possible dans $S$ :
- Donner le numéro $k$ à c
- S'appliquer récursivement sur la case suivante
- Si cet appel récursif a renvoyé true (ce qui signifie qu'une solution a été trouvée), renvoyer true
Renvoyer false (aucune solution n'a été trouvée)

Exercice

Écrire une fonction bool backtrack(int m[9][9], int i, int j) renvoyant true s'il est possible de remplir m à partir de la case m[i][j]. m sera modifié par la fonction (et contiendra alors une solution du sudoku).

Solution

In [11]:

bool backtrack(int m[9][9], int i, int j) {
    if(i > 8)
        return true;
    if(m[i][j] != -1)
        return backtrack(m, i + j/8, (j + 1)%9);
    int forbidden = line(m, i) | column(m, j) | square(m, 3*(i/3) + j/3);
    for(int k = 0; k < 9; k++) {
        if((forbidden & to_set(k)) == 0) {
            m[i][j] = k;
            if(backtrack(m, i + j/8, (j + 1) % 9))
                return true;
            m[i][j] = -1;
        }
    }
    return false;
}
bool backtrack(int m[9][9], int i, int j) {
    if(i > 8)
        return true;
    if(m[i][j] != -1)
        return backtrack(m, i + j/8, (j + 1)%9);
    int forbidden = line(m, i) | column(m, j) | square(m, 3*(i/3) + j/3);
    for(int k = 0; k < 9; k++) {
        if((forbidden & to_set(k)) == 0) {
            m[i][j] = k;
            if(backtrack(m, i + j/8, (j + 1) % 9))
                return true;
            m[i][j] = -1;
        }
    }
    return false;
}

Solution

In [12]:

backtrack(m_ex, 0, -1)
backtrack(m_ex, 0, -1)

Out[12]:

true

Solution

In [13]:

m_ex
m_ex

Out[13]:

{ { 7, 3, 4, 5, 2, 1, 0, 6, 8 }, { 6, 2, 1, 8, 0, 7, 5, 4, 3 }, { 0, 8, 5, 6, 3, 4, 2, 1, 7 }, { 5, 7, 2, 4, 6, 3, 8, 0, 1 }, { 3, 4, 6, 1, 8, 0, 7, 2, 5 }, { 1, 0, 8, 7, 5, 2, 4, 3, 6 }, { 2, 5, 0, 3, 1, 8, 6, 7, 4 }, { 4, 6, 3, 0, 7, 5, 1, 8, 2 }, { 8, 1, 7, 2, 4, 6, 3, 5, 0 } }