our $oopser = 0; # protect from endless loops
$#empsh = 20; # prefill worktable

for my $sh (1 .. 21) { # 21 shifts are 7 days with 3 shifts
	for my $shid (1 .. 3) { # every shift has 3 mandtory workers
		# find a free worker
		my $emp = 0;
		$oopser = 0;
		while ($emp == 0) {
			$oopser++; die if $oopser > 100;
			$emp = int( 1 + rand(20) ); # take a random worker
			$emp = 0 if $empsh->[$emp][$sh]; # already assigned
		}
		$empsh[$emp][$sh] = "work ($shid)"; # work this shift (8 hours)
		$empsh[$emp][$sh+1] = 'free (+)';   # and have 2 shifts rest (16 hours)
		$empsh[$emp][$sh+2] = 'free (++)';  # (German law says 11 hours between shifts)
		$shcount[$sh]++; # no of worker per shift
	}
	foreach my $emp (@empsh) { # all other workers are unassigned on this shift
		$emp->[$sh] ||= ' - ';
	}
}

my %emplist = map { $_ => $_ } (1 .. 20); # workerlist, delete()able
$oopser = 0;
while (keys %emplist) { # check for remaining every worker (maybe add "sort rand()"
	$oopser++; die if $oopser > 100;
	my @shnum = (); # no of shifts per worker
	for my $emp (keys %emplist) {
		foreach my $tag (@{ $empsh[$emp] }) {
			$shnum[$emp]++ if $tag =~ /^work/; # count his working shifts
		}
		if ($shnum[$emp] == 5) { # worked 5 shifts?
			delete $emplist{$emp};
		} # (each worker has to work exactly 5 shifts a week)
	}
	EMP: foreach my $emp (keys %emplist) { # who has to work more?
		my $sh = 1;
		while ($empsh[$emp][$sh] ne ' - ') { # find a unassigned shift for this worker
			if ($sh > 21) { # oops, none found?
				delete $emplist{$emp};
				print STDERR "$emp has underwork\n";
				next EMP; # re-run this program then
			}
			$sh++;
		}
		if ($shcount[$sh] >= 5) {
			# shift full
			$empsh[$emp][$sh] = 'free (shift full)';
		} elsif ($empsh[$emp][$sh+1] =~ /^work/) {
			# no 2 shifts rest possible
			$empsh[$emp][$sh] = 'free (-)';
		} elsif ($empsh[$emp][$sh+2] =~ /^work/) {
			# no 2 shifts rest possible
			$empsh[$emp][$sh] = 'free (--)';
		} else {
			# hehe, work here!
			$empsh[$emp][$sh] = 'work (backup)';
			$empsh[$emp][$sh+1] = 'free (+)';
			$empsh[$emp][$sh+2] = 'free (++)';
		}
	}
}

# now print
print "<table border><tr><td>***";
for my $sh (1 .. 21) {
	print "<th>-$sh-";
}
print "<td>";
for my $emp (1 .. 20) {
	print "<tr><th>", $emp;
	for my $sh (1 .. 21) {
		print "<td>", $empsh[$emp][$sh];
	}
}
print "</table>";