Cliff Pickover continues his torment of humanity with six puzzles each week (Saturday and Sunday are combined) with his 2006 day-by-day calendar:
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.
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.
See, I knew there had to be an easier way to do it. Finally, a good (?) reason to learn a new language!
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.
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. :-)