문제의 요지를 다시 정리하면, 체스보드에서 하나의 동전만 뒤집어서 특정 칸을 지칭하게 하는 것이다. 다시 말해, 64칸 체스보드 상태가 한 칸만 다른 체스보드 상태끼리 연결된 무향 연결 그래프 위의 각 노드에 64개의 값을 매핑시키는 적당한 함수를 찾고, 어떤 체스보드 상태도 64개의 매핑된 함수값이 모두 인접해 있음을 보이면 된다.
체스보드의 동전은 0 또는 1에 매핑되므로 체스판의 상태는 64비트 정수로 표현된다. 이때 각 비트의 주소는 8비트 주소이다.
8비트 주소의 자리값이 1 (또는 0)인 체스 칸들에 대해 패리티 체크를 진행하면 8비트 정수가 매핑된다. 즉, 64비트 정수를 8비트로 매핑하는 함수이다.
매핑 함수 F를 가정하고 우리가 원하는 체스보드 칸에 해당하는 8비트 정수 A, 현재 체스보드 상태 64비트 정수 B에 대해 (A XOR F(B)) XOR F(B) = A임을 이용할 수 있다. 우리는 동전을 뒤집은 뒤 체스보드 상태가 A가 되기를 원하는 것이고, F는 동전을 한 번 뒤집는 것으로 XOR 연산이 수행된다. A XOR F(B)는 계산할 수 있는 수이므로 A XOR F(B)에 해당하는 동전을 뒤집으면 이후 상태가 A가 되어 해결.
원래 내가 문제 냈을 때는 해밍 코드의 패리티 비트를 설정하는 비용+에러 비트를 발생시키는 비용으로 전체 칸 수의 로그만큼 뒤집을 기회를 줬는데 패리티 비트 자체로 칸을 표현하니까 하나로 충분하네
