Sudoku Brevity Contest

Online C++ programming contests.

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

Postby Beer Hunter » Wed Jan 25, 2006 6:14 am

I had a play around with Darryl's code, and was able to get it down to 167 tokens, even after putting back in the includes that he evilly left out. I was able to remove the \b stuff, and I got rid of the requirement that chars be unsigned.[syntax="cpp"]#include "algorithm"
#include "stdio.h"
#include "stdlib.h"
#include "time.h"

int main()
{
srand(time(0));
unthinkable_mayhem:
char 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\n\000123456789",
current_cell = 81;
while (current_cell--)
{
std::random_shuffle(puzzle_grid+133,puzzle_grid+142);
int attemps_at_current_cell = 9;
denied:
if (!attemps_at_current_cell) goto unthinkable_mayhem;
int number_to_try = puzzle_grid[133 + --attemps_at_current_cell], cell_not_solved = false, offset_iter = 9;
while (offset_iter--)
cell_not_solved |= puzzle_grid[L"\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]+L"\000\001\002\004\005\006\010\011\012"[offset_iter]] == number_to_try
|| puzzle_grid[L"\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]+L"\000\014\030\060\074\110\140\154\170"[offset_iter]] == number_to_try
|| puzzle_grid[L"\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]+L"\000\001\002\014\015\016\030\031\032"[offset_iter]] == number_to_try;
if (cell_not_solved) goto denied;
puzzle_grid[L"\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;
}
printf(puzzle_grid);
}[/syntax]
User avatar
Beer Hunter
 
Posts: 912
Joined: Sat Dec 13, 2003 7:12 pm
Location: Australia

Postby Beer Hunter » Wed Jan 25, 2006 6:35 am

Safari wrote:You guys use similar look-up strings. Anyone care toexplain the logic of their algorithm? :)
Mine goes row-by-row. It copies "123456789" into the row, calls random_shuffle on it, and checks if this introduced any duplicate digits in any column or 3x3 box. If it did, it re-shuffles the row and tries again.

In the event of unthinkable mayhem (about 35% of the time), the algorithm gives up and starts over.

I think the real trickery is in my code that checks for duplicate digits in columns and 3x3 boxes. It has two loops. The outer loop goes from '1' to '9': on the first iteration, it only detects duplicate 1s, and so on. The inner loop goes from 0 to 161, looping over a large lookup string. In the lookup string, each block of nine characters contains the offsets of the characters of a column or a 3x3 box.

The loop condition on the inner loop contains "i % 9 || (n = -1)". This resets 'n' to -1 whenever i is a multiple of nine (including when i == 0). Now, for the next nine iterations, the value of 'n' is incremented whenever it finds the current digit it's searching for. If 'n' is incremented twice (so it equals 1), there's a duplicate digit, so the code jumps back to the random_shuffle part.
User avatar
Beer Hunter
 
Posts: 912
Joined: Sat Dec 13, 2003 7:12 pm
Location: Australia

Postby marcdan221 » Wed Jan 25, 2006 8:08 am

Is there something wrong with the posted Sudoku code found here? When I run them, they give me the same Sudoku grid every time.
LIFE: Learning, Understanding and accepting. Good to go?
User avatar
marcdan221
 
Posts: 58
Joined: Thu Oct 06, 2005 8:10 pm
Location: Canada, Qc

Postby Safari » Wed Jan 25, 2006 9:00 am

Beer Hunter wrote:
Safari wrote:You guys use similar look-up strings. Anyone care toexplain the logic of their algorithm? :)
Mine goes row-by-row. It copies "123456789" into the row, calls random_shuffle on it, and checks if this introduced any duplicate digits in any column or 3x3 box. If it did, it re-shuffles the row and tries again.

In the event of unthinkable mayhem (about 35% of the time), the algorithm gives up and starts over.

I think the real trickery is in my code that checks for duplicate digits in columns and 3x3 boxes. It has two loops. The outer loop goes from '1' to '9': on the first iteration, it only detects duplicate 1s, and so on. The inner loop goes from 0 to 161, looping over a large lookup string. In the lookup string, each block of nine characters contains the offsets of the characters of a column or a 3x3 box.

The loop condition on the inner loop contains "i % 9 || (n = -1)". This resets 'n' to -1 whenever i is a multiple of nine (including when i == 0). Now, for the next nine iterations, the value of 'n' is incremented whenever it finds the current digit it's searching for. If 'n' is incremented twice (so it equals 1), there's a duplicate digit, so the code jumps back to the random_shuffle part.

Thanks! :)
I'll chew on this for a moment.
你 好!
User avatar
Safari
 
Posts: 1363
Joined: Sun Sep 19, 2004 11:07 am

Postby Darryl » Wed Jan 25, 2006 9:19 am

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


Mine is a little different than BH, but similar, though that is a good idea to insert the whole row and reduce the checks to just columns and 3x3 but it adds more time to solving.

Mine starts with digits 1-9, shuffles them at each digit, it tries the first number, if a number doesn't fit, it goes to the next, if it goes through all 9 numbers then that grid is unsolvable and it restarts. In testings, it typically finds a solution in under 300 tries which is almost instantly unlike bh's 500000 giveup and try again method :-)

Other things I did was created a template string for ouptutting with the spaces and linefeeds already in it. I only had to take care of where I inserted the numbers so in the end, i just output the string. All my string lookups were basicaly a way of converting a 81 square grid to my template grid which was 132, the offset lookups was to iterate through the grid either by column, row, or 3x3,

BH, I had solved the \b problem too, just forgot to repost the code.
I had thought of putting L in front of myliterals, but I thought that would add a token and never tried. LOL

Many of MS headers include stdio and stdlib so who am I not to take advantage. :-)
Re-removing them puts me at 161 :-)
Last edited by Darryl on Wed Jan 25, 2006 9:29 am, edited 2 times in total.
User avatar
Darryl
 
Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

Postby Darryl » Wed Jan 25, 2006 9:24 am

marcdan221 wrote:Is there something wrong with the posted Sudoku code found here? When I run them, they give me the same Sudoku grid every time.


They shouldn't unless you modified/deleted/left-out srand(time(0))

If you were to run one of the programs twice(or more, like frome a batch), with little time in between then time(0) might not have changed and will produce the same result. You have to allow a full second between each run.
User avatar
Darryl
 
Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

Postby marcdan221 » Wed Jan 25, 2006 10:03 am

I didn't modified the code except for one thing, I had to do add .h to all #include but I don't think that it would change a thing, right?

Anyways, here are my results.

For Alvaro's code at page 4:
Code: Select all
258 691 374
367 254 891
194 378 625

615 732 948
482 169 753
739 485 216

926 513 487
871 946 532
543 827 169


And for Darryl's code at page 4:
Code: Select all
561 347 928
274 981 635
893 256 417

127 495 386
386 712 594
945 863 271

719 624 853
458 139 762
632 578 000
218357496


And still Darryl's code but at page 5 (modified by BH):
Code: Select all
796 325 481
413 879 652
825 164 379

164 738 925
537 692 148
289 451 763

351 246 897
948 517 236
672 983 514


Am I doing something wrong? :?
LIFE: Learning, Understanding and accepting. Good to go?
User avatar
marcdan221
 
Posts: 58
Joined: Thu Oct 06, 2005 8:10 pm
Location: Canada, Qc

Postby Darryl » Wed Jan 25, 2006 11:21 am

ok are you saying that if you go back and run it now, you will get the same as above? That is a curious problem.

Since you had to add the .h, i am guessing you are using MSVC 6, I don't know of any srand/rand problems with that compiler, however I know there is a lot of STL problems with it so maybe it's random_shuffle()?

try running this and post output:

Code: Select all
#include <iostream>
#include <algorithm>
#include <time.h>
#include <string>
#include "windows.h"

using namespace std;

int main ()
{
   int countdown = 2;
   while( countdown--)
   {
      string test = "0123456789";
      srand((unsigned)time(0));
      cout << "time: " << time(0) << "\n";
      cout << "rand: " << rand() << "\n";
      random_shuffle(test.begin(),test.end());
      cout << "random_shuffle:" << test << "\n\n";

      Sleep(1000);
   }
}
User avatar
Darryl
 
Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

Postby marcdan221 » Wed Jan 25, 2006 3:19 pm

@Darryl: Done. Here is what I got.

Code: Select all
time: 1138223683
rand: 24199
random_shuffle:6892143705

time: 1138223684
rand: 23984
random_shuffle:0913548672
So that's fine. Curious isn't it?

FYI: I'm using Borland Compiler 5.5
LIFE: Learning, Understanding and accepting. Good to go?
User avatar
marcdan221
 
Posts: 58
Joined: Thu Oct 06, 2005 8:10 pm
Location: Canada, Qc

Postby Beer Hunter » Wed Jan 25, 2006 3:24 pm

Perhaps you could try removing the Sleep() call and see what results you get then?
User avatar
Beer Hunter
 
Posts: 912
Joined: Sat Dec 13, 2003 7:12 pm
Location: Australia

Postby marcdan221 » Wed Jan 25, 2006 4:01 pm

Ok, I know what's wrong (well don't know if it's supposed to be like that), everytime I use random_shuffle for the first time, it always uses the same random patern.

So if I launch the program three times...here is what I get:
Code: Select all
C:\Borland\BCC55\Projects>test2
time: 1138226180
rand: 9983
random_shuffle:6892143705

time: 1138226181
rand: 9768
random_shuffle:0913548672


C:\Borland\BCC55\Projects>test2
time: 1138226183
rand: 9337
random_shuffle:6892143705

time: 1138226184
rand: 9121
random_shuffle:0913548672


C:\Borland\BCC55\Projects>test2
time: 1138226425
rand: 22683
random_shuffle:6892143705

time: 1138226426
rand: 22467
random_shuffle:0913548672


In that case, I must say that random_shuffle isn't really random :roll:
rand is working just fine with srand(time(0)).

Is it like that for everyone? (I mean random_shuffle using the same patern each time you run your program)
LIFE: Learning, Understanding and accepting. Good to go?
User avatar
marcdan221
 
Posts: 58
Joined: Thu Oct 06, 2005 8:10 pm
Location: Canada, Qc

Postby Beer Hunter » Wed Jan 25, 2006 4:51 pm

The C++ standard doesn't guarantee that random_shuffle actually uses rand(), so there's no standardised way to seed it that I can tell. (Most implementations do use rand(); it seems that Borland did it differently.)
Try writing a function, "int mygen(int u) { return rand()%u;}", and passing it as the third parameter of random_shuffle.
User avatar
Beer Hunter
 
Posts: 912
Joined: Sat Dec 13, 2003 7:12 pm
Location: Australia

Postby Darryl » Thu Jan 26, 2006 4:10 am

After a little research, I've found that Prior to 6.0 borland use Rogue Wave STL. Which, doesn't use rand as it's default random number generator, though I had trouble finding what it did use. I found one obscure refernce and modified test to match.

Try this:
Code: Select all
#include <iostream>
#include <algorithm>
#include <time.h>
#include <string>
#include "windows.h"

using namespace std;

int main ()
{
   RandomNumberGenerator<int> rng;
   int countdown = 2;
   while( countdown--)
   {
      string test = "0123456789";
      srand((unsigned)time(0));
       random_shuffle(test.begin(),test.end(), rng );
      cout << "random_shuffle:" << test << "\n\n";

      Sleep(1000);
   }
}
Last edited by Darryl on Thu Jan 26, 2006 7:29 am, edited 1 time in total.
User avatar
Darryl
 
Posts: 1342
Joined: Wed Sep 01, 2004 10:50 am
Location: Cayman Islands

Postby tomcant » Thu Jan 26, 2006 5:00 am

Earlier on in this thread, Alvaro mentioned that his solver could generate sudokus with varied structure. I have looked at his entry, and understand how it works, but the sudokus generated all have the same structure. I was wondering how this could be varied... perhaps Alvaro could post his 209 token solution?

I would be very appreciative if anyone has any ideas...
If it wasn't for C, we would be using BASI, PASAL and OBOL.
User avatar
tomcant
 
Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

Postby tomcant » Fri Jan 27, 2006 6:57 am

Wow, real conversation killer there... :roll:
If it wasn't for C, we would be using BASI, PASAL and OBOL.
User avatar
tomcant
 
Posts: 3101
Joined: Tue Sep 23, 2003 1:56 am
Location: Colchester, UK

PreviousNext

Return to Contests

Who is online

Users browsing this forum: No registered users and 2 guests