Re:Programming Interview Question: Eight Queens
by ucarion on Tuesday December 31, 2013 @05:07PM
(#6993098)
Not sure if you're aware of this, but the technique of representing a chess board as a 64-bit bitmap is in fact the method used by pretty much all chess engines these days. These 64-bit unsigned long longs are known as "bitboards".
It can actually be done fairly quickly if you really only ask for 8x8 instead of a general NxN solver, and the person realizes one key thing: computers have gotten ridiculously fast, so that if you just bang out the first dumb thing that comes to mind, you can probably be done and have the answers before the people with the clever, general, efficient solutions get their solutions coded or even designed.
For instance, this brute force, ridiculously ugly, un-clever, only-works-for-8x8 solution took about 5 minutes or so to write, with half that spent deciding how to number the diagonals and looking at a couple of squares on a chessboard to see how rank/file maps to my diagonal numbering:
It takes under 0.5 seconds on my 2009 Mac Pro when compiled without optimization, and about half that with optimization.(To be completely honest, I rarely write C nowadays, so although it only took a few minutes to write, the damn thing took half an hour to debug. I wrote "1 <<" instead of "1L <<" because I thought for some reason that int was 64 bit nowadays).