«

Hello group,

I've been toying with a simple sudoku[1] solver. I meant for the code to
be short and easy to understand. I figured "brute force is simple" --
who needs finesse, when you've got muscle, right?

[1] http://en.wikipedia.org/wiki/Sudoku

Thus, the strategy is to test every legal "move" and to backtrack when
stuck. A recursive function seemed appropriate. I'd like to hear
comments and suggestions regarding the implementation.

Regards.

#include <stdio.h>

static int grid[9][9];

void read_grid(FILE *fp)
{
int i,j;
for (i=0; i < 9; ++i)
{
char buf[16];
fgets(buf, sizeof buf, fp);
for (j=0; j < 9; ++j)
{
char c = buf[j];
if ('1' <= c && c <= '9') grid[i][j] = c - '0';
}
}
}

void write_grid(void)
{
int i, j;
for (i=0; i < 9; ++i)
{
for (j=0; j < 9; ++j) printf("%d ", grid[i][j]);
putchar('\n');
}
}

int is_legal(int row, int col, int val)
{
int ii = row - row%3;
int jj = col - col%3;
int i, j, k = 0, res = 1;
for (i=0; i < 3; ++i)
for (j=0; j < 3; ++j, ++k)
res = res && (grid[row][k] != val) && (grid[k][col] != val) &&
(grid[ii+i][jj+j] != val);
return res;
}

void solve(int pos)
{
if (pos == 9*9) write_grid();
else
{
int row, col, val;
row = pos / 9;
col = pos % 9;
if (grid[row][col] != 0) solve(pos+1);
else
{
for (val=1; val <= 9; ++val)
{
if (is_legal(row, col, val))
{
grid[row][col] = val;
solve(pos+1);
}
}
grid[row][col] = 0;
}
}
}

int main(void)
{
read_grid(stdin);
solve(0);
return 0;
}

Trent Josephsen wrote:

> Boon wrote:
>
>> I've been toying with a simple sudoku[1] solver. I meant for the code
>> to be short and easy to understand. I figured "brute force is simple"
>> -- who needs finesse, when you've got muscle, right?
>>
>> [1] http://en.wikipedia.org/wiki/Sudoku
>>
>> Thus, the strategy is to test every legal "move" and to backtrack when
>> stuck. A recursive function seemed appropriate. I'd like to hear
>> comments and suggestions regarding the implementation.
>>
>> #include <stdio.h>
>>
>> static int grid[9][9];
>
> Generally you want to avoid global variables, as you probably know.

I didn't want is_legal() and solve() to require an additional parameter.
(I know this is not a very convincing reason.)

>> void read_grid(FILE *fp)
>> {
>> int i,j;
>> for (i=0; i < 9; ++i)
>> {
>> char buf[16];
>> fgets(buf, sizeof buf, fp);
>
> Wait, you're reading 16 characters in 9 times? At most you will have
> eleven (9 characters plus a newline and '\0').

I'm reading *at most* 16 characters (which should never happen).
NB : I didn't focus on the I/O routines, they may have holes.

BTW, in cygwin, the line ends with 0x0d 0x0a 0x00.
<pedantic mode>
Is it possible for a platform to "define" '\n' as a sequence of 10
characters ? Thereby making my buf too small to hold 9 characters,
newline, and nul.
</mode>

>> for (j=0; j < 9; ++j)
>> {
>> char c = buf[j];
>> if ('1' <= c && c <= '9') grid[i][j] = c - '0';
>
> Why bother changing each character (range '1' to '9') to an int (range 1
> to 9)? It isn't really necessary -- you only need to test if two
> characters are equal, not do any kind of math with them. Not with the
> brute force attack, anyway.

You're right. I'd just have to change the for loop in solve() to
for (val='1'; val <= '9'; ++val)

But this wouldn't buy much, either in simplicity or performance, don't
you agree ?

>> void solve(int pos)
>> {
>> if (pos == 9*9) write_grid();
>
> It's probably better to return a code indicating success than to print
> out the result from solve(), in case you want to do something with that
> in main(), like print out a different message depending on the result.

I see your point.

>> else
>> {
>> int row, col, val;
>> row = pos / 9;
>> col = pos % 9;
>> if (grid[row][col] != 0) solve(pos+1);
>> else
>> {
>> for (val=1; val <= 9; ++val)
>> {
>> if (is_legal(row, col, val))
>> {
>> grid[row][col] = val;
>> solve(pos+1);
>
> What if this call to solve() succeeds?

What does it mean for a call to succeed ?

> Does it stop recursing? No, it
> just returns /and continues testing all the other possibilities/. This
> could mean that you get more than one printout if there is more than one
> legal solution. Could be good, could be bad.

This is by design. I want to see whether a problem has multiple solutions.

> I'm really not liking this implementation because there's no way for the
> calling function to know whether the call to solve() succeeded.

By "succeed" do you mean find one solution or find all solutions or
something else ? Failing would mean not finding any solution ?

> In solve() this is bad because when it does succeed the previous level of
> recursion has no way of knowing that and continues searching for
> solutions (which may or may not exist), and prints them out as it comes
> to them. In main() this is bad because you have no way of discerning in
> the code whether the puzzle is solvable or not.

I'll keep your comments in mind.

> It occurs to me that you may want to know all the possible solutions of
> a particular puzzle; in that case you could let each call return the
> number of ways it found to solve the problem. This would need a
> variable that increments each time a solution is found. In any case,
> this function would be much more practical if you could tell whether it
> succeeded or not.

If it were to be used as a library function for example ?

Regards.

In article <48f771c1$0$8536$>,
Boon <root@localhost> wrote:
>Trent Josephsen wrote:
>
>> Boon wrote:

>> Generally you want to avoid global variables, as you probably know.
>
>I didn't want is_legal() and solve() to require an additional parameter.
>(I know this is not a very convincing reason.)

The important thing to remember about global variables is that *every*
global is part of the interface to *every* function in your program.
(Even if it doesn't use it now, there's nothing to stop it from
deciding to use it at some point in the future.)

If the program is small and self-contained, and the information you're
making global is something that the whole program needs, this will
probably be what you want. But small and self-contained programs have
an annoying habit of not wanting to stay small and self-contained.
Sooner or later you'll find yourself wishing that a program that was
written that way had "all the stuff everybody wants" arguments to its
functions so you could put it in a larger program as a module and use
that module for two things at once. So if you're going to use global
variables, at least keep that in mind, and make it easy to convert it
into that form later.

When I use globals, I like to wrap them all up in a small number of
structs. This has two benefits:
(1) It makes it easier to transform globals into pass-around-to-
everybody non-global data; just have everything that needs it (or,
transitively, calls something that needs it) take a pointer to a
struct of the appropriate type. Finding functions that need it and
converting them to use the non-global form is easy - just do a
search for the global struct name, and make the appropriate changes
everywhere it shows up.
(2) It makes it obvious everywhere you use a global variable that this
is a global you're using. That gives you clues about where to look
for more information about it, and reminds you to be careful about
changes there that may affect other chunks of code in completely
different places.




>BTW, in cygwin, the line ends with 0x0d 0x0a 0x00.
><pedantic mode>
>Is it possible for a platform to "define" '\n' as a sequence of 10
>characters ? Thereby making my buf too small to hold 9 characters,
>newline, and nul.
></mode>

No.
Well, maybe, but not in a way that affects you.
The platform is allowed to define "end of line in text files" however
it wants; but if you open the file in text mode, it's required to
convert each line from whatever the "native" format is into "sequence
of characters followed by '\n'", which is the internal representation
that a C program uses.

(Note that, on the other side of the stdio library, newline doesn't
even need to be represented by a (sequence of) character(s);
f'rexample, an implementation can use fixed-length space-padded lines,
and that implementation's stdio library would need to read the line,
trim trailing space padding, and insert '\n' between lines before
passing the data on to a C program.)

(This means that if you haven't opened the file in binary mode and
cygwin is giving you "\r\n" at the end of your lines, then either it's
failing to do end-of-line translation properly or it's defining
end-of-line differently than the rest of the system it lives in and
refusing to play nicely.)



dave

--
Dave Vandervies dj3vande at eskimo dot com
I'm probably getting senile, but I increasingly tend to regard C as a better
C++, in the spirit of Hoare's remark about Algol 60 being an improvement on
nearly all its successors. --Andrew Simmons in comp.lang.c

Trent Josephsen wrote:

> Boon wrote:

> > #include <stdio.h>
> >
> > static int grid[9][9];
>
> Generally you want to avoid global variables, as you probably know.

I disagree. This is a perfect usage for file scope (NOT global) data
constructs. I've been using that sort of thing for my game programming
some lately. It's a sort of data encapsulation model.




Brian

"Default User" <> writes:

> Trent Josephsen wrote:
>
>> Boon wrote:
>
>> > #include <stdio.h>
>> >
>> > static int grid[9][9];
>>
>> Generally you want to avoid global variables, as you probably know.
>
> I disagree. This is a perfect usage for file scope (NOT global) data
> constructs. I've been using that sort of thing for my game programming
> some lately. It's a sort of data encapsulation model.
>
>
>
>
> Brian

Frankly I think that is nonsense.

If efficiency was the issue he could simply malloc one bunch of result
containers or use in function statics to effectively hide things.

And file scope IS global (as anyone without a rod up their arse knows
it) since anyone can declare an extern and then see it.

On Oct 16, 7:08*am, Boon <root@localhost> wrote:
> Hello group,
>
> I've been toying with a simple sudoku[1] solver. I meant for the code to
> be short and easy to understand. I figured "brute force is simple" --
> who needs finesse, when you've got muscle, right?
>
> [1]http://en.wikipedia.org/wiki/Sudoku
>
> Thus, the strategy is to test every legal "move" and to backtrack when
> stuck. A recursive function seemed appropriate. I'd like to hear
> comments and suggestions regarding the implementation.
>
> Regards.
>
> #include <stdio.h>
>
> static int grid[9][9];
>
> void read_grid(FILE *fp)
> {
> * *int i,j;
> * *for (i=0; i < 9; ++i)
> * *{
> * * *char buf[16];
> * * *fgets(buf, sizeof buf, fp);
> * * *for (j=0; j < 9; ++j)
> * * *{
> * * * *char c = buf[j];
> * * * *if ('1' <= c && c <= '9') grid[i][j] = c - '0';
> * * *}
> * *}
>
> }
>
> void write_grid(void)
> {
> * *int i, j;
> * *for (i=0; i < 9; ++i)
> * *{
> * * *for (j=0; j < 9; ++j) printf("%d ", grid[i][j]);
> * * *putchar('\n');
> * *}
>
> }
>
> int is_legal(int row, int col, int val)
> {
> * *int ii = row - row%3;
> * *int jj = col - col%3;
> * *int i, j, k = 0, res = 1;
> * *for (i=0; i < 3; ++i)
> * * *for (j=0; j < 3; ++j, ++k)
> * * * *res = res && (grid[row][k] != val) && (grid[k][col] != val) &&
> (grid[ii+i][jj+j] != val);
> * *return res;
>
> }
>
> void solve(int pos)
> {
> * *if (pos == 9*9) write_grid();
> * *else
> * *{
> * * *int row, col, val;
> * * *row = pos / 9;
> * * *col = pos % 9;
> * * *if (grid[row][col] != 0) solve(pos+1);
> * * *else
> * * *{
> * * * *for (val=1; val <= 9; ++val)
> * * * *{
> * * * * *if (is_legal(row, col, val))
> * * * * *{
> * * * * * *grid[row][col] = val;
> * * * * * *solve(pos+1);
> * * * * *}
> * * * *}
> * * * *grid[row][col] = 0;
> * * *}
> * *}
>
> }
>
> int main(void)
> {
> * *read_grid(stdin);
> * *solve(0);
> * *return 0;
>
>
>
> }

Compare your method with this:

/* Program resolution of sudoku grids by backtracking,
with propagation of the constraints and variable
selection the most constrained (mrv: minimum remaining value).
The file is read from stdin. Try for example with:

53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79

Bernard Helmstetter, 2006
Translated to English by Dann Corbit
*/

#include <stdlib.h>
#include <stdio.h>
#include <string.h>

#define UNKNOWN 0

int grid[81];
int domain[81][10]; /* The list of possibilities */
int domain_cuts[81]; /* domain cuts */
int computer_nodes;

/* Read the grid from standard input, using the characters '0'-'9' and
'.' */
void read_grid()
{
int k = 0;

while (k < 81) {
char c = getchar();
if (c >= '1' && c <= '9')
grid[k++] = c - '0';
else if (c == '.')
grid[k++] = UNKNOWN;
else if (c == EOF) {
fprintf(stderr, "Bad format reading grid\n");
exit(1);
}
}
}

/* print the grid to standard output */
void print_grid()
{
int c,
l;

for (l = 0; l < 9; l++) {
for (c = 0; c < 9; c++) {
int k = l * 9 + c;
if (grid[k] == UNKNOWN)
printf(".");
else
printf("%c", grid[k] + '0');
}
putchar('\n');
}
putchar('\n');
}

/* remove all the values of the domains that are incompatible for case
'i' */
void restrict_domain(int i)
{
int l = i / 9,
c = i % 9;
int lb = l / 3;
int cb = c / 3;
int l2,
c2,
lr2,
cr2,
i2;

/* column constraints for case 'i' */
for (l2 = 0; l2 < 9; l2++) {
i2 = l2 * 9 + c;
if (domain[i2][grid[i]]) {
domain[i2][grid[i]] = 0;
domain_cuts[i2]--;
}
}

/* row constraints for case 'i' */
for (c2 = 0; c2 < 9; c2++) {
i2 = l * 9 + c2;
if (domain[i2][grid[i]]) {
domain[i2][grid[i]] = 0;
domain_cuts[i2]--;
}
}

/* verify the region containing case 'i' */
for (lr2 = 0; lr2 < 3; lr2++)
for (cr2 = 0; cr2 < 3; cr2++) {
i2 = (lb * 3 + lr2) * 9 + (cb * 3 + cr2);
if (domain[i2][grid[i]]) {
domain[i2][grid[i]] = 0;
domain_cuts[i2]--;
}
}
}

/* using the initial state, initialize the domain table */
void init_domain()
{
int i,
v;

for (i = 0; i < 81; i++) {
domain_cuts[i] = 9;
for (v = 1; v <= 9; v++)
domain[i][v] = 1;
}

/* restrict the domain by backtracking */
for (i = 0; i < 81; i++)
if (grid[i] != UNKNOWN)
restrict_domain(i);
}

void backtrack()
{
int i,
i_min = -1;
int cuts_min = 10;
int domain2[81][10];
int domain_cuts2[81];

/* look for a smaller domain */
for (i = 0; i < 81; i++) {
if (grid[i] == UNKNOWN && domain_cuts[i] < cuts_min) {
i_min = i;
cuts_min = domain_cuts[i];
}
}

/* Are all UNKNOWN fields resolved? */
if (i_min == -1) {
print_grid(); /* solution found */
return;
}
computer_nodes++;
for (grid[i_min] = 1; grid[i_min] <= 9; grid[i_min]++) {
if (domain[i_min][grid[i_min]] == 0)
continue;
/* Save the state between recursive calls */
memcpy(domain2, domain, sizeof(domain));
memcpy(domain_cuts2, domain_cuts, sizeof(domain_cuts));
restrict_domain(i_min);
backtrack();
memcpy(domain, domain2, sizeof(domain));
memcpy(domain_cuts, domain_cuts2, sizeof(domain_cuts));
}
grid[i_min] = UNKNOWN;
}

int main()
{
read_grid();
print_grid();
init_domain();
backtrack(0);
printf("%d nodes searched\n", computer_nodes);
return 0;
}

Richard<> writes:

> "Default User" <> writes:
>
>> Trent Josephsen wrote:
>>
>>> Boon wrote:
>>
>>> > #include <stdio.h>
>>> >
>>> > static int grid[9][9];
>>>
>>> Generally you want to avoid global variables, as you probably know.
>>
>> I disagree. This is a perfect usage for file scope (NOT global) data
>> constructs. I've been using that sort of thing for my game programming
>> some lately. It's a sort of data encapsulation model.
<snip>

> Frankly I think that is nonsense.
<snip>
> And file scope IS global (as anyone without a rod up their arse knows
> it) since anyone can declare an extern and then see it.

No. No matter how rude you are, you can't alter the fact that, in C,
scope and linkage are disconnected. The term "global" (usually)
conflates them.

Brian talks about encapsulation and non-global file scope data so I
conclude he is talking about static objects declared at file scope
which can not be seen using an "extern".

Even if this not what he meant, file scope is /not/ global (rod or no
rod).

--
Ben.

Ben Bacarisse <> writes:

> Richard<> writes:
>
>> "Default User" <> writes:
>>
>>> Trent Josephsen wrote:
>>>
>>>> Boon wrote:
>>>
>>>> > #include <stdio.h>
>>>> >
>>>> > static int grid[9][9];
>>>>
>>>> Generally you want to avoid global variables, as you probably know.
>>>
>>> I disagree. This is a perfect usage for file scope (NOT global) data
>>> constructs. I've been using that sort of thing for my game programming
>>> some lately. It's a sort of data encapsulation model.
> <snip>
>
>> Frankly I think that is nonsense.
> <snip>
>> And file scope IS global (as anyone without a rod up their arse knows
>> it) since anyone can declare an extern and then see it.
>
> No. No matter how rude you are, you can't alter the fact that, in C,
> scope and linkage are disconnected. The term "global" (usually)
> conflates them.

No. Forget linkaqe. We do not discuss Linkage. A file variable is
available globally to the program which is being compiled. You can play
word games if you wish. There was no mention of static.

>
> Brian talks about encapsulation and non-global file scope data so I
> conclude he is talking about static objects declared at file scope
> which can not be seen using an "extern".

You assume. But he did not mention static. I did. And there is no need
for them to file scope either. This was my point.

Without the mention of static then it can possibly be deduced that he
was doing a Heathfield and suggesting no such thing as Globals in C.

>
> Even if this not what he meant, file scope is /not/ global (rod or no
> rod).

Where do YOU declare your globals Ben? In something that is NOT a
file?

What part of you can access via an extern is wrong? In the obvious and
non clever understanding of what a global is?

Richard wrote:
> "Default User" <> writes:
>
> > Trent Josephsen wrote:
> >
> >> Boon wrote:
> >
> >> > #include <stdio.h>
> >> >
> >> > static int grid[9][9];
> >>
> >> Generally you want to avoid global variables, as you probably know.
> >
> > I disagree. This is a perfect usage for file scope (NOT global) data
> > constructs. I've been using that sort of thing for my game programming
> > some lately. It's a sort of data encapsulation model.
> >
> >
> >
> >
> > Brian
>
> Frankly I think that is nonsense.
>
> If efficiency was the issue he could simply malloc one bunch of result
> containers or use in function statics to effectively hide things.
>
> And file scope IS global (as anyone without a rod up their arse knows
>
> it) since anyone can declare an extern and then see it.

That statement implies that you're unfamiliar with the meaning of
'static' when applied at file scope. Contrary to what you're
suggesting, such declarations have internal linkage, not external
linkage. As a result, declaring the same identifier with external
linkage in a different translation unit will not make this definition
visible in that translation unit. You need to understand the
distinction between scope and linkage.

This is not a pedantic quibble, since 'grid' was in fact declared with
the keyword 'static'.

writes:

> Richard wrote:
>> "Default User" <> writes:
>>
>> > Trent Josephsen wrote:
>> >
>> >> Boon wrote:
>> >
>> >> > #include <stdio.h>
>> >> >
>> >> > static int grid[9][9];
>> >>
>> >> Generally you want to avoid global variables, as you probably know.
>> >
>> > I disagree. This is a perfect usage for file scope (NOT global) data
>> > constructs. I've been using that sort of thing for my game programming
>> > some lately. It's a sort of data encapsulation model.
>> >
>> >
>> >
>> >
>> > Brian
>>
>> Frankly I think that is nonsense.
>>
>> If efficiency was the issue he could simply malloc one bunch of result
>> containers or use in function statics to effectively hide things.
>>
>> And file scope IS global (as anyone without a rod up their arse knows
>>
>> it) since anyone can declare an extern and then see it.
>
> That statement implies that you're unfamiliar with the meaning of
> 'static' when applied at file scope. Contrary to what you're

No one mentioned static. I mentioned static.

> suggesting, such declarations have internal linkage, not external
> linkage. As a result, declaring the same identifier with external
> linkage in a different translation unit will not make this definition
> visible in that translation unit. You need to understand the
> distinction between scope and linkage.

I dont know where you got that impression of my meaning. I suppose its
that word "declare" again. I should have posted an example.

So you are telling me that "extern int c" in a header declares a new
object? Wow. My C is rusty ....

>
> This is not a pedantic quibble, since 'grid' was in fact declared with
> the keyword 'static'.

My point is valid. He is as well to maintain internal statics "in
function" or a malloc result set..

Littering stuff at file scope is poor practice in most cases.