3 ms·
Only if you already know the trick to attack this class of problems.
by danbruc 11y ago
Only if you already know the trick to attack this class of problems.
- semi-extrinsic 11y agoReally? Just by looking at the figure, bruteforcing for a couple of minutes and then noticing a solution which gives the same problem but 6x6 instead of 8x8, I was able to solve this without even pen and paper. Unless you're talking about an extremely abstract class of problems, I don't think that statement is true.
- wolfgke 11y agoNo, it's really that easy: Clearly the complete coverings with dominoes biject to matchings of the graph with vertices = squares and edges defined by 2-sets of squares sharing an edge on the chessboard. Clearly this graph is bipartite, but the two elements of the bipartision are of different cardinality. Thus no perfect matching can exist.