Yet another brute force sudoku solver

[Boon]

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]

Boon 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];

Generally you want to avoid global variables, as you probably know.

>
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').

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.

}
}
}

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();

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.

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? 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.

}
}
grid[row][col] = 0;
}
}

I'm really not liking this implementation because there's no way for the
calling function to know whether the call to solve() succeeded. 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.

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.

}

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

[Boon]

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.

[dj3vande]

In article <48**********************@news.free.fr>,
Boon <root@localhostwrote:

>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

[Default User]

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

[user923005]

On Oct 16, 7:08*am, Boon <root@localhostwrote:

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]

"Default User" <de***********@yahoo.comwrites:

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.

[Harald van =?UTF-8?b?RMSzaw==?=]

On Thu, 16 Oct 2008 22:15:35 +0200, Richard wrote:

>>Boon wrote:
static int grid[9][9];

And file scope IS global [...]
since anyone can declare an extern and then see it.

Not if the definition includes static, as this one does.

[Ben Bacarisse]

Richard<rg****@gmail.comwrites:

"Default User" <de***********@yahoo.comwrites:

>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.

[Richard]

Ben Bacarisse <be********@bsb.me.ukwrites:

Richard<rg****@gmail.comwrites:

>"Default User" <de***********@yahoo.comwrites:

>>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?

[jameskuyper]

Richard wrote:

"Default User" <de***********@yahoo.comwrites:

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'.

[Richard]

ja*********@verizon.net writes:

Richard wrote:

>"Default User" <de***********@yahoo.comwrites:

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.

[jameskuyper]

Richard wrote:

Ben Bacarisse <be********@bsb.me.ukwrites:

Richard<rg****@gmail.comwrites:

"Default User" <de***********@yahoo.comwrites:
Trent Josephsen wrote:
Boon wrote:

....

You appear to have found the "static" keyword in the following
declaration invisible:

>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. ...

Who's "we", kemo-sabe? I discuss linkage when it's relevant, as it is
to the question of whether or not something is global.

... A file variable is
available globally to the program which is being compiled.

Unless explicitly defined as static, in which case it has only
internal linkage, and cannot be accessed by name from any translation
unit of the program other than the one in which it was so defined.

... You can play
word games if you wish. There was no mention of static.

The declaration under discussion, which you yourself have quoted, says

static int grid[9][9];

That looks like a mention of "static" to me.

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.

The relevant use of the word "static" was the one written by Boon in
the very first message of this discussion. Not by you, and not by
Brian.

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.

Since Boon did mention static, you can drop that line of thought.

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?

He's not saying that globals don't have file scope. He's saying that
not all things declared with file scope are globals. Some things
declared at file scope have internal linkage, and therefore cannot, by
any reasonable definition of the term, be called globals. This doesn't
have anything to do with Richard Heathfield's definition of global; I
am in agreement with you that his definition is an unreasonably strict
definition.

What part of you can access via an extern is wrong?

The part where an extern declaration in one translation unit will NOT
make visible an object (or function) declared 'static' at file scope
in a different translation unit.

[jameskuyper]

Richard wrote:

ja*********@verizon.net writes:

Richard wrote:

"Default User" <de***********@yahoo.comwrites:

Trent Josephsen wrote:

Boon wrote:

#include <stdio.h>

The presence of the word "static" on the following line seems to
somehow have repeatedly escaped your attention:

static int grid[9][9];

....

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.

I bed to differ. In the section that you yourself have quoted above,
Boon definitely mentioned 'static', and did so long before you did.

<nit-pick>A strict interpretation of your last two sentences leads to
the deduction that you are "no one". I think you meant to say "no one
else". </nit-pick>

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.

No, it's not your use of declare (unless you actually meant "define"
in the following citation, in which case the sentence becomes
irrelevant to the subject under discussion, since the relevant object
was defined with 'static', not 'extern'). The problem is your use of
extern in the following:

it) since anyone can declare an extern and then see it.

That's true only of identifiers with external linkage, not identifiers
with internal linkage; file scope alone is not sufficient to make that
true.

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

No, I'm telling you that 'static int c' declared in one translation
unit and 'extern int c' declared in a different translation unit
cannot both refer to the same object, not even if the static
declaration occurs at file scope. The object referred to by the
'extern' declaration must also be defined somewhere, not merely
declared, but the 'static' declaration cannot provide that definition.
If you were not aware of this fact, as seems to be the case, then your
C is indeed 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.

I would generally agree, for objects with external linkage. I think
that file scope objects with internal linkage can be good practice in
many cases. Your statements to the contrary notwithstanding, only
functions in the same translation unit can see them, but all of those
functions can see them, which can be a useful combination in some
contexts. I've used such objects to coordinate the behavior of a call-
back function with the behavior of another function; those were the
only two functions which knew about the file-scope variable that
shared the same translation unit with them; it was invisible to all
the other translation units in the program.

[pete]

Ben Bacarisse wrote:

No matter how rude you are, you can't alter the fact that, in C,
scope and linkage are disconnected.

"Scope" is what "linkage" is all about.

The standard defines "linkage" in terms of "scope".

ISO/IEC 9899

6.2.2 Linkages of identifiers

1 An identifier declared in different scopes or in the same scope
more than once can be made to refer to the same object or function
by a process called linkage.

--
pete

[Default User]

Ben Bacarisse wrote:

Richard<rg****@gmail.comwrites:

"Default User" <de***********@yahoo.comwrites:

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.

Riley's a troll and an idiot, so no surprises there. And of course,
I've had him killfiled for a long time. I'm not sure he believes it,
but it's true.

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".

Yeppers. I've been encapsulating some of the operations through the use
of file-scope static data, static utility functions, and a small set of
public interface functions. In some ways it's like OO programming writ
large. In other ways it's very different.

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

I think I didn't express my initial thoughts well enough if you're
unsure. I can't draw any conclusions from Riley being confused.


Brian

[Ben Bacarisse]

pete <pf*****@mindspring.comwrites:

Ben Bacarisse wrote:

>No matter how rude you are, you can't alter the fact that, in C,
scope and linkage are disconnected.

"Scope" is what "linkage" is all about.

Yes, "disconnected" is too strong. Orthogonal? Too technical (and
the technical means has to be bent for it to fit). Independent?
Probably also too strong.

The trouble with the word "global" is that it conflates two ideas that
need to be taken separately to understand what is happening in C
programs.

--
Ben.

[Ben Bacarisse]

"Default User" <de***********@yahoo.comwrites:

Ben Bacarisse wrote:

<snip>

>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".

Yeppers. I've been encapsulating some of the operations through the use
of file-scope static data, static utility functions, and a small set of
public interface functions. In some ways it's like OO programming writ
large. In other ways it's very different.

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

I think I didn't express my initial thoughts well enough if you're
unsure.

No, I was clear about what you meant. I simply wanted to cover myself
to cut down on the number of posts exchanged since I knew Just Plain
Richard would accuse me of making unwarranted assumptions.

--
Ben.

[Trent Josephsen]

Boon wrote:

Trent Josephsen wrote:

>Boon wrote:

>>>
static int grid[9][9];

Generally you want to avoid global variables, as you probably know.

Okay, let me say here that I now regret that I used the word "global".

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

Entirely your choice. You're the author! :)

>

<snip>

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 ?

Granted. But I was thinking that in the future you might run across
sudoku puzzles that use the characters 'A' through 'I' (I have seen such
puzzles) and this would make it easier to extend.

<snip>

>What if this call to solve() succeeds?

What does it mean for a call to succeed ?

Where "success" is defined as "finding a solution."

>

>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.

Ah.

>

>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 ?

Yes. Also if you wanted to implement it such that it would only tell
you whether a puzzle was solvable (but wanted to have the fun of solving
it yourself).

Printing out each solution as you come to it is really the easiest way
to do this given what you have said about what you want it to do. That
said, there are other possibilities. Consider a function which returns
when it finds a solution but retains its state (via internal static
variables) so that it can continue looking for different solutions on
successive calls.

On second thought, that would probably be tricky to implement and make
it harder to extend. In fact, I'm probably getting in over my head
already, so I'll stop offering suggestions at this point.

Trent

[Boon]

Hello Dann,

user923005 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.

[snip my implementation]

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
*/

[snip Bernard's implementation]

Thanks Dann. In my opinion, Bernard's method is more complex than mine,
but it is very likely faster. Were there specific differences you wanted
to highlight ?

Regards.

[Nick Keighley]

On 16 Oct, 22:11, Richard<[e-mail]:

Ben Bacarisse <[e-mail]:

Richard<[e-mail]:

"Default User" <[e-mail]:
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.

Frankly I think that is nonsense.

And file scope IS global <snip unnecessary rudenesssince 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.

ah, Richard <whoeverhas been at Troll Pills again!

No. Forget linkaqe. We do not discuss Linkage.

yes we do!

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.

it is available at file scope. It could be said to be available
to the Tranaslation Unit but it ain't available to the program!

The trouble with the word "global" is it needs some context.
I used to use it situations like this

char *base_addr;

/* lots of code */

char read_dma_setting (void)
{return *(base_addr + DMA_SETTING_OFFSET);}

/* more code */
base_addr = 0x80001234;
rds = read_dma_setting();

[I *really* don't write code like that anymore!]

I'd describe base_addr as a "global parameter" of
read_dma_setting(). The term "global" would float around as well.
I found it ambiguous and stopped using the term. Some people
used to global to mean visible throughout the program.
Some just meant file visible. Its a confusing term.
Nowadays I use it as a pejorative term meaning "having too
much scope". "This program would be more robust if it used
less globals".

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.

pretty reasonable assumption. Note "file scope"

But he did not mention static.

static int grid[9][9];

(I'm not sure if that was what "Brian" posted as he's been snipped

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.

There *is* no such thing as a global in C. See the standard.

Even if this not what he meant, file scope is /not/ global

why not if you must use the word it's a reasonable usage.
If you mean "global" to ba an alias for "external linkage"
why not use the term?

<snip rudeness>

<snip stuff>
--
Nick Keighley

[Nick Keighley]

On 16 Oct, 22:21, Richard<[e-mail]:

Littering stuff at file scope is poor practice in most cases

depends what "littering" means. I submit most well written
non-trivial C programs have some file scope data.

Good way to start another argument anyway...

--
Nick Keighley

[jameskuyper]

Richard wrote:

ja*********@verizon.net writes:

Richard wrote:

"Default User" <de***********@yahoo.comwrites:
Trent Josephsen wrote:
Boon wrote:
#include <stdio.h>

static int grid[9][9];

....

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.

....

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.

Perhaps you should. I don't know how to make a file scope identifier
with internal linkage (such as the array 'grid' defined above) visible
from another translation unit by "declar[ing] an extern", unless the
identifier with external linkage refers to something different from
what the identifier with internal linkage refers to. If you know how
to do this, could you give us an example?

[Ben Bacarisse]

Nick Keighley <ni******************@hotmail.comwrites:

>Ben Bacarisse <[e-mail]:

<snip>

Even if this not what he meant, file scope is /not/ global

why not if you must use the word it's a reasonable usage.
If you mean "global" to ba an alias for "external linkage"
why not use the term?

I have no problem with people using the term, if they take care with
it. My remarks were about Just Plain Richard's suggestion that "file
scope is global". That is just plain wrong.

In addition, care is needed when talking to people who only know
languages where "global" is a scope. If we take the usual "global
variable = object with external linkage" meaning then C has the odd
property (odd as far as such people are concerned) that the name of a
"global variable" might be "in scope" only inside two tiny functions
out of a million lines of code.

--
Ben.

[Default User]

ja*********@verizon.net wrote:

Richard wrote:

[blither blather]

If you know how
to do this, could you give us an example?

He really is a troll. He's stringing you along for the response.

Brian

[user923005]

On Oct 20, 12:36*am, Boon <root@localhostwrote:

Hello Dann,

user923005 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.

[snip my implementation]

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
*/

[snip Bernard's implementation]

Thanks Dann. In my opinion, Bernard's method is more complex than mine,
but it is very likely faster. Were there specific differences you wanted
to highlight ?

It is many orders of magnitude faster. While it is a little more
complex, it is simple enough to understand.
AI problems are very interesting to me. I thought you might enjoy
looking at a highly efficient solution.

[Default User]

user923005 wrote:

On Oct 20, 12:36*am, Boon <root@localhostwrote:

Thanks Dann. In my opinion, Bernard's method is more complex than
mine, but it is very likely faster. Were there specific differences
you wanted to highlight ?

It is many orders of magnitude faster. While it is a little more
complex, it is simple enough to understand.
AI problems are very interesting to me. I thought you might enjoy
looking at a highly efficient solution.

I've been working on a solver that uses no brute force (that is, no
test and backtrack) methods. I have it now as smart as I am in solving
them. I have to increase my own understanding of things like "X-wing"
and other more advanced methods so I can create the algorithms.


Brian

[Giorgos Keramidas]

On Mon, 20 Oct 2008 04:51:34 -0700 (PDT), ja*********@verizon.net wrote:

Richard wrote:

>ja*********@verizon.net writes:

Richard wrote:
"Default User" <de***********@yahoo.comwrites:
Trent Josephsen wrote:
Boon wrote:
#include <stdio.h>

static int grid[9][9];

...

>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.

...

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.

Perhaps you should. I don't know how to make a file scope identifier
with internal linkage (such as the array 'grid' defined above) visible
from another translation unit by "declar[ing] an extern", unless the
identifier with external linkage refers to something different from
what the identifier with internal linkage refers to. If you know how
to do this, could you give us an example?

You can define an object with internal linkage in one file, and a
function with external linkage that returns a pointer to that object.
Then other translation units can call the function to obtain the runtime
location of the object and use the pointer to access it.

[Richard Heathfield]

Giorgos Keramidas said:

On Mon, 20 Oct 2008 04:51:34 -0700 (PDT), ja*********@verizon.net wrote:

>Richard wrote:

>>ja*********@verizon.net writes:
Richard wrote:
"Default User" <de***********@yahoo.comwrites:
Trent Josephsen wrote:
Boon wrote:
#include <stdio.h>

static int grid[9][9];

...

>>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.

...

>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.

Perhaps you should. I don't know how to make a file scope identifier
with internal linkage (such as the array 'grid' defined above) visible
from another translation unit by "declar[ing] an extern", unless the
identifier with external linkage refers to something different from
what the identifier with internal linkage refers to. If you know how
to do this, could you give us an example?

You can define an object with internal linkage in one file, and a
function with external linkage that returns a pointer to that object.
Then other translation units can call the function to obtain the runtime
location of the object and use the pointer to access it.

Yes, and that would provide access to the object in question, but not using
the *identifier* in question. In the case in point, the identifier,
'grid', is at file scope (which means it can be seen throughout the rest
of the translation unit in which it appears) but is static (which means it
can't be seen from anywhere else). James's point is that just adding:

extern int grid[9][9];

to another translation unit will *not* make the original identifier visible
in that other translation unit.

--
Richard Heathfield <http://www.cpax.org.uk>
Email: -http://www. +rjh@
Google users: <http://www.cpax.org.uk/prg/writings/googly.php>
"Usenet is a strange place" - dmr 29 July 1999

[Giorgos Keramidas]

On Tue, 21 Oct 2008 02:09:26 +0000, Richard Heathfield <rj*@see.sig.invalidwrote:

>Giorgos Keramidas said:

>>On Mon, 20 Oct 2008 04:51:34 -0700 (PDT), ja*********@verizon.net wrote:

>>Perhaps you should. I don't know how to make a file scope identifier
with internal linkage (such as the array 'grid' defined above) visible
from another translation unit by "declar[ing] an extern", unless the
identifier with external linkage refers to something different from
what the identifier with internal linkage refers to. If you know how
to do this, could you give us an example?

You can define an object with internal linkage in one file, and a
function with external linkage that returns a pointer to that object.
Then other translation units can call the function to obtain the
runtime location of the object and use the pointer to access it.

Yes, and that would provide access to the object in question, but not
using the *identifier* in question.

Of course. I should have read more carefully what James wrote, thanks :)

[Boon]

user923005 wrote:

Boon wrote:

>In my opinion, Bernard's method is more complex than mine, but it
is very likely faster. Were there specific differences you wanted
to highlight ?

It is many orders of magnitude faster.

Many orders of magnitude ?
So, at least 100 times faster, perhaps even 1000 times faster ?
Can you see that just by looking at the source code (static analysis) or
did you run both programs ?
Efficiency was not my main concern, but I will try to optimize my
implementation ;-)

I've only input 7 grids so far, below is the "hardest" I've seen.

.....968..
...1....7.
..2......3
..3...8..6
...4.2.3..
6..5...8.
9......5.
..7....1..
...594....

While it is a little more complex, it is simple enough to understand.

I will print it out, and study it. Thanks again for sharing.

AI problems are very interesting to me. I thought you might enjoy
looking at a highly efficient solution.

How does one properly benchmark a program that runs in less than 50 ms ?

Regards.

[James Kuyper]

Boon wrote:
....

How does one properly benchmark a program that runs in less than 50 ms ?

By making many repeated calls to the function, and dividing the total
amount of time spent by the number of calls. Whenever you do this, you
have to be careful to avoid possible optimization, which might cause the
function to be called only once to produce a result that it returns many
times. For a function as complicated as yours, that's less likely to be
a problem.

For really fast algorithms, to get accurate results you should,
properly, subtract the time spent performing any empty loop the same
number of times, before doing the division. Unfortunately, that's not
easy to do, because it is extremely likely that your compiler will
optimize away an empty loop.

[user923005]

On Oct 23, 3:25*am, Boon <root@localhostwrote:

user923005 wrote:

Boon wrote:

In my opinion, Bernard's method is more complex than mine, but it
is very likely faster. Were there specific differences you wanted
to highlight ?

It is many orders of magnitude faster.

Many orders of magnitude ?
So, at least 100 times faster, perhaps even 1000 times faster ?
Can you see that just by looking at the source code (static analysis) or
did you run both programs ?
Efficiency was not my main concern, but I will try to optimize my
implementation ;-)

I've only input 7 grids so far, below is the "hardest" I've seen.

....968..
..1....7.
.2......3
.3...8..6
..4.2.3..
6..5...8.
9......5.
.7....1..
..594....

While it is a little more complex, it is simple enough to understand.

I will print it out, and study it. Thanks again for sharing.

AI problems are very interesting to me. *I thought you might enjoy
looking at a highly efficient solution.

How does one properly benchmark a program that runs in less than 50 ms ?

Count the nodes.

For instance, with this one:
...1.8.6.4
..376.....
5........
......5...
...6.1.8..
....4.....
.........3
......752.
8.2.9.7..

Your program takes 789,878 nodes and the fast program takes 11,187
nodes. That's 70x faster, so a less than a factor of 100.

I have an interest in AI, and so these sorts of things are interesting
to me.

[user923005]

On Oct 23, 3:01*pm, user923005 <[e-mail]:

On Oct 23, 3:25*am, Boon <root@localhostwrote:

user923005 wrote:

Boon wrote:

>In my opinion, Bernard's method is more complex than mine, but it
>is very likely faster. Were there specific differences you wanted
>to highlight ?

It is many orders of magnitude faster.

Many orders of magnitude ?
So, at least 100 times faster, perhaps even 1000 times faster ?
Can you see that just by looking at the source code (static analysis) or
did you run both programs ?
Efficiency was not my main concern, but I will try to optimize my
implementation ;-)

I've only input 7 grids so far, below is the "hardest" I've seen.

....968..
..1....7.
.2......3
.3...8..6
..4.2.3..
6..5...8.
9......5.
.7....1..
..594....

While it is a little more complex, it is simple enough to understand.

I will print it out, and study it. Thanks again for sharing.

AI problems are very interesting to me. *I thought you might enjoy
looking at a highly efficient solution.

How does one properly benchmark a program that runs in less than 50 ms ?

Count the nodes.

For instance, with this one:
..1.8.6.4
.376.....
5........
.....5...
..6.1.8..
...4.....
........3
.....752.
8.2.9.7..

Your program takes 789,878 nodes and the fast program takes 11,187
nodes. *That's 70x faster, so a less than a factor of 100.

I have an interest in AI, and so these sorts of things are interesting
to me.

C:\tmp\sudoku>fast < sudoku7.txt
.....968..
...1....7.
..2......3
..3...8..6
...4.2.3..
6..5...8.
9......5.
..7....1..
...594....

453796821
861234975
729185463
132478596
584629317
697513284
948361752
376852149
215947638

2081 nodes searched

C:\tmp\sudoku>slow < sudoku7.txt
.....968..
...1....7.
..2......3
..3...8..6
...4.2.3..
6..5...8.
9......5.
..7....1..
...594....

453796821
861234975
729185463
132478596
584629317
697513284
948361752
376852149
215947638

80992 noeuds cherches

The ratio for your quoted problem (which is much easier than the one
that I quoted) is 39:1 slower

I guess that if we find a really hard one, the ratio will be even more
profound.

[Moi]

On Thu, 23 Oct 2008 15:06:43 -0700, user923005 wrote:

On Oct 23, 3:01Â*pm, user923005 <[e-mail]:

>On Oct 23, 3:25Â*am, Boon <root@localhostwrote:

user923005 wrote:
Boon wrote:

>In my opinion, Bernard's method is more complex than mine, but it
is very likely faster. Were there specific differences you wanted
to highlight ?

It is many orders of magnitude faster.

Many orders of magnitude ?
So, at least 100 times faster, perhaps even 1000 times faster ? Can
you see that just by looking at the source code (static analysis) or
did you run both programs ?
Efficiency was not my main concern, but I will try to optimize my
implementation ;-)

I've only input 7 grids so far, below is the "hardest" I've seen.

....968..
..1....7.
.2......3
.3...8..6
..4.2.3..
6..5...8.
9......5.
.7....1..
..594....

While it is a little more complex, it is simple enough to
understand.

I will print it out, and study it. Thanks again for sharing.

AI problems are very interesting to me. Â*I thought you might enjoy
looking at a highly efficient solution.

How does one properly benchmark a program that runs in less than 50
ms ?

Count the nodes.

For instance, with this one:
..1.8.6.4
.376.....
5........
.....5...
..6.1.8..
...4.....
........3
.....752.
8.2.9.7..

Your program takes 789,878 nodes and the fast program takes 11,187
nodes. Â*That's 70x faster, so a less than a factor of 100.

I have an interest in AI, and so these sorts of things are interesting
to me.

C:\tmp\sudoku>fast < sudoku7.txt
....968..
..1....7.
.2......3
.3...8..6
..4.2.3..
6..5...8.
9......5.
.7....1..
..594....

453796821
861234975
729185463
132478596
584629317
697513284
948361752
376852149
215947638

2081 nodes searched

Haha, mine does 2082::

. . . . 9 6 8 . .
. . 1 . . . . 7 .
. 2 . . . . . . 3
. 3 . . . 8 . . 6
. . 4 . 2 . 3 . .
6 . . 5 . . . 8 .
9 . . . . . . 5 .
. 7 . . . . 1 . .
. . 5 9 4 . . . .

4 5 3 7 9 6 8 2 1
8 6 1 2 3 4 9 7 5
7 2 9 1 8 5 4 6 3
1 3 2 4 7 8 5 9 6
5 8 4 6 2 9 3 1 7
6 9 7 5 1 3 2 8 4
9 4 8 3 6 1 7 5 2
3 7 6 8 5 2 1 4 9
2 1 5 9 4 7 6 3 8

Aantal=1 (calls=2082)
Method := recursive descent with bitmasks (narrowest first)
Maybe I counted the final+1 recursive call and you did not ?

Cheers,
AvK

[user923005]

On Oct 23, 3:42*pm, Moi <[e-mail]:

On Thu, 23 Oct 2008 15:06:43 -0700, user923005 wrote:

On Oct 23, 3:01*pm, user923005 <[e-mail]:

On Oct 23, 3:25*am, Boon <root@localhostwrote:

user923005 wrote:
Boon wrote:

>In my opinion, Bernard's method is more complex than mine, but it
>is very likely faster. Were there specific differences you wanted
>to highlight ?

It is many orders of magnitude faster.

Many orders of magnitude ?
So, at least 100 times faster, perhaps even 1000 times faster ? Can
you see that just by looking at the source code (static analysis) or
did you run both programs ?
Efficiency was not my main concern, but I will try to optimize my
implementation ;-)

I've only input 7 grids so far, below is the "hardest" I've seen.

....968..
..1....7.
.2......3
.3...8..6
..4.2.3..
6..5...8.
9......5.
.7....1..
..594....

While it is a little more complex, it is simple enough to
understand.

I will print it out, and study it. Thanks again for sharing.

AI problems are very interesting to me. *I thought you might enjoy
looking at a highly efficient solution.

How does one properly benchmark a program that runs in less than 50
ms ?

Count the nodes.

For instance, with this one:
..1.8.6.4
.376.....
5........
.....5...
..6.1.8..
...4.....
........3
.....752.
8.2.9.7..

Your program takes 789,878 nodes and the fast program takes 11,187
nodes. *That's 70x faster, so a less than a factor of 100.

I have an interest in AI, and so these sorts of things are interesting
to me.

C:\tmp\sudoku>fast < sudoku7.txt
....968..
..1....7.
.2......3
.3...8..6
..4.2.3..
6..5...8.
9......5.
.7....1..
..594....

453796821
861234975
729185463
132478596
584629317
697513284
948361752
376852149
215947638

2081 nodes searched

Haha, mine does 2082::

*. . . . 9 6 8 . .
*. . 1 . . . . 7 .
*. 2 . . . . . . 3
*. 3 . . . 8 . . 6
*. . 4 . 2 . 3 . .
*6 . . 5 . . . 8 .
*9 . . . . . . 5 .
*. 7 . . . . 1 . .
*. . 5 9 4 . . . .

*4 5 3 7 9 6 8 2 1
*8 6 1 2 3 4 9 7 5
*7 2 9 1 8 5 4 6 3
*1 3 2 4 7 8 5 9 6
*5 8 4 6 2 9 3 1 7
*6 9 7 5 1 3 2 8 4
*9 4 8 3 6 1 7 5 2
*3 7 6 8 5 2 1 4 9
*2 1 5 9 4 7 6 3 8

Aantal=1 (calls=2082)

Method := recursive descent with bitmasks (narrowest first)
Maybe I counted the final+1 recursive call and you did not ?

How does it do with this one:

1........
..2.......
...3......
....4.....
..........
......4...
.......3..
........1.
.........1

[Peter Nilsson]

Boon <root@localhostwrote:

I've only input 7 grids so far, below is the "hardest"
I've seen.

....968..
..1....7.
.2......3
.3...8..6
..4.2.3..
6..5...8.
9......5.
.7....1..
..594....

Try one designed to tax naive brute force solvers...
<http://en.wikipedia.org/wiki/
Image:Sudoku_puzzle_hard_for_brute_force.jpg>

<snip>

How does one properly benchmark a program that runs
in less than 50 ms ?

Check how well it scales to larger grids, e.g. 16x16,
or 25x25. The thing about exponential algorithms is
that it's usually not very hard to find a larger puzzle
that brings it to a stand still.

--
Peter

[Moi]

On Thu, 23 Oct 2008 16:11:43 -0700, user923005 wrote:

How does it do with this one:

1........
.2.......
..3......
...4.....
.........
.....4...
......3..
.......1.
........1

Well, it fails (caused by the two '4's in the center box, off course)
I needed to set the time-out to 60 seconds before finding out myself :-)

AvK

[user923005]

On Oct 23, 4:35*pm, Peter Nilsson <[e-mail]:

Boon <root@localhostwrote:

I've only input 7 grids so far, below is the "hardest"
I've seen.

....968..
..1....7.
.2......3
.3...8..6
..4.2.3..
6..5...8.
9......5.
.7....1..
..594....

Try one designed to tax naive brute force solvers...
* <http://en.wikipedia.org/wiki/
Image:Sudoku_puzzle_hard_for_brute_force.jpg>

<snip>

C:\tmp\sudoku>fast < sudoku9.txt
..........
......3.85
...1.2....
....5.7...
...4...1..
..9.......
5......73
...2.1....
.....4...9

987654321
246173985
351928746
128537694
634892157
795461832
519286473
472319568
863745219

73482 nodes searched
fast time = 0.11793593878551603

C:\tmp\sudoku>slow < sudoku9.txt
..........
......3.85
...1.2....
....5.7...
...4...1..
..9.......
5......73
...2.1....
.....4...9

987654321
246173985
351928746
128537694
634892157
795461832
519286473
472319568
863745219

69207226 noeuds cherches
slow time = 21.393947415104435

181 times faster wall time, 941 times faster in terms of nodes.

How does one properly benchmark a program that runs
in less than 50 ms ?

Check how well it scales to larger grids, e.g. 16x16,
or 25x25. The thing about exponential algorithms is
that it's usually not very hard to find a larger puzzle
that brings it to a stand still.

I found a very nice open source solver called yasss-0.4.8 that also
quickly diagnoses errant problems like the one I posed earlier:

1........
..2.......
...3......
....4.....
..........
......4...
.......3..
........1.
.........1

Yasss does require all the rows on a single line, but I may make a
version that allows either format, since it comes with source.