デレぽ（2019.12.21）に登場したクロスワード（ナンクロ）をコンピュータに解かせた

シンデレラガールズ

※2020.1.23 プログラムを修正（正しい結果が得られていなかった。名前として成立しているかにチェック漏れがあった）

経緯

2019年12月21日に、デレステの「デレぽ」に現れた問題。

「シンデレラガールズのアイドルの姓か名しか入らない」という制約があるので、プログラムにするのにはそれほど困りませんでした。

ソースコード

少量のソースコード共有 & その場でそれを実行できるサービス「Wandbox」に上げてあります。Rubyで書いています。
ページ下部の黒いウィンドウが実行結果で、その末尾の「[Info] Solved!」以降が最終的な解です。
「Run (or Ctrl+Enter)」ボタンでプログラムの実行もできます。
https://wandbox.org/permlink/Kbnmvd9ymaa3jCsi

データ確保

今回もim@sparql様にお世話になっております。かな表記のデータもあるのでそのまま使いました。ただ「姓+名」という形をしていないアイドル名もあるため、そこは注意して取得する必要がありました。具体的には、姓や名はデータが存在しなくてもよいとするために「OPTIONAL」を付けています（名前全体のかな表記を表す「imas:nameKana」は必ず存在する）。

SELECT ?n ?f ?g WHERE {
  ?i rdf:type imas:Idol;
     imas:Title "CinderellaGirls"@en;
     imas:nameKana ?n.
  OPTIONAL{ ?i imas:familyNameKana ?f }
  OPTIONAL{ ?i imas:givenNameKana ?g }
}

プログラムの方針

単純なバックトラック探索（候補が複数ある場合は、そのうち複数をすべて試し、条件が満たせないと確定したら打ち切る）です。 効率化のため、「行ないし列のうち、候補が複数あるものが二つ以上残っている場合は、その中で候補数が最も少ないもののみ次に試す」という方針を採用しています。例えば、

  • 探索1回目。15の行・列のうち13がまだ残っている。このうち入る名前の候補数が最小なのは「7 8 5 9」という行（これは一つしかない）なので、そこを確定させる。
  • 探索2回目。15の行・列のうち12がまだ残っている。このうち入る名前の候補数が最小なのは「5 9 11」という列で（二つの名前が該当する）*1、ここを二通りとも試す。

という具合に進んでいきます。

*1:実際には「12 8 15」という列も、該当する名前が二つだけである