10 Puzzleを解くプログラムをJavaで作ってみた。

　GoogleのNexus7のCMの「1158で10を作る」パズル(10 Puzzle)を解くプログラムをJavaで作ってみました。(^_^;

　算数チャレンジ
１，１，５，８
＋ − × ÷を用いて、
答えを10にしましょう。

　この前作った「ちょっと前の質問の小町算の類題をJavaで解いてみた。」の記事のところのプログラムで、数字を変えただけですぐに出来てしまいましたが、どうも括弧付けで凄く遅くなっているようなので作り直してみました。
　検索して調べてみたら、2つ目の参考URLより、括弧付けは全部で5パターンしかないようなので、そのことを利用して作ってみましたが、括弧がくどいようなので、括弧が省略できる場合には省略して表示するようにしてみました。(^_^;
　ちなみに、このパズルは、「テンパズル(10 Puzzle)」の他にも、「メイクテン(Make 10)」とか「切符番号の問題」と呼ばれているようです。プログラム名は先頭に数字が使えないようなので、「Make10」の方を採用しました。(^_^;

● Make10_1.java

/*
 * Make10_1.java
 * 
 */

import javax.script.*;

class Make10_1 {
    static ScriptEngineManager factory = new ScriptEngineManager();
    static ScriptEngine engine = factory.getEngineByName("JavaScript");
    
    static double dEval(String sExpr) {
        try{
            return( Double.parseDouble(engine.eval(sExpr).toString()) );
        }catch(Exception e){    // System.out.println(e);
            return( Double.NaN );
        }
    }
    
    static boolean nextRepPerm(int[] p, int n, int r) {
        int cy=1;
        
        for(int i=r-1; i>=0; i--) {
            p[i]+=cy;
            if(p[i]>=n){
                p[i]=0; cy=1;
            } else
                cy=0;
        }
        if(cy==0) return(true);
        return(false);
    }
    // 順列生成
    static boolean nextPerm(char[] p, int n, int r) {
        int i, j;
        char t;
        
        if(r <= 0 || n < r) return(false);
        for(i = r + 1; i <= n-1; i++)
            for(j = i; j >= r + 1 && p[j-1] < p[j]; j--){
                t = p[j]; p[j] = p[j-1]; p[j-1] = t;    // swap(p,j,j-1);
            }
        for(i = n - 1; i > 0 && p[i-1] >= p[i]; i--);
        if(i==0) return(false);
        for(j = n - 1; j > i && p[i-1] >= p[j]; j--);
        t = p[j]; p[j] = p[i-1]; p[i-1] = t;            // swap(p,j,i-1);
        for(j = n - 1; i < j; i++, j--){
            t = p[i]; p[i] = p[j]; p[j] = t;            // swap(p,i,j);
        }
        return(true);
    }
    
    public static String delSpace(String s) {
        return(s.replaceAll("\\s",""));
    }
    
    public static String delBracket(String s) {
        int lpo  = s.length()+1;    // lengthPlusOne
        String r = s.substring(0,lpo-1);
        int len  = r.length();
        char[] t = r.toCharArray();
        
        for(int i = 0; i< len; i++){
            if(t[i]=='('){
                int c = 0;
                for(int j = i+1; j< len; j++) {
                    if      (t[j]=='(') c++;
                    else if (t[j]==')') c--;
                    if (c< 0) {
                        t[i] = ' '; t[j] = ' ';     // ()を外しても
                        String d = new String(t);
                        if(dEval(s)==dEval(d))
                            r = d.substring(0);     // 同じ値なら外す
                        else {
                            t[i] = '('; t[j] = ')'; // 駄目なら戻す
                        }
                        break;
                    }
                }
            }
        }
        return(delSpace(r));
    }
    
    public static void main(String[] args) {
        final String NUM = "1158";      // 要素を昇順にソートしたもの
        final int[] Z = {0,0,0};
        final String OPR = "+-*/";      // nextRepPermのはソート不要
        final String[] BRACKET = {      // 括弧付けは全部で5パターン
            "(%c%c(%c%c(%c%c%c)))",
            "(%c%c((%c%c%c)%c%c))",
            "((%c%c%c)%c(%c%c%c))",
            "((%c%c(%c%c%c))%c%c)",
            "(((%c%c%c)%c%c)%c%c)",
        };
        
        int [] p = (int[])Z.clone();
        char[] o = OPR.toCharArray();
        char[] n = NUM.toCharArray();
        String sExpr="";

        long tm=System.nanoTime();      // Timer Start
        do{    //--- p loop ---//
            n = NUM.toCharArray();
            do{    //--- n loop ---//
                for(String b : BRACKET) { //--- b loop ---//
                    sExpr=String.format(b,n[0],o[p[0]],n[1],o[p[1]],n[2],o[p[2]],n[3]);
                    if(dEval(sExpr)==10)
                        System.out.println(delBracket(sExpr)+"==10");
                }
            }while(nextPerm(n,4,4));
        }while(nextRepPerm(p,4,3));
        
        tm=System.nanoTime()-tm;        // Timer Stop
        System.out.printf("Runtime : %.3f [sec]\n",(double)tm/1e9);
    }
}