Indeed, a let-bound [] is generalized to a polymorphic ('a list), while a let-bound (ref []), or (Array.make n []), is not generalized. It would be unsound to do so as if you had a reference to a polymorphic ('a list) you could add elements of different types in the list.
When a type variable is not generalized (polymorphic), it stays an "unknown" of the type system until it is unified to a known type:
# let r = ref [];;
val r : '_a list ref = {contents = []}
# r := 1 :: !r;;
- : unit = ()
# r;;
- : int list ref = {contents = [1]}
'_a is sometimes called a "weakly polymorphic variable", in fact it is not polymorphic at all. It is just an unknown.
In the code example above, the real type for '_a could be determined after two phrases in the top level. It may also happen as a compilation unit (if the code was written in a file instead of fed phrase-per-phrase to the toplevel). We wouldn't observe the intermediary '_a inferred type, as the type are inferred globally.
It is forbidden however to keep an "undetermined variable" in a module interface. This is what the error message here says: the variable '_a could neither be generalized (as it is not a let-bound value, but a reference resulting from a call to the "ref" function), nor determined by unification with something in the module.
Keeping undetermined variables in a module interface would break the separate compilation permitted by the interface/implementation distinction at the module level. Indeed, if a module A had undetermined variables in its interface, and modules B and C used A, B and C would have to coordinate each other to make sure that the instantiations they make (for the undetermined) are compatible; you couldn't compile B with A, and C with A, separately.
The solution is to give enough indications locally, in the module, so that the reference type can be determined:
let states = Array.make ... ([] : (int * int * dir) list * (char * int * int) array * string)
It also seems quite wrong to me. You should perhaps file a bug into
Mantis if no typing expert answers.