Java,Cの計算問題についての質問です


○○○○ － ○○○○ ＝ ○○○○

他のサイトにあった問題です。  
この計算の中に０～９の数字を使わなければいけないといった問題です。  
同じ数字を使っても良いです。  
０～９の数字を全て使ってかつ、正しい筆算になるのは何通りなのか求めたいです。

javaかCで解きたいのですが、解き方が浮かびません。  
また、このような問題を解くときに便利なライブラリ等はあるのでしょうか？  
解き方や考え方を教えてください。




正しい筆算ということなので、`4718 - 0023 = 4695`のような式は除外しました。

[code]

    #include <stdio.h>
    
    int digit(int num) {
        int a = num / 1000;
        int b = (num - a * 1000) / 100;
        int c = (num - a * 1000 - b * 100) / 10;
        int d = (num - a * 1000 - b * 100 - c * 10);
        return (1 << a) | (1 << b) | (1 << c) | (1 << d);
    }
    
    int main(void) {
        int cnt = 0;
        int lhs, rhs;
        for (rhs = 1000; rhs <= 9999; ++rhs) {
            for (lhs = rhs + 1000; lhs <= 9999; ++lhs) {
                int ans = lhs - rhs;
                if ((digit(lhs) | digit(rhs) | digit(ans)) == 0x3ff /* 0b1111111111 */) {
                    cnt++;
                }
            }
        }
        printf("%d\n", cnt);
        return 0;
    }
    
[/code]




式をA-B=Cと表すと、

  * Aは0000～9999
  * Bは0000～A
  * CはA-B固定

と限定できます。なお0000や9999のようなぞろ目は残り9文字を使い切れないので実際にはあり得ません。

全ての組み合わせを考慮しても5000万通りぐらいしかありませんので工夫せずに計算してもすぐ終わります。C#でこんな感じに書くと300960通りとなりました。

[code]

    for (int a = 1; a < 10000; a++)
    {
        for (int b = 1; b < a; b++)
        {
            int c = a - b;
            if (c < 0)
            {
                continue;
            }
    
            // 10種類含まれているかの判定
            // C#以外ではこの部分を変える必要がある
            if ((a * 100000000L + b * 10000 + c).ToString("D12").Distinct().Count() == 10)
            {
                count++;
            }
        }
    }
    
[/code]

