\(2HW\) マスの領域 A, B それぞれの連結性を保ちながら 1 マスずつ変更していき、最終的に A と B を入れ替える方法を構成すればよいです。

公式解説のハミルトン閉路を用いる方法はそのような方法の 1 つですが、ここではハミルトン閉路を用いない方法を紹介します。

以下では A の変化のみを記述し、B は A の補集合となるように自動的に変化するものとします。

はじめに領域 A, B をそれぞれグリッドの上半分、下半分とします。

次に、\(i=1,2,\cdots, H\) の順、その中で \(j=1, 2,\cdots, W\) の順に以下の操作をします。

• 領域 A からマス \((H+1-i, 2W+1-j)\) を削除し、マス \((H+i,W+j)\) を追加する。

この時点で A はグリッドの左半分となっています。

次に、\(i=1,2,\cdots, H\) の順、その中で \(j=1, 2,\cdots, W\) の順に以下の操作をします。

• 領域 A からマス \((i, W+1-j)\) を削除し、マス \((2H+1-i,W+j)\) を追加する。

以上の操作によって A がグリッドの下半分となり、A と B を入れ替える方法が構成されました。