Luchando para hacer algoritmo para generar tablero para un juego de rompecabezas

Question

Estoy buscando hacer un juego de rompecabezas numérico. Por el bien de la pregunta, digamos que el tablero es una cuadrícula que consta de 4 x 4 cuadrados. (En el juego de rompecabezas real, este número será 1..15)

Un número solo puede aparecer una vez en cada columna y una vez en cada fila, un poco como Sudoku, pero sin "cuadrados".

Válido:

[1, 2, 3, 4 
2, 3, 4, 1 
3, 4, 1, 2 
4, 1, 2, 3] 

Me parece que no puede llegar a un algoritmo que genere constantemente válida, al azar n n x tableros.

Escribo esto en C#.

Answer 1

La manera más fácil que puedo pensar sería crear un juego parcial y resolverlo. Si no se puede resolver, o si está mal, haz otra. ;-)

Answer 2

Sudoku sin cuadrados suena un poco como Sudoku. :)

http://www.codeproject.com/KB/game/sudoku.aspx

hay una explicación del código generador de tablero que utilizan allí.

Answer 3

No hay demasiadas combinaciones que deba probar. Siempre puede reorganizar una tabla válida, por lo que la fila superior es 1,2,3,4 (reasignando los símbolos), y la columna izquierda es 1,2,3,4 (reorganizando las filas 2 a 4). En cada fila solo hay 6 permutaciones de los 3 símbolos restantes, por lo que puede recorrerlas para encontrar cuál de las 216 posibles tablas es válida. También puede almacenar los válidos.

A continuación, elija una placa válida aleatoriamente, reorganice aleatoriamente las filas y reasigne aleatoriamente los símbolos.

Answer 4

Parece que podría usar este ejemplo válido como entrada para un algoritmo que intercambió aleatoriamente dos filas un número aleatorio de veces, luego intercambió dos columnas al azar un número aleatorio de veces.

Answer 5

Echa un vistazo a http://www.chiark.greenend.org.uk/~sgtatham/puzzles/ - tiene varios acertijos que tienen precisamente esta restricción (entre otros).

Answer 6

Use su primer ejemplo válido:

1 2 3 4 
2 3 4 1 
3 4 1 2 
4 1 2 3 

continuación, cree aleatoriamente 2 permutaciones de {1, 2, 3, 4}.

Utilice el primero para permutar filas y luego el segundo para permutar las columnas.

Usted puede encontrar varias formas de crear permutaciones en Knuth de The Art of Computer Programming (TAOCP), Volumen 4 Fascículo 2, de producción de todas las tuplas y permutaciones (2005), v + 128pp. ISBN 0-201-85393-0.

Si no puede encontrar una copia en una biblioteca, una pre-impresión (de la parte que trata sobre las permutaciones) está disponible en su sitio: fasc2b.ps.gz

---

EDITAR - CORRECCIÓN

El la solución anterior es similar a la de 500-Intenral Server Error. Pero creo que ambos no encontrarán todos los arreglos válidos.

Por ejemplo van a encontrar:

1 3 2 4 
3 1 4 2 
2 4 1 3 
4 2 3 1 

pero no ésta: se necesita

1 2 3 4 
2 1 4 3 
3 4 1 2 
4 3 2 1 

Un paso más: Después de la reordenación de filas y columnas (ya sea usando mi o 500 de forma), cree una permutación más (llamémosla s3) y úsela para permutar todos los números en la matriz.

s3 = randomPermutation(1 ... n) 
for i=1 to n 
    for j=1 to n 
    array[i,j] = s3(array[i,j]) 

Answer 7

No hablo C#, pero el siguiente algoritmo se debe traducir fácilmente.

asociado un conjunto que consta de la 1..N números con cada fila y columna:

for i = 1 to N 
    row_set[i] = column_set[i] = Set(1 .. N) 

luego hacer una sola pasada a través de la matriz, la elección de una entrada para cada posición al azar de los elementos de conjunto válido en esa fila y columna. Elimine el número elegido de los conjuntos de filas y columnas correspondientes.

for r = 1 to N 
    for c = 1 to N 
    k = RandomChoice(Intersection(column_set[c], row_set[r])) 
    puzzle_board[r, c] = k 
    column_set[c] = column_set[c] - k 
    row_set[r] = row_set[r] - k 
    next c 
next r 

Answer 8

de inicio mediante la lectura de mi serie de algoritmos de color gráfico:

http://blogs.msdn.com/b/ericlippert/archive/tags/graph+colouring/

Se va a parecer que esto no tiene nada que ver con su problema, pero en el momento en que haya terminado, Verás que tiene todo que ver con tu problema.

---

OK, ahora que usted ha leído eso, usted sabe que usted puede utilizar un algoritmo de coloreado de grafos para describir un Sudoku similar y luego resolver un caso específico del rompecabezas. Pero claramente puede usar el mismo algoritmo para generar rompecabezas.

Comience definiendo las regiones de gráfico que están totalmente conectadas.

A continuación, modifique el algoritmo para que intente encontrar dos soluciones.

Ahora cree un gráfico en blanco y establezca una de las regiones al azar en un color aleatorio. Intenta resolver el gráfico. ¿Hubo dos soluciones? Luego agrega otro color al azar. Pruébalo otra vez. ¿No hubo soluciones? Luego haga una copia de seguridad de un paso y agregue un color aleatorio diferente.

Sigue haciendo eso: agrega colores aleatorios, retrocede cuando no obtienes soluciones, y continúa hasta que obtienes un rompecabezas que tiene una solución única. Y tu estas listo; tienes un generador de rompecabezas aleatorio.

Answer 9

Parece que desea generar uniformemente distribuido Latin Squares.

Este pdf tiene una descripción de un método de Jacobson y Matthews (que fue publicado en otro lugar, una referencia de los cuales se puede encontrar aquí: http://designtheory.org/library/encyc/latinsq/z/)

O usted podría potencialmente pre-generar un "lote" de ellos (antes de enviar :-)), almacénelo en un archivo y elija uno al azar.

Espero que ayude.

Answer 10

Otra solución sería esta. Supongamos que tiene una serie de soluciones. Para cada uno de ellos, puede generar una nueva solución simplemente permutando los identificadores (1..15). Estas nuevas soluciones lógicamente son lo mismo, pero para un jugador parecerán diferentes.

La permutación se puede hacer tratando cada identificador en la solución inicial como un índice en una matriz, y luego mezclando esa matriz.