[Segmentation fault] Backtracking sudoku
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:
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:
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:
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:
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:
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
