Sudoku Brevity Contest

[Beer Hunter]

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]

[Beer Hunter]

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.

[marcdan221]

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

[Safari]

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.

[Darryl]

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

[Darryl]

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.

[marcdan221]

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?

[Darryl]

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);
   }
}


[marcdan221]

@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

[Beer Hunter]

Perhaps you could try removing the Sleep() call and see what results you get then?

[marcdan221]

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
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)

[Beer Hunter]

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.

[Darryl]

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);
   }
}


[tomcant]

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

[tomcant]

Wow, real conversation killer there...