Cracking The Coding Interview/Q 6.2

From Software Engineers Wiki
Jump to: navigation, search

There is an 8x8 chess board in which two diagonally opposite corners have been cut off. You are given 31 dominos, and a single domino can cover exactly two squares. Can you use the 31 dominos to cover the entire board? Prove your answer (by providing an example or showing why it's impossible).

Answer

This is a chess board, each square has color of either white or block, and all squares sharing the border have opposite color. Two diagonally corners were cut off, this means two squares got cut off, the these two squares should have same color. We want to cover this chess board with 2 square domino. When covering the board, one square covers white and the other square covers black. That is, there should be equal number of black and white square to cover entire board. But with two squares with same color got cut off, this condition is not met. Thus it is not possible to cover entire board.

Personal tools
Namespaces

Variants
Actions
Navigation
Toolbox