一般に、数字を使ったパズルは図形や盤を使ったパズルよりも比較的やさしいので、プログラミング入門用の教材に適しています。まずは 小町数 のパズルから始めましょう。
パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を小町数といいます。たとえば、123456789 とか 321654987 のような数字です。小町算 というものもあり、たとえば123+456+789 とか 321 * 654 + 987 のようなものです。
小町数は 1 から 9 までの数字を並べるわけですから、個数は全部で 9! = 362880 個しかありません。現在のように強力なマシンが使える環境では、総当たりで検索しても短時間で答えを見つけることができるでしょう。
最初に鎌田さんから出題された小町算を解いてみます。
問題を提供された鎌田さんに感謝いたします。今回は小町分数 (1) を解きます。使用する言語はどれでもいいのですが、Ｃ言語を使うと M.Hiroi が使っているオンボロマシン (Pentium 166 MHz) でも、あっというまに答えが出るので、あえて Perl を使うことにします。もちろん Lisp や Tcl でもかまいません。プログラムをほかの言語で書き換えてみるのも勉強になると思います。
まずはいちばん単純な、すべての小町数を生成してチェックするという方法を採用します。この方法は 生成検定法 (genarate and test) と呼ばれています。小町数の場合、1 から 9 までの順列を生成すればいいわけです。これはバックトラックを使えば簡単です。プログラムは次のようになります。
リスト：順列の生成
# グローバル変数
@use_flag = ();
@number = ();
# 探索（順列の生成）
sub search {
my $n = shift;
if( $n == 10 ){
&check_answer();
} else {
my $i;
for( $i = 1; $i <= 9; $i++ ){
if( !$use_flag[$i] ){
$use_flag[$i] = 1;
$number[$n] = $i;
&search( $n + 1 );
$use_flag[$i] = 0;
}
}
}
}
とくに難しいところはないはずです。このプログラムが理解できない方は、バックトラックの勉強をしましょう。拙作のプログラミング入門講座も参考になります。次は、生成した小町数が条件を満たしているかチェックするプログラムです。
リスト：条件のチェック
# チェック
sub check_answer {
my $num1 = 0;
my $num2 = 0;
my $i;
for( $i = 1; $i <= 4; $i++ ){
$num1 = $num1 * 10 + $number[$i];
}
for( $i = 5; $i <= 9; $i++ ){
$num2 = $num2 * 10 + $number[$i];
}
if( $num2 == ($num1 * 2) ){
print "Answer $num1, $num2\n";
}
}
問題は 4 桁の数 / 5 桁の数 = 1 / 2 とありますが、ようするに 5 桁の数が 4 桁の数の 2 倍になればいいわけです。生成した小町数は配列 @number に格納されています。これを前半 4 個と後半 5 個の数字に分けます。それぞれの値を変数 $num1 と $num2 に求めて、$num2 が $num1 の 2 倍になれば解答として出力します。結果は次のようになりました。
# プログラムの実行 $start = (times)[0]; &search( 1 ); $end = (times)[0] - $start; print "時間 $end\n";
Answer 6729, 13458 Answer 6792, 13584 Answer 6927, 13854 Answer 7269, 14538 Answer 7293, 14586 Answer 7329, 14658 Answer 7692, 15384 Answer 7923, 15846 Answer 7932, 15864 Answer 9267, 18534 Answer 9273, 18546 Answer 9327, 18654 時間 185.26
解は全部で 12 通りで、時間は約 186 秒かかりました。オンボロマシンなので、さすがにインタプリタでは遅いですね。それでは高速化に挑戦してみましょう。
パズルを生成検定法で解く場合、生成するデータの総数を減らすことができると、実行時間を大幅に短縮することができます。単純に考えると大量のデータを生成しなければならないような問題でも、パズルの特徴や性質を見極めて、データの総数を大幅に減らすように工夫することが大切です。
このパズルでは、与えられた数式から解を満たす数字の範囲を限定することができます。まず、4 桁の数字を考えてみます。この最大値は 9876 ですね。これを 2 倍した値 19752 が 5 桁の数字の最大値となります。1 はいちばん小さな値ですから、5 桁目は 1 に確定することができます。これだけで生成するデータ数は 1 / 9 となります。
今度は、5 桁の数字の最小値 12345 を考えます。これを半分にすると 6172 になります。これより小さな数字では 2 倍しても 5 桁の数字にはなりません。したがって、4 桁目の数字は 6, 7, 8, 9 を調べるだけでいいのです。最後に、5 桁の数字は偶数になることを忘れてはいけません。この 3 つの条件をプログラムに組み込んでみましょう。
リスト：グローバル変数の定義 # グローバル変数 @use_flag = (0,1,0,0,0, 0,0,0,0,0); @number = (0,1,0,0,0, 0,0,0,0,0); @number_list = ( [], # dummy [1], # 5桁 1 に確定ずみ [2,3,4,5,6,7,8,9], # 4 [2,3,4,5,6,7,8,9], # 3 [2,3,4,5,6,7,8,9], # 2 [2,4,6,8], # 1 偶数 [6,7,8,9], # 4 [2,3,4,5,6,7,8,9], # 3 [2,3,4,5,6,7,8,9], # 2 [2,3,4,5,6,7,8,9], # 1 );
配列 @number の構成を変更します。1 から 5 までで 5 桁の数字を表し、6 から 9 までで 4 桁の数字を表します。こうすると $number[1] は 1 となり、あとは $number[2] から $number[9] に入る数字を調べます。次に、新しい配列 @number_list を定義します。この配列には @number に入る可能性がある数字を格納します。Perl 5 からの機能であるリファレンスを使って、配列の中に無名の配列をセットしています。4 桁の数字の 4 桁目が [6, 7, 8, 9]、5 桁の数字の 1 桁目が [2, 4, 6, 8] となります。
Perl のリファレンスはＣ言語のポインタよりも安全で使いやすい、と M.Hiroi は思っているのですが、どうも世間ではポインタと同様に評判があまりよくないようです。ちょっと複雑な処理を行う場合、リファレンスを使うと簡単にプログラムできることが多いので、Perl ユーザーの方はリファレンスをマスターすることをおススメします。
この @number_list から数字を選ぶように、関数 search を書き換えます。プログラムは次のようになります。
リスト：探索
# 探索
sub search {
my $n = shift;
if( $n == 10 ){
&check_answer();
} else {
foreach $i ( @{$number_list[$n]} ){
if( !$use_flag[$i] ){
$use_flag[$i] = 1;
$number[$n] = $i;
&search( $n + 1 );
$use_flag[$i] = 0;
}
}
}
}
for 文で 1 から 9 までループしていたところを foreach で置き換えています。@number_list から数字を格納している配列を取り出し、foreach で数字をひとつずつ取り出して処理しています。ある桁のときには特定の数字から選ぶという処理を、関数 search 内で実現しようとすると、プログラムが汚くなります。条件をデータとして記述することで、プログラムはすっきりとします。仕事をするのは関数だけではありません。データにも仕事をさせましょう。関数 check_answer の修正は簡単なので省略します。
それでは実行してみます。
# プログラムの実行 $start = (times)[0]; &search( 2 ); $end = (times)[0] - $start; print "時間 $end\n";
・・・・ 省略 ・・・・ 時間 10.71
実行時間は約 11 秒ですから約 17 倍の高速化に成功しました。今回のパズルでは、生成するデータ数を減らすことができましたが、データを生成している途中でチェックを入れることで、無駄なデータをカットする方法もあります。これを枝刈りと呼びます。バックトラックを使ってパズルを解く場合、この枝刈りのよしあしによって実行時間が大きく左右されます。パズル固有の性質を良く調べて、適切な枝刈りを考えることが重要になります。このパズルでも、有効な枝刈りがあるかもしれません。
また、小町数を生成してチェックする以外にも方法はあります。たとえば、まず 4 桁の数字を生成し、それを 2 倍して 5 桁の数字を作り、それが小町数となっているかチェックする方法もあります。どちらの方法が速いか、興味のある方は試してみてください。
今度は小町分数 (2) を解いてみましょう。
小町分数 (1) では小町数を生成してチェックするという、もっとも単純な生成検定法を使いました。今度は 4 桁の数字を生成してから 5 桁の数字を計算し、小町数を満たしているかチェックすることにします。
4 桁の数字を生成するプログラムは簡単です。
リスト：4 桁の数字の生成
# グローバル変数
@use_flag = ();
@number = ();
# 探索（順列の生成）
sub search {
my $n = shift;
if( $n == 5 ){
&check_answer();
} else {
my $i;
for( $i = 1; $i <= 9; $i++ ){
if( !$use_flag[$i] ){
$use_flag[$i] = 1;
$number[$n] = $i;
&search( $n + 1 );
$use_flag[$i] = 0;
}
}
}
}
数字を 4 つ選ぶと $n は 5 になるので、関数 check_answer を呼び出してチェックするだけです。小町数のチェックも簡単です。
リスト：条件のチェック
sub check_answer {
my @flag = @use_flag; # コピー
my $num1 = 0;
my $num2;
my $c = 0;
my $i;
for( $i = 1; $i <= 4; $i++ ){
$num1 = $num1 * 10 + $number[$i];
}
$num2 = $num1 * 5 / 4;
foreach $i ( split( //, $num2 ) ){
if( ($i eq '.') or $flag[$i] ){
return 0;
}
$c++;
$flag[$i] = 1;
}
if( $c == 5 ){
print "$num1, $num2\n";
}
}
Perl の場合、数値と文字列は相互に変換されるので、数値を数字に分解するのは簡単です。split で 1 文字ずつ分解し、同じ数字が使われていないか @flag をチェックします。配列にアクセスするときは、数字から数値へ変換されるのでエラーにはなりません。この柔軟性が Perl の人気の秘密でしょう。もっとも、普通のプログラミング言語に慣れているユーザーからすると、気持ちの悪いところかもしれません。
Perl の数値計算は浮動小数点で行われます。割り切れない場合はドット ( . ) が出てくるので、条件を満たしていないことがわかります。使われていない数字が 5 つ揃えば小町数になるので、解として出力します。
実行結果は次のようになります。
9876, 12345 時間 2.31
解はひとつしかなく、実行時間は 2.3 秒でした。いやー、こちらの方が断然速かったですね。生成する数字は 9 * 8 * 7 * 6 = 3024 個しかないので、当然の結果といえるでしょう。このパズルは、解が 12345, 9876 の一通りしかなく数字の並びも面白くて、楽しむことができました。
ところで、このパズルはプログラムを作らなくても答えを求めることができます。小町分数 (1) のように、数式から解を満たす数字の範囲を限定すると、この答えを導くことができます。コンピュータを使わなくても解けるので、一般的な数理パズルとして通用するのではないでしょうか。
次の問題は小町平方数 (1) です。これは小町分数 (2) のプログラムを少し改造するだけで、簡単に求めることができます。生成する数字は 3 桁なので、実行速度はもっと速くなるでしょう。プログラムは省略するので、実際自分で試してみてください。結果は次のようになりました。
567, 321489 854, 729316 時間 0.61
3 桁の数字は 504 通りしかないので、インタプリタでも高速に求めることができます。
次の小町平方数 (2) はちょっとやっかいです。最小値 123456789 の平方根は 11111.1 で、最大値 987654321 の平方根は 31426.9 です。したがって、11112 から 31426 までの数値を 2 乗して、それが小町数になるかチェックすればいいでしょう。それでも 2 万回近くループするので、インタプリタではけっこう時間がかかるはずです。
プログラムは繰り返しで OK です。
リスト：小町分数(2)
# チェック
sub check {
my $num = shift;
my @flag =(1); # 0 は駄目よ
foreach $n ( split( //, $num ) ){
if( $flag[$n] ){
return 0;
}
$flag[$n] = 1;
}
return 1;
}
sub search {
my $num1;
for( $num1 = 11112; $num1 <= 31426; $num1++ ){
my $num2 = $num1 * $num1;
if( &check( $num2 ) ){
print "$num1, $num2\n";
}
}
}
とくに難しいところはないですね。実行結果は次のようになりました。
11826, 139854276 12363, 152843769 12543, 157326849 14676, 215384976 15681, 245893761 15963, 254817369 18072, 326597184 19023, 361874529 19377, 375468129 19569, 382945761 19629, 385297641 20316, 412739856 22887, 523814769 23019, 529874361 23178, 537219684 23439, 549386721 24237, 587432169 24276, 589324176 24441, 597362481 24807, 615387249 25059, 627953481 25572, 653927184 25941, 672935481 26409, 697435281 26733, 714653289 27129, 735982641 27273, 743816529 29034, 842973156 29106, 847159236 30384, 923187456 時間 12.03
解の総数は 30 通りで実行時間は 12 秒となりました。解はもっと少ないと思っていたので意外な結果でした。
小町算の続きです。なお、このページは Memorandum で取り上げたパズル「小町算」をまとめたものです。内容は重複しますがご了承くださいませ。
今度は小町算の中でも一番有名なパズルを解いてみましょう。
1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。
例：1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100
このパズルは xyzzy Lisp の Common Lisp 入門 ちょっと寄り道「小町算と小町数」 で解いたことがあります。そこで、今回は Perl でプログラムを作ってみましょう。Perl を使う場合、式は文字列で組み立てて、それを eval で計算した方が簡単です。プログラムは次のようになります。
リスト：小町算
sub komachi {
my ($n, $expr, $ans) = @_;
if( $n == 10 ){
print "$ans = $expr\n" if eval( $expr ) == $ans;
} else {
foreach $op ( '+', '-', '' ){
$new_expr = $expr . $op . $n;
&komachi( $n + 1, $new_expr, $ans ); # 再帰呼び出し
}
}
}
数字の間に入れる演算子は '+' と '-' と '' です。演算子として空文字列 '' を入れるところがポイントです。本当の演算子ではありませんが、これで数式を組み立てるときに、12 とか 345 のように数字と数字を結合することができます。あとは、次のように関数 komachi を呼び出します。
&komachi( 2, '1', 100 );
とても簡単ですね。'1' のかわりに '-1' を与えれば、- 符号から始まる式でも求めることができます。結果は次のようになります。
&komachi( 2, '1', 100 );
100 = 1+2+3-4+5+6+78+9 100 = 1+2+34-5+67-8+9 100 = 1+23-4+5+6+78-9 100 = 1+23-4+56+7+8+9 100 = 12+3+4+5-6-7+89 100 = 12+3-4+5+67+8+9 100 = 12-3-4+5-6+7+89 100 = 123+4-5+67-89 100 = 123+45-67+8-9 100 = 123-4-5-6-7+8-9 100 = 123-45-67+89
&komachi( 2, '-1', 100 );
100 = -1+2-3+4+5+6+78+9
- 符号から始まる式を含めると、解は全部で 12 通りになります。
それでは、数字を逆順に並べたらどうなるでしょうか。
1 から 9 までの数字を逆順に並べ、間に + と - を補って 100 になる式を作ってください。ただし、9 の先頭に - 符号はつけないことにします。
例：9 - 8 + 7 + 65 - 4 + 32 - 1 = 100この問題も Perl を使って簡単にプログラムを作ることができます。次のリストを見てください。
リスト：逆順の小町算
sub komachi {
my ($n, $expr, $ans) = @_;
if( $n == 0 ){
print "$ans = $expr\n" if eval( $expr ) == $ans;
} else {
foreach $op ( '+', '-', '' ){
$new_expr = $expr . $op . $n;
&komachi( $n - 1, $new_expr, $ans );
}
}
}
関数 komachi を再帰呼び出しするとき、引数 $n の値を -1 します。これで数字を逆順に並べることができます。そして、$n の値が 0 になったら再帰呼び出しを停止して式の値を eval で計算します。とても簡単ですね。結果は次のようになります。
&komachi( 8, '9', 100 );
100 = 9+8+76+5+4-3+2-1 100 = 9+8+76+5-4+3+2+1 100 = 9-8+7+65-4+32-1 100 = 9-8+76+54-32+1 100 = 9-8+76-5+4+3+21 100 = 98+7+6-5-4-3+2-1 100 = 98+7-6+5-4+3-2-1 100 = 98+7-6+5-4-3+2+1 100 = 98+7-6-5+4+3-2+1 100 = 98-7+6+5+4-3-2-1 100 = 98-7+6+5-4+3-2+1 100 = 98-7+6-5+4+3+2-1 100 = 98-7-6+5+4+3+2+1 100 = 98-7-6-5-4+3+21 100 = 98-76+54+3+21
解は全部で 15 通りあります。ちなみに、- 符号から始まる式は次の 3 通りになります。
&komachi( 8, '-9', 100 );
100 = -9+8+7+65-4+32+1 100 = -9+8+76+5-4+3+21 100 = -9-8+76-5+43+2+1
最後にもうひとつ、小町算のパズルを出題しましょう。
どちらの問題もそれほど難しくありません。(A), (B) ともに、解の候補は 20 個程度に絞り込むことができるので、プログラムを作らなくても解けると思います。ここで絞り込む方法は説明しないので、皆さん考えてみてください。
それでは、(A) と (B) の式で割り切れるパターンは何通りあるのでしょうか。プログラムを作って確かめてみましょう。Perl, Lisp, Prolog でプログラミングしてみました。
リスト：小町分数の解法(Perl版）
# 使用した数字
@use_flag = (0, 0, 0, 0, 0, 0, 0, 0, 0, 0);
sub komachi {
my ($n, $m, $p, $q) = @_;
if( $n == 9 ){
if( $p % $q == 0 ){
printf("%d / %d = %d\n", $p, $q, $p / $q );
}
} else {
foreach $i (1..9) {
if( !$use_flag[$i] ){
$use_flag[$i] = 1;
if( $n < $m ){
&komachi( $n + 1, $m, $p * 10 + $i, $q );
} else {
&komachi( $n + 1, $m, $p, $q * 10 + $i );
}
$use_flag[$i] = 0;
}
}
}
}
# 呼び出し
&komachi( 0, 5, 0, 0); # (A)
&komachi( 0, 6, 0, 0); # (B)
リスト：小町分数の解法(Lisp版)
(defun komachi (n l m p q)
(if (atom l)
(if (zerop (mod p q))
(format t "~D / ~D = ~D~%" p q (/ p q)))
(dolist (i l)
(if (< n m)
(komachi (1+ n) (remove i l) m (+ (* p 10) i) q)
(komachi (1+ n) (remove i l) m p (+ (* q 10) i))))))
; 呼び出し
(komachi 0 '(1 2 3 4 5 6 7 8 9) 5 0 0) ; (A)
(komachi 0 '(1 2 3 4 5 6 7 8 9) 6 0 0) ; (B)
リスト：小町分数の解法(Prolog版) komachi( 9, _, _, P, Q ) :- P mod Q =:= 0, N is P / Q, format( '~d / ~d = ~d~n', [P, Q, N] ), fail. komachi( N, L, M, P, Q ) :- N < 9, select( I, L, Rest ), ((N < M) -> (P1 is P * 10 + I, Q1 is Q) ; (Q1 is Q * 10 + I, P1 is P)), N1 is N + 1, komachi( N1, Rest, M, P1, Q1 ). % 呼び出し test1 :- komachi( 0, [1,2,3,4,5,6,7,8,9], 5, 0, 0 ). % (A) test2 :- komachi( 0, [1,2,3,4,5,6,7,8,9], 6, 0, 0 ). % (B)
どのプログラムでも 1 から 9 までの順列を生成し、その過程で分子の数値 p と分母の数値 q を計算します。分子の桁数は m で表しています。どのプログラミング言語でも簡単にプログラムできますね。結果は (A) が 187 通りで (B) が 1602 通りとなりました。
パズルの世界では、1 から 9 までの数字が 1 回ずつすべて登場する数を 小町数 といいますが、これに 0 を加えた数を 大町数 といいます。そして、0 から 9 までの 10 個の数字を 1 個ずつ使った計算を 大町算 といいます。それでは問題です。
0 から 9 までの数字を逆順に並べ、間に + と - を補って 999 になる式を作ってください。ただし、9 の先頭に - 符号はつけないことにします。
例：9 + 8 + 7 + 654 + 321 +(-) 0 = 999ちなみに、小町数の場合は 9 + 8 + 7 + 654 + 321 の 1 通りしかありません。この問題も Perl を使って簡単にプログラムを作ることができます。次のリストを見てください。
リスト：大町算
sub oomachi {
my ($n, $expr, $ans) = @_;
if( $n == -1 ){
print "$ans = $expr\n" if eval( $expr ) == $ans;
} else {
foreach $op ( '+', '-', '' ){
$new_expr = $expr . $op . $n;
&oomachi( $n - 1, $new_expr, $ans );
}
}
}
関数 oomachi を再帰呼び出しするとき、引数 $n の値を -1 します。これで数字を逆順に並べることができます。そして、$n の値が -1 になったら再帰呼び出しを停止して式の値を eval で計算します。とても簡単ですね。
それでは次の問題です。
○に 0 から 9 までの数字を 1 回ずつ入れて式を完成させてください。
（Ａ）○○○＋○○○＝○○○○数字 0 は○の最上位に入れることはできません。□はどんな数字でもかまいません。
プログラムですが、この問題も Perl で簡単に作成することができます。特に難しいところはないので、説明は不要でしょう。プログラムリストをお読みくださいませ。
#
# oomachi.pl : 大町算の解法
#
# Copyright (C) 2002-2005 Makoto Hiroi
#
# 使用した数字
@use_flag = ();
# 解の総数
$count;
# 数字のチェック
sub check {
my $num = shift;
my @flag = @use_flag;
foreach $n ( split( //, $num ) ){
return 0 if $flag[$n];
$flag[$n] = 1;
}
return 1;
}
# 問題 A
sub solve_a_sub {
my ($n, $a, $d) = @_;
if( $n == 3 ){
my $m = $a + $d;
if( $m > 1000 and &check( $m ) ){
$count++;
print "$a + $d = $m\n";
}
} else {
foreach $i (0 .. 9) {
next if $use_flag[$i] or ($n == 0 and $i == 0);
$use_flag[$i] = 1;
&solve_a_sub( $n + 1, $a, $d * 10 + $i );
$use_flag[$i] = 0;
}
}
}
sub solve_a {
my ($n, $a) = @_;
if( $n == 3 ){
&solve_a_sub( 0, $a, 0 );
} else {
foreach $i (0 .. 9) {
next if $use_flag[$i] or ($n == 0 and $i == 0);
$use_flag[$i] = 1;
&solve_a( $n + 1, $a * 10 + $i );
$use_flag[$i] = 0;
}
}
}
# 問題 B
sub solve_b {
my ($n, $a) = @_;
if( $n == 5 ){
foreach $j (2 .. 9) {
my $m = $a * $j;
last if $m > 100000;
if( &check( $m ) ){
$count++;
print "$m / $a = $j\n";
}
}
} else {
foreach $i (0 .. 9) {
last if $n == 0 and $i > 4;
next if $use_flag[$i] or ($n == 0 and $i == 0);
$use_flag[$i] = 1;
&solve_b( $n + 1, $a * 10 + $i );
$use_flag[$i] = 0;
}
}
}
# 問題 C
sub solve_c {
my $num1;
@use_flag = ();
for( $num1 = 31992; $num1 <= 99380; $num1++ ){
my $num2 = $num1 * $num1;
if( &check( $num2 ) ){
$count++;
print "$num2 = $num1 ^ 2\n";
}
}
}
@use_flag = ();
$count = 0;
print "***** A *****\n";
&solve_a( 0, 0 );
print "total = $count\n";
@use_flag = ();
$count = 0;
print "***** B *****\n";
&solve_b( 0, 0 );
print "total = $count\n";
@use_flag = ();
$count = 0;
print "***** C *****\n";
&solve_c();
print "total = $count\n";
999 = 9 + 8 + 7 + 654 + 321 + 0 999 = 9 + 8 + 7 + 654 + 321 - 0 999 = 9 + 8 + 765 + 4 + 3 + 210 999 = 987 + 6 + 5 - 4 - 3 - 2 + 10 999 = 987 + 6 - 5 - 4 + 3 + 2 + 10 999 = 987 - 6 + 5 + 4 - 3 + 2 + 10
246 + 789 = 1035 249 + 786 = 1035 264 + 789 = 1053 ・・・省略・・・ 876 + 429 = 1305 879 + 426 = 1305 879 + 624 = 1503
全部で 96 通り。
83672 / 10459 = 8 83752 / 10469 = 8 84296 / 10537 = 8 ・・・省略・・・ 97062 / 48531 = 2 97230 / 48615 = 2 97302 / 48651 = 2
全部で 94 通り。商が 6 になる場合は無し。
1026753849 = 32043 ^ 2 1042385796 = 32286 ^ 2 1098524736 = 33144 ^ 2 ・・・省略・・・ 9614783025 = 98055 ^ 2 9761835204 = 98802 ^ 2 9814072356 = 99066 ^ 2
全部で 87 通り。