shuffling a list with restrictions in Python

I have a problem with randomizing a list with restrictions in Python (3). I have seen a few other questions relating to this, but none of them really seem to solve my problem. I'm a beginner, so any help is much appreciated!

I'm designing an experiment using two types of stimuli: shapes and colors (four of each). I need to generate permutations of all 16 combinations, which I have done with random.shuffle-function:

import random

# letters are shapes, numbers are colors
x=["a1","a2","a3","a4","b1","b2","b3","b4","c1","c2","c3","c4","d1","d2","d3","d4"]

random.shuffle(x)

So far so good. However, I want to avoid a shape (letter) or color (number) to appear two times in succession in my result (e.g. "a2" followed by "a4", or "c2" followed by "a2").

Is there a way to make such a restriction?
Thanks in advance!

Something like this should give a reasonable answer in a reasonable time

import random
while 1:
    choices = ["a1", "a2","a3","b1","b2","b3","c1","c2","c3"]

    shuffle = []

    last = ""

    while choices:
        l = choices
        if last:
            l = [x for x in l if x[0] != last[0] and x[1] != last[1]]
        if not l:
            #no valid solution
            break 
        newEl = random.choice(l)
        last = newEl
        shuffle.append(newEl)
        choices.remove(newEl)
    if not choices:
        print(shuffle)
        break