$n^*=7$. The third question does not seem to have a pleasant answer. For instance, there are 2752 ways to add the numbers 1 through 5 to
$\matrix{ *****\ *\cr *****\ *\cr **6**\ *\cr *****\ *\cr *****\ *\cr *****\ 6}$
to get a pattern with 7 keys that has unique solution.