Interview Question

Financial Software Developer Interview New York, NY

Can you cover an 8x8 chess board with dominos if two corner

  squares are removed (not two from the same side, 2 diagonal from each other). A domino covers 2 squares and no dominos can hang over the side of the board.
Answer

Interview Answer

4 Answers

1

No. The more interesting answer is why. It took me a while to get this one, but I started looking at it from a linear algebra standpoint and that impressed the interviewer. So while it took me longer to get it than most people I explain it to, that didn't stop me from passing that round of the interview process (this was asked on the 2nd interview, although I don't know if it's a "second round" question).

Interview Candidate on Jun 28, 2012
0

Can you explain your idea from linear algebra in more detail? Thanks!

yoyo on Oct 25, 2012
2

It was pretty half baked, but the general idea was, if you look at the board with the two corner pieces removed, it kind of looks like a matrix like this:
0 1 1 1
1 1 1 1
1 1 1 1
1 1 1 0

The two middle columns are linearly dependent, and I was sort of trying to tie that into somehow converting the matrix into something like this

0 1
1 1
1 1
1 0

If the board looked like that, then to cover the top right square you need to put on a vertical domino, and likewise for the bottom left square. The leaves the only two uncovered squares as the one in the second row, first column, and the one in the third row, second column, a scenario in which covering them would be impossible.

I couldn't quite work this out, but I think the interviewer liked that I tried such an approach. It really goes to show that when you're on an interview like this, the answer, though it is the goal, is one of the last things they care about.

anonymous on Oct 25, 2012
6

No
In the chess board, there are 32 black squares and 32 white squares. The two squares taken off are in the same colour. And a domino always covers two squares one next another. So the two are different in colour. Therefore, whatever you try, you can never cover the whole board.

CZ on Nov 23, 2012

Add Answers or Comments

To comment on this Question, Sign In with Facebook or Sign Up