バックトラックでクイズを解いてみた

ようやく時間が取れるようになったのでレイトン教授の問題を解いてみた．1から8の数字を使って，3桁x1桁=4桁が成り立つような組み合わせを見つけるという問題．
なんか普通に見つける時間とプログラムする時間が同じくらいかかりそうだったから，プログラムすることにした．

これくらいなら枝狩りするまでもない，普通のバックトラックもとい総当りプログラム完成．

ハッシュをつくって，ある数字がどの深さ（桁）で使われているかという値を保持している．うーん，これでやると数字にするのが面倒くさい．そのことに気がついたときにはほとんど書き終わってた．うまく動かなくて30分くらいかかった．プログラムを動かしてちゃんと2つの答えが出てきて終了．ピカレットゲッツ！

timeで測って1.5secくらい．
きちんと枝狩りする場合，5桁目から条件入れるんだろうなぁ．この手の問題はPrologが得意そうだけど，Prolog書けないし，よくわからん．

#!/usr/bin/perl
use strict;
use warnings;

# Solving layton problems
my %hash = ();
solve(\%hash, 1);

sub solve{
  my ($hash_ref, $depth) = @_;

  if($depth == 9){
    is_correct($hash_ref);
  }else{
    for(my $i = 1; $i <= 8; $i++){
      next if (exists $hash_ref->{$i});
      my %new_hash = %$hash_ref;
      $new_hash{$i} = $depth;
      solve(\%new_hash, $depth + 1);
    }
  }
}

sub is_correct{
  my ($hash_ref) = @_;
  my ($n1, $n2, $ans) = (0, 0, 0);
  while( my ($key, $val) = each %$hash_ref){
    if ($val <= 3){
      $n1 += $key * (10 ** (3 - $val));
    }elsif ($val == 4){
      $n2 = $key;
    }else{
      $ans += $key * (10 ** (8 - $val));
    }
  }

  # If the answer is correct
  if ($n1 * $n2 == $ans) {
    print "$n1 \* $n2 = $ans\n";
    return 1;
  }
  return 0;
}