Saltar al contenido

Cuánto vale una ficha conocida con el barrido por filas

Con un barrido por filas, una ficha conocida quita entre 1 y 10 bits del árbol de búsqueda completo según la sola posición de su casilla en el barrido (mediana de 5,8 bits, en tableros 16x16 pintados), y varias fichas juntas valen menos que su suma. En esos tableros, 10 fichas bien repartidas dejan el árbol por encima de 10^15 nodos y de 16 a 24 lo bajan por debajo, una cifra comprobada solo de extremo a extremo. Nada de esto mide el puzle real, salvo dos comprobaciones de transferencia.

por Raphaël Anjou

experimentomediciónmedidoReducir la búsquedaBacktrackingActualizado 2026-11-14
Reproducircon semilla: se reproduce con la semilla indicadarelanza la búsquedaPresupuesto: unas 10,1 horas-núcleo para el estudio 16x16, unas 1,4 horas-núcleo para el mapa de tableros pequeños
Hardware y ejecución
Ejecución nativaSolo CPU
Núcleos
10
GPU
0
CPU
Apple silicon laptop (10 cores) and an 8-core Apple M1
Máquina
Portátil Apple silicon de 10 núcleos, como mucho 2 procesos a la vez, más un Apple M1 de 8 núcleos para tres etapas; el mapa de tableros pequeños corrió en un núcleo
Presupuesto
unas 10,1 horas-núcleo para el estudio 16x16, unas 1,4 horas-núcleo para el mapa de tableros pequeños
Inicio
con semillas fijas; semillas del pintor 300051, 300061, 300097, 300117, 300131 para los tableros 16x16; tableros pequeños: semillas 1 a 20 (8x8) y 1 a 5 (10x10)
Reproducir este resultado

con semilla: se reproduce con la semilla indicada

just experiments orders-and-pins all

Repite las etapas de fichas fijas del 16x16 (mapa de una ficha, pistas quitadas una a una, juegos de fichas repartidas y aleatorias, comprobación sobre el árbol entero) y luego analyze.py; semillas fijas y filas deterministas, pero la ejecución completa son unas 10 horas-núcleo. El mapa de tableros pequeños es una segunda receta, just experiments pin-map all (unas 1,6 horas-núcleo). Ninguna toca las piezas reales más allá de las cinco pistas.

Seguir explorando

Citado por

Fuente de la páginaVer como Markdown