Problem mit Lösen von Domino

Hallo,
ich habe mir folgende Funktion geschrieben, um ein klassischen Domino zu lösen (dabei sei jetzt mal außen vorgelassen, dass man den Stein auch drehen kann).

struct Stone {
	unsigned left, right;
	bool used;
};

bool Search(unsigned pos, unsigned goal, std::vector<Stone>& stones, std::vector<unsigned>& output) {
	if (pos == 0) {
		for (std::size_t i = 0; i < stones.size(); ++i) {
			if (!stones[i].used) {
				output.push_back(i);
				stones[i].used = true;
				++pos;
				return false;
			}
		}
	} else if (pos < goal) {
		unsigned number = stones[output.back()].right;
		for (std::size_t i = 0; i < stones.size(); ++i) {
			if (!stones[i].used) {
				if (stones[i].left == number) {
					output.push_back(i);
					stones[i].used = true;
					++pos;
					return false;
				}
			}
		}
		// kein passenden Stein gefunden
		output.pop_back();
		--pos;
		return false;
	}
	return true;
}

Aufrufen tu ich die Funktion so:

while(!Search(0, stones.size(), stones, output);

Nun habe ich aber das Problem, dass die Funktion nicht funktioniert, da wenn zwei mal kein passender Stein gefunden wurde, eigentlich der erste Stein wieder als unused markiert werden müsste. Nun weiß ich aber nicht, wie ih das da geschickt einbringen kann, könnt ihr mir da helfen?

SeppJ

Ich sehe da zwei Strategien, das technisch umzusetzen:
a) Du orientierst dich an der Realität: Das heißt kein used-Flag, sondern ein Stein den du anlegst, der wird tatsächlich aus deinem Steinvorrat entfernt. Wenn du einen Stein von der Kette entfernst, dann wird er dem Steinvorrat wieder zugefügt.
b) Wenn du dein Programm retten willst: Du könntest erst einmal nur Verweise (Zeiger) auf die benutzten Steine benutzen. Auf die Weise kannst du beim Entfernen eines Steins aus der fertigen Kette auf den Stein zugreifen und sein used-Flag ändern.

Ich würde a) machen.

Zu a)
da habe ich doch das Problem, dass wenn ich einen Stein entferne, ich mir ja irgendwie merken muss, ob er schonmal benutzt wurde oder nicht.
Sagen wir mal ich habe die Kette A-B-C-D so jetzt entferne ich D und gehe alle Steine durch, die an C dran können. Als erstes würde wieder D drankommen. Wenn ich jetzt für die Steine eine queue nehme, dann habe ich aber das Problem, dass ja dann nicht weiß wann ich einmal alle durch bin.

Zu b)
Was ist denn der unterschied zwischen einem Verweis, oder einem Index für den Steinvektor? Das Problem ist eben, dass wenn ich in der Kette A-B-C-D C und D entfernen will, nur bei D das used-Flag wieder auf false gesetzt werden soll. Wenn ich jetzt bei jedem Stein, den ich wieder entferne ach das used-Flag aus false setzte bekomme ich einfach eine Endlosschleife.

Niemand eine Idee?

bool Search(unsigned& pos, unsigned goal, unsigned& nextToLast, std::vector<Stone>& stones, std::vector<unsigned>& output) {
    if (pos == 0) {
        for (std::size_t i = 0; i < stones.size(); ++i) {
            if (!stones[i].used) {
                output.push_back(i);
                stones[i].used = true;
                ++pos;
                nextToLast = -1;
                return false;
            }
        }
    } else if (pos < goal) {
        unsigned number = stones[output.back()].right;
        for (std::size_t i = 0; i < stones.size(); ++i) {
            if (!stones[i].used) {
                if (stones[i].left == number) {
                    output.push_back(i);
                    stones[i].used = true;
                    ++pos;
                    nextToLast = -1;
                    return false;
                }
            }
        }
        // kein passenden Stein gefunden
       if (nextToLast >= 0)
            used[nextToLast] = false;
        nextToLast = output.back();
        output.pop_back();
        --pos;
        return false;
    }
    return true;
}

So ich hab die Suchfunktion jetzt mal so geändert, dass sich immer das vorletzte entfernte Element gemerkt und ggf. gelöscht wird. Jedoch läuft auch hier die Schleide nicht ganz durch. Ideen?