Sudoku Brevity Contest

[Alvaro]

But that doesn't call srand! So you'll probably get the same answer time after time.

[syntax="cpp"]#include "iostream"
#include "cstdlib"
#include "ctime"
#include "algorithm"

using namespace std;

int main(){
srand(time(0));
char m[]="\156.........\012..................... ................123456789";
random_shuffle(m+49,m+58);

while(*m)
cout << m["\n239 158 476\n546 372 918\n187 496 352\n\n395 687 241\n461 239 587\n872 541 693\n\n653 814 729\n928 765 134\n714 923 865"[--*m]];
}

[/syntax]
There you go: 65 tokens, with srand and all.

[Safari]

Yeah, I thought I would slip through anyway

Very...Very ... alienanic as allways. I must be the only one who writes readable code!

[Darryl]

Just out of curiosity, what was your 200 count solution? Or was it the same basis?

[Alvaro]

It was the one that also made permutations of groups of three rows or columns. Initially I thought that mechanism would generate good enough sudokus, but then I changed my mind. Anyway, if I do enter, I'll write something that can generate any sudokus.

[Darryl]

I have 2 questions about wierd things I came across...

I used a template string so that i didn't need to format it when i printed it. The template had the spaces and C\R in the right place and I just changed the sudoku values. Now, I also dual used the end of that string as a lookup table.

1. I tried to seperate the output part from the lookup part with a \0, however it seems i had trouble accessing the stuff after the \0.. can't remember exact problem(if it was with random_shuffle or with actually reading it with the index ie chararray[ix]) but had to abandon it... are you guys familiar with this problem?

2. After I got rid of the \0, ofcourse the lookup table now printed after my sudoku, so I put a number of \b (backspaces) at the end which worked perfectly to conceal the table....until I ran the program outside my ide in which case the backspaces didn't work...what's up with that?

Anyway here's my code and it's quite readable Safari
[syntax="cpp"]
//WARNING, THIS CODE ONLY WORKS WHEN COMPILED WITH CHAR AS UNSIGNED BY DEFAULT

#include "algorithm"
#include "ctime"
char puzzle_grid [154], cells_unsolved=81;

int main()
{
srand(time(0));
while(cells_unsolved)
{
strcpy(puzzle_grid,"000 000 000\n000 000 000\n000 000 000\n \n000 000 000\n000 000 000\n000 000 000\n \n000 000 000\n000 000 000\n000 000 000\n123456789\b\b\b\b\b\b\b\b\b\0");
int current_cell = cells_unsolved = 81;
while( current_cell--)
{
std::random_shuffle(puzzle_grid+132,puzzle_grid+141);
int attemps_at_current_cell = 9;
while(attemps_at_current_cell)
{
int number_to_try = puzzle_grid[132+ --attemps_at_current_cell], cell_solved = true,offset_iter = 9;
while(offset_iter--)
cell_solved &= puzzle_grid["\000\000\000\000\000\000\000\000\000\014\014\014\014\014\014\014\014\014\030\030\030\030\030\030\030\030\030\060\060\060\060\060\060\060\060\060\074\074\074\074\074\074\074\074\074\110\110\110\110\110\110\110\110\110\140\140\140\140\140\140\140\140\140\154\154\154\154\154\154\154\154\154\170\170\170\170\170\170\170\170\170"[current_cell]+"\000\001\002\004\005\006\010\011\012"[offset_iter]] != number_to_try
& puzzle_grid["\000\001\002\004\005\006\010\011\012\000\001\002\004\005\006\010\011\012\000\001\002\004\005\006\010\011\012\000\001\002\004\005\006\010\011\012\000\001\002\004\005\006\010\011\012\000\001\002\004\005\006\010\011\012\000\001\002\004\005\006\010\011\012\000\001\002\004\005\006\010\011\012\000\001\002\004\005\006\010\011\012"[current_cell]+"\000\014\030\060\074\110\140\154\170"[offset_iter]] != number_to_try
& puzzle_grid["\000\000\000\004\004\004\010\010\010\000\000\000\004\004\004\010\010\010\000\000\000\004\004\004\010\010\010\060\060\060\064\064\064\070\070\070\060\060\060\064\064\064\070\070\070\060\060\060\064\064\064\070\070\070\140\140\140\144\144\144\150\150\150\140\140\140\144\144\144\150\150\150\140\140\140\144\144\144\150\150\150"[current_cell]+"\000\001\002\014\015\016\030\031\032"[offset_iter]] != number_to_try;
if( cell_solved)
{
cells_unsolved--;
puzzle_grid["\000\001\002\004\005\006\010\011\012\014\015\016\020\021\022\024\025\026\030\031\032\034\035\036\040\041\042\060\061\062\064\065\066\070\071\072\074\075\076\100\101\102\104\105\106\110\111\112\114\115\116\120\121\122\140\141\142\144\145\146\150\151\152\154\155\156\160\161\162\164\165\166\170\171\172\174\175\176\200\201\202"[current_cell]] = number_to_try;
break;
}
}
}
}
printf(puzzle_grid);
}

[/syntax]

@ Alvaro, this competition is pretty much dead now so don't worry about entering another

[Alvaro]

Oh!

Well, to your first question, I am guessing you used "\012345...", which will be interpreted as '\012' followed by '3', '4', '5', ... The solution is using `\000' instead of just `\0'.

To your second question, I don't think the trick with the '\b's is valid, since it depends on the terminal behaving in a particular way that is not very standard (as you could feel yourself).

[Darryl]

Oh!

Well, to your first question, I am guessing you used "\012345...", which will be interpreted as '\012' followed by '3', '4', '5', ... The solution is using `\000' instead of just `\0'.

To your second question, I don't think the trick with the '\b's is valid, since it depends on the terminal behaving in a particular way that is not very standard (as you could feel yourself).

Thanks, I just figured out the 1st one, it's the strcpy is cutting off everything after \0. I had thought of your idea and put a space after \0 but it didn't work.

Had to switch to memcpy to make it work

[Safari]

What happened to BH? I want to see his 178 token solution =)

[Beer Hunter]

It's 171 tokens now, but the contest still goes for another week or so…

EDIT: Or does it? I just noticed Darryl's post on the previous page. Here's my solution.

[marcdan221]

Hi all,

I just couldn't resist to give it a try (Sudoku contest) right before going to bed yesterday. I guess i'm a late a little but i have my algorythmn already and it's working great (randomly generated each time I run it). I just need to ajust it a bit.

Anyways, I was wondering what you mean by "token" . How do I count how many token my program uses.

Thanks.

[Darryl]

Hi all,

I just couldn't resist to give it a try (Sudoku contest) right before going to bed yesterday. I guess i'm a late a little but i have my algorythmn already and it's working great (randomly generated each time I run it). I just need to ajust it a bit.

Anyways, I was wondering what you mean by "token" . How do I count how many token my program uses.

Thanks.

From MSDN:

A token is the smallest element of a C++ program that is meaningful to the compiler.

There is a program called tokxx.exe that can count the tokens in your source code.

The program is sort of hard to find, but here is a link I know that works: http://www.cyberkopia.net/gamer/modules ... d=6&lid=13

However several members have copies if that link goes down ever. I believe a few of us even have the source code in case you are using bsd or some other os, where you need to compile your own binary.

.
.
.

OK, For the rest of you guys, I have an idea to finish up this contest....for the remainder of the time, It's OPen contest, meaning post your solution and let's see who after seeing others solution can improve upon them to get a lower token count.... as Alvaro suggested, we should only use the entries that "...have a non-zero probability of generating any sudoku, given rand() is random enough."

Good Luck

[Darryl]

It's 171 tokens now, but the contest still goes for another week or so…

EDIT: Or does it? I just noticed Darryl's post on the previous page. Here's my solution.

Nice solution, I was looking for a way to shorten mine with goto's but couldn't find one...anyway, while we're at it I am curious about goto... I am not so familair with the "internals" of c++ execution so bear with me if I am not saying this correctly. When you have a loop or a function, isn't "something" push onto the stack and then popped when return? If so how do goto's affect that? Will continuous jumping out of a loop for example cause stack overflows?

[marcdan221]

@Darryl: Thank for the info.

I just realized my program was almost perfect until I figure out I was totaly not into it I'm making sure I don't use the same number twice in a row or/and column but not verifying not to use the same number in the same box. That's why it was so easy.

[Beer Hunter]

When you have a loop or a function, isn't "something" push onto the stack and then popped when return? If so how do goto's affect that? Will continuous jumping out of a loop for example cause stack overflows?

No, it doesn't allocate memory for that — it doesn't need to! All the variables involved have their place in the function's stack frame. Loops are equivalent to the use of if statements and gotos (and, no, if statements don't allocate memory either ;-)).

Functions need to allocate their local variables on the stack, or recursion wouldn't work. They also need to store a return address on the stack, or they wouldn't know where to resume execution after the function ends. Loops don't have either problem.

[Safari]

You guys use similar look-up strings. Anyone care toexplain the logic of their algorithm?