Se trata de una rama de esta pregunta .
Supongamos que tenemos piezas de puzzle que son básicamente cuadrados pero en los que cada lado puede ser recto, cóncavo o convexo. A continuación se muestra un ejemplo de tres piezas de este tipo: 
Está claro que puede haber $3^4=81$ diferentes tipos de piezas. Me preguntaba, dada una de cada tipo (y sin rotaciones o volteos permitidos), si era posible crear un rompecabezas estándar, utilizando sólo esos $81$ piezas. Por "rompecabezas estándar" me refiero a uno de dimensiones $m \times n$ donde todos los lados del perímetro son rectos.
A $1\times 81$ rompecabezas es claramente imposible, ya que requeriría que todos los $81$ piezas sean rectas tanto en el lado izquierdo como en el derecho. Un argumento similar es válido para $81\times 1$ rompecabezas.
A $3\times 27$ rompecabezas requeriría $27$ piezas con un lado recto izquierdo y $27$ piezas con borde recto, y si bien es cierto que existen esos dos conjuntos, tienen un solapamiento de $9$ piezas. Por tanto, esto no es posible. Como antes, un argumento similar vale para un $27\times 3$ rompecabezas.
Esto deja el $9\times 9$ posibilidad. A priori, no veo ninguna razón para que esto no sea posible. Y creo que tengo una prueba de que es posible, que es sobre lo que me gustaría saber su opinión.
Dada una $9\times 9$ rompecabezas, tenemos la situación siguiente: 
Cada lado negro de una pieza es fijo, pero cada lado verde de una pieza representa un posible tipo de conexión. Un tipo de conexión podría ser del tipo "recto - recto", "cóncavo - convexo" o "convexo - cóncavo". Me parece que si repasamos todos los tipos de conexión posibles para cada pieza, uno de esos escenarios debe dar un puzzle en el que cada una de las $81$ se utiliza exactamente una vez.
¿Estoy en lo cierto?
3 votos
"si pasamos por todos los tipos de conexión posibles para cada pieza" - No estoy seguro de entender lo que quieres decir. ¿Qué pasa con la pieza que tiene todos los lados rectos, la que tiene todos los lados cóncavos y la que tiene todos los lados convexos? ¿Podría aclararlo?
0 votos
@Michael Lee: Se probarían todos los tipos de conexión para todas las conexiones, incluidas las que mencionas (siempre que no estén en la frontera).
9 votos
Lo que describes suena como un método de fuerza bruta para generar una solución si es que existe, pero definitivamente no es una prueba de existencia.
0 votos
@Michael Lee: No estoy sugiriendo un algoritmo. Básicamente estoy preguntando si hay alguna razón por la que probar todas las conexiones posibles no debería dar como resultado un puzzle formado sólo por el $81$ tipos.
6 votos
Si existe tal solución, la encontrarás. Si no la hay, no la encontrarás. No veo razón para descartar ninguna de las dos posibilidades.
0 votos
@Robert Israel: ¿Podrías explicar por qué probando todos los tipos de conexión posibles no se llegaría necesariamente a la conclusión que yo saco?
7 votos
No lo hará si no hay una solución.
5 votos
@Jens; Robert Israel está diciendo que aunque el enfoque que sugieres es una estrategia válida para averiguar si hay una solución o no, no es en sí mismo una prueba de cualquier manera. Podrías acabar probando todas y cada una de las combinaciones y descubrir que ninguna de ellas forma realmente una rejilla válida (aunque en este caso concreto, como respondió Bram28, es de hecho posible y, por tanto, la fuerza bruta sí encontrará una solución cuando se aplique). Como ejemplo tonto de la negativa, podría afirmar que existe un booleano "a" tal que "a = no a", con la "prueba" de que si pruebo todos los valores posibles de a, uno de ellos debe funcionar.
2 votos
El "contenido" de la misma es esencialmente que lo que escribiste no es una prueba de existencia. Es un método para encontrar una solución, si es que existe, pero obviamente es posible modificar el rompecabezas de tal manera que el método que has descrito no genere una solución, como en el $3\times 27$ caso.