『マッチ棒の一筆書き』

藤村幸三郎氏の発案による問題だそうです。

図のようなマス目の線の上にマッチ棒を置いていきます。
マッチ棒は一筆書きのように繋がっており、しかも２本以上直線になってはいけません。
（つまり１本ごとに向きを変えます。）
線が交わってもいけません。

１×１２×２３×３

３本６本１３本

【問題１】

４×４では最大何本置けるでしょうか。

【問題２】

５×５では最大何本置けるでしょうか。

【問題３】

６×６では最大何本置けるでしょうか。

【課題】

ｎ×ｎの一般解は存在するでしょうか？