システムとLSIの設計技術に関する研究会「DAシンポジウム2017」(DA: Design Automation、2017年 8月30日から9月1日に石川県で開催)では、基調講演や招待講演、一般論文発表に加えて、「アルゴリズムデザインコンテスト」(ホームページ)という企画が行われた。同企画は2012年に開始し、今年で6回目となる。

 今年のコンテストでは、昨年に引き続き「ナンバーリンク」(※ナンバーリンクはニコリの登録商標)と呼ぶパズルを三次元に拡張した問題が出題された。参加5チームは出題された問題を解くソフトウエアやハードウエアを会場に持ち込み、制限時間内にどれくらい多くの問題を解けるかを競い合った。

 ナンバーリンクとは、盤面の格子中に配置された同じ数字同士を縦横の線で結ぶパズルである。ただし、1マスに線は1本しか引けず、線は交差してはいけない。このパズルは、LSIやボード上の配線経路を求める「1層配線問題」と親和性が高く、デザインコンテストの問題として企画開始から使われている。

図1●ビア位置が自由な三次元拡張ナンバーリンク。DAシンポジウムの図。

 三次元拡張が行われた昨年のコンテスでは、異なる層間を接続する“ビア”の位置があらかじめ指定されており、使用するビアが決まれば各層では1層配線問題を解くものとなっていた(関連記事)。今年のコンテストでは、ビア位置の指定を無くし、自由に選択できるように問題が拡張された。任意の位置にビアを配置することができ、ビアが異なる層の端点に直接接続されてもよいため、昨年よりも問題の難度が高くなっている(図1)。

図2●ルール違反となるコの字型迂回路。DAシンポジウムの図。

 回答ルールとして、①問題で指定された端点の間を分岐の無い線で接続する、②問題で指定された端点に接続の無い線を引いてはいけないとされており、同じ数字の置かれたマスは接続されているものとみなされる。そのため、同じ層内および層をまたいだコの字型の迂回路があるとルール違反となる(図2)。また、盤面のサイズも最大72×72、層数も最大8まで拡張された。参加者がこれらの拡張に対してどの様に対処するかが見所であった。

この先は会員の登録が必要です。有料会員(月額プラン)は登録月無料!