Custom unique rule

I'm not sure if there's a way to do this at the database level as you're using pivot tables. Because there is a many-to-many relationship it makes it a bit harder. If you had a one-to-one relationship it'd be a bit easier...you could do for example:

// in your migration
Schema::create('users', function($table) {
    $table->unsignedInteger('department_id');
    $table->string('username');
    $table->unique(['username', 'department_id']);
});

Because this is a little more complex you may want to try using some model observers instead.

See documentation here: https://laravel.com/docs/5.7/eloquent#observers

So in your creating/updating events you'd want something like:

class UserObserver
{
    /**
     * Event fired when saving a user.
     *
     * @param User $user
     *
     * @return bool
     */
    public function saving(User $user)
    {
        $users = User::where('username', $user->username)->get();
        $exists = false;

        $users->each(function ($model) use ($user, $exists) {
            if ($exists) {
                return false;
            }
            $exists = $model->departments->contains($user->departments);
        });

        return $exists;
    }
}

Here we're getting all the users that have the same username as the user who is being created or updated. Then we're running through each one and checking if they're in the same department.

You'll then need to "observe" the model in a service provider such as:

class AppService Provider 
{
    // ...
    public function boot()
    {
        User::observe(UserObserver::class);
    }
}