C++

Forum

 
Problems with sudoku solver.

R0b0t1 (7)
[CHANGED]

This might be a harder problem than I thought.

(Please be in mind I am compiling this as C, I thought to ask here because it seemed like a place I would likely get help)
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
 
#include <stdio.h>
#include <stdlib.h>

struct t_cell
{
    char val; //value
    char col; //column
    char row; //row
    char sub; //submatrix
} grid[81];

typedef struct t_cell cell;

void init_grid(cell *grid);
void fill_grid(cell *grid, FILE *stream);

int valid_row(cell *grid, int row);
int valid_col(cell *grid, int col);
int valid_sub(cell *grid, int sub);

inline int valid_cell(cell *grid, int pos);

#warning TODO: Program uses recursion. Complex puzzles may crash.
int solve_grid(cell *grid, int pos);


int main()
{
    int i = 0, j = 0;

    puts("Initializing grid constants...");
    init_grid(grid);
    puts("Done.\n");
    puts("Please type the 81 numbers of the sudoku board.\n"
         "Use a dash or 0 as unknown. "
         "Extraneous characters are ignored.\n");
    fill_grid(grid, stdin);

    //3---8--765692-7-3-4-83-621--1-6349----4-25-6--8-7--3247-2-4-6---9657314-1--962---
    puts("\nSolution: ");
    for(; i < 10000; i++)
    {
        solve_grid(grid, i < 81 ? i : i % 81);
        for(j = 0; j < 81; j++) printf("%d", grid[j].val);
        puts("\n");
    }

    for(i = 0; i < 81; i++) printf("%d", grid[i].val);
    return 0;
}

int solve_grid(cell *grid, int pos)
{
    int i = 0;

    if(pos == 81) return 1;
    if(grid[i].val != 0)
        return valid_cell(grid, pos) && solve_grid(grid, pos + 1);

    for(; i < 9; i++)
    {
        grid[i].val = i + 1;

        if(valid_cell(grid, pos) && solve_grid(grid, pos + 1)) return 1;
    }
    if(pos != 0) grid[pos].val = 0;

    return 0;
}

void init_grid(cell *grid)
{
    int i = 0;

    for(; i < 81; i++)
    {
        grid[i].row = (int)i/9;
        grid[i].col = (int)i%9;
        grid[i].sub = (int)(grid[i].row/3)*3+(grid[i].col/3);
    }
}

void fill_grid(cell *grid, FILE *stream)
{
    char s;
    int i = 0;

    for(; i < 80; i++)
    {
        s = fgetc(stream);

        if((s < '0' || s > '9') && s != '-') {i--; continue;}

        if(s == '-') grid[i].val = 0;
        else         grid[i].val = s - '0';
    }
}

int valid_row(cell *grid, int row)
{
    int total = 0, i = 0;

    for(; i < 81; i++)
        if(grid[i].row == row) total += grid[i].val;

    return total == 45;
}

int valid_col(cell *grid, int col)
{
    int total = 0, i = 0;

    for(; i < 81; i++)
        if(grid[i].col == col) total += grid[i].val;

    return total == 45;
}

int valid_sub(cell *grid, int sub)
{
    int total = 0, i = 0;

    for(; i < 81; i++)
        if(grid[i].sub == sub) total += grid[i].val;

    return total == 45;
}

inline int valid_cell(cell *grid, int pos)
{
    return valid_row(grid, grid[pos].row) &&
           valid_col(grid, grid[pos].col) &&
           valid_sub(grid, grid[pos].sub);
}
Last edited on
R0b0t1 (7)
Right, I'm just wondering if it usually takes this long for replies. Anyway, I'm making up one that is a little more (not much) different. I'll be updating it in a while (this post), but I would still like some help ;)
Zaita (2770)
It's the weekend. Most of the experts on this site are available weekdays while they are at work :)
Zaita (2770)
Some problems I can see:

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
 
int main()
{
    int i = 0, j = 0; // Why are these scoped here?

    puts("Initializing grid constants...");
    init_grid(grid);
    puts("Done.\n");
    puts("Please type the 81 numbers of the sudoku board.\n"
         "Use a dash or 0 as unknown. "
         "Extraneous characters are ignored.\n");
    fill_grid(grid, stdin);

        puts("\nSolution: ");
    for(; i < 100; i++) // Should be for (int i = 0; i < 100; i++)
    {
      for(j = 0; j < 81; j++)  // should be for (int j = 0; j < 81; j++)
        printf("%d", grid[j].val);
      
      puts("\n");
    }

    puts("\nSolution: ");
    for(; i < 81; i++)  // you haven't reset i to < 81. should be for(int i = 0; i < 81; i++)
      printf("%d", grid[i].val); 
    return 0;
}


There is no reason for you to scope the int i and int j at function level. You should ideally scope them at loop level. This also prevents problems like you have where you are not reseting the value of your int i before printing the results at the end.

I'd change all of your loops to use for (int i = 0; i < x; i++) etc. This might help solve some problems.

As for style. Personally, I think your code would be easier to read if your kept your statements on a different line than the condition.

e.g
1
2
3
4
5
6
7
8
 
    for(; i < 81; i++)
        if(grid[i].sub == sub) total += grid[i].val;

// is more readable as
    for(int i = 0; i < 81; i++) {
        if(grid[i].sub == sub) 
          total += grid[i].val;
    }


HTH.
R0b0t1 (7)
The reason I do not do as you say with the loop variables is because I as I'm compiling this a C, as I already said. Thank you, though, for telling me how I did not reset the variable to 0, that was an honest mistake.

EDIT: I'm still having problems... I may need to re-think this whole project. What a bummer. (edited code is still at the top)
Last edited on
Zaita (2770)
Ahhh ok, I was unaware that you couldn't do a loop in C like that. I've always used a C++ compiler regardless.

You haven't actually told us what the problem is though?
R0b0t1 (7)
Oh, sorry, update:

I've been testing it with an empty puzzle, to see if it can find the default solution (empty = all 0/all -). It successfully solves the first row, which is just simply 1-9, in order. I have a feeling it fails when it needs to decide, but this may be wrong, so I'd be glad if someone else examined it. (When using a non-default puzzle, nothing happens...)
Zaita (2770)
Ok. Firstly, you should init all of the values to 0 in the init function, otherwise you may end up with invalid squares (as you do).

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
 
void fill_grid(cell *grid, FILE *stream)
{
    char s;
    int i = 0;

    for(; i < 80; i++) // shud be 81, otherwise 1 square is never filled and becomes invalid
    {
        s = fgetc(stream);

        if((s < '0' || s > '9') && s != '-') {i--; continue;} // shud notify user of problem and '0' shudn't be allowed.

        if(s == '-') grid[i].val = 0;
        else         grid[i].val = s - '0';
    }
}
Zaita (2770)
I'd also have a read through
http://www.cplusplus.com/forum/lounge/2299/

where we discuss some methods to solve a sudoku puzzle :)
R0b0t1 (7)
The decrement of i is simply so that it ignores everything that isn't a number. I accept zero because my solver should treat it as undefined. (If you look, it just replaces - with 0 if it encounters one.)


The problem is probably caused, for some reason, when it needs to actually decide... apart from the default. Thank you for the page, I don't really think it will help, but I will look.
Topic archived. No new replies allowed.