Tech Interview

Chessboard

problem: using 31 dominoes, where one domino covers exactly two squares, can you cover all the empty squares on this chessboard (which has 62 spaces). if so, how? if not, why?   

Solution

i think everyone’s first inclination is to try and figure out how it is possible. then again, if you’ve heard a bunch of these questions before, you usually know that if the question says “if not, why?” or “prove whether its possible or impossible”, you can infer that it is not possible (otherwise, the question usually just asks for the solution).

after awhile fiddling around with the dominoes, you will start to realize that the most obvious solutions are not viable. if you start to think its impossible, think about why.

a reader emailed me telling me that using the picture of the chessboard without the squares colored will result in a very small percentage of people solving the problem. if i use the following picture

a much higher percentage of people will be able to solve the problem. the people who solve the problem using only the grid, usually represent the problem in their heads as the colored board.

still can’t figure it out? using the colored board, remember that a domino always covers a black square and a white square.

if you look at the board, you will see that the two squares missing are both black. this means that for all the squares on the board, each white square has a corresponding black square, except for two white ones. so even if you covered all the black/white pairs, you would still be left with two white squares, which will never be adjacent to each other, no matter how you lay out the dominoes.

Exit mobile version