Saltar al contenido

Sudoku y lógica proposicional

Solución:

La fórmula dice “para cada valor permitido de la fila $ i $ y el valor $ n $, hay al menos una columna $ j $ para la cual la ubicación $ (i, j) $ de la cuadrícula se rellena con el valor $ n $ “.

La traducción de Sudoko a la lógica proposicional no facilita fundamentalmente el problema. Cualquier problema de lógica también se puede reescribir como un Sudoku, y resolver cualquier tipo de problema en general es computacionalmente difícil (NP-completo).

¿$ bigwedge_ {i = 1} ^ {9} bigwedge_ {n = 1} ^ {9} bigvee_ {j = 1} ^ {9} ~ p (i, j, n) $ dice eso en el primer fila, el número uno se encontrará en la primera columna, o en la segunda columna, o en la tercera columna, etc.

No, la fórmula que dice eso es $ bigvee_ {j = 1} ^ {9} ~ p (1, j, 1) $ que es la especialización $ i = 1 $, $ n = 1 $ de la primera fórmula. La disyunción indexada por $ j $ desempaqueta a “p (1,1,1) OR p (1,2,1) OR p (1,3,1) OR … p (1,9,1)”.

Aunque se puede expresar como lógica proposicional, para soluciones prácticas, es computacionalmente más efectivo ver al Sudoku como un Problema de Satisfacción de Restricciones. Consulte el capítulo 6 de Russell y Norvig: Inteligencia artificial: un enfoque moderno, por ejemplo.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *