Invariants in Algorithms
8*8사이즈의 체스판에서 대각선으로 마주보는 두 꼭짓점 칸을 제거한 망가진 체스판이 있습니다. 이 체스판을 도미노로 덮을 예정입니다. 도미노는 정확히 체스판의 2칸을 덮습니다.
도미노끼리 겹치거나 망가진 체스판 밖으로 나오지 않도록 하면서 체스판을 완전히 덮을 수 있을까요?
Variables
변수 설정을 먼저 해보겠습니다. 도미노 하나를 덮을 때마다 변화하는 것은 체스판의 칸입니다. 하나를 덮을 때마다 2칸이 사라지고 정확히는 흰 칸과 검은 칸 하나씩 사라지게 됩니다.
여기서 흰 칸을 w, 검은 칸을 b라고 두겠습니다.
도미노를 덮어서 칸을 없애는 것은 w,b := w-1, b-1로 둘 수 있습니다.
Invariants
이 체스판에서 도미노를 덮는 행위를 반복하더라도 절대 변하지 않는 것은 총 체스판의 칸 수가 있습니다. 또 흰 칸과 검은 칸의 차이입니다. w - b = 2이고 이것이 문제의 불변량이 됩니다.
Conclusion
이제 (w - b)[w,b := w-1, b-1] = w - b = 2가 성립하는지 살펴보는 것으로 문제는 해결됩니다.
식을 정리하면 0 = 2가 나오므로 도미노로 체스판을 덮는 것은 불가능함을 알 수 있습니다.
