Partage
  • Partager sur Facebook
  • Partager sur Twitter

[FAIT][Défis] #3 : Des sudokus en folie !

Venez vous entraîner !

    24 septembre 2011 à 20:02:01

    Bonsoir,

    J'ai finalement fait le bench sur toutes les 49151 grilles minimales. Le constat :
    • Je me suis un peu trop avancé :honte: en affirmant que mon backtracking pouvait résoudre n'importe quelle grille en moins de 0.1s. En réalité, 185 grille (sur 50000, donc 0.37%) passent au dessus de 1s, et certaines dépassent les 3s...
    • La moyenne reste tout de même stable : 0.027s par grille.
    • J'ai refait le test avec un DLX, cette fois aucune mauvaise surprise, les perfs sont redoutables (cf. ci-dessous). :magicien: Il y a tout de même un certain écart entre la moyenne et le pire cas (en supposant que la fonction clock() donne des résultats fiables sous Windows).
    • Pour que le test soit sûr, il faudrait vérifier le retour de chaque grille, mais je ne dispose pas d'un tel fichier...


    Backtacking optimisé


    49152 grilles en 1343.02s
    moyenne = 0.0273237s/grille; max = 3.893s


    DLX


    49152 grilles en 35.351s
    moyenne = 0.000719218s/grille; max = 0.02100s


    Liste des grilles "pires des cas" pour mon backtracking :


    000000068900000002000400500041000000000035000050000000000800010300000700000100400
    000000201004030000000000000370000080600200000000500000540000600000070040002001000
    000000360430000000000500700000760000200000005000000100000042008070000040001000000
    000000408900300000000100000000000530000005100200060000000720006054000000000000010
    000000501100800000000000400005013000040000700000600000620000080000050020000004000
    000000592080010000000000000600200400410000000000000000006504000300000010000700008
    000000701060050000008000000000104000700000020030800000000070350004000600100000000
    000000840000720000000100000200050006000004030100000000000200001040000500030007000
    000001305600000100000020000004300070000005000000900000000070480510000000000600000
    000010800050000000200000000800000100000207000000500004600300070000000350048000000
    000040200030000800007000000040000001200080000000500070001700030600200400000000000
    000050600104000000000003000020400000060080000000000010000300206300107000000000500
    000060080020000000001000000070000102500030000000000400004201000300700600000000050
    000071006500000030000000000000080100800300000000000007007400200010002000000500080
    000081000300000500200000000060200300010000000000004000008000042500700000000060010
    000100038200005000000000000050000400400030000000700006001000050000060200060004000
    000107000900000200800000000002060000000400500000000701000030080070500000050000060
    000200030060000040000000000070050900800300000000000000000067100400005070300000800
    000200030060000040000000000090050800700300000000000000000069100400005060300000700
    000200030070000040000000000060050900800300000000000000000067100400005070300000800
    000200030090000040000000000060050800700300000000000000000069100400005060300000700
    000300500200080000000000000063500000100000020000030040700002000000100004080000300
    000309600200000050000000000500080000000400700000000001013000400000005030070020000
    000358000600000100000000000160000005000700030200004000030500070000010200000000000
    000400100250000000600050000070300000000800004000000020400020000030000700000006010
    000400100250000000600050000070300000000800004000000020400020000030000900000006010
    000400200083000000000000006010070000600000400000008300500320000007000080000000010
    000500900000703000100000000000400037900020000000000040030060000000008100045000000
    000600045300007000000000000600000007000002500040080000001050000020000060000700300
    000600200100000000000030000000200609710000000000800000009504000080000300000070010
    000600302040001000000000000203050000000000480006000000810000050000020700000300000
    000600302040001000000000000203050000000000490006000000810000050000020700000300000
    000600720810000000000040000200000801004500000000000200000300060700080000000000050
    000620900801000000000000000400108000030000700000200000590070000000005020000000001
    000700005300800000000000600000060300700000020000001000430050000060000001000200070
    000800600070400000200000000300001000000020070001000400150000002004600000000000030
    000810000300000040000000000670100000500000930000200000408003000020000001000000600
    000870600200000000000100000060054000000000021400000000070000050000200300500001000
    000900200450000000100000000008607000000000001000000040500021000070000600000040030
    000940500210000000000008000302100000000000400800000000040000890000200030000060000
    001430000700000080000000000000702000014000000000600020000060401850000000000000300
    001700500600800000000000000000200004050000030090004000200000800400030000000050900
    003100060080500000000000000007060200200000001000400500000082030040000000500000000
    003400060500000001000000000000706400800000002000300000120080000000000630050000000
    004036000100000500000000000062000000000050700000800200000002004700000030050700000
    004600000000000780050000000010300500200000106000400000700010000008000040000000003
    005000020000100000400000000000400108050000400009000000800620000030000700000009050
    006005030020040000000000000300700000000010800005000400000200056040008000100000000
    010009000000700200000000000000300160800400000000000502000010040200050000409000000
    010050300000200000080000000020400800700620000300000100500000020000001000000000060
    010050300000200000080000000020400800700620000300000100900000020000001000000000060
    010050300000200000080000000060400800700620000300000100500000020000001000000000060
    010050300000200000080000000060400800700620000300000100900000020000001000000000060
    010050300000600000080000000060400800700260000300000100900000020000001000000000060
    010050300000800000070000000020400700600280000300000100900000020000001000000000080
    010050700000200000080000000020400800700620000300000100900000020000001000000000060
    010050700000200000080000000060400800700620000300000100900000020000001000000000060
    010050800000200000070000000020400700500620000300000100900000020000001000000000060
    010050800000200000070000000060400700500620000300000100900000020000001000000000060
    010400700000000280000000000208050000000001600005600000040000003000020050600000000
    010400700000000290000000000209050000000001600005800000040000003000020050600000000
    010500400000000290000000000209060000000001700006800000040000003000020060700000000
    010500800000000290000000000209060000000001700006700000040000003000020060700000000
    020001000000070800600000050000000021000630000080000000706000400500004000000200000
    020001000000080900600000050000000021000630000040000000708000400500007000000200000
    020500000000000308000000900300400050800030000000000010000020700050100000604000000
    040000600000070100000080000050400000000000027000003000107200000000100530800000000
    040060000000000350000010000009000100300800000000400060400200700060005000000000003
    050000801003600000000000000204000060000071000000000008000400390070030000100000000
    050060700008400000000000000400102000003000600000500200020070000000000034100000000
    060300100007500000000000000000200005800000030040070000000018400002000800500000000
    080000010004030000000600500600000003000020400010000000300108000000500070000000200
    081020000030009000000000000700600500000180000000000001400005000000000130000000086
    082700400000100000000000000310005000500040300000000000004093000600000010000000008
    083000070000610000000000000601700000400000080000000002020408000500000100000000300
    100000200003700000500400000200010000080000003000000040020300000600000100000007050
    100030670720000000000000000000201400300000500000400000008000030040500000000000001
    100300520080000000000000000005600000600000008000004070002000300070010000000080600
    100600000407000000000800700003000500070000200000010000050302000600000040000000001
    140000030000720000000000000080603000006000200000000100007500080200400000000080000
    200000080000400030000005000000040006000700400800000500074000100030020000000008000
    200000300000800500000001000080002040000030700000000000600070020057400000000000001
    200100600004000500000000000030040000800000009000050700050700010000800030007000000
    200500070060030000000000000000040501004008000050000020100700000003000400000200000
    200500070060030000000000000000040501004009000050000020100800000003000400000200000
    300050001000010000000000060002600300000204000000000005850000700000900020100000000
    300600100007000008000000000080001000000300200005000060000540070020060000100000000
    370000060000100000000000200000003400500000001000060000401500000000070058030000000
    400600300200700000010000000000270000000000018000000050306000700050008000000010000
    480001000000090200000000000050700008602030000000000010200400300030000000000008000
    560100040000800000000000000301040000020000008000000700400000530700008000000200000
    600050001000010000000000070002700300000204000000000005850000600000900020100000000
    600130000004000800000000000007500000000020060080000030000400709300001000020000000
    600400503000030700000000000000370100800000040200000000007000002000600080010000000
    700000200030060000000000000060010000300000080000700500002400060500207000000000001
    700040800000000390000000000013900000000070600000100000000050010600300000200000005
    700081000000000530000000000000605200400300008000000000000070064005200000010000000
    700600300000501000800000000040002000000070800010000000000400001006000020300050000
    700800200050100000000000000300050060000400001006000080000026300001000000040000000
    700800400000290000000000000021000090000500700000000010500000620300006000000010000
    706080000900000001000400000000003600040200000000000900680009000000010040000000020
    780200000000600500000000000050030000000001070006000020000050301200400000001000000
    800093000000000601000000000500200040000701200000000000000020480010600000300000000
    800094000000000701000000000300200050000701200000000000000030580010600000400000000
    800100000000006400000000000680000020000050300700040000004300000000200080500000009
    901006000800500000000000000040200000000000960000050000050000402300010000000009070
    020000350000010000040000000800205000000000906000400000901060000700009000000000020
    190000200000037000000000000607000800000100000300000000020400010005028000000000003
    100000800000060200000300000200070000000001040080000030007000560040803000000000000
    708000065000200400000000000000060001300000080040500000270000500000081000000000000
    004000200010500000000000060600010000000020070030000000200000140007800000000300600
    300500070060020009000000000000300500800000040010009000500470000000000901000000000
    060205700000300000000000000300000200700001000001090000820600000000040009000000010
    010600420000800000000050000005000030700400000000001000200030700000000504040000000
    000010003450000000000000080000400700900000500008000006000701020060000400000080000
    040030000000000201000000800001400000200000600000070000000506040600002000070000080
    040030000000000801000000200001400000200000600000070000000506040600002000070000080
    200304000000000070800000000000610700004000900600500000070000060000200003010000000
    200405000000000010800000000000730100005000900700600000030000070000200004010000000
    800405000000000010200000000000730100005000900700600000030000070000200004010000000
    450060300070010000000000000600000050000003700001800000700000010000200008000009000
    006000300040000050000080000000603500400200000100000000005700000000010004090000800
    500100006000430000000000080000200300000007040100000000020000500040008000000050001
    680010000000000250000000000000004006004500000070000100500200040003070000100000000
    620000000000100500000000000200040050000020100070008000100000040005300000000700002
    100500400000000680000000000020608000000000700000200000306070000000010020700000009
    600200090000150000000000000510000700000800040070000008800000100400003000000070000
    500040320000170000000000000830000600000720000000000000000008001020600000007000040
    000570013400000000000000008000600420810000000000000000100420000050000600000001000
    083000060000720000000000000000003010520000000700050000009004500000000204000100000
    083000070000420000000000000000003010640000000200060000009005600000000405000100000
    680000200000340000000000000050700080000000023900100000000008500003020000700000000
    000600804301000000000000000700500030000200001000007000260000700040010000000000020
    800000020000100800000070000420000600500700000000300001000040050000050007010000000
    200400600000500010000000000500080004300020000000000080000705300008000002010000000
    800600001000400020000000000053000000002050000040700000700001000000000250000020300
    050000270000830000100000000020700000000040008500000300301000006000200050000000000
    600020500900000030000000000001000007020060000000400010480000600000001002000300000
    200500080001020000000000000070008000003000020000070600600200001040000700000300000
    100000300060007000000080004500000710010800000000020000200001000000300008000000060
    701000000000500020000040600540000010030060000000800000000000306900100000000000400
    100800050000040030000600000060020900000003001000000000000900400300000200507000000
    020008500000700060000000000400000007000020030000010000308600000000500002600000100
    003090400800700000000000000500000904700200000000001600090060000000300020060000000
    000060200080300000100000000064000300000500040000001000700100000002000600000040080
    007000501200400000000000000820600000000010700000000000000200380005000060010004000
    000007401200300000000000000080530000004000700000000000030000650000004080700010000
    040000058300010000000000000501008000000000620600000000007000005000600100020300000
    603200000000040001000000000002000940700001000000050000070400080150000000000000300
    400000670050100000000000000070030000000000260080500000201000005600002000000080000
    020000308000010000400000000500060010803000000000700000000800400070400000005000090
    000300501080070000000000000000080200100500000004000070000401060350000000000000300
    205700000800050300000000000090000100000200000000000030030081000400000020000900007
    800600000000000450000001000000040700600000300000020000074000020000800001020300000
    000360000020000800000100000100000060000002500000000007008000240300700000000040005
    300040500000000001200000000070000300000108000400600000000070230008000060010000000
    005000003000700400010080000040005200000300000200000000000020610703000000000004000
    000600450070001000000300000000080600100000000000002000038040000000700010400000002
    400700005000000070000200000630000800500000200000010000000004100070500000001000090
    240000060000051000000000300000040800700500000000000001000200075018000000000900000
    260000007000031000000000400000050030800100000000000900000600018039000000000500000
    302400006500009000010000000000700400080000010000300000000080060700000300000010000
    402500006300009000010000000000700500080000010000300000000080060700000400000010000
    760000000000000408000010000000640100300000500008000000000500023000003060040000000
    000200040800000300010000000002004000000080050070000100000710600400500000000000001
    000300062010000000000000000050400100600050000000000008700208000300000500000040010
    000306700820000000000000000006050020200000030050007000300200000000480000000000100
    600000903000401000000000000000100080000073000900000004540030000080000010000000200
    000940700021000000000000000700001300800000004000200000040005020300080060000000000
    130000900000005008000200000000130000400000070000900000002007080000040100090000000
    020100000000000050000060000500002070000400600001000000860007000000030001200000400
    150000000600000800000900000302000070700000010000200000040017000000050900000000200
    634000000000250000000000070250000030000100000300000000001000800070004000000030200
    000000209300000010400000000000301000000600400000400500025080000070050000000000040
    800300000050000040700010000100605700000400000000000000024000030000020800000001000
    041000000600030000000200000700500008000004000000100000020000910000090200800003000
    080500300000000240000000000500000001000007060300020000000300700004060000062000000
    000401000005000700000000840000610003240000000500000000000200050001070000030000000
    800010000000000053060000000000402600100000000000000002023600000000870010000000500
    080000400300600000000700005100200000000000052400000000700000300000080060020050000
    080000100300500000000600004100200000000000042700000000600000300000080050020040000
    000200400005000800030070000000108030100400000000000050024000100000050000600000000
    400750000002030000000000000000500064010000000000000080570000300000002100600400000
    050003600200700000000000000830400000000020070000000100000001200700000040040060000
    000040230800500000000000000060001000000020700300000400000300068002400000010000000


    Citation : Pouet_forever

    Ton code a résolu 1466 grilles, où est la dernière ? :lol:


    Oui, je sais, le programme comptabilise le dernière ligne (vide). La flemme de corriger...

    Au fait, tu pourrais faire s'il te plait un 2e bench sur les 1000/2000 premières entrées du second fichier (attention, le format est légèrement différent) ?.
    • Partager sur Facebook
    • Partager sur Twitter
      24 septembre 2011 à 21:14:21

      Citation : yoch

      Au fait, tu pourrais faire s'il te plait un 2e bench sur les 1000/2000 premières entrées du second fichier (attention, le format est légèrement différent) ?.


      Oui, et non. :-°
      J'avais commencé, mais j'ai une moyenne a 4,5 secondes par grille sur une centaine de grilles, j'ai stoppé parce que c'était trop long. ^^
      • Partager sur Facebook
      • Partager sur Twitter
        25 septembre 2011 à 3:28:38

        Pour le bench sur les 1465 grilles, j'ai
        1465 grilles en 392.281s

        soit environ 0.3s par grille(Sur un ordinosaure).
        #include <stdio.h>
        #include <stdlib.h>
        #include <time.h>
        
        #define N   9
        
        typedef struct
        {
            int pos;
            int n;
        } cell;
        
        
        
        cell cells[N * N];
        int possibility[N * N][N + 1];
        
        
        int cmp(void const *p, void const *q)
        {
            return ((cell *)q)->n - ((cell *)p)->n;
        }
        
        
        
        void grid_display(int *g)
        {
            for(int i = 0; i < N; i++)
            {
                for(int j = 0; j < N; j++)
                    printf("%d", g[i * N + j]);
                puts("");
            }
            puts("");
        }
        
        
        int check_square(int *g, int row, int col, int v)
        {
            int ox = (col / 3) * 3;
            int oy = (row / 3) * 3;
        
            for(int i = oy; i < oy + 3; i++)
                for(int j = ox; j < ox + 3; j++)
                    if(g[i * N + j] == v)
                        return 0;
            return 1;
        }
        
        
        
        int check_row_col(int *g, int row, int col, int v)
        {
            for(int i = 0; i < N; i++)
                if(g[i * N + col] == v || g[row * N + i] == v)
                    return 0;
            return 1;
        }
        
        
        int check_cell(int *g, int pos, int v)
        {
            int col = pos % N;
            int row = pos / N;
            return check_row_col(g, row, col, v) && check_square(g, row, col, v);
        }
        
        
        
        
        int singleton_block(int *g)
        {
            int n_singletons = 0;
            for(int i = 0; i < N; i += 3)
                for(int j = 0; j < N; j += 3)
                {
                    int pos = 0;
                    for(int k = 1; k <= N; k++)
                    {
                        int count = 0;
                        for(int ii = i; ii < i + 3; ii++)
                            for(int jj = j; jj < j + 3; jj++)
                            {
                                if(!g[ii * N + jj] && check_cell(g, ii * N + jj, k))
                                {
                                    count++;
                                    pos =  ii * N + jj;
                                }
                            }
                        if(count == 1)
                        {
                            g[pos] = k;
                            n_singletons++;
                        }
                    }
                }
            return n_singletons;
        }
        
        
        
        int singleton_col(int *g)
        {
            int n_singletons = 0;
            for(int col = 0; col < N; col++)
            {
                int pos = 0;
                for(int k = 1; k <= N; k++)
                {
                    int count = 0;
                    for(int row = 0; row < N; row++)
                    {
                        if(!g[ row * N + col])
                        {
                            if(check_cell(g, row * N + col, k))
                            {
                                count++;
                                pos =  row * N + col;
                            }
                        }
                    }
                    if(count == 1)
                    {
                        g[pos] = k;
                        n_singletons++;
                    }
                }
            }
            return n_singletons;
        }
        
        
        int singleton_row(int *g)
        {
            int n_singletons = 0;
            for(int row = 0; row < N; row++)
            {
                int pos = 0;
                for(int k = 1; k <= N; k++)
                {
                    int count = 0;
                    for(int col = 0; col < N; col++)
                    {
                        if(!g[ row * N + col])
                        {
                            if(check_cell(g, row * N + col, k))
                            {
                                count++;
                                pos =  row * N + col;
                            }
                        }
                    }
                    if(count == 1)
                    {
                        g[pos] = k;
                        n_singletons++;
                    }
                }
            }
            return n_singletons;
        }
        
        
        int backtrack(int *g, int id)
        {
            int pos = cells[id].pos;
            if(id == N * N)
                return 1;
            if(g[pos])
                return backtrack(g, id + 1);
            else
            {
                for(int k = 1; k <= N; k++)
                {
                    if(possibility[pos][k])
                        if(check_cell(g, pos, k))
                        {
                            g[pos] = k;
                            if(backtrack(g, 0))
                                return 1;
                        }
                }
                g[pos] = 0;
                return 0;
            }
        }
        void solve(int *g)
        {
            int find = 0;
            do
            {
                find = singleton_row(g) + singleton_col(g) + singleton_block(g);
                for(int i = 0; i < N * N; i++)
                {
                    int n = 0;
                    int last = 0;
                    if(!g[i])
                    {
                        for(int k = 1; k <= N; k++)
                            if(check_cell(g, i, k))
                            {
                                possibility[i][k] = 1;
                                last = k;
                                n++;
                            }
                            else
                                possibility[i][k] = 0;
                        if(n == 1)
                        {
                            g[i] = last;
                            find = 1;
                        }
                    }
                    cells[i].pos = i;
                    cells[i].n = n;
                }
            }
            while(find);
        
            //qsort(cells, N * N, sizeof *cells, cmp);
            backtrack(g, 0);
        }
        
        #define SZBUF   100
        int main (void)
        {
            FILE* fp = fopen("shorters_sudokus.txt", "r");
            if (fp == NULL)
            {
                fprintf(stderr, "Impossible d'ouvrir le fichier");
                exit(0);
            }
        
            int grille[N * N] = {0};
        
            char buffer[SZBUF] = {0};
            size_t elapsed = 0, counter = 0;
            while (fgets(buffer, SZBUF, fp) != NULL)
            {
                for (int i=0; i < 81; i++)
                    grille[i] = buffer[i] == '.' ? 0 : buffer[i] - '0';
        
                clock_t t1 = clock();
                solve (grille);
                clock_t t2 = clock();
        
                elapsed += (t2-t1);
                counter++;
            }
        
            printf("%u grilles en %gs\n\n", counter, (double)elapsed/CLOCKS_PER_SEC);
        
            fclose(fp);
        
            return 0;
        }
        

        Avec seulement avec un traitement des cas triviaux avant de lancer le bactrack(sans tri préalable par nombre de possibilités par case).

        edit:
        @Yoch: DLX kesako?
        • Partager sur Facebook
        • Partager sur Twitter
        Zeste de Savoir, le site qui en a dans le citron !
          25 septembre 2011 à 7:21:07

          Citation : GurneyH

          @Yoch: DLX kesako?


          C'est un algo extrêmement puissant permettant de résoudre assez rapidement le problème de couverture exacte. Je compte faire un post là dessus, dans lequel j’essaierai de détailler un peu le principe, et donner un code.
          • Partager sur Facebook
          • Partager sur Twitter
          Anonyme
            25 septembre 2011 à 12:52:00

            Dites voir, la méthode dela force brute, elle consiste à tester tous les chiffres possibles et voir s'ils sont bons non ?
            • Partager sur Facebook
            • Partager sur Twitter
              25 septembre 2011 à 13:02:44

              Citation : informaticienzero

              Dites voir, la méthode dela force brute, elle consiste à tester tous les chiffres possibles et voir s'ils sont bons non ?


              C'est ça. :)
              L'erreur à ne pas faire est de tester si la grille est valide seulement après avoir rempli toutes les cases.
              Il faut pour chaque nombre que tu places, vérifier si la grille est toujours valide, sinon tester un autre nombre ou retourner en arrière(si plus de possibilités).

              @Yoch:
              Je viens de faire une recherche sur l'algorithme DLX. Sympa! :)
              Je vais essayer.
              • Partager sur Facebook
              • Partager sur Twitter
              Zeste de Savoir, le site qui en a dans le citron !
                25 septembre 2011 à 13:59:33

                Voici comme promis : :)

                Le sudoku : une instance du problème de la couverture exacte



                Nombre de problèmes de satisfactions de contraintes peuvent être ramenés au problème dit "problème de la couverture exacte". C'est le cas aussi pour le problème du sudoku. :)

                Ramener le problème du sudoku à celui de la couverture exacte revient à modéliser le problème par contraintes : il y a 4 types de contraintes dans un sudoku classique :
                • un seul exemplaire de chaque signe sur chaque ligne.
                • un seul exemplaire de chaque signe sur chaque colonne.
                • un seul exemplaire de chaque signe sur chaque bloc.
                • chaque cellule, doit contenir exactement un signe.


                Algorithme X et liens dansants : le DLX est né...


                Image utilisateur


                D. Knuth (professeur émérite en informatique à l'université Stanford, et auteur du très célèbre ouvrage "The Art of Computer Programming") a élaboré un algorithme permettant de résoudre récursivement le problème de la couverture exacte : j'ai nommé l'algorithme X.

                Cet algo ne serait rien sans une structure de données spéciales associée, qui donne à l'algorithme toute sa puissance. Il s'agit d'une modélisation de tableau 2D en un réseau de listes doublement chainées, qui confère d'excellentes performances à l'algorithme X. Vous pouvez admirer ci-contre une représentation de la structure en question.

                Knuth à nommé cette structure "dancing links" (liens dansants), et une fois couplé avec l'algo en question, je vous présente l'algo <acronym title="Dancing Links for X algorithm">DLX</acronym> !
                Le nom de cette structure de données provient, aux dires de l'auteur :

                Citation : D. Knuth

                This process causes the pointer variables inside the global data structure to execute an
                exquisitely choreographed dance; hence I like to call (1) and (2) the technique of dancing
                links.





                Un exemple d'application : résolution d'une grille 25x25



                Code :


                #include <stdlib.h>
                #include <stdio.h>
                #include <limits.h>
                #include <time.h>
                
                
                
                #define N       (5)
                #define N_2     (N*N)
                #define base    ('A')
                
                
                //  Variable globale - grille 25x25
                    int grille[N_2][N_2] =
                    {
                        { 0 , 0 ,'L', 0 , 0 , 0 ,'U', 0 , 0 ,'K', 0 , 0 , 0 ,'G', 0 , 0 , 0 , 0 ,'C','Q', 0 , 0 ,'I', 0 ,'X'},
                        { 0 , 0 , 0 , 0 ,'Q','H', 0 ,'R', 0 , 0 ,'K', 0 , 0 , 0 , 0 , 0 ,'V', 0 , 0 , 0 ,'A','M','T', 0 , 0 },
                        {'D','A','B','H','I', 0 , 0 , 0 ,'C', 0 , 0 , 0 ,'X','T', 0 , 0 ,'F', 0 , 0 , 0 , 0 , 0 , 0 ,'V','K'},
                        {'U','V','X','W', 0 , 0 ,'D','J','E', 0 , 0 , 0 ,'I','R','A', 0 , 0 ,'O', 0 , 0 ,'C','H', 0 , 0 , 0 },
                        {'K', 0 , 0 ,'G', 0 ,'X','F', 0 ,'B','W','Q','D', 0 , 0 ,'L', 0 , 0 , 0 , 0 , 0 , 0 , 0 ,'O', 0 , 0 },
                        { 0 , 0 , 0 , 0 , 0 ,'Q','I','U', 0 , 0 , 0 ,'O', 0 ,'S', 0 , 0 , 0 , 0 ,'R', 0 , 0 , 0 , 0 ,'P','N'},
                        { 0 , 0 , 0 ,'E', 0 ,'D','V','K', 0 ,'J', 0 , 0 , 0 ,'P','Q', 0 , 0 ,'L', 0 ,'A','M','I','Y', 0 ,'H'},
                        { 0 , 0 ,'F', 0 ,'C', 0 ,'R','A', 0 , 0 , 0 , 0 ,'N','U','G', 0 , 0 , 0 ,'I','W','S', 0 , 0 ,'B', 0 },
                        { 0 ,'I', 0 ,'Q','H', 0 ,'O','Y', 0 , 0 ,'L', 0 , 0 ,'D', 0 , 0 ,'B', 0 , 0 ,'K','T', 0 ,'U', 0 , 0 },
                        { 0 ,'M','G', 0 , 0 ,'W','C', 0 , 0 , 0 , 0 , 0 ,'T', 0 , 0 , 0 , 0 , 0 , 0 ,'J', 0 ,'R', 0 ,'D','V'},
                        {'M', 0 ,'R', 0 ,'E','B', 0 , 0 , 0 , 0 , 0 , 0 ,'D', 0 , 0 ,'C', 0 , 0 , 0 ,'H', 0 ,'A', 0 ,'G','W'},
                        { 0 , 0 , 0 ,'P','W', 0 , 0 ,'G', 0 , 0 ,'A','Y', 0 , 0 ,'E', 0 , 0 , 0 , 0 , 0 ,'X', 0 ,'N', 0 , 0 },
                        { 0 , 0 , 0 ,'K','Y', 0 , 0 ,'L', 0 , 0 , 0 , 0 , 0 ,'W','U','T', 0 ,'N','D', 0 , 0 , 0 , 0 , 0 , 0 },
                        {'H','L','T','S', 0 , 0 , 0 , 0 ,'W', 0 , 0 , 0 ,'V', 0 ,'K','X', 0 , 0 , 0 ,'F', 0 , 0 ,'Q','J', 0 },
                        {'N','B', 0 , 0 , 0 , 0 ,'H', 0 ,'S','Y','F','P', 0 ,'C','I','K', 0 ,'E', 0 ,'L', 0 , 0 , 0 ,'T','O'},
                        {'L','Q', 0 , 0 , 0 , 0 , 0 ,'E', 0 ,'U','R', 0 ,'F', 0 , 0 ,'B','I', 0 , 0 ,'X','D', 0 ,'J', 0 ,'T'},
                        {'B', 0 , 0 ,'A', 0 , 0 , 0 , 0 , 0 ,'C', 0 , 0 , 0 , 0 ,'Y','S', 0 , 0 ,'U','V','P', 0 , 0 ,'X', 0 },
                        {'T', 0 , 0 ,'X','P', 0 ,'J', 0 , 0 , 0 , 0 , 0 ,'Q','A', 0 , 0 , 0 ,'W', 0 ,'E','R','Y', 0 ,'C', 0 },
                        { 0 ,'H', 0 , 0 ,'N','Y','Q', 0 , 0 , 0 ,'X','I','S','E', 0 ,'F', 0 , 0 ,'T', 0 , 0 ,'K','W','A', 0 },
                        { 0 , 0 ,'K','Y','F','T','A', 0 , 0 ,'G', 0 , 0 ,'P','N', 0 , 0 , 0 , 0 ,'J','O','Q','L', 0 , 0 ,'U'},
                        {'V','W', 0 , 0 , 0 ,'U', 0 ,'P', 0 , 0 , 0 ,'H', 0 , 0 ,'R','G', 0 ,'X', 0 , 0 , 0 ,'N','M', 0 ,'Q'},
                        { 0 ,'G', 0 ,'O', 0 , 0 ,'T', 0 , 0 ,'F', 0 ,'X', 0 ,'B','N','M', 0 , 0 ,'K','C', 0 , 0 ,'E', 0 ,'Y'},
                        {'C','U', 0 ,'J', 0 ,'G','Y','N','O','S', 0 , 0 , 0 ,'I', 0 ,'V', 0 ,'F', 0 , 0 ,'B', 0 , 0 , 0 , 0 },
                        {'I', 0 , 0 , 0 , 0 ,'R','E', 0 , 0 , 0 ,'W','S','O', 0 ,'J', 0 , 0 ,'A', 0 , 0 , 0 , 0 ,'K', 0 , 0 },
                        { 0 ,'P', 0 , 0 ,'T','C', 0 ,'X','M','D', 0 , 0 , 0 ,'Q', 0 , 0 , 0 , 0 , 0 ,'Y', 0 ,'U','L','O', 0 }
                    };
                
                
                ////////////////////////////////////////////////////////////
                //             Fonction d'affichage
                ////////////////////////////////////////////////////////////
                void affichage (int grille[N_2][N_2])
                {
                    for (int i=0; i<N_2; i++)
                    {
                        for (int j=0; j<N_2; j++)
                        {
                            printf( ((j+1)%N) ? "%c " : "%c|", grille[i][j]);
                        }
                        putchar('\n');
                        if (!((i+1)%N))
                        {
                            for (int i=0; i<N_2*2; i++)
                                putchar('-');
                            putchar('\n');
                        }
                    }
                    puts("\n\n");
                }
                
                ////////////////////////////////////////////////////////////
                //          DLX : définition et fonctions
                ////////////////////////////////////////////////////////////
                
                typedef union
                {
                    unsigned size;
                    struct
                    {
                        unsigned short i;
                        unsigned short j;
                        char val;
                    } cell;
                } dlx_t;
                
                typedef struct _node
                {
                    struct _node* left;
                    struct _node* right;
                    struct _node* up;
                    struct _node* down;
                    struct _node* head;
                    dlx_t data;
                } Node;
                
                
                Node* CreateRoot (void)
                {
                    Node* root = malloc (sizeof *root);
                    root->right = root->left = root->up = root->down = root;
                    root->head = NULL;
                    return root;
                }
                
                Node* CreateHeader (Node* root)
                {
                    Node* header = malloc (sizeof *header);
                    // gestion des liens right & left
                    header->left = root->left;
                    header->right = root;
                    root->left->right = header;
                    root->left = header;
                    // gestion des liens up & down
                    header->up = header->down = header;
                    // initialise nbElements
                    header->data.size = 0;
                    header->head = NULL;
                    return header;
                }
                
                Node* CreateNode (Node* header, Node* last)
                {
                    Node* node = malloc (sizeof *node);
                    // gestion des liens up & down
                    node->up = header->up;
                    node->down = header;
                    header->up->down = node;
                    header->up = node;
                    node->head = header;
                    // gestion des liens right & left
                    if (last == NULL)
                    {
                        node->right = node->left = node;
                    }
                    else
                    {
                        node->left = last;
                        node->right = last->right;
                        last->right->left = node;
                        last->right = node;
                    }
                    // incremente nbElements du header
                    header->data.size++;
                    return node;
                }
                
                static void cover (Node* header)
                {
                    // supprime le header
                    header->left->right = header->right;
                    header->right->left = header->left;
                    // traitement des noeuds
                    for (Node* iter = header->down; iter != header; iter = iter->down)
                    {
                        for (Node* iter2 = iter->right; iter2 != iter; iter2 = iter2->right)
                        {
                            iter2->up->down = iter2->down;
                            iter2->down->up = iter2->up;
                            iter2->head->data.size--;
                        }
                    }
                }
                
                static void uncover (Node* header)
                {
                    // traitement des noeuds
                    for (Node* iter = header->up; iter != header; iter = iter->up)
                    {
                        for (Node* iter2 = iter->left; iter2 != iter; iter2 = iter2->left)
                        {
                            iter2->up->down = iter2;
                            iter2->down->up = iter2;
                            iter2->head->data.size++;
                        }
                    }
                    // restaure le header
                    header->left->right = header;
                    header->right->left = header;
                }
                
                
                Node* pile[4*N_2*N_2];
                int search (Node* root, unsigned n)
                {
                    int ret = 0;
                
                    if (root == root->right)
                    {
                        // recupere les information et remplit la grille
                        for (unsigned k=0; k < n; k++)
                        {
                            grille[pile[k]->data.cell.i][pile[k]->data.cell.j] = pile[k]->data.cell.val;
                        }
                        return 1;
                    }
                
                    // recherche la colonne avec le moins de noeuds
                    unsigned min = UINT_MAX;
                    Node* header = NULL;
                    for (Node* iter = root->right; iter != root; iter = iter->right)
                    {
                        if (iter->data.size < min)
                            header = iter, min = iter->data.size;
                    }
                
                    //if (min == 0) return false;
                
                    // procedure
                    cover(header);
                    for (Node* iter = header->down; iter != header; iter = iter->down)
                    {
                        //Node* row = iter;
                        pile[n] = iter;
                        for (Node* iter2 = iter->right; iter2 != iter; iter2 = iter2->right)
                            cover(iter2->head);
                
                        ret += search(root, n+1);
                
                        //iter = row, header = row->head;
                        for (Node* iter2 = iter->left; iter2 != iter; iter2 = iter2->left)
                            uncover(iter2->head);
                    }
                    uncover(header);
                
                    return ret;
                }
                
                void DeleteAll (Node* root)
                {
                    Node *nextr, *nextd;
                    for (Node* iter = root->right; iter != root; iter = nextr)
                    {
                        for (Node* iter2 = iter->down; iter2 != iter; iter2 = nextd)
                        {
                            nextd = iter2->down;
                            free (iter2);
                        }
                        nextr = iter->right;
                        free (iter);
                    }
                    free (root);
                }
                
                ////////////////////////////////////////////////////////////
                //                  Resolution Sudoku
                ////////////////////////////////////////////////////////////
                
                void add_row (Node* header[], unsigned l, unsigned c, char val)
                {
                    unsigned pos[4];
                    unsigned k = val-base;
                    // calcule les positions pour les contraintes
                    pos[0] = (l*N_2)+c;
                    pos[1] = (l*N_2)+k;
                    pos[2] = (c*N_2)+k;
                    pos[3] = ((N*(l/N)+c/N)*N_2)+k;
                    // ajoute les contraintes au dancing links
                    Node* last = NULL;
                    for (unsigned i=0; i < 4; i++)
                    {
                        last = CreateNode (header[i*N_2*N_2+pos[i]], last);
                        last->data.cell.i = l;
                        last->data.cell.j = c;
                        last->data.cell.val = val;
                    }
                }
                
                int main (void)
                {
                    affichage(grille);
                
                    Node* header[4*N_2*N_2];
                
                    clock_t t1 = clock();
                
                    // cree la racine
                    Node* root = CreateRoot();
                
                    // cree les headers
                    for (unsigned i=0; i < 4*N_2*N_2; i++)
                        header[i] = CreateHeader(root);
                
                    for (unsigned l=0; l < N_2; l++)
                        for (unsigned c=0; c < N_2; c++)
                        {
                            if (grille[l][c] != 0)
                                add_row (header, l, c, grille[l][c]);
                            else for (int val=base; val < base+N_2; val++)
                                    add_row (header, l, c, val);
                        }
                
                    // appelle la resolution par DLX
                    search(root, 0);
                
                    DeleteAll (root);
                
                    clock_t t2 = clock();
                
                    affichage(grille);
                
                    printf(" time elapsed = %gs\n", (double)(t2-t1)/CLOCKS_PER_SEC);
                
                    return 0;
                }
                


                Sortie :


                .
                    L    |  U     K|      G  |      C Q|    I   X|
                        Q|H   R    |K        |  V      |A M T    |
                D A B H I|      C  |    X T  |  F      |      V K|
                U V X W  |  D J E  |    I R A|    O    |C H      |
                K     G  |X F   B W|Q D     L|         |    O    |
                --------------------------------------------------
                         |Q I U    |  O   S  |      R  |      P N|
                      E  |D V K   J|      P Q|    L   A|M I Y   H|
                    F   C|  R A    |    N U G|      I W|S     B  |
                  I   Q H|  O Y    |L     D  |  B     K|T   U    |
                  M G    |W C      |    T    |        J|  R   D V|
                --------------------------------------------------
                M   R   E|B        |    D    |C       H|  A   G W|
                      P W|    G    |A Y     E|         |X   N    |
                      K Y|    L    |      W U|T   N D  |         |
                H L T S  |      W  |    V   K|X       F|    Q J  |
                N B      |  H   S Y|F P   C I|K   E   L|      T O|
                --------------------------------------------------
                L Q      |    E   U|R   F    |B I     X|D   J   T|
                B     A  |        C|        Y|S     U V|P     X  |
                T     X P|  J      |    Q A  |    W   E|R Y   C  |
                  H     N|Y Q      |X I S E  |F     T  |  K W A  |
                    K Y F|T A     G|    P N  |      J O|Q L     U|
                --------------------------------------------------
                V W      |U   P    |  H     R|G   X    |  N M   Q|
                  G   O  |  T     F|  X   B N|M     K C|    E   Y|
                C U   J  |G Y N O S|      I  |V   F    |B        |
                I        |R E      |W S O   J|    A    |    K    |
                  P     T|C   X M D|      Q  |        Y|  U L O  |
                --------------------------------------------------
                
                
                
                E T L M R|V U O A K|S N W G P|D H B C Q|F J I Y X|
                O F P N Q|H G R Y I|K C E J B|W V S X U|A M T L D|
                D A B H I|S L M C Q|Y U X T O|J F R E G|N W P V K|
                U V X W S|N D J E P|M F I R A|Y K O L T|C H G Q B|
                K Y C G J|X F T B W|Q D H V L|A N I M P|E S O U R|
                --------------------------------------------------
                A D J L V|Q I U G B|H O Y S W|E X T R M|K F C P N|
                X N S E O|D V K T J|C R B P Q|U G L F A|M I Y W H|
                Y K F T C|P R A H M|J E N U G|O D V I W|S Q X B L|
                R I W Q H|F O Y N X|L A M D V|P B C S K|T G U E J|
                P M G B U|W C S L E|I K T F X|Q Y H N J|O R A D V|
                --------------------------------------------------
                M O R I E|B K F U N|T Q D X S|C J P Y H|L A V G W|
                F J U P W|O M G D T|A Y L H E|I R Q V B|X C N K S|
                G C Q K Y|A X L I V|B J R W U|T O N D S|H P F M E|
                H L T S D|E P C W R|N M V O K|X A U G F|Y B Q J I|
                N B A V X|J H Q S Y|F P G C I|K M E W L|U D R T O|
                --------------------------------------------------
                L Q V C G|M S E P U|R W F K H|B I Y A X|D O J N T|
                B R D A M|I N W F C|O T J L Y|S Q K U V|P E H X G|
                T S I X P|K J D V O|U G Q A M|N L W H E|R Y B C F|
                J H O U N|Y Q B R L|X I S E C|F P G T D|V K W A M|
                W E K Y F|T A H X G|V B P N D|R C M J O|Q L S I U|
                --------------------------------------------------
                V W E F L|U B P K A|D H C Y R|G T X O I|J N M S Q|
                Q G H O A|L T I J F|P X U B N|M S D K C|W V E R Y|
                C U M J K|G Y N O S|E L A I T|V W F Q R|B X D H P|
                I X Y D B|R E V Q H|W S O M J|L U A P N|G T K F C|
                S P N R T|C W X M D|G V K Q F|H E J B Y|I U L O A|
                --------------------------------------------------
                
                
                
                 time elapsed = 0.025s
                
                Process returned 0 (0x0)   execution time : 0.272 s
                Press any key to continue.
                • Partager sur Facebook
                • Partager sur Twitter
                Anonyme
                  25 septembre 2011 à 14:10:49

                  Je vais essayer cet aprèms, mais après avoir réviser le controle de maths (et accessoirement ranger ma chambre). ^^

                  En tout cas, ta méthode est extrêmement rapide yoch, moins d'une seconde !
                  • Partager sur Facebook
                  • Partager sur Twitter
                    25 septembre 2011 à 15:06:26

                    Citation : GurneyH

                    vérifier si la grille est toujours valide

                    yeap, mais pas besoin de tester toute la grille, juste les lignes où on vient de changer un chiffre.

                    Assez hallucinant ce DLX là... le mec a dû y réfléchir plus que 5 minutes je suppose.
                    • Partager sur Facebook
                    • Partager sur Twitter
                      25 septembre 2011 à 15:30:01

                      Argh, j'ai même pas encore pu commencé à envisager de faire le premier qu'il y en a déjà un troisième... (je parle des défis :D ) ?!?
                      Bon, comme mes cours m'empêche grandement de progresser (il en va de même pour mon entêtement personnel à vouloir résoudre un problème avant d'en commencer un autre) je poste ce message surtout pour me rappeler l'existence d'un tel défi à faire! (il faut que je le fasse aussi pour le deuxième défi...)
                      Sinon, est-ce possible de créer un programme qui crée des grilles de sudoku? En tout cas, si l'exercice est faisable et encore jamais proposé... pourquoi pas en faire le sujet d'un défi numéro X^^ sur ce bonne journée à tous, j'ai encore beaucoup de boulot moi (OSEF, je sais :D mais ça me plait de le dire )
                      • Partager sur Facebook
                      • Partager sur Twitter
                        25 septembre 2011 à 18:01:22

                        Citation : Ccile

                        Sinon, est-ce possible de créer un programme qui crée des grilles de sudoku? En tout cas, si l'exercice est faisable et encore jamais proposé... pourquoi pas en faire le sujet d'un défi numéro X^^


                        Oui, c'est possible, et même assez accessible une fois l'exercice fait. Le mode d'emploi en étapes :
                        1. Lancer un backtracking (ou autre) sur une grille vide doit la remplir, seulement toujours de la même façon...
                        2. Ensuite, on peut mettre en place un système aléatoire de remplissage. Par exemple, pour chaque case, on utilise une liste aléatoire définie au départ (attention de ne pas changer de séquence au milieu, on va corrompre le backtracking et risquer une boucle infinie).
                        3. Ensuite, on crée une fonction qui puisse vérifier le nombre de solutions d'une grille (1 ou >1).
                        4. Puis on tire des cases aléatoirement, et on essaye de supprimer la valeur (en testant avec la fonction créée en 3) : a) si la grille reste valide, c'est bon b) sinon, on remets la valeur à sa place.
                        5. On récupère à la fin une grille de sudoku valide ! :)
                        • Partager sur Facebook
                        • Partager sur Twitter
                          25 septembre 2011 à 18:35:10

                          Vraiment sympathique, cette méthode DLX, je ne connaissais pas...
                          • Partager sur Facebook
                          • Partager sur Twitter
                          Staff désormais retraité.
                            25 septembre 2011 à 19:20:26

                            Si seulement je comprenais... ^^
                            • Partager sur Facebook
                            • Partager sur Twitter
                              25 septembre 2011 à 23:45:31

                              Y'a un truc que je capte pas. Dans le problème de couverture exacte, comment représenter la grille de sudoku ? il y a un exemple, mais je suis pas sûr d'avoir saisi le truc. Et après comment avec l'algo X on peut arriver à déterminer les nombres à mettre dans les cases ?
                              Dans le principe, j'ai compris l'algo, mais j'arrive pas à l'appliquer, que ce soit les pentaminos ou le sudoku. :(
                              • Partager sur Facebook
                              • Partager sur Twitter
                                26 septembre 2011 à 7:08:19

                                Tu as bien lu ça ?

                                Chaque ligne représente une possibilité pour une case du sudoku, et tu dois remplir (=mettre à 1, soit créer un noeud à la ligne/colonne correspondante pour le DLX) dans chaque ligne du tableau 4 cases, correspondant aux 4 contraintes évoquées plus haut.

                                Une fois le problème de satisfaction des contraintes résolu (avec la fonction de résolution récursive), il doit te rester 81 lignes (listes doublement chainées avec le DLX) qui correspondent à la couverture exacte, et sont la solution recherchée. Tu dois alors stocker la solution d'une façon ou d'une autre, parce que tu dois laisser le programme reconstruire la structure originale avant de quitter, si tu ne veux pas de fuite de mémoire.
                                • Partager sur Facebook
                                • Partager sur Twitter
                                  26 septembre 2011 à 20:54:12

                                  Ouais, ouais, j'ai lu, mais je bug. :-°
                                  Je verrai pour me repencher dessus si j'ai le temps. :)
                                  • Partager sur Facebook
                                  • Partager sur Twitter
                                    26 septembre 2011 à 21:01:13

                                    Qui est plus performant et donne un meilleur résultat : backtracking ou DLX ?

                                    Pour mon programme je teste les cases de la grille si celle si est vide et il ya q'une seul solution donc je la lui attribut et je retourne a la case (0, 0) sinon je continue . C'est une bonne chose ? je peut passer directement au backtracking ?

                                    • Partager sur Facebook
                                    • Partager sur Twitter
                                      26 septembre 2011 à 21:07:24

                                      Citation : kaka551

                                      Pour mon programme je teste les cases de la grille si celle si est vide et il ya q'une seul solution donc je la lui attribut et je retourne a la case (0, 0) sinon je continue . C'est une bonne chose ? je peut passer directement au backtracking ?


                                      Bha oui c'est un bon début mais tu résoudras pas toutes les grilles avec cette méthode. Donc oui il vaut mieux passer au backtracking.
                                      • Partager sur Facebook
                                      • Partager sur Twitter
                                        26 septembre 2011 à 21:12:29

                                        Cette methode ne résoudra effectivement que les grilles très faciles (singletons uniquement), mais elle peut etre utilisée comme pré-traitement avant de lancer un backtrcking (cf. le post de GurneyH, par exemple).
                                        • Partager sur Facebook
                                        • Partager sur Twitter
                                          26 septembre 2011 à 21:53:27

                                          Oui, ça ne résout que les grille assez facile, mais je compte me passer au backtracking. c'est une bonne occasion pour l'apprendre et l’exercer.

                                          EDIT :

                                          J'ai pas eu beaucoup de temps ces derniers temps. mais aujourd'hui, j'ai amélioré mon solveur pour qu'il utilise le backtracking (ca ressemble au code proposé par yoch dans son tuto).

                                          La code :


                                          #include <stdio.h>
                                          #include <stdlib.h>
                                          
                                          int chercheDansLigne(char grille[][9], int ligne, int nbr);
                                          int chercheDansCollone(char grille[][9], int collone, int nbr);
                                          int chercheDansRegion(char grille[][9], int X, int Y, int nbr);
                                          int resoudre(char grille[][9], int pos);
                                          
                                          int main()
                                          {
                                          
                                              char grille[9][9];
                                              int i, j, entre;
                                              for(i = 0; i < 9; i++)
                                              scanf("%1c%1c%1c%1c%1c%1c%1c%1c%1c%1c", &grille[i][0], &grille[i][1], &grille[i][2], &grille[i][3], &grille[i][4],
                                                                                      &grille[i][5], &grille[i][6], &grille[i][7], &grille[i][8], &entre);
                                          
                                              for(i = 0; i < 9; i++)
                                                  for(j = 0; j < 9; j++)
                                                      grille1[i][j] -= grille1[i][j] == ' ' ? 32 : '0';
                                          
                                              resoudre(grille, 0);
                                          
                                              for(i = 0; i < 9; i++){
                                                  for(j = 0; j < 9; j++)
                                                      printf("%d ",grille[i][j]);
                                                      printf("\n");}
                                          
                                              return 0;
                                          }
                                          
                                          int chercheDansLigne(char grille[][9], int ligne, int nbr)
                                          {
                                              int i;
                                              for(i = 0; i < 9; i++)
                                                  if(grille[ligne][i] == nbr)
                                                      return 1;
                                          
                                              return 0;
                                          }
                                          
                                          int chercheDansCollone(char grille[][9], int collone, int nbr)
                                          {
                                              int i;
                                              for(i = 0; i < 9; i++)
                                                  if(grille[i][collone] == nbr)
                                                      return 1;
                                          
                                              return 0;
                                          }
                                          
                                          int chercheDansRegion(char grille[][9], int X, int Y, int nbr)
                                          {
                                              int i, j;
                                              for(i = ((int)floor(X / 3) * 3); i < ((int)floor(X / 3) * 3) + 3; i++)
                                                  for(j = ((int)floor(Y / 3) * 3); j < ((int)floor(Y / 3) * 3) + 3; j++)
                                                      if(grille[i][j] == nbr)
                                                          return 1;
                                          
                                              return 0;
                                          }
                                          
                                          int resoudre(char grille[][9], int pos)
                                          {
                                             int i = pos / 9, j = pos % 9, k;
                                          
                                             if(pos == 81)
                                             return 1;
                                          
                                             if(grille[i][j] != 0)
                                             return resoudre(grille, pos+1);
                                          
                                             for(k = 1; k < 10; k++)
                                             {
                                                 if(!chercheDansCollone(grille, j, k) && !chercheDansLigne(grille, i, k) && !chercheDansRegion(grille, i, j, k))
                                                 {
                                                     grille[i][j] = k;
                                                     if(resoudre(grille, pos+1))
                                                     return 1;
                                                 }
                                             }
                                          
                                             grille[i][j] = 0;
                                             return 0;
                                          }
                                          

                                          • Partager sur Facebook
                                          • Partager sur Twitter

                                          [FAIT][Défis] #3 : Des sudokus en folie !

                                          × Après avoir cliqué sur "Répondre" vous serez invité à vous connecter pour que votre message soit publié.
                                          × Attention, ce sujet est très ancien. Le déterrer n'est pas forcément approprié. Nous te conseillons de créer un nouveau sujet pour poser ta question.
                                          • Editeur
                                          • Markdown