Partitioning algorithm for a list of lists in Python

I'm working on a music related problem and I need some help with a crucial step.

I have four lists of numbers from 0 to 11 (including). These lists are to be thought of as vertically aligned. I want to partition those 4 lists into 4 blocks, each block containing all the numbers from 0 to 11, and each row of the block containing 0 to 11 elements from each list. An example:

l_1 = [0,1,4,9,5,8,3,10,2,11,6,7]
l_2 = [7,6,11,2,10,3,8,5,9,4,1,0]
l_3 = [0,11,8,3,7,4,9,2,10,1,6,5]
l_4 = [5,6,1,10,2,9,4,7,3,8,11,0]

A solution is to take elements from the beginning of each row and combining then. For example, a solution for partitioning this block is:

s = [(1,11),(1,2,9),(1,1,10),(2,10)]

The block would look like this:

p_1 = [[0],[1],[4,9,5,8,3,10,2,11,6,7],[]]
p_2 = [[7,6,11,2,10,3,8,5,9,4,1],[],[0],[]]
p_3 = [[],[0,11,8,3,7,4,9,2,10],[1],[6,5]]
p_4 = [[],[5,6],[],[1,10,2,9,4,7,3,8,11,0]]

Here, if we take the elements of same index on each p_list, we have a complete listing of the numbers from 0 to 11 (we can see this by looking at the lists vertically). For instance:

p_1[0] + p_2[0] + p_3[0] + p_4[0] = [0,7,6,11,2,10,3,8,5,9,4,1]

My problem is not to verify a solution, is to actually find one algorhitmically. That is, given 4 rows, how to find a sequence of partitions that is a solution to the problem. Since my background is mostly on music, I come to you for some assistance.

Thank you in advance!

EDIT: As pointed out below, there's also the [(12),(12),(12),(12)] solution. The goal here is to achieve as much diversity as possible of solutions, running this algorhithm through a large number of quartets of different rows.