% 
% Appointment scheduling in MiniZinc.
% 
% From Stack Overflow
% Appointment scheduling algorithm (N people with N free-busy slots, constraint-satisfaction)
% http://stackoverflow.com/questions/11143439/appointment-scheduling-algorithm-n-people-with-n-free-busy-slots-constraint-sa
% ""
% Problem statement
%
% We have one employer that wants to interview N people, and therefore makes N 
% interview slots. Every person has a free-busy schedule for those slots. Give an algorithm 
% that schedules the N people into N slots if possible, and return a flag / error / etc if 
% it is impossible. What is the fastest possible runtime complexity?
% 
% My approaches so far
% 
% Naive: there are N! ways to schedule N people. Go through all of them, for each permutation, 
% check if it's feasible. O( n! )
% 
% Backtracking:
% 
%     Look for any interview time slots that can only have 1 person. Schedule the person, 
%     remove them from the list of candidates and remove the slot.
%     Look for any candidates that can only go into 1 slot. Schedule the person, remove them 
%     from the list of candidates and remove the slot.
%     Repeat 1 & 2 until there are no more combinations like that.
%     Pick a person, schedule them randomly into one of their available slots. Remember 
%     this operation.
%     Repeat 1, 2, 3 until we have a schedule or there is an unresolvable conflict. If we have a 
%     schedule, return it. If there's an unresolvable conflict, backtrack.
% 
% This is O( n! ) worst case, I think - which isn't any better.
% 
% There might be a D.P. solution as well - but I'm not seeing it yet.
% 
% Other thoughts
% 
% The problem can be represented in an NxN matrix, where the rows are "slots", columns are 
% "people", and the values are "1" for free and "0" for busy. Then, we're looking for a 
% row-column-swapped Identity Matrix within this matrix. Steps 1 & 2 are looking for a row or a 
% column with only one "1". (If the rank of the matrix is = N, I that means that there is a 
% solution. But the opposite does not hold) Another way to look at it is to treat the matrix 
% as an unweighed directed graph edge matrix. Then, the nodes each represent 1 candidate and 1 
% slot. We're then looking for a set of edges so that every node in the graph has one outgoing 
% edge and one incoming edge. Or, with 2x nodes, it would be a bipartite graph.
% 
% Example of a matrix:
% 
% 1 1 1 1
% 0 1 1 0
% 1 0 0 1
% 1 0 0 1
% 
% I have a feeling that this might be NP-C.
% ""
% 
% This is a matrix based approach.

% 
% This MiniZinc model was created by Hakan Kjellerstrand, hakank@bonetmail.com
% See also my MiniZinc page: http://www.hakank.org/minizinc/
%

include "globals.mzn"; 
int: n = 4;

% rows are time slots
% columns are people
array[1..n, 1..n] of int: m = array2d(1..n, 1..n,
[
1, 1, 1, 1,
0, 1, 1, 0,
1, 0, 0, 1,
1, 0, 0, 1,
]);

% decision variables
% 
% the assignment of persons to a slot (appointment number 1..n)
array[1..n, 1..n] of var 0..1: x;

solve satisfy;
% solve :: int_search(x, first_fail, indomain_min, complete) satisfy;

% 
% Matrix approach
% 
constraint
  forall(i in 1..n) (
    % ensure a free slot
    sum([m[i,j]*x[i,j] | j in 1..n]) = 1

    /\ % ensure one assignment per slot
    sum([x[i,j] | j in 1..n]) = 1
    /\
    sum([x[j,i] | j in 1..n]) = 1
  )
;

output 
[
  if j = 1 then "\n" else " " endif ++
    show(x[i,j])
  | i,j in 1..n
]
++
[
  if fix(x[i,j]) = 1 then "\nslot " ++ show(i) ++ ": " ++ show(j) else "" endif
  | i,j in 1..n
]
;