Introducción
Este desafío es similar a los problemas del Proyecto Euler . Se me ocurrió porque estaba jugando un juego de tablero engañosamente simple y no pude encontrar una solución eficiente para responder una pregunta simple sobre su mecánica.
Quarto es una variante divertida de 4 seguidas. Se juega en un tablero de 4 por 4 con 16 piezas únicas (no se duplican piezas). Cada turno cada jugador coloca 1 pieza en el tablero. Cada pieza tiene 4 características binarias (corta / alta, negra / blanca, cuadrada / circular, hueca / sólida). ¡El objetivo es hacer cuatro en una fila, ya sea horizontal, vertical o a lo largo de las 2 diagonales, para cualquiera de las cuatro características! Entonces 4 piezas negras, 4 piezas blancas, 4 piezas altas, 4 piezas cortas, 4 piezas cuadradas, 4 piezas circulares, 4 piezas huecas o 4 piezas sólidas.
La imagen de arriba muestra un juego terminado, hay cuatro en fila debido a 4 piezas cuadradas.
Desafío
En Quarto, algunos juegos pueden terminar en empate.
El número total de posibles posiciones finales es de 16!
aproximadamente 20 billones.
¿Cuántas de esas posiciones finales son empates?
Reglas
La solución debe ser un programa que calcule y genere el número total de posiciones finales que son sorteos. La respuesta correcta es
414298141056
Solo puede usar información de las reglas del juego que se han deducido manualmente (sin prueba asistida por computadora).
Las simplificaciones matemáticas del problema están permitidas, pero deben explicarse y probarse (manualmente) en su solución.
El ganador es el que tiene la solución más óptima en términos de tiempo de ejecución de la CPU.
Para determinar el ganador, ejecutaré todas las soluciones con un tiempo de ejecución de menos de 30 m en un MacBook Pro 2.5 GHz Intel Core i7 con 16 GB de RAM .
No hay puntos de bonificación por encontrar una solución que también funcione con otros tamaños de tablero. Aunque eso sería bueno.
Si corresponde, su programa debe compilarse dentro de 1 minuto en el hardware mencionado anteriormente (para evitar el abuso de la optimización del compilador)
Las lagunas predeterminadas no están permitidas
Envíos
Por favor publique:
- El código o un enlace github / bitbucket al código.
- La salida del código.
- Su tiempo de ejecución medido localmente
- Una explicación de tu enfoque.
Fecha límite
La fecha límite para las presentaciones es el 1 de marzo, así que aún queda mucho tiempo.
Respuestas:
C: 414298141056 sorteos encontrados en aproximadamente
52.5 minutos.Solo una simple búsqueda de profundidad con una tabla de transposición consciente de la simetría. Utilizamos la simetría de los atributos bajo permutación y la simetría diédrica de 8 pliegues del tablero.
Puntuación medida (@wvdz):
Puntuación (usuario + sys): 1m35.727s
fuente
-O3 -march=native
y obtuve 1m48s en mi máquina. (CC @wvdz)Java, 414298141056 sorteos, 23m42.272s
Espero que no esté mal visto publicar una solución al propio desafío, pero la razón por la que publiqué este desafío en primer lugar fue que me volvía loco que no pudiera encontrar una solución eficiente yo mismo. Mi mejor intento tomaría días en completarse.
Después de estudiar la respuesta del usuario 1502040 , logré modificar mi código para que se ejecutara en un tiempo razonable. Mi solución sigue siendo significativamente diferente, pero robé algunas ideas:
La principal diferencia entre esta solución y la del usuario 1502040 es que no uso una tabla Zobrist, sino una representación canónica de una placa, donde considero que cada placa tiene 48 posibles transposiciones sobre las características (2 * 4). No giro ni transpongo todo el tablero, sino solo las características de las piezas.
Esto es lo mejor que se me ocurrió. ¡Las ideas para optimizaciones obvias o menos obvias son bienvenidas!
Puntuación medida:
Puntuación (usuario + sys): 23m42.272s
fuente