ナンプレ自動解法に不可欠
ナンプレをコンピュータに解かせる方法を追求しています。現在、6個の有名な解法のJavaScriptプログラミン化がほぼ完成し、新聞や解説書に載っている平易な課題の正答を得るまでになりました。ちょっとひねった課題はもっと多くの解法を組み込む必要があります。
今、7番目にXY-WING法を織り込むべく四苦八苦しています。何故、XY-WING解法かというとある参考資料に載っている課題を解くにはXY-WINGが必要という単純な理由です。
XY-WINGのアルゴリズムを整理してプログラミングに至るには組み合わせについてもっと深く理解しておくことが大切でありました。遅ればせながらおさらいします。
課題の空マス数にもよりますが81個のマスの内、空きマス数が50台であれば、空きマスの候補数は多くて5～6個程です。この6個の数字から2つを選んで関連を極めて候補数を1に近づける手法が解法と言えます。
決められた数(n)の中から一定数(r)を選ぶ組み合わせを求める一般式を図に表しました。
2番目の式は階乗演算子を使わない表現で（nから数を下げながらr個のかけ算）を（1から数を上げながらr個のかけ算）で割って求めることができます。
分子は数を下げる始値は(n-0)であるので終値は(n-r+1)になります。
ナンプレを解くには組み合わせ数の他に組み合わせそのものが必要です。数が4種であっても1234だけでなく2579などのように連番でない数を扱います。このような場合、サイズ4の配列に数を埋め込みます。
組み合わせをすべて出力
存在するかを証明するには、存在例を１つ挙げればよい場合がありますが、存在しないことを証明するにはすべてをチェックする必要があります。
ナンプレでは空白マスを埋めるには、当初、9つあった候補数を1つに絞ることに帰着します。
ナンプレを解くには候補数から2つを選び他のマスとの関連を調べて候補数を1つずつ減らしていきます。
ナンプレの候補数の最大値は9ですが初期ヒント数は20～30、言い換えて残マスが61～51程度の課題が多いので6個以下になることが多いです。よって6個から2つ選ぶ事象を研究することにします。
この方式の利点
候補数やまとめ文字数の組み合わせはかなりの数になります。ここでは必要な情報を必要なタイミングで生成するのでメモリの節約を図っています。
動作結果
以下には2～6種の数から2文字を選ぶ組み合わせを算出して表示しています。数字は2桁であれば1と2、6桁ならば1～6としています。そのあとで文字列の中に指定された2文字が含まれるかを検索しています。一つは2つ合わせて検索し、もう一つは1つずつ検索する関数を用意し、算出結果を表示しています。
サンプルコード
<!DOCTYPE html>
<html>
<head>
<meta charset="UTF-8">
</head>
<textarea id="msg" style="width:1100px; height:450px; font-size:14px; overflow-y:scroll;"></textarea>
<img style="margin-left:200px; margin-top:-480px; opacity:0.6;" src="https://1.bp.blogspot.com/-gARR6ehVBP8/UZB6YR-tXBI/AAAAAAAASCo/fZGPc8JEd6w/s800/search_mushimegane.png" width="381" height="440">
<script type="text/javascript">
const searchResult = ["2つは含まれない", "2つ含まれる"];
const searchStatus = ["1つも含まれない", "1つ含まれる", "2つ含まれる"];
const combination = (nums, k) => { //numsで指定された文字からk文字を選ぶ組み合わせ配列を求める
let ans = []; //1,2,3,4 ===> 1,2 1,3 1,4 2,3 2,4 3,4
if(nums.length < k) {return [];}
if(k === 1) {
for(let i=0; i<nums.length; i++) {ans[i]=[nums[i]];}
} else {
for(let i=0; i<nums.length-k+1; i++) {
let row=combination(nums.slice(i+1), k-1);
for(let j=0; j<row.length; j++) {ans.push([nums[i]].concat(row[j]));}//ここで指定された文字からk文字を選ぶ
}
}
return ans; //配列の数が算出されたnCr組み合わせ数
}
//最大6文字から2文字を選ぶ組み合わせ
for(var i=2; i<=6; ++i){ //選択文字列から組み合わせ表を作る
var w=genArray(i); //6 1234 [1,2],[1,3],[1,4],[2,3],[2,4],[3,4]
debugOut(letter7(w[1])+letter3(w[0])+" "+i+"C2="+w[2]);
}
debugOut("\n使用例（2つ合わせた状態）");
search2n("235", "24");
search2n("12346", "36");
search2n("3561", "51");
search2n("3521", "46");
search2n("914327", "36");
search2n("12356", "41");
debugOut("\n使用例（1つずつの状態）");
search2m("235", "24");
search2m("12346", "36");
search2m("3561", "51");
search2m("3521", "46");
search2m("914327", "36");
search2m("12356", "41");
function genArray(i){ //組み合わせ配列を生成
var t=0; //配列全体の値
var number=new Array(i); //配列を定義し初期化する
for(var j=0; j<i; ++j){number[j]=j+1; t=t*10+(j+1);}//1, 2, 3, 4, 5, 6
var ary = combination(number, 2);
var v=JSON.stringify(ary); //ary全体
var w=v.substr(1).substr(0,v.length-2); //最外側の[と]を削除した配列中身
return [ary.length, t, w]; //6 1234 [1,2],[1,3],[1,4],[2,3],[2,4],[3,4]
}
//指定された文字列に2文字が2つ含まれているか検索する関数
function search2n(string6, chr){ //2つ含まれる:1、そうでない（1つ含まれているorまったく含まれていない）:0
var yn = string6.indexOf(chr.substr(0,1))>=0 && string6.indexOf(chr.substr(1,1))>=0 ? 1 : 0;//2つ含まれる場合:1
debugOut(string6+" に "+chr+" が"+searchResult[yn]);
return yn;
}
function search2m(string6, chr){ //2つ含まれる:2、1つ含まれる:1、1つも含まれない:0
var status = new Array(0,0,0,0,0,0,0,0,0,0); //初期値:0
for(var i=0; i<string6.length; ++i) status[string6.substr(i,1)-0]=1;
var yn = status[chr.substr(0,1)-0] + status[chr.substr(1,1)-0]; //2つの状態 : 0 1 2
debugOut(string6+" に "+chr+" が"+searchStatus[yn]);
return yn;
}
function debugOut(p1){
var s=p1+'\n';
document.getElementById("msg").innerHTML += s;
console.log(s);
}
function letter3(n){return (" "+n).slice(-3);} <!-- send ' 1' -->
function letter7(n){return (" "+n).slice(-7);} <!-- send ' 123456' -->
</script>
</html>
さいごに
指定された組み合わせをダイナミックに求めすべてを明らかにし、ナンプレで利用する検索例を表示しました。ナンプレを解くには高校で習った数学が役に立ちます。
当時の教科書はもうないのでネット上でおさらいしました。ゆくゆくは世界でもっとも難問と掲げる右のような問題を解けるように頑張っています。