4つの数字で10を作る

4つの数字と+−×÷を使って10を作るパズルを解くプログラム。
切符の数字や、自動車のナンバープレートの数字などで、きっとやったことがあると思う。

プログラムの考え方は単純で、コンピュータの力にあかせて全ての組み合わせを試してみる、というもの。

・2個の数字から+−×÷で作ることができる全部の数字を列挙する。
・それを使って、3個の数字から作ることができる全部の2個の数字を列挙する。
・それらを使って、4個の数字から作り出すことができる3個の数字を列挙する。
・4個の数字は 3:1 に分ける場合と、2:2 に分ける場合があるので、両方とも試す。
・4個の数字は 0000 〜 9999 だから、たかだか1万通り全部試してみればいい。

ソースコードを文末に貼り付けておきました。phpという言語で書いてあります。

さて、なぜ唐突に10を作る問題を取り上げたかというと、ここ最近囲碁とブログにはまっているrikunora妻が、
ある日、難しいパズルが解けたと言って、この問題を持ちかけてきたからです。
* 10を作る まだ言ってる >> 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で作った記憶があります。
当時、上のやり方を友人から教わり、かなり苦労して作ったあげく、
プログラムを1晩以上ぶっ続けで回し続けてようやく結果が得られたものでした。
今は同じ事がちょっとした合間にできて、答も一瞬にして求まるという、長足の進歩ですねぇ。(おっさんの昔話)


<?php
/**
* 4個の数字から+−×÷を用いて10を作る問題
*/
class	Make10 {

	protected	$Input = array( 0, 0, 0, 0 );	// 入力する4個の数字
	protected	$FinalAns = 10;		// 最後に期待する答、デフォルト=10
	protected	$IsSolved = false;	// 解けたかどうかフラグ、1パターンで探索を打ち切るときに使う
	protected	$TraceStack = array();	// 途中経過を表示するためのスタック
	
	////////////////////////////////////////////////////////////////////
	
	/**
	* 4つの数字を配列にして入力する
	*/
	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;
	}
	
	////////////////////////////////////////////////////////////////////
	
	/**
	* 計算処理の中心部
	* 扱っている数字の個数(0〜4個)によって再帰的に処理を行う
	*/
	protected function	resolve( array $numbers ){
		
	//	if( $this->IsSolved ){	// 1回解けたら打ち切る
	//		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:	// 数字が2個
				$result = $this->twoNumbers( $numbers );
				foreach( $result as $ans ){
					$this->resolve( $ans );	// 再帰呼び出し
				}
				break;
			
			case 3:	// 数字が3個
				$result = $this->threeNumbers( $numbers );
				foreach( $result as $ans ){
					$this->resolve( $ans );	// 再帰呼び出し
				}
				break;
				
			case 4:	// 数字が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;	// 判定誤差
	
	/**
	* 1個の数字の処理
	* 解けたかどうかの判定
	*/
	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;
	}
	
	/**
	* 2個の数字の処理
	* 2個の数字が作り出すことのできる全ての1個の数字を返す
	*/
	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;
	}

	/**
	* 3個の数字の処理
	* 3個の数字が作り出すことのできる全ての2個の数字の組を返す
	*/
	protected function threeNumbers( array $numbers ){
		$result = array();
		
		$a = $numbers[0];
		$b = $numbers[1];
		$c = $numbers[2];
		
		// (ab)c, (bc)a, (ca)b の3通りの組み合わせ
		$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;
	}
	
	/**
	* 3個の数字を(2個,1個)に分けて、2個の数字の組を返す
	*/
	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;
	}

	/**
	* 4個の数字の処理
	* 4個の数字が作り出すことのできる全ての3個の数字の組を返す
	*/
	protected function fourNumbers( array $numbers ){
		$result = array();
		
		$a = $numbers[0];
		$b = $numbers[1];
		$c = $numbers[2];
		$d = $numbers[3];
		
		// 3:1の組に分ける、(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 );

		// 2:2の組に分ける、(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;
	}

	/**
	* 4個の数字を(3個,1個)に分けて、3個の数字の組を返す
	*/
	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;
	}

	/**
	* 4個の数字を(2個,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";
}
/* */

?>