Sudoku Brevity Contest

Online C++ programming contests.

Moderators: Darobat, RecursiveS, Dante Shamest, Bugdude, Wizard, raimo

Sudoku Brevity Contest

Postby Darryl » Mon Jan 16, 2006 8:13 pm

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.
Last edited by Darryl on Fri Jan 20, 2006 1:43 am, edited 2 times in total.
User avatar
Darryl
 
Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

Postby Darobat » Mon Jan 16, 2006 9:32 pm

Moved.

I may have to try this... 8)
Code: Select all
#include <stdio.h>
struct W{char m,M[4??),w;void x(char
*W)??<w^=w;while(w[W]!=0)putchar(W[w
]^M[w++%5??));}W():m(040),w(0){char*
X="d@PLfAU\x05P)sHEMoTTPF""\31";for(
;w<5;w++[M??)=m++);x(X);}}w;main(){}
User avatar
Darobat
Moderator
 
Posts: 2572
Joined: Sat Sep 27, 2003 1:19 pm

Postby Beer Hunter » Tue Jan 17, 2006 12:55 am

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?
User avatar
Beer Hunter
 
Posts: 912
Joined: Sat Dec 13, 2003 7:12 pm
Location: Australia

Postby Togra » Tue Jan 17, 2006 2:42 am

lol @ BH
Yeah, obviously such a restriction should be given...
Togra
 
Posts: 188
Joined: Wed Jul 28, 2004 8:51 am
Location: NL

Postby Darryl » Tue Jan 17, 2006 7:23 am

Beer Hunter wrote: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.
User avatar
Darryl
 
Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

Postby Safari » Tue Jan 17, 2006 12:57 pm

Does it have to create different types of sudokus for each run?
I.e. should we use randomness in some sense?
你 好!
User avatar
Safari
 
Posts: 1363
Joined: Sun Sep 19, 2004 11:07 am

Postby Corsix » Tue Jan 17, 2006 1:17 pm

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));
}
Code: Select all
#include <stdio.h>
char*_="XxTIHRCXCxTIHRXRCxTIHXHRCxTIXIHRCxTXTIHRCxXxTIHRCX";
int main(int l){for(l+=7;l!=putchar(010);++l);if(*(++_))main
(*_!=88?(putchar(*_^073)|putchar(33))&1:0xffff2a8b);}
User avatar
Corsix
 
Posts: 1181
Joined: Fri Jul 23, 2004 9:33 am
Location: Berkeley, UK

Postby Darryl » Tue Jan 17, 2006 1:51 pm

Safari wrote: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 :-)
User avatar
Darryl
 
Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

Postby Safari » Tue Jan 17, 2006 2:12 pm

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!
你 好!
User avatar
Safari
 
Posts: 1363
Joined: Sun Sep 19, 2004 11:07 am

Postby Darryl » Tue Jan 17, 2006 3:14 pm

Safari wrote: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.
User avatar
Darryl
 
Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

Postby Safari » Tue Jan 17, 2006 3:36 pm

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?
你 好!
User avatar
Safari
 
Posts: 1363
Joined: Sun Sep 19, 2004 11:07 am

Postby Safari » Tue Jan 17, 2006 5:34 pm

Okay, after cleaning the code I'm down to 337 tokens.
你 好!
User avatar
Safari
 
Posts: 1363
Joined: Sun Sep 19, 2004 11:07 am

Postby Safari » Tue Jan 17, 2006 6:04 pm

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

All hail the hamster!
你 好!
User avatar
Safari
 
Posts: 1363
Joined: Sun Sep 19, 2004 11:07 am

Postby Darryl » Tue Jan 17, 2006 6:05 pm

I'm at 319, though still long ways away from BeerHunter (if his runs in a reasonable amount of time)
User avatar
Darryl
 
Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

Postby Beer Hunter » Wed Jan 18, 2006 12:37 am

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.
User avatar
Beer Hunter
 
Posts: 912
Joined: Sat Dec 13, 2003 7:12 pm
Location: Australia

Next

Return to Contests

Who is online

Users browsing this forum: No registered users and 1 guest