Q:

Calendar scheduling: wait time between games

I am working on a sports scheduling algorithm with several different constraints, one (two) of them being a minimum and/or maximum wait time between games. Of the same team, that is.
So if Team Blue is scheduled at 4pm (finishes at 5pm) in Field 1, and we have a maximum wait of 3 hours and a minimum of 1, then its next game ought to be scheduled:

between 6pm and 8pm, or
between 12pm and 2pm

Visually, where M is the scheduled match we are talking about and X the eligible slots:
 +------+------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
 | 11am | 12pm | 1pm | 2pm | 3pm | 4pm | 5pm | 6pm | 7pm | 8pm | 9pm |
 +------+------+-----+-----+-----+-----+-----+-----+-----+-----+-----+
 |      | X    | X   | X   |     | M   |     | X   | X   | X   |     |
 +------+------+-----+-----+-----+-----+-----+-----+-----+-----+-----+

This constraint is tricky because every time a new game is scheduled, two new limitations are posted: one for each team making up the game.
The scenario where this calendar scheduling algorithm is used is having a list of games (i.e. round-robin) that need to be assigned any of the available slots. A slot is made up of a field, a start date and an end date. An example competition would be:

Weekend Tournament: 8 teams playing a double round-robin (14 games
  each). The Club provides 3 fields and is open Saturday all day
  (9am-9pm) and Sunday morning (9am-14pm). Additional constraints may be
  posted.

The current scheduling algorithm works in a very non-complicated way: it iterates the list of matches and attempts to schedule it in the first eligible slot.
for game in games:
    for slot in slots:
        if eligible(game, slot):
            schedule(game, slot)

In practice the algorithm does more things, aiming at different targets, but this is the essence of the way it operates.
If not all games could be scheduled (due to constraints), an additional process is started to try to improve the result. Since these games could not be scheduled in open slots, we look at used slots. If any of these slots is eligible, we try to reschedule the other game currently occupying it, first looking at open slots, then at used slots (the process is repeated until a certain depth). If that other game is rescheduled, the former slot is now open and given to the unscheduled game. 
Perhaps the pseudocode gives a better picture:
for unscheduled_game in unscheduled_games:
    for used_slot in used_slots:
        if eligible(unscheduled_game, used_slot) and (reschedule(used_slot.game, open_slots) or reschedule(used_slot.game, used_slots)):
            schedule(unscheduled_game, used_slot)

And that is about it. The point of this post is trying to figure out ways to try to handle the wait time constraint. It is a really punishing constraint, and is a huge detriment to the effectiveness of the algorithm. 
What is the aim of this post? Looking for suggestions, known scheduling algorithms, anything that could help me work with the minimum/maximum wait time constraint. 
I need to implement this solution on top of the existing algorithm, so constraint programming would not be a feasible solution (pun not intended) because it would require modelling and reformulating the problem entirely from scratch, and I don't have the resources for that.
Introducing a scoring function would not work either. Right now constraints work in a black-or-white type of way: either you pass them or you do not. There are no greys.
I would like to add that I have been trying ways to solve it myself, but none were successful. One of them is:
For each unscheduled game, we look at any eligible slot, ignoring the wait time constraint. Then we try to eliminate the "block" by rescheduling the games that are causing it. If we can reschedule all of them, the conflict disappears and the slot now becomes eligible for the game, effectively scheduling it. In pseudocode:
for unscheduled_game in unscheduled_games:
    for slot in slots:
        if eligible(unscheduled_game, slot, except=WAIT_TIME):
            conflicting_games = find_conflicts(unscheduled_game, slot, constraint=WAIT_TIME)
            if all([reschedule(g) for g in conflicting_games]):
                schedule(unscheduled_game, slot)
                break

But as I said, this is not very helpful. No improvement is observed whatsoever, because rescheduling the conflicts is very hard. I think this happens for the same reasons the unscheduled games could not be scheduled in the first place. The constraint block is too tight and too spread.
Lastly, I want to add that I am working in Python. Mentioning it in case this is relevant at all.

A:

A simple way of approaching this in a pragmatic manner could be:

allow games to be scheduled initially on slots violating the contraints, so you can start with a schedule where each game gets a slot
afterwards run an evolutionary algorithm like simulated annealing to minimize a score which measures the "degree of constraint violation". 

This approach requires a simple modification operation, which could be something like exchanging the content of two randomly chosen slots.
Measuring the degree of violation should be quite simple in your case: just sum up the waiting hours of each team which are over the allowed maximum, or under the allowed minimum. If that sum reaches 0, your algorithm found a solution and can be stopped immediately.
This is not a 100% algorithm, not guaranteeing that in case there is a solution, it will always find it. However, I would expect if there are several possible solutions, chances are high this algorithm finds one where the score reaches zero (which means all constraints are fulfilled). If the algorithm does not find a solution within a reasonable amount of time, there are probably no solutions, or only so few that they are actually hard to find. 
But for your case, this may be good enough, SA is actually very easy to implement, and it can be probably extended by all kinds of constraints in case it is necessary.
There is also a simple improvement which might help: whenever the algorithm finds a score which is lower than the ones found before, run do a greedy "hill climbing" search, by trying out all pairs of slots and check if there a swap of those slots can reduce the score further.

