That was fun, it seems to work pretty well, employees are distributed randomly in each departments:
select EmployeeId, DepartmentId
from
( select
ROW_NUMBER() OVER(ORDER BY NEWID()) as RankEmployee
, Id as EmployeeId
from Employee
) e ,
( select
ROW_NUMBER() OVER(ORDER BY NEWID()) as RankDepartment
, (select count(1) from Department) as CountDepartment
, Id as DepartmentId
from Department
) d
where (RankEmployee + RankDepartment) % CountDepartment = 0
The condition
(RankEmployee + RankDepartment) % CountDepartment = 0
will retrieve only one row for each employee.
And ranks are computed randomly with OVER(ORDER BY NEWID())
. See this answer for details.