ファイナルファンタジー13-2の「時の狭間」の時計の文字盤(?)のようなものから数字を消していくパズルの、削除手順を探すスクリプト。

2010/12/19追加：

ブラウザで動作するものはこっち。

時の狭間　数字消しパズルの解法検索スクリプト

#!/usr/bin/perl

use strict;
use warnings;

my $list = [{pos => 'A', val => 2},
	    {pos => 'B', val => 3},
	    {pos => 'C', val => 5},
	    {pos => 'D', val => 4},
	    {pos => 'E', val => 2},
	    {pos => 'F', val => 2},
	    {pos => 'G', val => 4},
	    {pos => 'H', val => 1},
	    {pos => 'I', val => 3},
	    {pos => 'J', val => 2}];

sub next_entry_idx {
    my ($list, $idx) = @_;

    my $ent = $list->[$idx];
    my $diff = $ent->{val};

    my $idx1 = $idx - $diff;
    if ($idx1 < 0) {
	$idx1 += @$list;
    }

    my $idx2 = $idx + $diff;
    if ($idx2 > @$list - 1) {
	$idx2 -= @$list;
    }

    if ($idx1 == $idx2) {
	return ($idx1);
    } else {
	return ($idx1, $idx2);
    }
}

sub is_removed {
    my ($stack, $idx) = @_;

    foreach my $i (@$stack) {
	return 1 if $i == $idx;
    }

    return 0;
}

sub remove_entry {
    my ($list, $removed, $idx) = @_;

    push @$removed, $idx;
    if (@$removed == @$list) {
	return 1;		# 全部消せたので終了
    }

    my @next = next_entry_idx($list, $idx);	# 次の針の位置

    foreach my $next_idx (@next) {
	next if is_removed($removed, $next_idx); # 針の先に数字がない

	if (remove_entry($list, $removed, $next_idx)) {
	    return 1;	# 解が見つかっている
	}
	# 次の手順を試す
    }

    # 手詰まり。一つもどる。
    pop @$removed;
    return;
}

sub dump_result {
    my ($list, $removed) = @_;

    foreach my $idx (@$removed) {
	print "$list->[$idx]{pos} ";
    }
    print "\n";
}

sub search {
    my ($list) = @_;

    my $removed = [];	# 削除済みエントリ
    my $i;
    for ($i = 0 ; $i < @$list ; $i++) {
	if (remove_entry($list, $removed, $i)) {
	    print "Found\n";
	    dump_result $list, $removed;
	    return 1;
	}
    }

    return 0;
}

search $list;

スクリプトの$listに文字盤の数字の並びを設定する。例えば以下のような数字の並びになっている場合は、上記スクリプトのように$listを設定すればよい。A〜Jは位置を識別するためにつけた名前で、$listの'pos'に指定する。この例ではアルファベットにしているが、ひらがな等、別になんでもよい。設定する開始位置も12時位置でなくても構わない。

数字の並びの例

スクリプトを実行すると以下のように、数字を消す順番が表示される。

Found
A I F D J B E C H G

A->I->F->..と順番に消していけばよい。

なかなか解けないのでスクリプトを作ったのだが、なんかいい解法があるのだろうか。