A few weeks ago the topic of IQ caught my eye. In the last ten years I have taken a variety of IQ test and have got a variety of results. While they tend to vary tremendously from site to site, the net consensus information I can gather from them is that I am, in fact, getting stupider as the years progress. That piece of information was for free, but has nothing to do with what this program is about:
Somewhere along the line I was thinking to myself, "Golly gee, do these IQ tests even mean anything? I wonder what IQ Einstein had?" I searched and searched only to find that he, in fact, never took an IQ test in his life. On the other hand he did compose a test of his own
Upon inspection you might note that the complexity of the test nowhere rivals the Rubik's Cube. Makes me wonder what Einstein would've thought of it had it been invented during his age. He might have restated his claim that only 2% of the world's population would be able to solve it. The test takes the form of those logic puzzles that they force feed us in gradeschool and highschool. I wonder if only now they teach us such things after such a celebrity figure as Einstein invented a quiz like this.
So one lonely night I sat down to work on the thing. It took me about half an hour to figure out. I challenged friends to it and it took them roughly the same time. Phew, I haven't fallen off the wagon yet. Though while solving it I couldn't help but notice an ambiguity in the questions. Friends likewise pointed out: in some parts the quiz refers to house ordering in terms of left-to-right, while in others it refers to it in terms of first-to-last. This got me curious: Dould it matter whether left is first or right is first? Did I make any false assumptions that might've compromised my solution? So I set about to write a brute-force solver for the quiz.
The quiz involves arranging five permutations of five elements such that all constraints are made. A single permutation of five elements has 5! = 120 different arrangements. Five of them have 120^5 = 24,883,200,000 different possibile arrangements. So whatever solver I create it will most likely require two things: (a) to process a lot of checks per second, and (b) for me to let it sit for a good long time while it crunches away at an answer.
I wrote my first brute-force checker as simple as it gets, in the language of Lua of all things. I even had it manually calculating each permutation as it went. Naturally it went incredibly slow, at such a rate that it wouldn't finish even within a day.
My second version was written in C++. I precached the list of 120 permutations of 5 objects for speed's sake. It pulled 400,000 checks per second on my 1.83GHz Intel Core Duo. This would still take someone something like 16 hours to check all solutions, and I couldn't help but feel I could get more out of my CPU considering only one of the two cores were being utilized.
A third version was designed to use both cores. That ran at 650,000 checks per second. ETA was now 10 hours and I still wasn't happy.
I then set about designing a GPU-based solver. I checked various implementation methods. The initial versions relied on an input texture specifying what indices the solver was currently at -- these ran at about 3,000,000 checks per second with my Radeon X1600. I realized the texture lookups were slowing me down and instead set aside two of the variables as U and V coordinates to the output framebuffer while leaving the other three to be manually specified as shader uniforms. That jumped me up to 7,000,000 checks per second.
I checked several different options for improving performance. Would condition statements + discards run faster in the GPU, or would things run faster if I coded the entire conditional expression as a mathematics function of squares, products, and sums? Turns out the math pathway is much much faster. Currently all my math is done in integer form. I kept meaning to test and see if sparing the conversion and using lots of floor()'s in its place would make things go faster.
While the fragment program is designed to check many parallel combinations at once, its means of reporting them is still limited. It is designed to write a '0' to the buffer if a problem checks out, or a '1' if it fails in some way. From there the CPu has to determine whether a zero occurs in the buffer and print out exactly where. I tried several options for using the GPU to speed this process up as well: I tried generating mipmaps of the destination texture and reading from the lowest mip-level texel to find whether it was off-white or not. This might've been a bad idea considering some mipmap generation methods bias their texels towards-white to otherwise prevent them from darkening. Oh well, that can be explored further. Likewise I didn't write a FBO reduction shader. My experiences with those have been slow ones. So if anyone wants to try that out feel free to. My last creative attempt at using the GPU to check results was to use a VBO+PBO to render the texels of the destination texture into a 1-pixel viewport, such that a color of zero would result in drawing a point at the origin and thus filling the viewport. This also slowed the program down too much. I never did experiment with the GL histogram routines. I just settled for a CPU-based checker, and things seemed to go fast enough.
The version you see before you I managed to get up to 8,000,000 checks per second. It can check all 24 billion combinations in somewhere around 50 minutes. I posted the results of what I found at the bottom of the page, so scroll down further for a good spoiler.
- Einstein's Quiz - GPU Based Solver
Binary
- Mac OS X 10.4
Source Code Dependencies: Core Libraries v.2
It turns out I found not only one but seven solutions that work for Einstein's quiz. Seven when solving the problem assuming that left is first. I ran the thing again assuming that right was first and found five more. Here is what I found:
Assuming left is first:found valid permutation [0, 0, 0, 0, 0] -------------- YELLOW NORWAY WATER DUNHIL CATS BLUE DANE TEA BLEND HORSES RED BRIT MILK PM BIRDS GREEN GERMAN COFFEE PRINCE FISH WHITE SWEDE BEER BM DOGS found valid permutation [78, 17, 75, 37, 76] -------------- GREEN NORWAY COFFEE BLEND FISH BLUE GERMAN WATER PRINCE CATS YELLOW SWEDE MILK DUNHIL DOGS RED BRIT BEER BM HORSES WHITE DANE TEA PM BIRDS found valid permutation [80, 14, 74, 62, 48] -------------- GREEN NORWAY COFFEE PM BIRDS BLUE GERMAN WATER PRINCE CATS RED BRIT MILK BLEND HORSES YELLOW DANE TEA DUNHIL FISH WHITE SWEDE BEER BM DOGS found valid permutation [80, 14, 74, 62, 62] -------------- GREEN NORWAY COFFEE PM BIRDS BLUE GERMAN WATER PRINCE FISH RED BRIT MILK BLEND HORSES YELLOW DANE TEA DUNHIL CATS WHITE SWEDE BEER BM DOGS found valid permutation [82, 16, 74, 62, 53] -------------- GREEN NORWAY COFFEE PM BIRDS BLUE GERMAN WATER PRINCE CATS WHITE SWEDE MILK BLEND DOGS YELLOW DANE TEA DUNHIL FISH RED BRIT BEER BM HORSES found valid permutation [82, 16, 74, 62, 64] -------------- GREEN NORWAY COFFEE PM BIRDS BLUE GERMAN WATER PRINCE FISH WHITE SWEDE MILK BLEND DOGS YELLOW DANE TEA DUNHIL CATS RED BRIT BEER BM HORSES found valid permutation [83, 17, 75, 63, 52] -------------- GREEN NORWAY COFFEE PM BIRDS BLUE GERMAN WATER PRINCE CATS WHITE SWEDE MILK BLEND DOGS RED BRIT BEER BM HORSES YELLOW DANE TEA DUNHIL FISHAssuming right is first:
found valid permutation [10, 35, 44, 19, 82] -------------- YELLOW DANE TEA DUNHIL FISH RED BRIT BEER BM HORSES WHITE SWEDE MILK BLEND DOGS BLUE GERMAN WATER PRINCE CATS GREEN NORWAY COFFEE PM BIRDS found valid permutation [52, 59, 104, 97, 29] -------------- RED BRIT BEER BM HORSES YELLOW DANE TEA DUNHIL CATS WHITE SWEDE MILK BLEND DOGS BLUE GERMAN WATER PRINCE FISH GREEN NORWAY COFFEE PM BIRDS found valid permutation [52, 59, 104, 97, 40] -------------- RED BRIT BEER BM HORSES YELLOW DANE TEA DUNHIL FISH WHITE SWEDE MILK BLEND DOGS BLUE GERMAN WATER PRINCE CATS GREEN NORWAY COFFEE PM BIRDS found valid permutation [98, 105, 104, 97, 97] -------------- WHITE SWEDE BEER BM DOGS YELLOW DANE TEA DUNHIL CATS RED BRIT MILK BLEND HORSES BLUE GERMAN WATER PRINCE FISH GREEN NORWAY COFFEE PM BIRDS found valid permutation [108, 35, 44, 67, 58] -------------- WHITE DANE TEA PM BIRDS RED BRIT BEER BM HORSES YELLOW SWEDE MILK DUNHIL DOGS BLUE GERMAN WATER PRINCE CATS GREEN NORWAY COFFEE BLEND FISH