424,853 Members | 1,570 Online
Need help? Post your question and get tips & solutions from a community of 424,853 IT Pros & Developers. It's quick & easy.

# Yet another brute force sudoku solver

 P: n/a 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 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; } Oct 16 '08 #1
38 Replies

 P: n/a 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 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; } Oct 16 '08 #2

 P: n/a Trent Josephsen wrote: Boon wrote: #include 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 Oct 16 '08 #5

 P: n/a On Oct 16, 7:08*am, Boon 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 #include #include #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; } Oct 16 '08 #6

 P: n/a "Default User" Boon wrote: #include 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. Oct 16 '08 #7

 P: n/a 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. Oct 16 '08 #8

 P: n/a RichardTrent Josephsen wrote: >>Boon wrote: >#include 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) dataconstructs. I've been using that sort of thing for my game programmingsome lately. It's a sort of data encapsulation model. Frankly I think that is nonsense. 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. Oct 16 '08 #9

 P: n/a Ben Bacarisse "Default User" >Trent Josephsen wrote:Boon wrote:#include 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) dataconstructs. I've been using that sort of thing for my game programmingsome lately. It's a sort of data encapsulation model. >Frankly I think that is nonsense. >And file scope IS global (as anyone without a rod up their arse knowsit) 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? Oct 16 '08 #10

 P: n/a Richard wrote: "Default User" 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'. Oct 16 '08 #11

 P: n/a ja*********@verizon.net writes: Richard wrote: >"Default User" 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 resultcontainers or use in function statics to effectively hide things.And file scope IS global (as anyone without a rod up their arse knowsit) 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. Oct 16 '08 #12

 P: n/a Richard wrote: Ben Bacarisse 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) dataconstructs. I've been using that sort of thing for my game programmingsome lately. It's a sort of data encapsulation model. Frankly I think that is nonsense. 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. Oct 16 '08 #13

 P: n/a 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 Oct 16 '08 #15

 P: n/a Ben Bacarisse wrote: Richard Frankly I think that is nonsense. 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 Oct 16 '08 #16

 P: n/a pete 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. Oct 16 '08 #17

 P: n/a "Default User" >Brian talks about encapsulation and non-global file scope data so Iconclude he is talking about static objects declared at file scopewhich 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 norod). 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. Oct 16 '08 #18

 P: n/a Hello Dann, user923005 wrote: Boon wrote: >I've been toying with a simple sudoku[1] solver. I meant for the code tobe 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/SudokuThus, the strategy is to test every legal "move" and to backtrack whenstuck. A recursive function seemed appropriate. I'd like to hearcomments 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. Oct 20 '08 #20

 P: n/a On 16 Oct, 22:11, Richard#include >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) dataconstructs. I've been using that sort of thing for my game programmingsome lately. It's a sort of data encapsulation model. Frankly I think that is nonsense. And file scope IS global -- Nick Keighley Oct 20 '08 #21

 P: n/a On 16 Oct, 22:21, Richard

 P: n/a Richard wrote: ja*********@verizon.net writes: Richard wrote: "Default User" 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? Oct 20 '08 #23

 P: n/a Nick Keighley Ben Bacarisse 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. Oct 20 '08 #24

 P: n/a 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 Oct 20 '08 #25

 P: n/a On Oct 20, 12:36*am, Boon

 P: n/a user923005 wrote: On Oct 20, 12:36*am, Boon

 P: n/a On Mon, 20 Oct 2008 04:51:34 -0700 (PDT), ja*********@verizon.net wrote: Richard wrote: >ja*********@verizon.net writes: Richard wrote:"Default User" static int grid[9][9]; ... >And file scope IS global (as anyone without a rod up their arse knowsit) 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 itsthat 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. Oct 21 '08 #28

 P: n/a On Tue, 21 Oct 2008 02:09:26 +0000, Richard Heathfield 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 identifierwith internal linkage (such as the array 'grid' defined above) visiblefrom another translation unit by "declar[ing] an extern", unless theidentifier with external linkage refers to something different fromwhat the identifier with internal linkage refers to. If you know howto do this, could you give us an example? You can define an object with internal linkage in one file, and afunction with external linkage that returns a pointer to that object.Then other translation units can call the function to obtain theruntime 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 :) Oct 21 '08 #30

 P: n/a user923005 wrote: Boon wrote: >In my opinion, Bernard's method is more complex than mine, but itis very likely faster. Were there specific differences you wantedto 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. Oct 23 '08 #31

 P: n/a 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. Oct 23 '08 #32

 P: n/a On Oct 23, 3:25*am, Boon

 P: n/a On Oct 23, 3:01*pm, user923005 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. Oct 23 '08 #34

 P: n/a On Thu, 23 Oct 2008 15:06:43 -0700, user923005 wrote: On Oct 23, 3:01Â*pm, user923005 On Oct 23, 3:25Â*am, Boon In my opinion, Bernard's method is more complex than mine, but itis very likely faster. Were there specific differences you wantedto 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,187nodes. Â*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 interestingto 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 Oct 23 '08 #35

 P: n/a On Oct 23, 3:42*pm, Moi 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 Oct 23 '08 #36

 P: n/a Boon 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 Oct 23 '08 #37

 P: n/a 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 Oct 23 '08 #38

 P: n/a On Oct 23, 4:35*pm, Peter Nilsson 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. Oct 24 '08 #39

### This discussion thread is closed

Replies have been disabled for this discussion.