C sharp - Problemas al generar una matriz

Estoy haciendo un proyecto que se basa en un juego Hitori. El resto de la aplicacion ya esta hecho, pero estoy teniendo problemas al generar una matriz de numeros valida para el juego, o sea, que tenga solucion, y generar una distinta cada vez que se inicie el juego, que es realmente el corazon de la aplicacion. Escucho ideas.
Las condiciones son que no se pueden marcar casillas adyacente entre si, o sea, en la misma columna y la misma fila una al lado de la otra. Asi como tampoco se pueden marcar de forma que alguna casilla quede incomunicada con las demas de forma vertical u horizontal.

Entego el proyecto antes del viernes.
Gracias por la ayuda