レンガの配置問題から4色問題

CodinGameでlevel40に到達

簡易な問題は減り、最期は鬼問ばかり、プログラム的には解けても時間制限で解けない問題の連続

 

 

最後に解いたのは1x2のブロックを長方形w*hに縦横自在に配置できる時

全部で何パターンありますかという問題

https://www.codingame.com/training/medium/paving-with-bricks

 

 

そこから4色で塗り分けられるか4色問題に挑戦したものがこちら

https://colab.research.google.com/drive/1LvYSCMebwikoF-oioDStgESANp8V2FUa?usp=sharing

 

少し難易度をあげるため四方を帝国領（１）にしてみました。

 

塗り分けメインは15行ほど、少しでもランダムパターンになるように+10行

8ｘ9のサイズでも時間がかかるのでその打ち切りルーチンで+5行

 

 

寝て起きて、偶数列で一列にして交互にすれば3色で簡単にできると気がついて

枠をちょっとだけ変えて、3色にしてみる。

意外に塗り分けられそうなことがわかる。

 

レンガなら3色で塗り分けられる説が誕生した。