Solveur de sudoku

Commenter

Contenu du snippet

Salut, voici un solveur de sudoku que j'ai fais ce matin, afin de revoir
mon utilisation des nodes 
#include <iostream>   
#include <string>   
#include <vector>   
#include <stdio.h>   
#include <stdlib.h>   
#include "math.h"   

using namespace std;   

std::string tab;   

void draw()   
{   
    int i, j;   

    system("cls");   
    for(i = 0; i < 9; i++)   
    {   
        for(j = 0; j < 9; j++)   
        {   
            cout << tab[i*9+j] << " ";   
        }   
        cout << endl;   
    }   
}   

class node   
{   
    public :   
    node()   
    {   
        x = 0;   
        y = 0;   
    }   

    int x;   
    int y;   
};   

class Solver   
{   
    public :   
    Solver()   
    {   
        nb_open = 0;   
        ptr = NULL;   
        w = 0;   
        h = 0;   
    }   

    bool fonction(int _w, int _h, const char *_ptr)   
    {   
        int i;   
        int x, y;   
        bool notfound = false;   

        w = _w;   
        h = _h;   
        if(ptr == NULL || w == 0 || h == 0)   
        return false;   

        while(!issolved())   
        {   
            draw(); // je redessine l'ecran   

            node *current = NULL;   

            if(iscompleted() || notfound) // si le sudoku est complet ou si un node n'est pas correct   
            {   
                notfound = false;   
                current = get_last(); // je demande le node le plus récent   

                if(current != NULL)   
                {   
                    if(get_nombre(current->x, current->y) == 9 || get_increment(current->x, current->y) == -1) // si le node n'est pas incrementable   
                    {   
                        verify_increment(); // je supprime tous les nodes qui ne sont pas incrementable   
                        current = get_last();// je demande le node le plus récent   

                        if(current != NULL)   
                        {   
                            int nombre = get_increment(current->x, current->y);   
                            if(nombre != -1)   
                            set_nombre(current->x, current->y, nombre); //j'incremente le node   
                        }   
                    }   
                    else   
                    {   
                        int nombre = get_increment(current->x, current->y);   
                        if(nombre != -1)   
                        set_nombre(current->x, current->y, nombre);//j'incremente le node   
                    }   
                }   
            }   
            else   
            {   
                if(get_next(&x, &y) == 1) // je cherche la prochaine '.' qui correspond à une case vide   
                {   
                    int nombre = get_default(x, y); //   

                    if(nombre != -1)// si il existe un nombre que l'on peut mettre dans la case(x, y) tout en respectant les regles   
                    {   
                        add_node(x, y, nombre); // ajout du node   
                    }   
                    else // sinon on revien en arriere afin de changer un node précedent   
                    notfound = true;   
                }   
            }   
        }   

        return true;   
    }   
    bool get_next(int *x, int *y)   
    {   
        int i, j;   

        for(i = 0; i < h; i++)   
        {   
            for(j = 0; j < w; j++)   
            {   
                if(iscompleted(j, i) == false)   
                {   


  • x = j;   

  • y = i;

                    return true;   
                }   
            }   
        }   
        return false;   
    }   
    int get_default(int x, int y)   
    {   
        int i;   

        for(i = 0; i <= 9; i++)   
        {   
            if(isright(x, y, i))   
            {   
                return i;   
            }   
        }   

        return -1;   
    }   
    int get_increment(int x, int y)   
    {   
        int i;   

        int nombre = get_nombre(x, y);   

        for(i = nombre+1; i <= 9; i++)   
        {   
            if(isright(x, y, i))   
            {   
                return i;   
            }   
        }   

        return -1;   
    }   
    int get_nombre(int x, int y)   
    {   
        if(ptr[y*w+x] == '.')   
        return -1;   

        return ptr[y*w+x] - 48;   
    }   
    void set_nombre(int x, int y, int var)   
    {   
        if(var == -1)   
        ptr[y*w+x] = '.';   
        else   
        ptr[y*w+x] = var + 48;   
    }   

    bool issolved()   
    {   
        if(iscompleted())   
        {   
            int i, j;   

            for(i = 0; i < h; i++)   
            for(j = 0; j < w; j++)   
            {   
                if(isright(j, i, get_nombre(j, i)) == 0)   
                return false;   
            }   
            return true;   
        }   
        return false;   
    }   
    bool isright(int x, int y, int var)   
    {   
        int i, j;   
        bool cond = true;   

        for(i = 0; i < h && cond; i++)   
        {   
            for(j = 0; j < w && cond; j++)   
            {   
                if( (j == x || i == y) &&   
                    !(j == x && i == y))   
                {   
                    if(get_nombre(j, i) == var)   
                    return false;   
                }   
            }   
        }   

        return true;   
    }   

    bool iscompleted()   
    {   
        int i, j;   

        for(i = 0; i < h; i++)   
        {   
            for(j = 0; j < w; j++)   
            {   
                if(!iscompleted(j, i))   
                return false;   
            }   
        }   
        return true;   
    }   
    bool iscompleted(int x, int y)   
    {   
        if(get_nombre(x, y) == -1)   
        return false;   

        return true;   
    }   

    void add_node(int x, int y, int var)   
    {   
        node *foo = new node;   
        foo->x = x;   
        foo->y = y;   
        set_nombre(x, y, var);   
        open_list.push_back(foo);   
        nb_open++;   
    }   
    node *get_last()   
    {   
        if(nb_open > 0)   
        {   
            return open_list[nb_open-1];   
        }   

        return NULL;   
    }   
    void verify_increment()   
    {   
        if(nb_open > 0)   
        {   
            if(get_nombre(open_list[nb_open-1]->x, open_list[nb_open-1]->y) == 9 ||   
               get_increment(open_list[nb_open-1]->x, open_list[nb_open-1]->y) == -1)   
            {   
                pop();   
                verify_increment();   
            }   
        }   
    }   
    bool pop()   
    {   
        if(nb_open > 0)   
        {   

            set_nombre(open_list[nb_open-1]->x, open_list[nb_open-1]->y, -1);   
            delete open_list[nb_open-1];   
            nb_open--;   
            open_list.pop_back();   

            return true;   
        }   
        return false;   
    }   

    void erase_data()   
    {   
        open_list.erase(open_list.begin(), open_list.end());   
        ptr = NULL;   
        w = 0;   
        h = 0;   
        nb_open = 0;   
    }   

    vector <node*> open_list;   
    int w;   
    int h;   
    char *ptr;   
    int nb_open;   
};   

int main()   
{   
    Solver sudoku;   

    tab+= ".3...1...";   
    tab+= "..6....5.";   
    tab+= "5.....983";   
    tab+= ".8...63.2";   
    tab+= "....5....";   
    tab+= "9.38...6.";   
    tab+= "714.....9";   
    tab+= "32....8..";   
    tab+= "...4...3.";   

    sudoku.fonction(9, 9, tab.c_str());   
    sudoku.erase_data();   

    draw();   

    return 0;   
}

A voir également

S'inscrire maintenant

Vous n'êtes pas encore membre ?

inscrivez-vous, c'est gratuit et ça prend moins d'une minute !

Les membres obtiennent plus de réponses que les utilisateurs anonymes.

Le fait d'être membre vous permet d'avoir un suivi détaillé de vos demandes et codes sources.

Le fait d'être membre vous permet d'avoir des options supplémentaires.

Du même auteur (smartties)