どうせバックトラックするなら最初からバックトラックしてやれ、ということでperl（結果的に
十分実用的であったｗ）で書いてみた。

@mat=(
1,0,0,　2,3,0,　0,0,0,
0,0,8,　0,6,0,　5,0,0,
0,0,0,　0,0,5,　0,0,8,

0,0,3,　0,0,0,　0,2,9,
0,0,0,　5,0,0,　4,0,0,
9,0,0,　0,0,4,　0,3,0,

0,6,0,　0,0,0,　0,0,0,
0,0,1,　6,0,0,　0,7,0,
8,0,0,　0,7,0,　0,0,4
);　　　
　　　
$t1 = (times)[0];
find(0);

sub find
{
　　　my $k;
　　　my $p=$_[0];
　　　if( $p >= 80) {
　　printdata();
　　　$t2 = (times)[0];
　　　$t3 = $t2 - $t1;
　　　print "$t3 秒\n";
　　exit;
　}

　if( $mat[$p]) {find( $p+1);}
　else {
　　for( $k=1; $k<= 9; $k++) {
　　　if( IsThisOK( $p, $k)) {
　　　　$mat[$p] = $k;
　　　　find( $p+1);
　　　　$mat[$p] = 0;
　　　}
　　}
　}
}

※インテンドの空白が全角になってるので注意