Sudoku !

Le classique !

a marqué ce sujet comme résolu.

Exactement comme dit Eusèbe, sans oublier de revenir en arrière une fois le backtrack fait (ie. annuler les changements effectués en cas de blocage). C'est surtout ce point qui risque d'être un peu délicat à gérer, mais rien de bien insurmontable.

Une solution assez simple pour résoudre cela, c'est de garder une copie de la grille avant chaque descente dans le backtracking et de la récuperer lorsqu'on remonte.

+0 -0

Bonjour ! Voici ma contribution en c++.

J'avais fait cette exercice à la base pour résoudre un probleme sur Euler project (Problème 96). J'ai adapté pour répondre aux normes.

J'ai utilisé 2 méthodes récursives pour résoudre une grille. La première est un recherche en profondeur bête et méchante. On prend la première case vide, on y met la première valeur possible qui ne rentre pas en conflit avec une autre dans la/le ligne/colonne/carré. On l'assigne et on descend d'un cran en profondeur pour recommencer. Si aucune valeur n'est possible alors on remonte et ainsi de suite.

La deuxième méthode est par contrainte (CSP) et backtracking. Grossièrement, cherche la case vide qui a le moins de possibilité. On prend la première possibilité, on l'affecte et on l'enlève des valeurs possibles des cases qui sont vides dans la/le ligne/colonne/carré. Bien evidemment on fait une sauvegarde (cherchez "checkpoint" dans mon code) et on descend d'un cran pour recommencer. S'il existe une case vide avec aucune possibilité alors on remonte, on restaure les valeurs sauvegardées et on test avec une autre valeur.

En espèrant que cela vous plaise.

main.cpp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include <iostream>
#include <fstream>
#include <sstream>
#include <vector>

#include "Grid.h"
#include "Solver.h"

void load_from_file(std::ifstream &ifsFile, std::vector<Grid> &allSudoku)
{
    std::string line;
    while (std::getline(ifsFile, line))
    {
        allSudoku.push_back(Grid());
        allSudoku.back().load(line);
    }
}

void write_in_file(std::ofstream &ofsFile, std::vector<Grid> &solution)
{
    for(size_t i = 0; i < solution.size(); ++i)
    {
        ofsFile << solution[i].get_grid_in_string() + "\n";
    }
}

void load_from_file_euler(std::ifstream &ifsFile, std::vector<Grid> &allSudoku)
{
    std::string line;
    int lineNbr = 0;
    while (std::getline(ifsFile, line))
    {
        if(line[0] == 'G')
        {
            lineNbr = 0;
            allSudoku.push_back(Grid());
            continue;
        }
        for(int i = 0; i < 9; ++i)
        {
            allSudoku.back()(i, lineNbr) = (line[i] - 0x30);
        }

        ++lineNbr;
    }
}

int main(int argc, const char* argv[])
{
    //read
    std::ifstream ifsFile("./Grids2.txt");
    if(!ifsFile.is_open())
    {
        return -1;
    }

    std::vector<Grid> allSudoku;
    load_from_file(ifsFile, allSudoku);

    std::vector<Grid> solution;
    solution.resize(allSudoku.size());

    int sum = 0;
    Solver solver;
    for(size_t i = 0; i < allSudoku.size(); ++i)
    {
        std::cout << "start grid # " << i << std::endl;
        solver.solve_it(allSudoku[i], solution[i]);
        sum += (solution[i](0, 0) * 100 + solution[i](1, 0) * 10 + solution[i](2, 0));
        std::cout << "end" << std::endl;
    }

    std::cout << "sum = " << sum << std::endl;

    //write
    std::ofstream ofsFile;
    ofsFile.open("solutions.txt");
    write_in_file(ofsFile, solution);
    ofsFile.close();

    return 0;
}

Grid.h

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#ifndef __GRID_HPP__
#define __GRID_HPP__

#include <array>
#include <stdint.h>

class Solver;

class Grid
{
public:
    Grid() { memset(&this->_array, 0, sizeof(this->_array)); }
    ~Grid() {}

    inline uint8_t& operator() (uint32_t x, uint32_t y)
    {
        return this->_array[x + 9 * y];
    }

    inline uint8_t& operator[] (uint32_t i)
    {
        return this->_array[i];
    }

    inline Grid& operator= (Grid &other)
    {
        memcpy(&this->_array, &other._array, sizeof(this->_array));
        return *this;
    }


    void load(const std::array<uint8_t, 81> &orignialArray);
    void load(const std::string &str);
    std::string get_grid_in_string();

    void display();
    void display_time_to_solve();

    bool is_complete();
    bool is_in_square(uint32_t x, uint32_t y, uint8_t value);
    bool is_in_row(uint32_t x, uint32_t y, uint8_t value);
    bool is_in_column(uint32_t x, uint32_t y, uint8_t value);

    void set_time(long long time) { this->_time = time; }

private:

    std::array<uint8_t, 81> _array;

    long long _time;
};

#endif

Grid.cpp

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
#include "Grid.h"

#include <iostream>
#include <string>

#include "Solver.h"

void Grid::load(const std::array<uint8_t, 81> &orignialArray)
{
    memcpy(&this->_array, &orignialArray, sizeof(this->_array));
}

void Grid::load(const std::string &str)
{
    for(uint32_t i = 0; i < this->_array.size(); ++i)
    {
        if(str[i] != '.') this->_array[i] = str[i] - '0';
    }
}

std::string Grid::get_grid_in_string()
{
    std::string str;
    for(uint32_t i = 0; i < this->_array.size(); ++i)
    {
        str.push_back(this->_array[i] + '0');
    }

    return str;
}

void Grid::display()
{
    std::cout << std::endl;
    for(uint32_t y = 0; y < 9; ++y)
    {
        if(y % 3 == 0 && y > 0)
            std::cout << "----+-----+----" << std::endl;

        for(uint32_t x = 0; x < 9; ++x)
        {
            if(x % 3 == 0 && x > 0)
                std::cout << " | ";
            if((*this)(x, y) == 0)
                std::cout << "-";
            else
                std::cout << (int)(*this)(x, y);
        }
        std::cout << " " << std::endl;
    }
}

void Grid::display_time_to_solve()
{
    std::cout << "Time to solve : " << this->_time << " ns" << std::endl;
}

bool Grid::is_complete()
{
    for(uint32_t y = 0; y < 9; ++y)
    {
        for(uint32_t x = 0; x < 9; ++x)
        {
            uint8_t value = (*this)(x, y);
            if(value == 0 || this->is_in_column(x, y, value)
            || this->is_in_row(x, y, value) || this->is_in_square(x, y, value))
            return false;
        }
    }
    return true;
}

bool Grid::is_in_square(uint32_t x, uint32_t y, uint8_t value)
{
    int cx = 3 * (x / 3);
    int cy = 3 * (y / 3);
    for(uint32_t j = 0; j < 3; ++j)
    {
        for(uint32_t i = 0; i < 3; ++i)
        {
            if(cx + i == x && cy + j == y) continue;
            if((*this)(cx + i, cy + j) == value && (*this)(cx + i, cy + j) != 0) return true;
        }
    }

    return false;
}

bool Grid::is_in_row(uint32_t x, uint32_t y, uint8_t value)
{
    for(uint32_t i = 0; i < 9; ++i)
    {
        if(i == x) continue;
        if((*this)(i, y) == value && (*this)(i, y) != 0) return true;
    }
    return false;
}

bool Grid::is_in_column(uint32_t x, uint32_t y, uint8_t value)
{
    for(uint32_t i = 0; i < 9; ++i)
    {
        if(i == y) continue;
        if((*this)(x, i) == value && (*this)(x, i) != 0) return true;
    }
    return false;
}

Possibilities.h

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
#ifndef __POSSIBILITIES_HPP__
#define __POSSIBILITIES_HPP__

#include <array>
#include <vector>
#include <stdint.h>

class Grid;

class Possibilities
{
public:

    Possibilities() 
    {
        for(uint32_t i = 0; i < this->_array.size(); ++i)
        {
            this->_array[i].reserve(9);
        }
    }

    ~Possibilities() {}

    inline std::vector<uint8_t>& operator() (int x, int y)
    {
        return this->_array[x + 9 * y];
    }

    inline std::vector<uint8_t>& operator[] (int i)
    {
        return this->_array[i];
    }

    inline void add(int x, int y, uint8_t value)
    {
        this->_array[x + 9 * y].push_back(value);
    }

    void find_possibilities(Grid &grid);

    bool remove_if_exist(int x, int y, uint8_t value, std::pair<int, int> &pair);
       
private:

    std::array<std::vector<uint8_t>, 81> _array;

};

#endif

Possibilities.cpp

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include "Possibilities.h"
#include "Grid.h"

void Possibilities::find_possibilities(Grid &grid)
{
    //get all possibilities
    for(uint32_t y = 0; y < 9; ++y)
    {
        for(uint32_t x = 0; x < 9; ++x)
        {
            if(grid(x, y) == 0)
            {
                for(uint32_t possibleValue = 1; possibleValue <= 9; ++possibleValue)
                {
                    if(!grid.is_in_column(x, y, possibleValue) && !grid.is_in_row(x, y, possibleValue)
                        && !grid.is_in_square(x, y, possibleValue))
                    {
                        this->_array[x + 9 * y].push_back(possibleValue);
                    }
                }
            }
        }
    }
}

bool Possibilities::remove_if_exist(int x, int y, uint8_t value, std::pair<int, int> &pair)
{
    std::vector<uint8_t> &vector = this->_array[x + 9 * y];

    for(size_t i = 0; i < vector.size(); ++i)
    {
        if(vector[i] == value)
        {
            vector.erase(vector.begin() + i);
            pair = std::make_pair(x, y);
            return true;
        }
    }

    return false;
}

Et enfin : Solver.h

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
#ifndef __SOLVER_HPP__
#define __SOLVER_HPP__

#include <array>
#include <list>
#include <stdint.h>

#include "Possibilities.h"

class Grid;

class Solver
{
public:

    Solver() {}

    ~Solver() {}

    void solve_it(Grid &grid, Grid &solution);

protected:

    void solve_DFS(Grid &grid, Grid &solution);
    void solve_CSP(Grid &grid, Grid &solution);

    bool recursive_DFS(Grid grid, Possibilities &possibilities, Grid &solution);
    bool recursive_CSP(Grid grid, Possibilities &possibilities, Grid &solution);
};

void clear_screen();

#endif

Solver.cpp

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
#include "Solver.h"

#include <iostream>
#include <chrono>

#include "Grid.h"

void clear_screen()
{
#ifdef WIN32
    std::system("cls");
#else
    // Assume POSIX
    std::system("clear");
#endif
}

void Solver::solve_it(Grid &grid, Grid &solution)
{
    auto start = std::chrono::high_resolution_clock::now();
    this->solve_CSP(grid, solution);
    auto end = std::chrono::high_resolution_clock::now();
    solution.set_time(std::chrono::duration_cast<std::chrono::nanoseconds>(end - start).count());
}

void Solver::solve_DFS(Grid &grid, Grid &solution)
{
    Possibilities possibilities;
    possibilities.find_possibilities(grid);

    if(!this->recursive_DFS(grid, possibilities, solution))
        std::cout << "DFS - ERROR" << std::endl;
}

bool Solver::recursive_DFS(Grid grid, Possibilities &possibilities, Grid &solution)
{
    //clear_screen();
    //grid.display();
    if(grid.is_complete())
    {
        solution = grid;
        return true;
    }

    //search first empty
    uint32_t i;
    for(i = 0; i < 81; ++i)
    {
        if(grid[i] == 0) break;
    }

    if(i >= 81) return false;

    //for all possibilities
    auto j = possibilities[i].begin();
    while(j != possibilities[i].end())
    {
        uint32_t x = i % 9;
        uint32_t y = i / 9;
        if(!grid.is_in_column(x, y, *j) && !grid.is_in_row(x, y, *j) && !grid.is_in_square(x, y, *j))
        {
            grid[i] = *j;
            if(recursive_DFS(grid, possibilities, solution)) return true;
        }
        ++j;
    }

    return false;
}

void Solver::solve_CSP(Grid &grid, Grid &solution)
{
    Possibilities possibilities;
    possibilities.find_possibilities(grid);

    if(!this->recursive_CSP(grid, possibilities, solution))
        std::cout << "CSP - ERROR" << std::endl;
}

bool Solver::recursive_CSP(Grid grid, Possibilities &possibilities, Grid &solution)
{
    //clear_screen();
    //grid.display();
    if(grid.is_complete())
    {
        solution = grid;
        return true;
    }

    //search first empty with lowest possibilities
    uint32_t index = -1;
    uint32_t min = 9;
    for(uint32_t i = 0; i < 81; ++i)
    {
        if(grid[i] == 0 && possibilities[i].size() < min)
        {
            min = possibilities[i].size();
            index = i;
        }
    }

    if(index < 0 || index > 80 || min < 1)
    {
        return false;
    }

    uint32_t x = index % 9;
    uint32_t y = index / 9;
    std::vector<std::pair<uint32_t, uint32_t>> checkpoint;
    uint32_t value;
    std::pair<int, int> pair;

    for(uint32_t possibilitiesIndex = 0; possibilitiesIndex < possibilities[index].size(); ++possibilitiesIndex)
    {
        value = possibilities[index][possibilitiesIndex];
        grid[index] = value;

        //erase in row
        for(uint32_t i = 0; i < 9; ++i)
        {
            if(grid(i, y) == 0 && i != x)
            {
                if(possibilities.remove_if_exist(i, y, value, pair))
                {
                    checkpoint.push_back(pair);
                }
            }
        }

        //erase in column
        for(uint32_t i = 0; i < 9; ++i)
        {
            if(grid(x, i) == 0 && i != y)
            {
                if(possibilities.remove_if_exist(x, i, value, pair))
                {
                    checkpoint.push_back(pair);
                }
            }
        }

        //erase in square
        int cx = 3 * (x / 3);
        int cy = 3 * (y / 3);
        for(uint32_t j = 0; j < 3; ++j)
        {
            for(uint32_t i = 0; i < 3; ++i)
            {
                if(cx + i == x && cy + j == y) continue;
                if(grid(cx + i, cy + j) == 0)
                {
                    if(possibilities.remove_if_exist(cx + i, cy + j, value, pair))
                    {
                        checkpoint.push_back(pair);
                    }
                }
            }
        }

        //success or undo erase
        if(recursive_CSP(grid, possibilities, solution)) return true;
        else
        {
            for(size_t k = 0; k < checkpoint.size(); ++k)
            {
                possibilities.add(checkpoint[k].first, checkpoint[k].second, value);
            }
            checkpoint.clear();
        }
    }

    return false;
}

voila ! (Oui faire un objet solver est inutile mais j'avais envie ^^)

+0 -0

Lu'!

Quelques commentaires sur ton C++, des choses à revoir :

  • ça manque vraiment de const,
  • quand un int n'est pas indiqué, on utilise pas un int,
  • on ne met dans les headers que le strict minimum vital,
  • si ton destructeur est vide, ne l'implémente pas, pareil pour le constructeur,
  • ta fonction recursive_CSP est au moins 3 fois trop longue,
  • n'utilise pas "this" pour autre chose que lever des ambiguités et passer des accès à l'objet courant, C++ est assez verbeux comme ça,
  • une fonction membre est nécessairement "inline", pas la peine de l'ajouter,
  • memset(&this->_array, 0, sizeof(this->_array)); BEURK ! std::array::fill,
  • memcpy(&this->_array, &other._array, sizeof(this->_array));, ou plus simplement on laisse la copie de array faire son travail, et on n'a plus besoin d'implémenter la copie/affectation de la classe Grid.
+3 -0

Une version utilisant un SAT-solver, en python. L'idée est de construire une formule CNF générale à toute grille, d'y ajouter les contraintes supplémentaires propre à chaque grille, et de passer le tout à un solveur.

Un sudoku se modélise assez facilement en SAT, il suffit d'exprimer les contraintes suivantes en logique booléenne ($O(n^4)$ clauses pour une grille de $n \times n$) :

  • pour chaque case, il existe (au moins) une valeur entre 1 et N (existence) ;
  • pour chaque ligne/colonne/bloc, il y a une seule valeur k entre 1 et N (unicité).

Voici le code, également utilisable sur des grilles de dimension supérieure (met approx 4s à résoudre une grille 36x36 vide, au delà ça prend trop de temps).

Pour comprendre le code, il faut savoir que les contraintes sont exprimées au format DIMACS, soit :

  • les variables sont des nombres à partir de 1 ;
  • not(x) s'écrit -x ;
  • la formule est exprimée en Conjonctive Normal Form, sous forme de liste de liste (conjonction de disjonctions).

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
from itertools import product, combinations, count, chain
import numpy as np
from time import time
import pycosat

GRIDS = """\
000000068900000002000400500041000000000035000050000000000800010300000700000100400
080000400300600000000700005100200000000000052400000000700000300000080060020050000
080000100300500000000600004100200000000000042700000000600000300000080050020040000
000200400005000800030070000000108030100400000000000050024000100000050000600000000
400750000002030000000000000000500064010000000000000080570000300000002100600400000
050003600200700000000000000830400000000020070000000100000001200700000040040060000
000040230800500000000000000060001000000020700300000400000300068002400000010000000
""".split()


_N = 3      # for 9x9 grid size
N = _N ** 2

gen = count(1)
dom = range(N)
cnf_vars = {v : next(gen) for v in product(dom, repeat=3)}   # création des variables booléennes
revert = dict(zip(cnf_vars.values(), cnf_vars.keys()))       # mapping inverse variables -> index

# precompute indexes
rows = [[(i, j) for j in dom] for i in dom]
cols = [[(i, j) for i in dom] for j in dom]
blocs = [[(i, j) for i, j in product(range(x, x + _N), range(y, y + _N))]
         for x, y in product(range(0, N, _N), repeat=2)]

# on preconstruit la liste des contraintes, qui est valable pour toute grille
cnf = []

# existence : pour chaque case, il existe (au moins) une valeur entre 1 et N
cnf.extend([[cnf_vars[i,j,k] for k in range(N)]
            for i, j in product(dom, repeat=2)])

# unicite : pour chaque ligne/colonne/bloc, il y a une seule valeur k entre 1 et N    
cnf.extend([[-cnf_vars[i1,j1,k], -cnf_vars[i2,j2,k]]
            for row in rows
            for (i1,j1), (i2,j2) in combinations(row, 2)
            for k in dom])
cnf.extend([[-cnf_vars[i1,j1,k], -cnf_vars[i2,j2,k]]
            for col in cols
            for (i1,j1), (i2,j2) in combinations(col, 2)
            for k in dom])
cnf.extend([[-cnf_vars[i1,j1,k], -cnf_vars[i2,j2,k]]
            for bloc in blocs
            for (i1,j1), (i2,j2) in combinations(bloc, 2)
            for k in dom
            if i1 != i2 and j1 != j2]) # avoid redundancy from rows/cols

def make_grid(s):
    return np.array(list(map(int, s))).reshape((N,N))

def grid_constraints(grid):
    #yield grid-specific clauses to list of constraints
    return [[cnf_vars[i, j, grid[i][j] - 1]]
            for i, j in product(dom, repeat=2)
            if grid[i][j] != 0]

def decode(result):
    solution = {revert[v][:2]: revert[v][2] + 1 for v in result if v > 0}
    return [[solution[i,j] for j in dom] for i in dom]

def solve(grid):
    clauses = grid_constraints(grid)
    result = pycosat.solve(chain(cnf, clauses))
    return result if isinstance(result, str) else decode(result)


t1 = time()
for grid in map(make_grid, GRIDS):
    solution = solve(grid)
    if isinstance(solution, str):
        print(solution)
t2 = time()
print("%d grids" % len(GRIDS))
print("elapsed time %.4fs (average by grid: %.3fs)" % (t2-t1, (t2-t1) / len(GRIDS)))

Résultat, pour les 185 grilles de l'énoncé, avec pycosat :

1
2
185 grids
elapsed time 2.4361s (average by grid: 0.013s)
+1 -0
Banni

Il y a quelques temps j'avais fait un truc pour tester la méthode ci-dessous.

On maintient une liste des possibilités pour chaque case. On a différents blocs dans lesquels chaque symbole doit apparaitre une fois : les lignes, les colonnes et les blocs 3×3.

On considère une case contenue dans un certain bloc. Si la case n'a plus qu'une possibilité, on peut barrer cette possibilité des autres cases (du bloc considéré). Si la case est la seule à avoir une possibilité donnée, on peut faire pareil et « séparer » les symboles : on sait que le symbole en question est sur la case considérée et que les 8 autres sont sur les 8 autres cases (donc on modifie les possibilités en fonction). Mais on peut généraliser cela en considérant que si n symboles n'apparaissent que sur n cases, alors on peut barrer les autres symboles de ces n cases. Dualement, si n cases ont comme possibilités cumulées n symboles, alors on peut barrer ces n symboles des n autres cases. On voit que la première version de l'énoncé est équivalente à la seconde en prenant le complément à 9 de n.

Et pour le backtracking, on choisit la case qui a le moins de possibilités.

D'après mes souvenirs, ça utilisait moins le backtracking que je m'attendais.

Concernant le code, je n'ai pas trop envie de m'y replonger. À part le compiler, je ne lui vois pas d'utilité. Rien n'est beau ni général. C'est en C avec des bouts de lib de C++. Concernant le format d'entrée, je préfère faire un utilitaire pour convertir l'un en l'autre.

Le C.

  1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
341
342
343
344
345
346
347
348
349
350
351
352
353
354
355
356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
377
378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
393
394
395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
410
411
412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
431
432
433
434
435
#include <cstdio>
#include <vector>
#include <bitset>

#define print(...) /*/*/ printf(__VA_ARGS__)

FILE *fin = fopen("grids.txt", "r");
FILE *fout = fopen("solutions.out", "w");

const int NONE = -1;
const int BOX = 0;
const int COL = 1;
const int ROW = 2;
const int SIZE = 3;
const int GSIZE = SIZE*SIZE;
const int NB_REGIONS = GSIZE*3;

struct Region
{
  int xSq[GSIZE];
  int ySq[GSIZE];
  bool toRule;
};

struct Grid
{
  std::bitset<GSIZE> sqColorPoss[GSIZE][GSIZE];
  int sqColor[GSIZE][GSIZE];
  
  Grid()
  { }
  
  Grid(const Grid& other)
  {
    for (int x = 0; x < GSIZE; ++x)
    for (int y = 0; y < GSIZE; ++y)
    {
      sqColorPoss[x][y] = other.sqColorPoss[x][y];
      sqColor[x][y] = other.sqColor[x][y];
    }
  }
};

std::vector<Grid*> grids;

Region allRegions[NB_REGIONS];
Region* blocks[GSIZE];
Region* cols[GSIZE];
Region* rows[GSIZE];
Region* sqRegions[GSIZE][GSIZE][3];

void resetRegions();
void buildRegions();
void readGrid(Grid& grid);
void printGrid(Grid& grid);
Grid& addGrid(Grid* grid = 0);
void delGrid();
void setSquareToRule(int x, int y);
void fill(int x, int y, int col, Grid& grid);
bool nextSelection(std::bitset<GSIZE>& selection, int nbElem, int minSize = 2);
bool applyRule(Region& region, Grid& grid);
bool loopRule(Grid& grid);
bool backtracking(Grid& grid);

int main()
{
  buildRegions();
  
  for (int i = 0; i < 185; i++)
  {
    resetRegions();
    Grid& curGrid = addGrid();
    readGrid(curGrid);
    
    backtracking(curGrid);
  }
  
  delGrid();
  
  return 0;
}

void resetRegions()
{
  for (int iRegion = 0; iRegion < NB_REGIONS; ++iRegion)
  {
    allRegions[iRegion].toRule = false;
  }
}

void buildRegions()
{
  int iRegion = 0;
  
  int iBlock = 0;
  for (int xStart = 0; xStart < GSIZE; xStart += SIZE)
  for (int yStart = 0; yStart < GSIZE; yStart += SIZE)
  {
    blocks[iBlock] = &allRegions[iRegion];
    ++iRegion;
    
    int xEnd = xStart+SIZE;
    int yEnd = yStart+SIZE;
    
    int iSq = 0;
    for (int x = xStart; x < xEnd; ++x)
    for (int y = yStart; y < yEnd; ++y)
    {
      blocks[iBlock]->xSq[iSq] = x;
      blocks[iBlock]->ySq[iSq] = y;
      sqRegions[x][y][BOX] = blocks[iBlock];
      ++iSq;
    }
    ++iBlock;
  }
  
  int iCol = 0;
  for (int x = 0; x < GSIZE; ++x)
  {
    cols[iCol] = &allRegions[iRegion];
    ++iRegion;
    
    for (int y = 0; y < GSIZE; ++y)
    {
      cols[iCol]->xSq[y] = x;
      cols[iCol]->ySq[y] = y;
      sqRegions[x][y][COL] = cols[iCol];
    }
    ++iCol;
  }
  
  int iRow = 0;
  for (int y = 0; y < GSIZE; ++y)
  {
    rows[iRow] = &allRegions[iRegion];
    ++iRegion;
    
    for (int x = 0; x < GSIZE; ++x)
    {
      rows[iRow]->xSq[x] = x;
      rows[iRow]->ySq[x] = y;
      sqRegions[x][y][ROW] = rows[iRow];
    }
    ++iRow;
  }
}

void readGrid(Grid& grid)
{
  for (int y = 0; y < GSIZE; ++y)
  for (int x = 0; x < GSIZE; ++x)
  {
    grid.sqColorPoss[x][y].set();
    grid.sqColor[x][y] = NONE;
  }
  
  for (int y = 0; y < GSIZE; ++y)
  for (int x = 0; x < GSIZE; ++x)
  {
    char col;
    fscanf(fin, "%d", &col);
    col -= 1;
    
    if (col != NONE)
    {
      fill(x, y, col, grid);
    }
  }
}

void printGrid(Grid& grid)
{
  for (int y = 0; y < GSIZE; ++y)
  {
    for (int x = 0; x < GSIZE; ++x)
    {
      if (grid.sqColorPoss[x][y].none())
        fprintf(fout, "X ");
      else if (grid.sqColor[x][y] == NONE)
        fprintf(fout, "* ");
      else
        fprintf(fout, "%d ", grid.sqColor[x][y] +1);
    }
    fprintf(fout, "\n");
  }
  fprintf(fout, "\n -- \n\n");
}

Grid& addGrid(Grid* grid)
{
  if (grid == 0)
    grid = new Grid();
  
  grids.push_back(grid);
  
  return *grid;
}

void delGrid()
{
  if (grids.empty())
    return;
  
  delete grids.back();
  grids.pop_back();
}

void clearGrids()
{
  for (int iGrid = 0, nbGrids = grids.size(); iGrid < nbGrids; ++iGrid)
    delete grids[iGrid];
  grids.clear();
}

void setSquareToRule(int x, int y)
{
  for (int regionType = 0; regionType < 3; ++regionType)
  {
    sqRegions[x][y][regionType]->toRule = true;
  }
}

void fill(int x, int y, int col, Grid& grid)
{
  for (int regionType = 0; regionType < 3; ++regionType)
  {
    Region* region = sqRegions[x][y][regionType];
    for (int iSq = 0; iSq < GSIZE; ++iSq)
    {
      int xSq = region->xSq[iSq];
      int ySq = region->ySq[iSq];
      if (grid.sqColorPoss[xSq][ySq][col])
      {
        grid.sqColorPoss[xSq][ySq][col] = false;
        setSquareToRule(xSq, ySq);
      }
    }
  }
  
  grid.sqColorPoss[x][y].reset();
  grid.sqColorPoss[x][y].set(col);
  grid.sqColor[x][y] = col;
}

bool nextSelection(std::bitset<GSIZE>& selection, int nbElem, int minSize)
{
  do
  {
    int pos = 0;
    
    while (selection[pos])
    {
      selection[pos] = false;
      ++pos;
      if (pos >= nbElem)
        return false;
    }
    
    selection[pos] = true;
  }
   while (selection.count() < minSize);
  
  return true;
}

bool applyRule(Region& region, Grid& grid)
{
  region.toRule = false;
  
  int toRule[GSIZE];
  int nbToRule = 0;
  
  for (int iSq = 0; iSq < GSIZE; ++iSq)
  {
    int x = region.xSq[iSq];
    int y = region.ySq[iSq];
    if (grid.sqColor[x][y] == NONE)
    {
      toRule[nbToRule] = iSq;
      ++nbToRule;
    }
  }
  
  std::bitset<GSIZE> selection;
  
  while (nextSelection(selection, nbToRule))
  {
    std::bitset<GSIZE> unionColors;
    for (int iSq = 0; iSq < nbToRule; ++iSq)
    {
      if (selection[iSq])
      {
        int x = region.xSq[toRule[iSq]];
        int y = region.ySq[toRule[iSq]];
        unionColors |= grid.sqColorPoss[x][y];
      }
    }
    
    int selectionSize = selection.count();
    int unionColorsSize = unionColors.count();
    
    if (unionColorsSize < selectionSize)
    {
      return false;
    }
    
    if (unionColorsSize == selectionSize)
    {
      for (int iSq = 0; iSq < nbToRule; ++iSq)
      {
        if (selection[iSq])
          continue;
        int x = region.xSq[toRule[iSq]];
        int y = region.ySq[toRule[iSq]];
        if ((grid.sqColorPoss[x][y] & unionColors).any())
        {
          grid.sqColorPoss[x][y] &= ~unionColors;
          setSquareToRule(x, y);
        }
      }
    }
  }
  
  for (int iSq = 0; iSq < nbToRule; ++iSq)
  {
    int x = region.xSq[toRule[iSq]];
    int y = region.ySq[toRule[iSq]];
    int nbColPoss = grid.sqColorPoss[x][y].count();
    if (nbColPoss == 0)
      return false;
    if (nbColPoss == 1)
    {
      int col = 0;
      while (!grid.sqColorPoss[x][y][col])
        ++col;
      fill(x, y, col, grid);
    }
  }
  
  return true;
}

// -- +++++++

bool loopRule(Grid& grid)
{
  bool redo;
  
  do
  {
    redo = false;
    for (int iRegion = 0; iRegion < NB_REGIONS; ++iRegion)
    {
      Region& region = allRegions[iRegion];
      if (region.toRule)
      {
        redo = true;
        if (!applyRule(region, grid))
        {
          for (int iRegion = 0; iRegion < NB_REGIONS; ++iRegion)
            allRegions[iRegion].toRule = false;
          return false;
        }
      }
    }
  } while (redo);
  
  return true;
}

bool backtracking(Grid& grid)
{
  if (!loopRule(grid))
    return false;
  
  // Pas certain qu'un tas serait mieux (voire même certain que ce ne serait pas mieux).
  int xMinNbPoss = 0;
  int yMinNbPoss = 0;
  int minNbPoss = grid.sqColorPoss[0][0].count();
  for (int x = 0; x < GSIZE; ++x)
  for (int y = 0; y < GSIZE; ++y)
  {
    int curNbPoss = grid.sqColorPoss[x][y].count();
    if (minNbPoss == 1 || (curNbPoss != 1 && curNbPoss < minNbPoss))
    {
      xMinNbPoss = x;
      yMinNbPoss = y;
      minNbPoss = curNbPoss;
    }
  }
  
  if (minNbPoss == 1)
  {
    print("\e[1;32mOn affiche la grille car on a trouvé une solution.\e[0;m\n");
    printGrid(grid);
    return true;
  }
  
  bool solutionFound = false;
  
  for (int col = 0; col < GSIZE; ++col)
  {
    if (grid.sqColorPoss[xMinNbPoss][yMinNbPoss][col])
    {
      print("\e[1;31mOn effectue un backtrack sur %d %d = %d.\e[0;m\n", xMinNbPoss, yMinNbPoss, col+1);
      
      Grid& nGrid = addGrid(new Grid(grid));
      
      fill(xMinNbPoss, yMinNbPoss, col, nGrid);
      
      if (backtracking(nGrid))
        solutionFound = true;
      
      // Enlever pour ne pas s'arrêter à la première solution trouvée.
      if (solutionFound)
        break;
      
      delGrid();
      
      print("\e[0;34mFin du backtrack sur %d %d = %d.\e[0;m\n", xMinNbPoss, yMinNbPoss, col+1);
      
      print("\e[0;34mOn cherche autre chose :\e[0;m\n");
      
      grid.sqColorPoss[xMinNbPoss][yMinNbPoss][col] = false;
      setSquareToRule(xMinNbPoss, yMinNbPoss);
      
      if (backtracking(grid))
        solutionFound = true;
      
      break;
    }
  }
  
  return solutionFound;
}

Pour la conversion si vous avez Haskell.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
import System.Environment
import Data.List.Split
import Data.Char

x |> f = f x
f |>> g = g . f
conjugate (f,g) h = f |>> h |>> g 

data List2d a = List2d { list :: [[a]] }

-- Je ne sais pas comment faire pour que la composée
-- de deux foncteurs soit un foncteur.
instance Functor List2d where
  fmap = fmap (conjugate (list,List2d)) $ map . map

type Sudoku = List2d Integer
data Serializer a = Serializer { reader :: String -> a, printer :: a -> String }

zds_ser, perso_ser :: Serializer Sudoku

zds_ser = Serializer {
  reader = chunksOf 9
       |>> List2d
       |>> fmap (toInteger . digitToInt),
  printer = undefined
}

perso_ser = Serializer {
  reader = undefined,
  printer = fmap show
        |>> list
        |>> map unwords
        |>> unlines
}

main :: IO ()
main = do
  format:_ <- getArgs
  case format of
    "zds" -> interact $ lines
                    |>> map ( (reader zds_ser) |>> (printer perso_ser) )
                    |>> unlines

+0 -0

Noooooon pas les concours centrale supélec ^^ je lève le nez de mes annales pour me détendre ici et je tombe sur ça ?! :p le pire c'est que l'algorithme DLX de Knuth c'est mon sujet de TIPE ^^ Et c'est pas vraiment "facilement implémentable" qui me serait venu à l'esprit dans la mesure où la liste doublement chainée toroïdale 2D n'est pas vraiment quelque chose de simple à mettre en place de façon performante :p Mais si jamais je finis mon code assez rapidement (vacances de noel j'espère) je le mettrai ici ;)

+1 -0

wouuh un taupin ! :D yep exactement, mais je commence à me dire que la représentation matricielle ensembliste d'une grille destinée à l'algo c'est un peu sale ^^ j'ai trouvé quelques liens de matrices d'exemples (dans la thèse de Knuth à ce sujet) et je dois dire que les tableurs excels sont vachement volumineux ^^ Du coup je l'adapterai peut être à un simple problème de pentaminos ou un autre truc de pavement :)

+0 -0

Je m'étais penché sur la résolution de sudokus en C il y a quelques mois, voici le lien vers le dépôt git.

Il y a 2 solvers

  • un backtracker "classique"

  • un backtracker DLX

Voici les temps de résolution sur les grilles fournies (secondes):

Test Classique DLX
185 grilles difficiles pour le backtracking 411.51 0.14
1465 grilles difficiles 20.49 0.77
Toutes les grilles avec 17 indices (49151) 5320.53 8.14

Les 2 solvers peuvent traiter des tailles de grilles différentes de 9x9. Ils trouvent toutes les solutions pour chaque grille (pas d'arrêt après la 1ère solution trouvée).

Dans le répertoire data vous trouverez d'autres grilles, de tailles variées si vous souhaitez faire des tests différents.

Pour ce défi j'ai ajouté un générateur de grille à partir du solveur DLX, je mets l'algo en secret pour ceux qui veulent suivre leur propre intuition :) Le but est de générer des grilles à solution unique avec le minimum d'indices révélés.

1
2
3
4
5
6
7
8
9
Génération d'un grille aléatoire avec un algo DLX adapté
Mélange des cases de la grille
Pour chaque case
    Vider la case
    Résoudre la grille (DLX s'arrêtant dès que plus d'une solution est trouvée)
    Si nombre de solutions > 1
        Remettre la valeur d'origine dans la case
    Fin si
Fin pour

Le temps d'exécution est bien entendu plus long que pour une résolution (quelques secondes pour une grille 16x16). D'après les tests que j'ai faits, plus le temps de génération est long, plus la grille sera longue à résoudre (logique vu l'algo).

+0 -0

Je me permet de (légèrement) déterrer juste pour dire que j'ai fini ma solution dans le cadre de mon projet scolaire, l'algorithme est encore largement optimisable, mais il tourne et n'est pas trop dégueu (sachant que ça tourne en python quand meme …). Implémentation de l'algo DLX : sur les ordis (du lycée qui puent la mort) ça donne ça :

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
-------------------------------------------
Loading file 'toSolve.txt' ...
File loaded in 0.031866809927586316s. 
-------------------------------------------
File name : 17 number grids
sudoku size : 9
number of sudokus : 43
-------------------------------------------
Statistics : 
Total time : 23.54962196302438
Mean time for one puzzle : 0.547665627047
-------------------------------------------

et sur les 0,5s de recherche, on a environ 0,01s pour l'algo DLX et le reste pour la construction de la structure de donnée (merci python qui ne connait pas les listes et les pointeurs efficaces …) Voilà voilà :) Je en met pas le code ici car il est long et sale mais si vous etes intéressés envoyez moi un MP

+2 -0

Implémentation de l'algo DLX Je en met pas le code ici car il est long et sale mais si vous etes intéressés envoyez moi un MP

LeB0ucEtMistere

Je serais très intéressé de voir ton algo (et je suis sur que je ne suis pas le seul). Tu peux mettre ton code dans une balise secret, sur github ou sur un pastebin s'il est trop long. Pour le propreté, partager ton code est le meilleurs moyen d'avoir des retours et donc de t'améliorer :)

+1 -0

Je vais être le naïf (le cancre ?) de service ! Disons que je suis faux débutant ! Ici, il y a du haut niveau, même des taupins, c'est pour dire … Dans les règles du sudoku énoncées plus haut, il y a l'unicité de la grille. Je me suis inspiré d'une leçon de yoch pour écrire en python les algorithmes de son intervention sur openclassrooms. Ça marche, mais l'algorithme s'arrête à la première solution trouvée. Il faut continuer le backtracking pour trouver les autres si elles existent. C'est là que je coince, je ne vois pas comment passer outre l'arrêt de l'algorithme. Quand j'aurai franchi ce stade, j'aurai d'autres questions. Merci à l'avance

+0 -0

Salut !

Tout d'abord tout le monde peut y arriver, et le fait d'être taupin n'avantage pas vraiment. Les taupins c'est des gens normaux, on est pas tous major de promo en MP** à H4 hein.

Tu devrais poster ton code, c'est le seul moyen de pouvoir t'aider. Si tu pouvais aussi détailler ta méthode aussi ça serait bien.

+0 -0

La méthode est ici,je n'ai fait que transcrire en Python, (qui est le langage des prépas aujourd'hui).

Voici la version basique de l'algorithme :

 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

J'ai aussi réalisé les versions améliorées, mais c'est le même principe.

+0 -0

C'est normal que ton code s'arrête à la première solution, vu qu'il y a un return.

Pour lister les solutions, une piste serait de commencer par les compter : comment est-ce que tu t'y prendrais ? Une autre piste (parce que tu fais du python) est d'utiliser un générateur et de faire yield True au lieu de return True, ce qui te permet de lister les solutions.

(et pour info, mon tuto est disponible ici aussi : là)

+1 -0
Connectez-vous pour pouvoir poster un message.
Connexion

Pas encore membre ?

Créez un compte en une minute pour profiter pleinement de toutes les fonctionnalités de Zeste de Savoir. Ici, tout est gratuit et sans publicité.
Créer un compte