与えられた任意の「覆面算」を自動的に解くJavaScriptプログラム

覆面算を総当り法で解くコード。

サンプルの計算式は,abc - cb1 = 100 というもの。書き換え可能。

計算式を入力:<br>
<textarea id="formula" cols="60" rows="10">

// 1-9の間をとる数の個数
head_num = 2;

// 0-9の間をとる数の個数
body_num = 1;

// 数が満たすべき関係式
target_func = function (
	a,c,b // 1-9の間をとる数を最初にまとめて引数とする
){
	return (
		dig2num( a,b,c )
		-
		dig2num( c,b,1 )
		==
		100
	);
};
</textarea><br>
<br>

<input type="button" value="実行" onclick="init()"><br>
<br>

結果表示:<br>
<textarea id="res" cols="20" rows="10"></textarea>


<script>

// 可変長の引数を1ケタずつ並べて整数を作る
var dig2num = function(){
	var sum = 0;
	for( var i = 0; i < arguments.length; i ++ ){
		sum *= 10;
		sum += arguments[ i ];
	}
	return sum;
};


// 1-9の間をとる数(先頭に来るべき数)の再帰
function rec_head( head_i, head_num, body_num, cnt_set ){
	if( head_i < head_num ){
		for( var i = 1; i <= 9; i ++ ){
			cnt_set[ head_i ] = i;
			rec_head( head_i + 1, head_num, body_num, cnt_set );
		}
	}else{
		// 先頭の再帰は終了して,先頭以外の数の再帰へ
		rec_body( head_num, 0, body_num, cnt_set );
	}
}


// 0-9の間をとる数(先頭以外の数)の再帰
function rec_body( head_num, body_i, body_num, cnt_set ){
	if( body_i < body_num ){
		for( var i = 0; i <= 9; i ++ ){
			cnt_set[ head_num + body_i ] = i;
			rec_body( head_num, body_i + 1, body_num, cnt_set );
		}
	}else{
		// 再帰の末尾部分
		
		// 関係式を評価
		if( target_func.apply( this, cnt_set ) ){
			// 解を保管
			answers.push( cnt_set.join(",") );
			document.getElementById("res").value += cnt_set.join(",") + "\n";
		}
	}
}


var answers = [];

// メイン処理
function init(){
	document.getElementById("res").value = "";
	eval( document.getElementById("formula").value );

	var cnt_set = [];
	for( var i = 0; i < ( head_num + body_num ); i ++ ){
		cnt_set.push( 0 );
	}

	rec_head( 0, head_num, body_num, cnt_set );
	
	alert("終了");
}


</script>

実装のポイント

for文で0から9まで,という繰り返しが任意個の変数分だけコーディングされる必要があるわけだが,その部分を再帰を利用してひとまとめに統合・再利用しているところが特徴。

target_funcの中に,変数が満たすべき覆面算の関係式を記述する。

先頭の数字は0にはなれないので,先頭か,そうでないかによって場合わけをしている。

可変長引数の関数をうまく使って,任意の桁並びの整数を表現しやすくしているのもポイント。

実行結果

未知変数の個数が5〜6個ならば楽勝。

// 1-9の間をとる数の個数
head_num = 2;

// 0-9の間をとる数の個数
body_num = 4;

// 数が満たすべき関係式
target_func = function (
	a,c,b,d,e,f // 1-9の間をとる数を最初にまとめて引数とする
){
	return (
		dig2num( a,b,c,d )
		-
		dig2num( c,b,1 )
		==
		dig2num( a, e, f, a )
	);
};

↑これは一瞬で解ける。

算数道場 1・ 数と計算10・虫食い算_その4
http://www.rakugakukobo.com/sansuu/sandojyo/sando_1/sd1_10_h3_04.htm

  • その3_虫食い算・足し算の基本(2)・その5_ 虫食い算のかけ算

しかし,Googleの入社試験あたりになると,未知変数の数が10個ぐらいになって,ブラウザがフリーズする。

var head_num = 3;
var body_num = 6;
var target_func = function (
	w, d, g,
	o, t, l, e, c, m
){
	return (
		dig2num( w, w, w, d, o, t )
		-
		dig2num( g, o, o, g, l, e )
		==
		dig2num( d, o, t, c, o, m )
	);
};

メモリの消費量がみるみる増えていってしまう。

【Book】非公認 Googleの入社試験 | Hyhy's Weblog
https://hyhy.wordpress.com/2009/10/19/%E3%80%90book%E3%80%91%E9%9D%9E%E5%85%AC%E8%AA%8D%E3%80%80google%E3%81%AE%E5%85%A5%E7%A4%BE%E8%A9%A6%E9%A8%93/

  • 次の覆面算を解いてください。もちろん、MとEの値は交換可能です。また、Oが最初にくることはありません。「WWWDOT-GOOGLE=DOTCOM」

また,「1から9までの数字を一回ずつ使う」のような制約条件も組み込みづらい。

マッチング条件式の中に,数値の重複がないことを検査する等式を組み込めば一応実現できる。

しかし,0から9までが10ケタあるとして,合計で10^10通りの数の候補があって,実際には0から9を並び替えた10!通りの候補に絞られるわけなので,マッチングが無駄になる。

総当り処理の候補からもとからはずしておいたほうが効率がよいはず。

覆面算です。□には1〜9までの数字が1回づつはいります。この計算を完成... - Yahoo!知恵袋
http://detail.chiebukuro.yahoo.co.jp/qa/question_detail/q11108510116

  • 覆面算です。□には1〜9までの数字が1回づつはいります。 この計算を完成さることはできますか? ただし、元のひかれる数字はできるだけ小さい数にすること。

改良案

解空間の生成と,マッチング処理を,各1ステップずつ行なうようにしたい。

解空間を最初から全部作っておかないのは,メモリ消費が大きくならないようにするため。

1こ候補を作っては,1個分のマッチング検査を行うようにすればよいはず。


また,今回のコードでは満たすべき関係式をJavaScriptコードの形でevalさせているが,これをもっとコードではない純粋な覆面算の文字列として表記できるようにしたい。

最終的には,電卓のようなボタン形式が一番よい。使いやすいから。

まずは,数式をパースする処理を書くところからだ。


さらに,処理の実行時間が長いとブラウザ上でフリーズが発生するが,それをうまく回避したい。

setTimeoutで細切れにイベントとして処理を時分割する手もあるし,HTML5のworkerでページの裏側に処理を隠すという手もある。

いずれにしても,ブラウザとしての実行だけに限らず,WSH/JScriptでのCUI実行時にライブラリ化できるように条件分岐させたい。

windowが定義されていない状況下ではsetTimeoutを使わないように自動的に分岐させ,GUIモードとCUIモードの両方で使えるようにするということだ。

つづく