Breaking Eggs And Making Omelettes

Topics On Multimedia Technology and Reverse Engineering


Archives:

Brute Force Puzzles

January 28th, 2006 by Multimedia Mike

Cliff Pickover continues his torment of humanity with six puzzles each week (Saturday and Sunday are combined) with his 2006 day-by-day calendar:


Cliff Pickover's Instrument of Terror

As a good number of his puzzles can be solved by brute forcing through the entire solution space, modern computing technology can assist us greatly in mitigating Pickover’s reign of terror. Such is the case with the January 19 puzzle. The actual puzzle is explained a bit more “colorfully”. I’ll distill the mathematical principles. There is a grid of 8 squares laid out as a 4×2 matrix:

  1 2 3 4
  5 6 7 8

You have to place 8 letters in the 4 squares: (B G I O R T V Y) obeying the following rules: Neither R nor I can occupy square 1 or 5; neither V nor T can occupy squares 1..4. Y is left of R, V is left of T, R is above I, and O and B are on odd quares. I took the “p is left of q” type rules to mean that p to directly to the left of q.

Anyway, I deductively came up with a solution. But it seemed there might be more solutions. Sure enough, the official solution was different but challenged the reader to find out how many solutions there are. Fine! I will. Read on to find the solutions and the program to figure it out…

There are (8! = 40320) possible arrangements. According to my program there are 6 solutions:

 O G Y R
 B V T I

 O G Y R
 V T B I

 Y R O G
 B I V T

 Y R B G
 O I V T

 B G Y R
 O V T I

 B G Y R
 V T O I

Here is the program to solve the puzzle. The tricky part is computing the permutations but not if you cheat and look for code on the internet to do it for you. The program simply runs through all possible arrangements/permutations and checks each if it conforms to all the rules as expressed mathematically.

/*
* Program to brute-force the solution(s) to Cliff Pickover’s
* 2006/01/19 puzzle.
*
* visit() function was found here:
* http://paul.rutgers.edu/~rhoads/Code/code.html
* It’s the permutation function described as “short and bewildering”.
*/

#include
#include

int level = -1;
#define N 8
int Value[N];

#define R_INDEX 0
#define O_INDEX 1
#define Y_INDEX 2
#define G_INDEX 3
#define B_INDEX 4
#define I_INDEX 5
#define V_INDEX 6
#define T_INDEX 7

void visit (int k)
{
int i, j;
char color_string[] = “ROYGBIVT”;

Value[k] = ++level;
if (level == N)
{
do {

/* processing happens in here */

/* R and I cannot be in first column (1 or 5) */
if ((Value[R_INDEX] == 1) || (Value[R_INDEX] == 5) ||
(Value[I_INDEX] == 1) || (Value[I_INDEX] == 5))
break;

/* V and T cannot be in first row (1..4) */
if ((Value[V_INDEX] < = 4) || (Value[T_INDEX] <= 4)) break; /* Y is to the left of R and V is to the left of T; this means that Y and V cannot be in last column (4 or 8 ) and R and T cannot be in first column (already established for R); this also assumes that Y and R must be adjacent, same for V & T */ if ((Value[Y_INDEX] == 4) || (Value[Y_INDEX] == 8 ) || (Value[V_INDEX] == 4) || (Value[V_INDEX] == 8 ) || (Value[T_INDEX] == 1) || (Value[T_INDEX] == 5) || (Value[Y_INDEX] != Value[R_INDEX] - 1) || (Value[V_INDEX] != Value[T_INDEX] - 1)) break; /* R is above I; this means R cannot be on row 2 and I cannot be on row 1 and that R's index needs to be 4 less than I's index */ if ((Value[R_INDEX] >= 5) || (Value[I_INDEX] < = 4) || (Value[R_INDEX] != (Value[I_INDEX] - 4))) break; /* O and B are on odd indices */ if (((Value[O_INDEX] & 1) == 0) || ((Value[B_INDEX] & 1) == 0)) break; /* if processing gets this far then the permutation qualifies */ /* iterate over the box numbers... */ for (i = 1; i <= 8; i++) { /* search through the value (color) array... */ for (j = 0; j < 8; j++) { if (Value[j] == i) { printf (" %c", color_string[j]); } } if (i == 4) printf ("\n"); } printf ("\n\n"); } while (0); /* just need 1 iteration */ } else for (i = 0; i < N; i++) if (Value[i] == 0) visit(i); level--; Value[k] = 0; } int main(void) { int i; for (i=0; i < N; i++) Value[i] = 0; visit(8); return 0; } [/c]

Posted in Pickover Puzzles | 4 Comments »

4 Responses

  1. Kostya Says:

    It seems to be one of those combinatorial-logical puzzle which could be quite easily solved with languages like Prolog, where you have just to write puzzle rules and execute program. While my knowledge of Prolog is next to nothing, I managed to hack example code from one of Prolog interpreters and solve a dozen of puzzles from one book.

    It was also fun to develop TrueMotion 2 frame decoder in Perl.

  2. Multimedia Mike Says:

    See, I knew there had to be an easier way to do it. Finally, a good (?) reason to learn a new language!

  3. Pianosaurus Tvedt Says:

    I realize this is old, but I was reading through your archive and ended up spending the night playing with Prolog. Here’s a solution to this puzzle (fairly obfuscated, and probably not particularly efficient, but it’s a start):

    %%%% START %%%%

    % Set constraints defined by the puzzle.
    leftof(X, Y) :- ((X == ‘Y’, Y == ‘R’, !);
    (X == ‘V’, Y == ‘T’, !);
    (X \== ‘Y’, X \== ‘V’, Y \== ‘R’, Y \== ‘T’)).
    above(X, Y) :- (X == ‘R’, Y == ‘I’, !); (X \== ‘R’, Y \== ‘I’).
    row1ok(X) :- X == ‘V’ -> fail ; !.
    col1ok(X) :- X == ‘I’ -> fail ; !.
    evenok(X) :- (X == ‘O’; X == ‘B’) -> fail ; !.

    % Define grid.
    grid(A, B, C, D, E, F, G, H) :-

    % Positions A-H are permutations of valid characters.
    permutation([‘B’,’G’,’I’,’O’,’R’,’T’,’V’,’Y’],
    [A, B, C, D, E, F, G, H]),

    % Set up position of A-H.
    leftof(A, B), leftof(B, C), leftof(C, D), leftof(D, ”),
    leftof(E, F), leftof(F, G), leftof(G, H), leftof(H, ”),
    above(A, E), above(B, F), above(C, G), above(D, H),
    above(E, ”), above(F, ”), above(G, ”), above(H, ”),

    % Make sure nothing is in an illegal position.
    row1ok(A), row1ok(B), row1ok(C), row1ok(D),
    col1ok(A), col1ok(E),
    evenok(B), evenok(F), evenok(D), evenok(H),

    % Print out valid results and fail silently.
    % This is entirely unneccesary, but makes the printout prettier.
    write([A,B,C,D]), nl, write([E,F,G,H]), nl, nl, fail.

    % That’s it. This is just a shortcut you can use in the interpreter.
    solutions :- setof([],A^B^C^D^E^F^G^H^grid(A,B,C,D,E,F,G,H),[]); !.

    % This directive is only needed if you want to compile this to
    % native code, to get it to print something.
    :- initialization(solutions).

    %%%% END %%%%

    I hope you have some pre-tags to put on this. It’s a mess in this tiny box…

    Anyway, the results were the same as yours. My Athlon 64 at 1 GHz finishes at
    user 0m0.077s
    sys 0m0.002s
    …as if that was descriptive of anything.

    Just thought a code example might be interesting to someone.

  4. Multimedia Mike Says:

    Absolutely, that was interesting! I still have that calendar as I quit trying to manually solve the puzzles about halfway through April of 2006. That’s when I decided I would use it as a motivation for learning Prolog. But obviously, that has yet to materialize. :-)