Couverture exacte et sudokus

Dans un précédent texte, le problème de la couverture exacte, l'algorithme X et les Dancing Links ont été présentés. Maintenant, voyons comment cette ménagerie peut être utilisée afin de résoudre des grilles de sudokus.

Grille de Sudoku

Un puzzle de sudoku de taille standard (9x9) peut être vu comme un problème de satisfaction de contraintes impliquant 81 variables, lesquelles sont toutes définies sur le domaine {1,2,3,4,5,6,7,8,9}, et 27 contraintes alldiff[1] se chevauchant. En substance, il s'agit de remplir chaque ligne, colonne et région de la grille avec des nombres différents compris dans le domaine {1,2,3,4,5,6,7,8,9}.

En outre, il est possible de généraliser la définition précédente en caractérisant une grille de sudoku à partir de la taille de ses régions.

Ainsi, une grille de Sudoku dont les régions font N lignes par M colonnes comportera:

Par ailleurs, chaque cellule sera définie sur le domaine {1,2,...,N∙M}.

Conséquemment, un puzzle de sudoku devient en fait un problème de satisfaction de contrainte impliquant (N∙M)2 variables, toutes définies sur le domaine {1,2,...,N∙M}, et 3∙N∙M contraintes alldiff se chevauchant.

Matrice binaire d'une grille de Sudoku

Afin de résoudre des grilles de sudoku à l'aide de l'algorithme X, nous devons trnasformer ces dernières en instances du problème de la couverture exacte. C'est-à-dire que nous devons construire une matrice binaire qui encode cette instance.

Afin de comprendre le processus de construction, voyons comment se compose la matrice binaire associée à une grille sudoku dont les régions font N lignes par M colonnes et possédant donc (N∙M)2 cellules.

Pour comprendre comment tout cela se traduit en pratique, voici les matrices de couverture associées à des grilles vides de différentes tailles.

Construction de la matrice de couverture

Maintenant que la structure et les caractéristiques de la matrice binaire d'une grille de Sudoku sont connues, nous pouvons énoncer un algorithme permettant de construire cette dernière.

L'algorithme suivant prend en entrée une grille de Sudoku dont les régions font N lignes par M colonnes et construit la matrice de couverture correspondante:

  • Pour chaque cellule C dans S :
    • Pour chaque valeur V dans le domaine de C :
      • Ajouter une ligne à la matrice de couverture et y insérer des 1 aux positions suivantes :
        1. 0∙(N∙M)2 + Ligne[C] ∙ (N∙M) + Colonne[C]
        2. 1∙(N∙M)2 + Ligne[C] ∙ (N∙M) + V
        3. 2∙(N∙M)2 + Colonne[C] ∙ (N∙M) + V
        4. 3∙(N∙M)2 + (⌊Ligne[C]÷N⌋+⌊Colonne[C]÷M⌋∙M) ∙ (N∙M) + V

Implantation

Grille de sudoku

Une grille de sudoku est tout simplement modélisée par un tableau à deux dimensions de cellules. Chaque cellule est définie sur un domaine donnée. Ce domaine borne la plage de valeurs de que cette cellule peut prendre.

template <uint16 Domain = 9>
class Cell {
public:
    static const uint16 domain = Domain;

    Cell() : is_set(false) {}

    Cell(uint16 value) throw (std::domain_error) :
        value(value), is_set(true) {

        if (value >= Domain)
            throw std::domain_error("Value out of cell's domain !");
    }

    const Cell& operator=(const Cell& rhs) {
        is_set = rhs.is_set;
        value = rhs.value;
        return *this;
    }

    const Cell& operator=(uint16 value) {
        set(value);
        return *this;
    }

    uint16 get() const throw(std::logic_error) {
        return is_set
             ? value
             : throw std::logic_error("Cell's value isn't set.");
    }

    void set(uint16 value) throw (std::domain_error) {
        if (value >= Domain)
            throw std::domain_error("Value out of cell's domain !");

        is_set = true;
        this->value = value;
    }

    operator uint16() const { return get(); }
    bool setted() const { return is_set; }
    void reset() { is_set = false; }

private:
    uint16 value;   // Current cell value.
    bool is_set;    // Boolean to mark if the cell is set.
};

Deux cellules sont égales si elles sont dans le même état. En particulier, si la valeur des deux cellules est fixée, cette dernière est utilisée pour la comparaison. Autrement, la comparaison est effectuée entre le statu des deux cellules.

template <uint16 Domain>
bool operator==(const Cell<Domain>& a, const Cell<Domain>& b) {
    return a.setted() && b.setted()
         ? a.get() == b.get()
         : a.setted() == b.setted();
}

template <uint16 Domain>
bool operator!=(const Cell<Domain>& a, const Cell<Domain>& b) {
    return !operator==(a, b);
}

La surcharge habituelle de l'opérateur d'extraction de flux.

template <uint16 Domain>
std::ostream& operator<<(std::ostream& out,
                         const Cell<Domain>& cell) {
    if (!cell.setted())
        return out << "-";

    uint16 value = cell.get();
    return value < 10
         ? out << char(value + 48)
         : out << char(value + 55);
}

Comme mentionné précédemment, une grille de sudoku est caractérisée par la taille des régions la composant — les arguments du template. Pour le reste, il s'agit simplement d'une matrice de cellules. L'opérateur d'insertion de flux est surchargé afin de faciliter la construction des grilles à partir d'une représentation textuelle.

template <uint16 Row = 3, uint16 Col = 3>
class Grid {
public:
    // Expose some static informations about the grid.
    static const uint16 size = Row * Col;
    static const uint16 rows = Row;
    static const uint16 columns = Col;
    static const uint16 num_cells = size * size;

    const Grid& operator=(const Grid& rhs) {
        for (uint16 i = 0; i < size; ++i)
            for (uint16 j = 0; j < size; ++j)
                cells[i][j] = rhs.cells[i][j];

        return *this;
    }

    void operator<<(std::string grid) {
        if (grid.size() != num_cells)
            throw std::logic_error("Representation error !");

        std::transform(grid.begin(), grid.end(), grid.begin(), tolower);

        for (uint16 i = 0; i < num_cells; i++) {
            uint16 row = i / size;
            uint16 col = i % size;

            if (grid[i] == 'x' || grid[i] == ' ')
                cells[row][col].reset();
            else if ('a' <= grid[i] && grid[i] <= 'w')
                cells[row][col] = uint16(grid[i] - 87);
            else if ('0' <= grid[i] && grid[i] <= '9')
                cells[row][col] = uint16(grid[i] - 48);
            else
                throw std::logic_error("Value out of range !");
        }
    }

    Cell<size>& operator()(uint16 row, uint16 col) {
        if (row >= size || col >= size)
            throw std::out_of_range("Bad subscripts !");

        return cells[row][col];
    }

    const Cell<size>& operator()(uint16 row, uint16 col) const {
        if (row >= size || col >= size)
            throw std::out_of_range("Bad subscripts !");

        return cells[row][col];
    }

protected:
    Cell<size> cells[size][size];
};

Les opérateurs d'égalité ne sont définis que pour des grilles de tailles identiques. Deux grilles sont considérées égales si toutes les cellules d'indices correspondants sont égales.

template <uint16 Row, uint16 Col>
bool operator==(const Grid<Row, Col>& a, const Grid<Row, Col>& b) {
    for (uint16 i = 0; i < Grid<Row, Col>::size; ++i)
        for (uint16 j = 0; j < Grid<Row, Col>::size; ++j)
            if (a(i, j) != b(i, j))
                return false;

    return true;
}

template <uint16 Row, uint16 Col>
bool operator!=(const Grid<Row, Col>& a, const Grid<Row, Col>& b) {
    return !operator==(a, b);
}

Encore une fois, l'opérateur d'extraction de flux est surchargé pour les grilles de sudoku.

template <uint16 Row, uint16 Col>
std::ostream& operator<<(std::ostream& out, const Grid<Row, Col>& sudoku) {
    for (uint32 i = 0; i < Grid<Row, Col>::size; i++) {
        for (uint32 j = 0; j < Grid<Row, Col>::size; j++)
            out << sudoku(i, j) << " ";
        out << "\n";
    }
    return out;
}

Construction et représentation de la matrice binaire

Tel que mentionné dans un texte précédent, le véhicule le plus simple pour représenter la matrice binaire encodant l'instance du problème de la couverture exacte tout en préservant la mémoire est une matrice clairsemée.

La fonction ci-dessous emploie cette structure de données afin de stocker la matrice binaire associée à la grille de sudoku. Matrice binaire évidemment construite à partir de l'algorithme énoncé précédemment.

template <uint16 Row, uint16 Col>
Grid<Row, Col> solve(const Grid<Row, Col>& sudoku) {
    // The solution to an exact cover problem is a list of row
    // indexes. We need a way to map those indexes to a value and
    // the corresponding cell in the Sudoku's grid. Thus the need
    // for this vector which, given a row index, allow us to find
    // the associated cell and its value in the solved grid.
    std::vector<std::pair<Subscript<uint16>, uint16> > index;

    // A sparse matrix large enough to old the exact cover instance.
    // Since it's a sparse matrix, we don't have to pay for this
    // excess storage.
    RowMappedMatrix<bool> bmatrix(power<Grid<Row, Col>::size, 3>::value,
                                  power<Grid<Row, Col>::size, 2>::value * 4);

    uint32 irow = 0; // Instance matrix row index.

    // In order to fill the cover matrix,
    // go over each cell of the grid.
    for (uint16 row = 0; row < Grid<Row, Col>::size; row++) {
        for (uint16 col = 0; col < Grid<Row, Col>::size; col++) {
            // Current region index for this cell.
            uint16 region = row / Grid<Row, Col>::rows +
                            col / Grid<Row, Col>::columns * Grid<Row, Col>::columns;

            // Cell's domain start and stop values.
            uint16 start = 0;
            uint16 stop = Grid<Row, Col>::size;

            // If the cell's value is known, its
            // domain boils down this single value.
            if (sudoku(row, col).setted()) {
                start = sudoku(row, col).get();
                stop = start + 1;
            }

            // For each value in the cell domain, fill a row in the
            // sparse matrix holding the exact cover problem instance.
            for (uint16 value = start; value < stop; value++) {

                uint16 col0 = Grid<Row, Col>::num_cells * 0 +
                              Grid<Row, Col>::size * row + col;
                uint16 col1 = Grid<Row, Col>::num_cells * 1 +
                              Grid<Row, Col>::size * row + value;
                uint16 col2 = Grid<Row, Col>::num_cells * 2 +
                              Grid<Row, Col>::size * col + value;
                uint16 col3 = Grid<Row, Col>::num_cells * 3 +
                     region * Grid<Row, Col>::size + value;

                bmatrix(irow, col0) = true;
                bmatrix(irow, col1) = true;
                bmatrix(irow, col2) = true;
                bmatrix(irow, col3) = true;

                irow++; // Increment the instance matrix row index.

                // We've just inserted a new line in the instance matrix,
                // note in the index vector which cell is associated to this
                // row and what is the value associated to it for this entry.
                index.push_back(std::make_pair(make_subscript(row, col), value));
            }
        }
    }

    Grid<Row, Col> solution;
    std::vector<uint32> cover(exact_cover::solve(bmatrix));
    for (size_t i = 0; i < cover.size(); i++) {
        Subscript<uint16> subscript = index[cover[i]].first;
        uint16 value = index[cover[i]].second;
        solution(subscript.row, subscript.col) = value;
    }

    return solution;
}

Cette méthode fonctionne bien pour des grilles de sudoku dont la taille ne dépasse pas 81 cellules. Au delà de cette limite, les performances se dégradent perceptiblement. Les recherches répétées dans la matrice clairsemée se font effectivement sentir.

Heureusement, nous pouvons tirer partie des caractéristiques particulières des matrices binaires associées aux grilles de sudoku afin d'accélérer le traitement. En particulier, nous savons que chaque ligne comprend exactement 4 éléments, et ce, peu importe la taille de la grille de sudoku.

Dès lors, nous pouvons imaginer une classe ne stockant que ces quatre éléments pour chaque ligne et dont l'interface est celle d'une matrice. Les accès à la matrice binaire, maintenant effectués en temps constant, ne constituent plus un goulot d'étranglement.

template <uint16 Row, uint16 Col>
class SudokuBinaryMatrix {
public:
    struct RowDescriptor {
        RowDescriptor(uint16 row, uint16 col, uint16 value,
            uint32 col0, uint32 col1, uint32 col2, uint32 col3) :
            cell(Subscript<uint16>(row, col)), value(value) {
            cols[0] = col0;
            cols[1] = col1;
            cols[2] = col2;
            cols[3] = col3;
        }

        Subscript<uint16> cell;
        uint16 value;
        uint32 cols[4];
    };

    void operator<<(const Grid<Row, Col>& grid) {
        mrows.clear();

        for (uint16 row = 0; row < Grid<Row, Col>::size; row++) {
            for (uint16 col = 0; col < Grid<Row, Col>::size; col++) {
                // Current region index for this cell.
                uint16 region = row / Grid<Row, Col>::rows +
                                col / Grid<Row, Col>::columns *
                                      Grid<Row, Col>::columns;

                // Cell's domain start and stop values.
                uint16 start = 0;
                uint16 stop = Grid<Row, Col>::size;

                // If the cell's value is known, its
                // domain boils down this single value.
                if (grid(row, col).setted()) {
                    start = grid(row, col).get();
                    stop = start + 1;
                }

                // For each value in the cell domain, fill a row in
                // the sparse matrix representing the exact cover
                // problem instance.
                for (uint16 value = start; value < stop; value++) {
                    uint16 col0 = Grid<Row, Col>::num_cells * 0 +
                                  Grid<Row, Col>::size * row + col;
                    uint16 col1 = Grid<Row, Col>::num_cells * 1 +
                                  Grid<Row, Col>::size * row + value;
                    uint16 col2 = Grid<Row, Col>::num_cells * 2 +
                                  Grid<Row, Col>::size * col + value;
                    uint16 col3 = Grid<Row, Col>::num_cells * 3 +
                         region * Grid<Row, Col>::size + value;

                    mrows.push_back(RowDescriptor(row, col, value, col0,
                                                  col1, col2, col3));
                }
            }
        }
    }

    const SudokuBinaryMatrix& operator=(SudokuBinaryMatrix rhs) {
        std::swap(mrows, rhs.mrows);
        return *this;
    }

    bool operator()(uint32 row, uint32 col) const {
        uint16 quarter = col / power<Grid<Row, Col>::size, 2>::value;
        return mrows[row].cols[quarter] == col;
    }

    const RowDescriptor& operator[](uint32 row) const {
        return mrows[row];
    }

    uint32 rows() const { return mrows.size(); }

    uint32 cols() const {
        return power<Grid<Row, Col>::size, 2>::value * 4;
    }

private:
    std::vector<RowDescriptor> mrows;
};

Avec cette nouvelle structure de données spécialisée, la fonction résolvant les grilles de sudoku peut être réécrite de la manière suivante.

template <uint16 Row, uint16 Col>
Grid<Row, Col> solve(const Grid<Row, Col>& sudoku) {
    Grid<Row, Col> solution;
    std::vector<uint32> cover;
    SudokuBinaryMatrix<Row, Col> matrix;

    matrix << sudoku;
    cover = exact_cover::solve(matrix);
    for (size_t i = 0; i < cover.size(); i++) {
        uint32 row = cover[i];
        uint16 value = matrix[row].value;
        Subscript<uint16> cell = matrix[row].cell;
        solution(cell.row, cell.col) = value;
    }

    return solution;
}

Conclusion

Plusieurs autres problèmes de satisfaction de contraintes peuvent être reformulés en problèmes de couverture exacte et résolu avec une approche semblable à celle employée dans ce texte.

Par ailleurs, il est intéressant de constater à quel point une interface générique offre de la flexibilité à l'utilisateur lorsque vient le temps d'optimiser certains cas particuliers.

Le code source est disponible sur github: exact-cover.

  1. Toutes les variables impliquées dans cette contrainte doivent prendre des valeurs distinctes.