{"id":196,"date":"2006-01-28T19:10:19","date_gmt":"2006-01-29T03:10:19","guid":{"rendered":"http:\/\/multimedia.cx\/eggs\/?p=196"},"modified":"2020-07-25T23:20:43","modified_gmt":"2020-07-26T06:20:43","slug":"brute-force-puzzles","status":"publish","type":"post","link":"https:\/\/multimedia.cx\/eggs\/brute-force-puzzles\/","title":{"rendered":"Brute Force Puzzles"},"content":{"rendered":"

Cliff Pickover<\/a> continues his torment of humanity with six puzzles each week (Saturday and Sunday are combined) with his 2006 day-by-day calendar:<\/p>\n


\n\"Cliff
\n<\/center><\/p>\n

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:<\/p>\n

\r\n  1 2 3 4\r\n  5 6 7 8\r\n<\/pre>\n
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”<\/em> type rules to mean that p<\/em> to directly to the left of q<\/em>.<\/p>\n
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.<\/strong> Read on to find the solutions and the program to figure it out…<\/p>\n
<\/p>\n
There are (8! = 40320) possible arrangements. According to my program there are 6 solutions:<\/p>\n
\r\n O G Y R\r\n B V T I\r\n\r\n O G Y R\r\n V T B I\r\n\r\n Y R O G\r\n B I V T\r\n\r\n Y R B G\r\n O I V T\r\n\r\n B G Y R\r\n O V T I\r\n\r\n B G Y R\r\n V T O I\r\n<\/pre>\n
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.<\/p>\n