usando Random

[[Delphius]]

La verdad es que viendo el código de ejemplo, se me hace un poco enredado y confusa la manera de resolverlo. Siento que da demasiadas vueltas... no entiendo el propósito de las variables Max, auxcol, poscol, posfil, con y en especial x, que la evalúas repetidas veces.

Te complicas demasiado, Yo lo veo más simple: mantengo un vector booleano de tamaño 9 al que llamaré NroUsados. De modo que cuando NroUsados[nro] = true quiere decir que ese número ya fue asignado en alguna posición (que no interesa en realidad cual) y por tanto ya no puede ser asignado.
Básicamente pido un nro aleatorio entre 1 y 9, y me fijo si ese ya fue "usado". De no ser usado lo asigno y lo marco como true, en caso contrario pido otro. Ahora resulta obvio que aquí se requiere un bucle para que itere hasta que se "encuentre" por azar algún número libre de la lista.

En el mejor caso se encuentra el número en la primera pasada. En el peor caso puede encontrarse tras varias pasadas* (aunque por estadística se podría llegar a decir que no se necesitarían más de 5 pasadas en promedio). Una vez encontrado el número salimos de ese ciclo y podemos hacer la asignación a la posición y además, por tanto, el marcado como usado.

* Bueno, en realidad el ciclo puede ser infinito... existe aún la pequeñísima probabilidad de que el generador pseudoaleatorio nunca generase el número adecuado para finalizar el ciclo. Si se tiene ese "miedo" puede introducirse una mejora al código que puede garantizar la "elección" de un número:
en lugar de generar un número en el rango (1,9) simplemente le pedimos que genere números enteros mas grandes. Al resultado le calculamos el resto de 9:

nro = AleatorioEntero() MOD 9.

Ahora en nro siempre tendremos un número que estará en el valor [0,8]. Para "convertirlo" al rango [1,9] solo hace falta sumarle 1:

Matriz[i,j] = nro + 1;

Simplemente voy recorriendo la matriz y asignando los valores aleatorios.

Si con eso no te abres esa cabeza...