Кости домино

[secrettop]

Привет!
Поступила тема, на которую гугл и яндекс не дали ответа, достаточно странный парадокс, точнее ответ был дан, но в кривоватой форме, о чем позже.
Суть задачи: Написать программу, которая будет брать из мешка случайную кость и класть на "стол", далее брать еще кость и проверять, можно ли составить цепочку(в виде прямой), если кость не подходит, то убирать её обратно в мешок, если ни одна из костей в мешке не подходит, то убирая кости со стола по одной приходить к тому, чтобы можно было завершить цепочку(напр.: убрали одну кость в мешок и начали заново из него брать и нам выпадает такая комбинация чтоб линия продолжала собираться), чтобы не осталось в мешке костей.
Гугл и яндекс мне нашли только один вид программы, которая из данных костей составляет комбинацию, но не умеет самостоятельно выбирать кости и делать откаты.
Вот код:

#include <iostream>
#include <cstdio>
#include <vector>
#include <cstring>
 
using namespace std;
 
bool vis[7];
vector<int> edge_index[7][7];
int degree[7];
 
// can reach v from u?
bool dfs(int u, int v) {
    if (u == v) {
        return true;
    }
    vis[u] = true;
    for (int i = 0; i <= 6; ++i) {
        if ((edge_index[u][i].size() > 0 || edge_index[i][u].size() > 0)
                && vis[i] == false) {
            if (dfs(i, v)) {
                return true;
            }
        }
    }
    return false;
}
 
bool is_connected() {
    memset(vis, 0, sizeof(vis));
    for (int i = 0; i <= 6; ++i) {
        if (degree[i]) {
            dfs(i, -1);
            break;
        }
    }    
    for (int i = 0; i <= 6; ++i) {
        if (degree[i] > 0 && vis[i] == false) {
            return false;
        }
    }
    return true;
}
 
int main (void) {
    int n; // number of dominoes
    scanf("%d", &n);
    memset(degree, 0, sizeof(degree));
    for (int i = 0; i <= 6; ++i) {
        for (int j = 0; j <= 6; ++j) {
            edge_index[i][j].clear();
        }
    }
    for (int i = 1; i <= n; ++i) {
        int u, v;
        scanf("%d%d", &u, &v);
        edge_index[u][v].push_back(i);
        degree[u]++;
        degree[v]++;
    }
 
    int n_odd = 0; // number of nodes
    for (int i = 0; i <= 6; ++i) {
        if (degree[i] % 2 == 1) {
            n_odd++;
        }
    }
 
    if (n_odd > 2 || is_connected() == false) {
        // if number of odd degree node is more 2
        // eulerian path doesn't exist for this graph
        printf("No solution\n");
    } else {
        int u = -1; // starting node
 
        // start node with an odd degree node, if exists
        for (int i = 0; i <= 6; ++i) {
            if (degree[i] % 2 == 1) {
                u = i;
                break;
            }
        }
 
        // if odd degree node not found, start with a node
        // start with any vertex
        if (u == -1) {
            for (int i = 0; i <= 6; ++i) {
                if (degree[i] > 0) {
                    u = i;
                    break;
                }
            }
        }
        // n steps - at each step, remove one
        for (int i = 0; i < n; ++i) {
            int selected_ind;
            bool forward_selected;
            for (int j = 0; j <= 6; ++j) {
                if (edge_index[u][j].size() > 0 ||
                    edge_index[j][u].size() > 0) {
                    int cur_ind;
                    bool forward;
                    if (edge_index[u][j].size() > 0) {
                        cur_ind = edge_index[u][j].back();
                        edge_index[u][j].pop_back();
                        forward = true;
                    } else {
                        cur_ind = edge_index[j][u].back();
                        edge_index[j][u].pop_back();
                        forward = false;
                    }
                    degree[u]--;
                    degree[j]--;
 
                    memset(vis, 0, sizeof(vis));    
                    if (degree[u] == 0 || dfs(u, j) == true) {
                        // remove edge
                        selected_ind = cur_ind;
                        forward_selected = forward;
                        u = j; // so we are in j now.
                        break;
                    } else {
                        // back to previous state
                        if (forward) {
                            edge_index[u][j].push_back(cur_ind);
                        } else {
                            edge_index[j][u].push_back(cur_ind);
                        }
                        degree[u]++;
                        degree[j]++;
                    }
                }
            }
            printf("%d %c\n", selected_ind, forward_selected ? '+' : '-');
        }
    }
 
    return 0;
}

Помогите кто чем может. Кости стандартные, 28 штук, как и в обычной игре, код надо на Си, гугл выдал тот код только на плюсах.