[Segmentation fault] Backtracking sudoku

**Azhatoth** · 24/08/2013, 00h03

Bonjour à vous,

Je fais du C depuis des années par passe-temps, et je voulais me faire un résolveur de sudoku en GUI, donc j'ai commencé par l'algorithme en console, voici le code:

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
// structure.h
// Définit la structure du programme
 
#ifndef STRUCTURE_HEADER
#define STRUCTURE_HEADER
 
 
/*
 * Représente une case de la grille
 */
struct cell {
    int position, value;
};
 
/* 
 * Crée une case et la renvoie
 */
struct cell new_cell( void );
 
/* 
 * Crée et initialise la grille en tant que tableau 2D
 */
struct cell** init_grid( void );
 
/*
 * Affiche la grille dans la console
 */ 
void print_grid( struct cell** grid );
 
/*
 * Libère la mémoire allouée pour la grille
 */
void free_grid( struct cell** grid );
 
#endif

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
// structure.c
 
#include <stdio.h>
#include <stdlib.h>
 
#include "structure.h"
 
struct cell new_cell( void ) {
    static int position = 0;
    struct cell cell;
 
    cell.position = position++;
    cell.value = 0;
    return cell;    
}
 
struct cell** init_grid( void ) {
    int index, row, column;
    struct cell** grid = ( struct cell** )malloc( sizeof( struct cell ) * 4 );
 
    for( index = 0; index < 4; index++ ) 
        grid[ index ] = ( struct cell* )malloc( sizeof( struct cell ) * 4 );
 
    for( row = 0; row < 4; row++ ) {
        for( column = 0; column < 4; column++ )
            grid[ row ][ column ] = new_cell();
    }
 
    return grid;
}
 
void print_grid( struct cell** grid ) {
    int row, column;
 
    for( row = 0; row < 4; row ++ ) {
        for( column = 0; column < 4; column++ )
            printf( "%d ", grid[ row ][ column ].value );
        printf( "\n" );
    }
}
 
void free_grid( struct cell** grid ) {
    int index;
 
    for( index = 0; index < 4; index++ );
        free( grid[ index ] );
 
    free( grid );
}

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
// solving.h
// Contient les algorithmes de résolution
 
#ifndef SOLVING_HEADER
#define SOLVING_HEADER
 
#include "structure.h"
 
/*
 * Détermine si la valeur manque sur la ligne
 */
int missing_in_row( struct cell** grid, int row, int value );
 
/* 
 * Détermine si la valeur manque sur la colonne
 */
int missing_in_column( struct cell** grid, int column, int value );
 
/*
 * Détermine si la valeur manque dans le carré 2x2
 */
int missing_in_square( struct cell** grid, int cell_position, int value );
 
/*
 * Détermine si la grille est potentiellement valide
 */ 
int valid_grid( struct cell**, int cell_position, int value );
 
/*
 * Résoud la grille 
 */ 
int solve( struct cell** grid, int cell_position );
 
#endif

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
// solving.c
 
#include <stdio.h>
#include <stdlib.h>
 
#include "solving.h"
#include "structure.h"
 
int missing_in_row( struct cell** grid, int row, int value ) {
    int column;
 
    for( column = 0; column < 2; column++ ) {
        if( grid[ row ][ column ].value == value )
            return 0;
    }
 
    return 1;
}
 
int missing_in_column( struct cell** grid, int column, int value ) {
    int row;
 
    for( row = 0; row < 2; row++ ) {
        if( grid[ row ][ column ].value == value )
            return 0;
    }
 
    return 1;
}
 
int missing_in_square( struct cell** grid, int cell_position, int value ) {
    int row = cell_position / 4, column = cell_position % 4;
    int origin_row = row - row % 2, origin_column = column - column % 2;
 
    for( row = origin_row; row < origin_row + 2; row++ ) {
        for( column = origin_column; column < origin_column + 2; column++ ) {
            if( grid[ row ][ column ].value == value )
                return 0;
        }
    }
 
    return 1; 
}
 
int valid_grid( struct cell** grid, int cell_position, int value ) {
    return( missing_in_row( grid, cell_position, value ) &&\
            missing_in_column( grid, cell_position, value ) &&\
            missing_in_square( grid, cell_position, value ));
}
 
int solve( struct cell** grid, int cell_position ) {
    int current_value, row, column;
 
    row = cell_position / 4;
    column = cell_position % 4;
 
    if( cell_position == 16 ) 
        return 1;
 
    if( grid[ row ][ column ].value != 0 ) 
        return solve( grid, cell_position + 1 ); 
 
    for( current_value = 1; current_value < 5; current_value++ ) {
        if( valid_grid( grid, cell_position, current_value )) {
            grid[ row ][ column ].value = current_value;
 
            if( solve( grid, cell_position + 1 ))
                return 1;
        }
    }     
 
    grid[ row ][ column ].value = 0;
    return 0;
}

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
 
// sudoku_solver.c
 
 
#include <stdio.h>
#include <stdlib.h>
 
#include "solving.h"
#include "structure.h"
 
int main( void ) {
 
    struct cell** grid = init_grid();
 
    grid[ 0 ][ 0 ].value = 2;
    grid[ 0 ][ 1 ].value = 3;
    grid[ 0 ][ 2 ].value = 4;
 
    grid[ 1 ][ 0 ].value = 1;   
    grid[ 1 ][ 2 ].value = 3;
    grid[ 1 ][ 3 ].value = 2;
 
    grid[ 2 ][ 0 ].value = 4;
    grid[ 2 ][ 1 ].value = 1;
    grid[ 2 ][ 3 ].value = 3;
 
    grid[ 3 ][ 1 ].value = 2;
    grid[ 3 ][ 2 ].value = 1;
    grid[ 3 ][ 3 ].value = 4;
 
    grid[ 0 ][ 3 ].value = 1; /* @@@@@@@@@@@@ */
    grid[ 1 ][ 1 ].value = 4; /* @@@@@@@@@@@@ */
    grid[ 2 ][ 2 ].value = 2; /* @@@@@@@@@@@@ */
    /*grid[ 3 ][ 0 ].value = 3;*/ /* @@@@@@@@@@@@ */
 
    printf( "Grid before solving:\n" );
    print_grid( grid );
 
    solve( grid, 0 );
 
    printf( "\nGrid after solving\n" );
    print_grid( grid );
 
    printf( "\nFreeing grid\n" );
    free_grid( grid );
 
    return 0;
}

Pour vérifier les algorithmes, j'ai commencé avec une grille 2x2, même s'il manque une seule valeur à trouver, j'obtiens une erreur de segmentation, dans la boucle de la fonction solve( struct cell** grid, int cell_position ). J'ai bien l'impression que le plantage se fait toujours sur la 2ème ligne dans cette fonction, quelque soit la taille de la grille.

L'allocation semble correcte étant donné que j'arrive à afficher la grille, j'ai pensé à une explosion de la pile, mais pas avec une seule valeur à chercher, en d'autres termes, je sèche =\

Je compile avec gcc *.c -Wall -ansi -pedantic -o sudoku_solver sur mon netbook archlinux.

PS: Désolé, mais j'ai pris l'habitude de coder en anglais 8D

Invité · 24/08/2013, 00h42

Bonsoir,

Dans la fonction valid_grid(), tu rentres cell_position que tu utilises directement :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
    return( missing_in_row( grid, cell_position, value ) &&\
            missing_in_column( grid, cell_position, value ) &&\
            missing_in_square( grid, cell_position, value ));

ok pour

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

int missing_in_square( struct cell** grid, int cell_position, int value )

mais...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
int missing_in_row( struct cell** grid, int row, int value );
int missing_in_column( struct cell** grid, int column, int value );

**Azhatoth** · 24/08/2013, 14h17

Effectivement... Quel étourdi.

Code C :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
 
int valid_grid( struct cell** grid, int cell_position, int value ) {
    return( missing_in_row( grid, cell_position / 4, value ) &&\
            missing_in_column( grid, cell_position % 4, value ) &&\
            missing_in_square( grid, cell_position, value ));
}

Tout est opérationnel, merci du coup de main, collègue

[Segmentation fault] Backtracking sudoku

C

Discussions similaires

Partager

Partager