Puzzle - kyoupuro @ ウィキ

0043 :

問題文

解説

パズルを完成させることができる数字を答える。
最初に同じ数字を2個抜き出してから、残りの数字でパズルが完成するかどうかを全探索で調べればいい。
今どの数字が何個残っているかを記憶しておくといい。

プログラム

C

C++

...

#include <iostream>
#include <string>
#include <vector>
using namespace std;
 
bool flag;
 
void solve(char id, int n[]) {
    int cnt = 0;
    for (char i = '1'; i <= '9'; i++) {
        if (n[i] == 0) cnt++;
    }
 
    if (cnt == 9) {
        flag = true;
        return;
    }
 
    while (!n[id]) id++;
     
    if (n[id] >= 3) {
        n[id] -= 3;
        solve(id, n);
        n[id] += 3;
    } else if (id <= '7' && n[id] >= 1 && n[id+1] >= 1 && n[id+2] >= 1) {
        n[id]--;
        n[id+1]--;
        n[id+2]--;
        solve(id, n);
        n[id]++;
        n[id+1]++;
        n[id+2]++;
    } else {
        return;
    }
}
 
int main() {
    string s;
    while (cin >> s) {
        int n[256] = {0};
        vector<char> ans;
        for (int i = 0; i < s.size(); i++) {
            n[s[i]]++;
        }
 
        for (char i = '1'; i <= '9'; i++) {
           if (n[i] == 4) continue;
 
           flag = false;
           for (char j = '1'; j <= '9'; j++) {
                if (flag) break;
 
                int w[256];
                for (char k = '1'; k <= '9'; k++) {
                    w[k] = n[k];
                }
                w[i]++;
 
                if (w[j] < 2) continue;
                w[j] -= 2; // 最初に2つの同じ数字のペアを抜き出す
 
               solve('1', w);
            }
 
            if (flag) ans.push_back(i);
        }
 
        if (ans.size() == 0) cout << '0' << endl;
        else {
            cout << ans[0];
            for (int i = 1; i < ans.size(); i++) cout << ' ' << ans[i];
            cout << endl;
        }
    }
     
    return 0;
}

Java