constraint satisfaction problem missing one constraint : <p>I'm a lab practises tutor at the university, based on last year student comments, we wanted, my boss and I, to address them. My boss chose to go with writing a C script and I pick python (python-constraint) to try to resolve our problem. </p>

<h2>Informations</h2>

<ul>
<li>There are 6 sessions</li>
<li>There are 4 roles</li>
<li>There are 6 practices</li>
<li>There are 32 students</li>
<li>There are 4 students per team</li>
</ul>

<h2>Problem :</h2>

<p>Assign each student to 4 roles, in 4 practices in 4 different sessions. </p>

<h2>Constraints :</h2>

<ol>
<li>Students should do a role once </li>
<li>Students should do 4 different practices out of 6</li>
<li>Students should do only one practice per session</li>
<li><strong>Student should meet the same mate only once</strong></li>
</ol>

<h2>Templates :</h2>

<p>Here is the template that I feel with students, where each team is composed of 4 students, positions [0, 1, 2 or 3] are roles assigned to them. Each available position is numbering from 1 to 128</p>

<pre class="lang-py prettyprint-override"><code>[# Semester
   [ # Session
     [ # Practice/Team
1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16],
  [17, 18, 19, 20],
  [21, 22, 23, 24]],
 [[25, 26, 27, 28],
  [29, 30, 31, 32],
  [33, 34, 35, 36],
  [37, 38, 39, 40],
  [41, 42, 43, 44],
  [45, 46, 47, 48]],
 [[49, 50, 51, 52],
  [53, 54, 55, 56],
  [57, 58, 59, 60],
  [61, 62, 63, 64],
  [65, 66, 67, 68],
  [69, 70, 71, 72]],
 [[73, 74, 75, 76],
  [77, 78, 79, 80],
  [81, 82, 83, 84],
  [85, 86, 87, 88],
  [89, 90, 91, 92],
  [93, 94, 95, 96]],
 [[97, 98, 99, 100],
  [101, 102, 103, 104],
  [105, 106, 107, 108],
  [109, 110, 111, 112]],
 [[113, 114, 115, 116],
  [117, 118, 119, 120],
  [121, 122, 123, 124],
  [125, 126, 127, 128]]]
</code></pre>

<p>In other words : </p>

<p>This is a session : </p>

<pre class="lang-py prettyprint-override"><code> [[1, 2, 3, 4],
  [5, 6, 7, 8],
  [9, 10, 11, 12],
  [13, 14, 15, 16],
  [17, 18, 19, 20],
  [21, 22, 23, 24]],
</code></pre>

<p>Those team do the same practice: </p>

<pre class="lang-py prettyprint-override"><code>[
    [1, 2, 3, 4],
    [25, 26, 27, 28],
    [49, 50, 51, 52],
    [73, 74, 75, 76],
    [97, 98, 99, 100],
    [113, 114, 115, 116]
]
</code></pre>

<p>Those position do the same role : </p>

<pre class="lang-py prettyprint-override"><code>[
   1,
   5,
   9,
   13,
   17,
   21,
   25,
   ...
]
</code></pre>

<h2>What I have so far :</h2>

<p>Using <a href="http://labix.org/doc/constraint/" rel="noreferrer">python-constraint</a> I was able to validate the first three constraints : </p>

<pre class="lang-py prettyprint-override"><code>Valid solution : False
            - sessions  : [True, True, True, True, True, True]
            - practices : [True, True, True, True, True, True]
            - roles     : [True, True, True, True]
            - teams     : [False, False, True, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, False, True, False, False, False, False, False]
</code></pre>

<h3>For those that may interesting I simply do like this :</h3>

<p>For each condition I use <a href="http://labix.org/doc/constraint/" rel="noreferrer">AllDifferentConstraint</a>. For example, for one session I do: </p>

<pre class="lang-py prettyprint-override"><code>problem.addConstraint(AllDifferentConstraint(), [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24])
</code></pre>

<p>I'm not able to find a way to constraint team, my last attempt on the entire <code>semester</code> was this : </p>

<pre class="lang-py prettyprint-override"><code>    def team_constraint(self, *semester):
        students = defaultdict(list)

        # get back each teams based on the format [# Semester [ #Session [# Practice/Team ... 
        teams = [list(semester[i:i+4]) for i in range(0, len(semester), 4)]

        # Update Students dict with all mate they work with
        for team in teams:
            for student in team:
                students[student] += [s for s in team if s != student]

        # Compute for each student if they meet someone more than once 
        dupli = []
        for student, mate in students.items():
            dupli.append(len(mate) - len(set(mate)))

        # Loosly constraint, if a student meet somone 0 or one time it's find
        if max(dupli) &gt;= 2:
            print("Mate encounter more than one time", dupli, min(dupli) ,max(dupli))
            return False
        pprint(students)
        return True
</code></pre>

<h1>Questions :</h1>

<ol>
<li>Is it possible to do what I want for the team conditions ? What I mean is I have no idea if it is possible to assign 12 mates to each student and each of them meet the same mate only once.</li>
<li>For the team constraint, did I miss a more performant algorithm ?  </li>
<li>Any pist that I can follow ? </li>
</ol>
