Sudoku Brevity Contest

[Darryl]

OK kids, last contest didn't work out so well. Hopefully this one will drum up a liitle more interest.

Your mission is to generate a Sudoku puzzle in the fewest tokens possible.

The rules..
1. You must generate a random complete Sudoku algorithmically, no pre-generated string lookups or tables and the generated puzzle should be different each time your program is run.

2. As usual, I will use tokxx as the token counter, however not as usually strings will be limited to 255 chars. Anything over will get a 5 token penalty [edit] rule modified

3. the format of the output of your program should be as follows:

239 158 476
546 372 918
187 496 352

395 687 241
461 239 587
872 541 693

653 814 729
928 765 134
714 923 865

4. Submit entries to littled at gmail dot com by Jan 31, 2006

ps. I'll be participating so don't submit before the 29th.

[Darobat]

Moved.

I may have to try this...

[Beer Hunter]

I got it down to 185 tokens, but I doubt that it will finish before the heat death of the universe. Are there any speed restrictions?

[Togra]

lol @ BH
Yeah, obviously such a restriction should be given...

[Darryl]

I got it down to 185 tokens, but I doubt that it will finish before the heat death of the universe. Are there any speed restrictions?

There are no time restrictions within reason, heat death of universe, however would be grounds for disqualification.

edit: Just to clear up within reason : I can't go and make a sandwich and come back and your proram is still running, so roughly 5 - 10 minutes.

[Safari]

Does it have to create different types of sudokus for each run?
I.e. should we use randomness in some sense?

[Corsix]

1. You must generate a random complete Sudoku algorithmically, no pre-generated string lookups or tables and the generated puzzle should be different each time your program is run.

so

Code: Select all

#include "time.h"
#include "math.h"

int main()
{
    srand(time(0));
}

[Darryl]

Does it have to create different types of sudokus for each run?
I.e. should we use randomness in some sense?

Not sure what you mean by types, but what I mean is the numbers are in different positions.

Basically, I don't want your program to create the same static Soduku every time, as for randomness, there are different ways to achieve it but as Corsix mention, srand(time(0)) and rand() is probably the most token efficient, however I could see someone using just time(0) to "seed" their own algorithm

btw, my first attemp is 388, but it fast and has a lot of fat to trim

[Safari]

This was my thought:

I could get the number at pos (0,0) randomly and build the rest of the puzzle built on that. Since nothing else is done randomly I would get 9 different of puzzles.

I hope it's okay!

[Darryl]

This was my thought:

I could get the number at pos (0,0) randomly and build the rest of the puzzle built on that. Since nothing else is done randomly I would get 9 different of puzzles.

I hope it's okay!

I struggled with this because I didn't want to outright say no and I tried to think of a comprimise, but 9 just isn't random enough because if I run the program 9 times for instance, I am almost certainly going to get a duplicates.

[Safari]

My first working (as far as I can see, does anyone know of a program that checks this (or maybe could make one?)) solution is at 413 tokens. I should be able to cut some off.


@ Darryl

Secondly, this one can compute MAX 362880 different puzzles. This should be "random" enough, ayy?

[Safari]

Okay, after cleaning the code I'm down to 337 tokens.

[Safari]

lol, just noticed I could cut off a bunch of tokens.
Tokens: 289

104 tokens until I beat BH's "heat death of the universe" solution.

All hail the hamster!

[Darryl]

I'm at 319, though still long ways away from BeerHunter (if his runs in a reasonable amount of time)

[Beer Hunter]

I was able to bring the execution time down to a few seconds. I now have 231 tokens (228 plus 3 for the long string penalty).

Oh, and about randomness, I have a proposal: assuming that rand() (or random_shuffle) is good enough, an entry must be capable of producing any Sudoku grid, even if some are more likely than others.