Tasks with dominoes at interviews
From personal experience, I can say that tasks that are somehow related to covering dominoes of any surfaces are quite popular at interviews. Conditions may vary, but the essence of all remains one.
There is a chessboard of 8 by 8 cells, the lower left and upper right corners of which are cut off.
Is it possible to completely cover such a board with 2 × 1 square dominoes?
An even number of cells remains on the board (62), so at first glance a solution is possible. However, let's do one very simple thing:
We colorized the cells through one. Now everything is becoming apparent. Each domino can occupy strictly two cells: one white and one black. No other options are given. We look at which cells on the board are cut off - both black, respectively, we have 32 white and 30 black cells and it is not possible to completely cover such a board.
The conditions of the problem can vary, but in general, tasks on the possibility-impossibility are immediately evident.
There is a large 3x3x3 cheese cube consisting of 27 identical cheese and mouse cubes, which, eating one cube, is taken for the cheese cube adjacent to it on the verge. Can a mouse completely eat all the cheese if the central cube is replaced by an inedible dummy?
The task is the same, only in space, and not on the plane. We count the cells: in the initial scenario, this is 14 by 13, after removing the central cube: 14 by 12, and as a result, there is no solution.
The next most popular tasks are counting the number of solutions.
Two boards are given:
2 cells are cut out on each. The number of options for covering dominoes which of the boards more? In both cases, cells of different colors were cut out, so that all the knowledge with the coloring from the previous examples will not help us here. There is not much time for interviewing tasks, so you need to look for some kind of clue. But she is. We exclude from the first option all coatings containing cut out cells of the second board, and from the second option - the first. (If it’s easier to imagine - then we can assume that the cut cells are initially covered with a domino - which cannot be moved, and, obviously, in this way we bring the boards to an identical state and the number of coating options will also be identical). After that, consider the lower corner 3 by 2 cells. In the second embodiment, the lower left cell can be coated in only one way.
The remaining part, with the exception of this angle, is identical, respectively, and the number of coatings is also identical. Thus, for each coating variant of the second board, the coating variant of the first board is compared. However, in the first case, an option is also possible where all the dominoes are located vertically, which does not correspond to any variant of the second board. Consequently, the number of options for covering the board with cells cut in the corner is greater.
Find the number of options for domino coating 2xN cells.
Let it be covered by X (N) methods. Consider the option of covering the upper left cell:
The remaining part in the first case can be covered with X (N-1) methods, and in the second, obviously, X (N-2).
Since all coverage options are listed and none of them will coincide, we obtain the equation X (N) = X (N-1) + X (N-2)
X (1) = 1, X (2) = 2, and X (N) will be equal to N + 1 the number of the Fibonacci sequence.
Write a program that calculates the number of ways to cover a 3xN cell board with dominoes.
I must say right away that perhaps there is also an optimal solution for this example, but here I will move from particular solutions to general ones. In fact, all that is behind such tasks can be represented by a bipartite graph , one of the many vertices of which is black cells, and the other is white. Domino coverage is nothing more than the maximum matching of such a graph. To search for it, various algorithms can be used (for example, Kuhn), with the calculation of the number of options, everything is somewhat more complicated. In any case, this is beyond the scope of this article.
In conclusion, to demonstrate, the implementation of the forehead algorithm in python:
Example 1
There is a chessboard of 8 by 8 cells, the lower left and upper right corners of which are cut off.
Is it possible to completely cover such a board with 2 × 1 square dominoes?
An even number of cells remains on the board (62), so at first glance a solution is possible. However, let's do one very simple thing:
We colorized the cells through one. Now everything is becoming apparent. Each domino can occupy strictly two cells: one white and one black. No other options are given. We look at which cells on the board are cut off - both black, respectively, we have 32 white and 30 black cells and it is not possible to completely cover such a board.
The conditions of the problem can vary, but in general, tasks on the possibility-impossibility are immediately evident.
Example 2
There is a large 3x3x3 cheese cube consisting of 27 identical cheese and mouse cubes, which, eating one cube, is taken for the cheese cube adjacent to it on the verge. Can a mouse completely eat all the cheese if the central cube is replaced by an inedible dummy?
The task is the same, only in space, and not on the plane. We count the cells: in the initial scenario, this is 14 by 13, after removing the central cube: 14 by 12, and as a result, there is no solution.
The next most popular tasks are counting the number of solutions.
Example 3
Two boards are given:
2 cells are cut out on each. The number of options for covering dominoes which of the boards more? In both cases, cells of different colors were cut out, so that all the knowledge with the coloring from the previous examples will not help us here. There is not much time for interviewing tasks, so you need to look for some kind of clue. But she is. We exclude from the first option all coatings containing cut out cells of the second board, and from the second option - the first. (If it’s easier to imagine - then we can assume that the cut cells are initially covered with a domino - which cannot be moved, and, obviously, in this way we bring the boards to an identical state and the number of coating options will also be identical). After that, consider the lower corner 3 by 2 cells. In the second embodiment, the lower left cell can be coated in only one way.
The remaining part, with the exception of this angle, is identical, respectively, and the number of coatings is also identical. Thus, for each coating variant of the second board, the coating variant of the first board is compared. However, in the first case, an option is also possible where all the dominoes are located vertically, which does not correspond to any variant of the second board. Consequently, the number of options for covering the board with cells cut in the corner is greater.
Example 4
Find the number of options for domino coating 2xN cells.
Let it be covered by X (N) methods. Consider the option of covering the upper left cell:
The remaining part in the first case can be covered with X (N-1) methods, and in the second, obviously, X (N-2).
Since all coverage options are listed and none of them will coincide, we obtain the equation X (N) = X (N-1) + X (N-2)
X (1) = 1, X (2) = 2, and X (N) will be equal to N + 1 the number of the Fibonacci sequence.
Example 5
Write a program that calculates the number of ways to cover a 3xN cell board with dominoes.
I must say right away that perhaps there is also an optimal solution for this example, but here I will move from particular solutions to general ones. In fact, all that is behind such tasks can be represented by a bipartite graph , one of the many vertices of which is black cells, and the other is white. Domino coverage is nothing more than the maximum matching of such a graph. To search for it, various algorithms can be used (for example, Kuhn), with the calculation of the number of options, everything is somewhat more complicated. In any case, this is beyond the scope of this article.
In conclusion, to demonstrate, the implementation of the forehead algorithm in python:
from itertools import combinations
# формирование матрици инцидентности опущено для краткости
# оно тривиально
# Например, для доски 2x2 с номерами клеток:
# 1 2
# 3 4
# это:
# mat = [
# [0, 1, 1, 0],
# [0, 0, 0, 1],
# [0, 0, 0, 1],
# [0, 0, 0, 0]
#]
# 1 => 2, 1 => 3, 2 => 4, 3 => 4
# Обратные направления ( напр. 3 => 1 )
# не представляют для нас интереса
N = len(mat)
# создаем итератор со всеми парами вершин
all_edges = combinations(xrange(N), 2)
# фильтруем по матрице инцидентности
edges = [(x,y) for x,y in all_edges if mat[x][y]]
# отфильтровываем все максимальные варианты
matchings = [tuples for tuples in combinations(edges, N/2) \
if len(set(reduce(lambda x, y: x+y, tuples))) == N]
print len(matchings)
# осторожно, сложность O(N!)