另一个蛮力数独求解器 [英] Yet another brute force sudoku solver
问题描述
Hello group，
我一直在玩一个简单的数独[1]求解器。我的意思是代码要简单易懂。我认为蛮力很简单。 -
谁需要技巧，当你有肌肉时，对吧？ :-)
[1] http： //en.wikipedia.org/wiki/Sudoku
因此，策略是测试每一个合法的移动。
陷入困境时回溯。递归函数似乎是合适的。我想听听
关于实施的意见和建议。
问候。
#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 =行 - 行％3;
int jj = col - col％3;
int i，j，k = 0，res = 1;
for（i = 0;我< 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;
}
无效解决（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;
求解（pos + 1）;
}
}
grid [row] [col] = 0;
}
}
}
int main（无效）
{
read_grid（stdin）;
求解（0）;
返回0;
}
Boon写道：
Hello group，
我一直在玩一个简单的数独[1]求解器。我的意思是代码要简单易懂。我认为蛮力很简单。 -
谁需要技巧，当你有肌肉时，对吧？ :-)
[1] http： //en.wikipedia.org/wiki/Sudoku
因此，策略是测试每一个合法的移动。
陷入困境时回溯。递归函数似乎是合适的。我想听听
关于实施的意见和建议。
问候。
#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）;
等等，你在9次读16个字符？最多你将获得11美元（9个字符加上换行符和''\ 0''）。
for（j = 0; j< 9; ++ j）
{
char c = buf [j];
if（''1' '< = c&& c< =''9''）grid [i] [j] = c - ''0'';
为什么要将每个字符（范围1到9）更改为int（范围1
到9）？这不是必须的 - 你只需要测试两个
字符是否相等，而不是用它们进行任何数学计算。无论如何不是用
暴力攻击。
}
}
}
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;
}
无效解决（int pos）
{
if（pos = = 9 * 9）write_grid（）;
返回代表成功的代码可能比打印来自solve（）的结果更好，而不是打印
，以防万一想要在main（）中使用那个
，比如根据结果打印出不同的消息。
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）;
如果对solve（）的调用成功怎么办？它会停止递归吗？不，它
只返回/并继续测试所有其他可能性/。这个
可能意味着如果有多个
的法律解决方案，您将获得多个打印输出。可能是好的，可能是坏的。
}
}
grid [row] [col] = 0;
}
}
我真的不喜欢这个实现，因为有没有办法让
调用函数知道对solve（）的调用是否成功。在
solve（）中这很糟糕，因为当它成功时，前一级
递归无法知道并继续搜索
解决方案（可能存在或可能不存在），并在它们出现时将它们打印出来。
给它们。在main（）中这很糟糕，因为你无法辨别
代码是否可以解决这个谜题。
我觉得你可能想知道
a特殊拼图的所有可能解决方案;在这种情况下，您可以让每个调用返回它找到的解决问题的方式。这需要一个
变量，每次找到解决方案时都会增加。在任何情况下，
如果你能分辨出它是否成功，这个函数会更实用。
}
int main（无效）
{
read_grid（stdin）;
求解（0）;
返回0;
}
Trent Josephsen写道：
Boon写道：
>我一直在玩一个简单的数独[1]求解器。我的意思是代码
简短易懂。我认为蛮力很简单
- 当你有肌肉时，谁需要技巧，对吧？ :-)
[1] http：// en。 wikipedia.org/wiki/Sudoku
因此，策略是测试每一个合法的移动。
卡住时回溯。递归函数似乎是合适的。我想听听有关实施的意见和建议。
#include< stdio.h>
静态网格[9] [9 ]。
一般来说，你可能想要避免全局变量。
我不想让is_legal（）和solve（）需要额外的参数。
（我知道这不是一个非常有说服力的理由。）
> void read_grid（FILE * fp）
{
int i， j;
for（i = 0; i< 9; ++ i）
{char buf [16];
fgets（buf，sizeof buf，fp）;
等等，你在9次读16个字符？你最多只需要11美元（9个字符加一个换行符和''\ 0''）。
我正在阅读*最多* 16个字符（绝不应该发生）。
注意：我没有关注在I / O例程中，它们可能有漏洞。
BTW，在cygwin中，行以0x0d 0x0a 0x00结束。
< pedantic mode>
平台是否可以定义？ ''\ n''作为一个10
字符的序列？从而使我的buf太小而不能容纳9个字符，
换行，并且没有。
< / mode>
< blockquote class =post_quotes>
> for（j = 0; j <9; ++ j）
{c / c charf = buf [j];
if（''1''< = c&& ; c< =''9''）grid [i] [j] = c - ''0'';
为什么要将每个字符（范围1到9）更改为int（范围1
到9）？这不是必须的 - 你只需要测试两个
字符是否相等，而不是用它们进行任何数学计算。无论如何，不是用
暴力攻击。
你是对的。我只需要将solve（）中的for循环更改为
for（val ='''''; val< ='''9''; ++ val）
但这不是很多，无论是简单还是表现，你不同意吗？
> void solve（int pos）
{
if（pos == 9 * 9）write_grid（）;
返回代表成功的代码可能比打印来自solve（）的结果更好，而不是打印
，以防万一想要在main（）中使用
做一些事情，比如根据结果打印出不同的消息。
我明白你的观点。
>否则
{int，col，val;
row = pos / 9;
col = pos％9;
if（grid [row] [col] ！= 0）求解（pos + 1）;
{
for（val = 1; val< = 9; ++ val）
{
if（is_legal（row，col，val））
{
grid [row] [col] = val;
solve（pos + 1）;
如果对solve（）的调用成功怎么办？
成功通话意味着什么？
是否会停止递归？不，它
只返回/并继续测试所有其他可能性/。这个
可能意味着如果有多个
的法律解决方案，您将获得多个打印输出。可能是好的，可能是坏的。
这是设计的。我想知道一个问题是否有多个解决方案。
我真的不喜欢这个实现，因为没有办法获得
调用函数来知道对solve（）的调用是否成功。
成功你的意思是找到一个解决方案或找到所有解决方案或
其他什么？失败意味着没有找到任何解决方案？
在solve（）中这很糟糕，因为当它成功时，前一级别的
递归已经没有办法知道并继续搜索
解决方案（可能存在或可能不存在），并将它们打印出来，因为它们来自他们的b $ b。在main（）中这很糟糕，因为你无法辨别代码是否可以解决这个谜题。
我会记住你的意见。
我想你可能想要的了解所有可能的解决方案
a特殊拼图;在这种情况下，您可以让每个调用返回它找到的解决问题的方式。这需要一个
变量，每次找到解决方案时都会增加。在任何情况下，
如果你能判断它是否成功，这个函数会更实用。
如果它被用作库函数？
问候。
文章< 48 ********************** @ news.free.fr> ;,
Boon< root @ localhostwrote：
> Trent Josephsen写道：
> Boon写道：
>通常你想要避免全局变量，你可能知道。
我不想要is_legal（）和solve（）来要求额外的参数。
（我知道这不是一个非常有说服力的理由。）
关于全局变量要记住的重要事项是：* every *
global是程序中* every *函数接口的一部分。
（即使它现在没有使用它，也没有什么可以阻止
决定在将来某个时候使用它。）
如果程序很小并且是自包含的，并且你需要整个程序需要的信息是全局的，那么这将是
可能就是你想要的。但小而自足的节目却有一种讨厌的习惯，就是不想保持小而且自足。
迟早你会发现自己希望以这种方式编写的程序是所有人都想要的东西。它的
函数的参数，所以你可以将它作为一个模块放在一个更大的程序中，并使用
这个模块同时用于两件事。因此，如果您要使用全局
变量，至少要记住这一点，并且以后可以很容易地将它转换成该表格。
当我使用全局变量时，我喜欢将它们全部包含在少量
结构中。这有两个好处：
（1）它可以更容易地将全局变换为pass-around-to-
每个非全局数据;只需拥有需要它的所有东西（或者，传递地，
，调用需要它的东西）获取指向适当类型的
结构的指针。找到需要它的函数和
将它们转换为使用非全局形式很简单 - 只需执行一次
搜索全局结构名称，并进行相应的更改
无处不在。
（2）它使你在使用全局变量时显而易见这个
是全局的你是使用。这为你提供了关于在哪里查看
的线索，了解更多关于它的信息，并提醒你要小心
那里的变化可能会影响其他的代码块。 />
不同的地方。
> BTW，在cygwin中，该行以0x0d 0x0a 0x00结尾。
<迂腐模式>
平台是否有可能定义？ ''\ n''作为10个字符的序列？从而使我的buf太小而不能容纳9个字符，
换行符和nul。
< / mode>
No.
嗯，也许，但不会影响到你。
平台是允许定义文本文件中的行尾然而它想要的是b $ b;但是如果你在文本模式下打开文件，则需要
转换来自native的任何内容。格式是序列
字符后跟''\ n'''，这是C程序使用的内部表示
。
（注意，在stdio库的另一端，换行没有
甚至需要用（序列）字符表示;
f''re示例，一个实现可以使用固定长度的空格填充行，
并且该实现的stdio库需要读取该行，
修剪尾随空格填充，并在
将数据传递给C程序之前在行之间插入''\ n'。）
（这意味着，如果你没有以二进制模式打开文件，并且
cygwin在你的行尾给你\\\\ n，那么无论是'b $ b'还是没有正确地进行终端翻译，或者它的定义与b / b
不同于系统的其他部分住在和
拒绝玩得很好。）
dave
-
Dave Vandervies dj3vande at at eskimo dot com
我可能已经老了，但我越来越倾向于认为C是一个更好的因为Hoare'的关于Algol的评论的精神。 60几乎是所有接班人的改进。 - 在comp.lang.c中安德鲁·西蒙斯
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;
}
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;
}
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 <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
这篇关于另一个蛮力数独求解器的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
