News for hackers. Stuff that matters.
Re:Programming Interview Question: Eight Queens by Crito on Tuesday December 31, 2013 @05:54PM (#6993298)
How I'd do it by hand:

Each row must have a queen, and each row must have the queen in a different position. Therefore there are 8 rows and we just need to find a correct permutation of them.

Number each row 0 through 7. Generate permutations of these numbers.

To check for diagonal collisions between permutation indices x and y: abs(perm[x]-perm[y]) == abs(x-y)

(In other words, if rows 2 and 4 cannot be two places apart, rows 6 and 7 cannot be one place apart.)

Check for diagonal collisions as you're writing out possible valid permutations by hand. Doesn't take long to generate solutions since you don't have to actually draw or mentally picture a board to work out diagonal collisions. You just need to keep 8 single digit numbers in your head.

There are no comments on this comment yet.