4つの数字で10を作る
４つの数字と＋−×÷を使って１０を作るパズルを解くプログラム。
切符の数字や、自動車のナンバープレートの数字などで、きっとやったことがあると思う。
プログラムの考え方は単純で、コンピュータの力にあかせて全ての組み合わせを試してみる、というもの。
・２個の数字から＋−×÷で作ることができる全部の数字を列挙する。
・それを使って、３個の数字から作ることができる全部の２個の数字を列挙する。
・それらを使って、４個の数字から作り出すことができる３個の数字を列挙する。
・４個の数字は 3:1 に分ける場合と、2:2 に分ける場合があるので、両方とも試す。
・４個の数字は 0000 〜 9999 だから、たかだか１万通り全部試してみればいい。
ソースコードを文末に貼り付けておきました。phpという言語で書いてあります。
さて、なぜ唐突に１０を作る問題を取り上げたかというと、ここ最近囲碁とブログにはまっているrikunora妻が、
ある日、難しいパズルが解けたと言って、この問題を持ちかけてきたからです。
* １０を作る まだ言ってる >> https://ameblo.jp/rikunora/entry-12321427106.html
* そんなのググれば… >> https://ameblo.jp/rikunora/entry-12321424248.html
* 3478 >> https://ameblo.jp/rikunora/entry-12321077566.html
『( 3, 4, 7, 8 ) を使って 10 を作れ。』
この答、コンピュータの力を借りずに自力で解くのは、かなり難しい。
自分の頭で解くことは早々にあきらめ、プログラムを走らせると、以下の出力が得られます。
( 3, 4, 7, 8 )
3 4 7 8
1.75 3 8
1.25 8
10
OK
この数字の列を上から読み解いて、
( 3 - 7 / 4 ) * 8 = 10
という解答が得られるわけです。
あっさり解けたように見えますが、コンピュータの力を借りず自分の頭で解くのはかなり大変だったはずで、
rikunora妻には一定の評価を与えないわけにはいきません。
この 10を作るプログラム、元をたどれば今を去る数十年前、まだ rikunora がプログラムというものを覚え立ての頃、
8-bitマイコン上の N-BASICで作った記憶があります。
当時、上のやり方を友人から教わり、かなり苦労して作ったあげく、
プログラムを１晩以上ぶっ続けで回し続けてようやく結果が得られたものでした。
今は同じ事がちょっとした合間にできて、答も一瞬にして求まるという、長足の進歩ですねぇ。（おっさんの昔話）
<?php /** * ４個の数字から＋−×÷を用いて１０を作る問題 */ class Make10 { protected $Input = array( 0, 0, 0, 0 ); // 入力する４個の数字 protected $FinalAns = 10; // 最後に期待する答、デフォルト=10 protected $IsSolved = false; // 解けたかどうかフラグ、１パターンで探索を打ち切るときに使う protected $TraceStack = array(); // 途中経過を表示するためのスタック //////////////////////////////////////////////////////////////////// /** * ４つの数字を配列にして入力する */ public function setInput( array $input0 ){ $this->Input = $input0; } /** * 期待する答をセットする、デフォルト値=10 */ public function setFinalAns( $ans ){ $this->FinalAns = $ans; } /** * 処理実行 */ public function run(){ $this->IsSolved = false; $this->TraceStack = array(); $this->resolve( $this->Input ); return $this->IsSolved; } //////////////////////////////////////////////////////////////////// /** * 計算処理の中心部 * 扱っている数字の個数（０〜４個）によって再帰的に処理を行う */ protected function resolve( array $numbers ){ // if( $this->IsSolved ){ // １回解けたら打ち切る // return; // } // このさい全パターンやってみよう // 結果表示のため、今、試している数字の組を積んでゆく array_push( $this->TraceStack, $numbers ); switch( count($numbers) ){ // 数字の個数で場合分け case 1: $result = $this->oneNumber( $numbers ); if( $result ){ $this->printStack(); // 途中経過を出力 $this->IsSolved = true; // 解けた！ } break; case 2: // 数字が２個 $result = $this->twoNumbers( $numbers ); foreach( $result as $ans ){ $this->resolve( $ans ); // 再帰呼び出し } break; case 3: // 数字が３個 $result = $this->threeNumbers( $numbers ); foreach( $result as $ans ){ $this->resolve( $ans ); // 再帰呼び出し } break; case 4: // 数字が４個 $result = $this->fourNumbers( $numbers ); foreach( $result as $ans ){ $this->resolve( $ans ); // 再帰呼び出し } break; default: print "ERROR: 意図しない数字の個数、". count($numbers) ."個.\n"; exit(); } array_pop( $this->TraceStack ); } /** * スタックの表示 */ protected function printStack(){ foreach( $this->TraceStack as $numbers ){ print "\t"; foreach( $numbers as $num ){ print "$num "; } print "\n"; } } const EPS = 0.00000001; // 判定誤差 /** * １個の数字の処理 * 解けたかどうかの判定 */ protected function oneNumber( array $numbers ){ $result = false; $a = $numbers[0]; // 探していた答と一致するか判定 // if( $a == $this->FinalAns ){ // 誤差を考慮に入れる if( ($a - $this->FinalAns) < self::EPS && ($a - $this->FinalAns) > - self::EPS ){ $result = true; } return $result; } /** * ２個の数字の処理 * ２個の数字が作り出すことのできる全ての１個の数字を返す */ protected function twoNumbers( array $numbers ){ $result = array(); $a = $numbers[0]; $b = $numbers[1]; $ans = $a + $b; $result[0] = array( $ans ); $ans = $a - $b; $result[1] = array( $ans ); $ans = $b - $a; $result[2] = array( $ans ); // 引くには逆順がある $ans = $a * $b; $result[3] = array( $ans ); if( $b != 0 ){ // 0割禁止 $ans = $a / $b; $result[4] = array( $ans ); } if( $a != 0 ){ // 0割禁止 $ans = $b / $a; $result[5] = array( $ans ); // 割るには逆順がある } return $result; } /** * ３個の数字の処理 * ３個の数字が作り出すことのできる全ての２個の数字の組を返す */ protected function threeNumbers( array $numbers ){ $result = array(); $a = $numbers[0]; $b = $numbers[1]; $c = $numbers[2]; // (ab)c, (bc)a, (ca)b の３通りの組み合わせ $idx = 0; // print "Try3: $a, $b, $c \n"; $result3 = $this->threeOrders( $a, $b, $c ); foreach( $result3 as $ans ){ $result[$idx] = $ans; $idx++; } // print "Try3: $b, $c, $a \n"; $result3 = $this->threeOrders( $b, $c, $a ); foreach( $result3 as $ans ){ $result[$idx] = $ans; $idx++; } // print "Try3: $c, $a, $b \n"; $result3 = $this->threeOrders( $c, $a, $b ); foreach( $result3 as $ans ){ $result[$idx] = $ans; $idx++; } return $result; } /** * ３個の数字を(2個,1個)に分けて、２個の数字の組を返す */ protected function threeOrders( $a, $b, $c ){ $result = array(); $result2 = $this->twoNumbers( array( $a, $b ) ); $idx = 0; foreach( $result2 as $ans ){ $result[$idx] = array( $ans[0], $c ); $idx++; } return $result; } /** * ４個の数字の処理 * ４個の数字が作り出すことのできる全ての３個の数字の組を返す */ protected function fourNumbers( array $numbers ){ $result = array(); $a = $numbers[0]; $b = $numbers[1]; $c = $numbers[2]; $d = $numbers[3]; // ３：１の組に分ける、(abc)d, (bcd)a, (cda)b, (dab)c // print "Try4-31: $a, $b, $c, $d \n"; $result += $this->fourOrders31( $a, $b, $c, $d ); // print "Try4-31: $b, $c, $d, $a \n"; $result += $this->fourOrders31( $b, $c, $d, $a ); // print "Try4-31: $c, $d, $a, $b \n"; $result += $this->fourOrders31( $c, $d, $a, $b ); // print "Try4-31: $d, $a, $b, $c \n"; $result += $this->fourOrders31( $d, $a, $b, $c ); // ２：２の組に分ける、(ab)(cd), (ac)(bd) // print "Try4-22: $d, $a, $b, $c \n"; $result += $this->fourOrders22( $a, $b, $c, $d ); // print "Try4-22: $a, $c, $b, $d \n"; $result += $this->fourOrders22( $a, $c, $b, $d ); return $result; } /** * ４個の数字を(3個,1個)に分けて、３個の数字の組を返す */ protected function fourOrders31( $a, $b, $c, $d ){ $result = array(); $result2 = $this->threeNumbers( array( $a, $b, $c) ); $idx = 0; foreach( $result2 as $ans ){ $result[$idx] = array_merge( $ans, array($d) ); $idx++; } return $result; } /** * ４個の数字を(2個,2個)に分けて、２個の数字の組を返す */ protected function fourOrders22( $a, $b, $c, $d ){ $result = array(); $result2A = $this->twoNumbers( array( $a, $b ) ); $result2B = $this->twoNumbers( array( $c, $d ) ); $idx = 0; foreach( $result2A as $ansA ){ foreach( $result2B as $ansB ){ $result[$idx] = array_merge( $ansA, $ansB ); } } return $result; } } //////////////////////////////////////////////////////////////////////// // BEGIN Main $self = new Make10(); $self->setFinalAns( 10 ); /* 特定の数字の組で試す * $self->setInput( array( 9, 9, 9, 9 ) ); if( true == $self->run() ){ print "OK"; } /* */ /* 0〜9999 まで全てを試す */ for( $n=0; $n <=9999; $n++ ){ $m = $n; $a = floor($m / 1000); $m -= ($a * 1000); $b = floor($m / 100); $m -= ($b * 100); $c = floor($m / 10); $m -= ($c * 10); $d = $m; print "( $a, $b, $c, $d )\n"; $self->setInput( array( $a, $b, $c, $d ) ); if( true == $self->run() ){ print "OK"; } print "\n"; } /* */ ?>
