Project Euler 185

题目

Number Mind

The game Number Mind is a variant of the well known game Master Mind.

Instead of coloured pegs, you have to guess a secret sequence of digits. After each guess you're only told in how many places you've guessed the correct digit. So, if the sequence was \(1234\) and you guessed \(2036\), you'd be told that you have one correct digit; however, you would NOT be told that you also have another digit in the wrong place.

For instance, given the following guesses for a \(5\)-digit secret sequence,

90342 ;2 correct
70794 ;0 correct
39458 ;2 correct
34109 ;1 correct
51545 ;2 correct
12531 ;1 correct

The correct sequence \(39542\) is unique.

Based on the following guesses,

5616185650518293 ;2 correct
3847439647293047 ;1 correct
5855462940810587 ;3 correct
9742855507068353 ;3 correct
4296849643607543 ;3 correct
3174248439465858 ;1 correct
4513559094146117 ;2 correct
7890971548908067 ;3 correct
8157356344118483 ;1 correct
2615250744386899 ;2 correct
8690095851526254 ;3 correct
6375711915077050 ;1 correct
6913859173121360 ;1 correct
6442889055042768 ;2 correct
2321386104303845 ;0 correct
2326509471271448 ;2 correct
5251583379644322 ;2 correct
1748270476758276 ;3 correct
4895722652190306 ;1 correct
3041631117224635 ;3 correct
1841236454324589 ;3 correct
2659862637316867 ;2 correct

Find the unique 16-digit secret sequence.

解决方案

本代码基于深度优先搜索寻找答案，枚举的内容是枚举线索中“未确定的正确数位组合”。实现时，使用了嵌套DFS。外层的DFS用于搜索每个线索；内层DFS属于组合枚举，用于寻找“未确定的正确数位组合”。

使用的优化如下：

1. 将每条线索基于正确数量从小到大排序，避免一开始枚举组合的数量过大。
2. 如果遍历到某条线索，发现正确数量太多，那么及时返回。
3. 枚举某条线索的“未确定的正确数位组合”时，忽略那些目前是错误的或者是已经填数的数位。

本题也可以使用meet-in-the-middle思想，或者是模拟退火算法完成。

代码

# include <bits/stdc++.h>
using namespace std;
const int N = 22;
const int M = 16;
const int D = 10;
int vis[M][D] = {0};
int tmp[M];
int A[N][M] = {
        {2, 3, 2, 1, 3, 8, 6, 1, 0, 4, 3, 0, 3, 8, 4, 5},
        {3, 8, 4, 7, 4, 3, 9, 6, 4, 7, 2, 9, 3, 0, 4, 7},
        {3, 1, 7, 4, 2, 4, 8, 4, 3, 9, 4, 6, 5, 8, 5, 8},
        {8, 1, 5, 7, 3, 5, 6, 3, 4, 4, 1, 1, 8, 4, 8, 3},
        {6, 3, 7, 5, 7, 1, 1, 9, 1, 5, 0, 7, 7, 0, 5, 0},
        {6, 9, 1, 3, 8, 5, 9, 1, 7, 3, 1, 2, 1, 3, 6, 0},
        {4, 8, 9, 5, 7, 2, 2, 6, 5, 2, 1, 9, 0, 3, 0, 6},
        {5, 6, 1, 6, 1, 8, 5, 6, 5, 0, 5, 1, 8, 2, 9, 3},
        {4, 5, 1, 3, 5, 5, 9, 0, 9, 4, 1, 4, 6, 1, 1, 7},
        {2, 6, 1, 5, 2, 5, 0, 7, 4, 4, 3, 8, 6, 8, 9, 9},
        {6, 4, 4, 2, 8, 8, 9, 0, 5, 5, 0, 4, 2, 7, 6, 8},
        {2, 3, 2, 6, 5, 0, 9, 4, 7, 1, 2, 7, 1, 4, 4, 8},
        {5, 2, 5, 1, 5, 8, 3, 3, 7, 9, 6, 4, 4, 3, 2, 2},
        {2, 6, 5, 9, 8, 6, 2, 6, 3, 7, 3, 1, 6, 8, 6, 7},
        {5, 8, 5, 5, 4, 6, 2, 9, 4, 0, 8, 1, 0, 5, 8, 7},
        {9, 7, 4, 2, 8, 5, 5, 5, 0, 7, 0, 6, 8, 3, 5, 3},
        {4, 2, 9, 6, 8, 4, 9, 6, 4, 3, 6, 0, 7, 5, 4, 3},
        {7, 8, 9, 0, 9, 7, 1, 5, 4, 8, 9, 0, 8, 0, 6, 7},
        {8, 6, 9, 0, 0, 9, 5, 8, 5, 1, 5, 2, 6, 2, 5, 4},
        {1, 7, 4, 8, 2, 7, 0, 4, 7, 6, 7, 5, 8, 2, 7, 6},
        {3, 0, 4, 1, 6, 3, 1, 1, 1, 7, 2, 2, 4, 6, 3, 5},
        {1, 8, 4, 1, 2, 3, 6, 4, 5, 4, 3, 2, 4, 5, 8, 9}
};
int B[N] = {0, 1, 1, 1, 1, 1, 1, 2, 2, 2, 2, 2, 2, 2, 3, 3, 3, 3, 3, 3, 3, 3};
bool dfs1(int, int);
bool dfs2(int f, int finish, int f1, int cnt, int st, char *neglect) {
    if (f1 == cnt) {
        for (int i = 0; i < M; i++)
            vis[i][A[f][i]]++;
        if (dfs1(f + 1, finish + cnt)) return true;
        for (int i = 0; i < M; i++)
            vis[i][A[f][i]]--;
        return false;
    }
    for (int i = st; i < M; i++) {
        if (neglect[i]) continue;
        tmp[i] = A[f][i];
        if (dfs2(f, finish, f1 + 1, cnt, i + 1, neglect)) return true;
        tmp[i] = -1;
    }
    return false;
}
bool dfs1(int f, int finish) {
    if (f == N) {
        for (int i = 0; i < M; i++) {
            if (tmp[i] == -1) {
                for (int j = 0; j < D; j++) {
                    if (vis[i][j] == 0)
                        tmp[i] = j;
                }
            }
        }
        return true;
    }
    int cnt = B[f];
    for (int i = 0; i < M; i++)
        cnt -= (A[f][i] == tmp[i]);
    if (cnt < 0)return false;
    char neglect[M] = {0};
    for (int i = 0; i < M; i++)
        if (tmp[i] != -1 || vis[i][A[f][i]]) neglect[i] = 1;
    if (dfs2(f, finish, 0, cnt, 0, neglect)) return true;
    return false;
}
int main() {
    memset(tmp,-1,sizeof(tmp));
    dfs1(0, 0);
    string ans;
    for (int i = 0; i < M; i++)
        ans += char('0' + tmp[i]);
    cout << ans << endl;
    return 0;
}