ヒント

ちょっとだけ参考になるかもしれないヒントです。 何の障害物のない5 * 5の正方形状に配置されている場合、どこからスタートしても全部塗りつぶせるでしょうか？ 答えは否です。実は塗りつぶせない場合が存在するのですが それを確かめるために下図のような市松模様を考えてみます。

さて上の市松模様でどのタイルにおいても隣接するタイルと異なる色となっていることが分かります。 これによってタイル塗りの経路にしたがって通るタイルの色（以下経路色列）を書き出していくと赤と白が交互に出てくることが分かります。 最初に白のタイルから始めた場合、白赤白赤白赤…白赤白となり白が13個、赤が12個必要になりますが しかし実際のタイルは赤13個白12個であるため矛盾が生じてしまいます。つまり白から塗り始めてすべて塗りつぶすことはできないこと分かります。 赤のタイルから始めた場合は経路色列を書き出していくと赤が13個、白が12個であり矛盾は生じません。 ただしあくまで矛盾が生じないというだけで必ず解けるか否かは別の問題なのですが 5 * 5の正方形状の場合必ず解くことができます。（証明は略しますがすべての赤のタイルでの塗る経路を実際に作るか、またはその経路を作り出すアルゴリズムを示せばOKです。）

一般の場合でも全部で奇数個のタイルを塗りつぶす場合、経路色列は塗り始めのタイルが1個多くなります。 このため奇数個のタイルを塗りつぶす場合、多いほうの色のタイルから塗り始めないと全部塗りつぶすことができません。 また最後に塗るタイルは塗り始めたタイルと同じ色となります。 全部で偶数個のタイルを塗りつぶす場合は経路色列のタイルの色はそれぞれ同じ数になりますので、 どこから塗り始めても問題ありません。最後に塗るタイルの色は塗り始めたタイルとは異なる色になります。

上のことをn * nの正方形状のタイルに当てはめて考えると、 nが奇数の場合は右上の端と同じ色のタイルから塗り始めないといけないことになります。
また下図のように4 * 4の正方形状から1つのセルがタイルでない場合

白のタイルのほうが1枚多いので白から塗り始めなければいけないことが分かります。

ちなみに下の図のように本来赤が塗られている場所が2つ欠けている場合、 白に対して赤が2つ足りないことになります。

この場合はどうやっても塗りつぶすことができません。 このように少なくとも赤と白の色の数の差が1個以内でないと塗りつぶすことはできません。