universidad san martín de porres inteligencia artificial y robóticacrucigrama integrantes aguilar...

““Universidad San Martín de Porres”Universidad San Martín de Porres” “Inteligencia Artificial y Robótica” “Inteligencia Artificial y Robótica”

““CRUCIGRAMA”CRUCIGRAMA”INTEGRANTESINTEGRANTES

Aguilar Pastor, SaraAguilar Pastor, Sara

Blancas Tunqui, Alicia Blancas Tunqui, Alicia

Choquepure Choque, Jenny Choquepure Choque, Jenny

Gonzáles Guillén, JoséGonzáles Guillén, José

Paredes Flores, MarceloParedes Flores, Marcelo

IntroducciónIntroducción

El trabajo que ha sido desarrollado es una El trabajo que ha sido desarrollado es una propuesta de solución ya que existen propuesta de solución ya que existen diferentes formas de realizarlas, dicho diferentes formas de realizarlas, dicho trabajo pertenece al curso de Inteligencia trabajo pertenece al curso de Inteligencia Artificial y Robótica, el trabajo desarrollado Artificial y Robótica, el trabajo desarrollado tiene como titulo “Creación de tiene como titulo “Creación de Crucigrama” .Crucigrama” .

IntroducciónIntroducción

El presente trabajo consiste en aplicar el El presente trabajo consiste en aplicar el tema de búsqueda aplicado en el curso de tema de búsqueda aplicado en el curso de Inteligencia Artificial y Robótica en un Inteligencia Artificial y Robótica en un juego de Crucigrama, planteándolo, juego de Crucigrama, planteándolo, implementándolo y solucionándolo en un implementándolo y solucionándolo en un lenguaje de programación de alto nivel lenguaje de programación de alto nivel como LISP.como LISP.

El ProblemaEl Problema El problema a resolver mediante los El problema a resolver mediante los

algoritmos de búsqueda inteligente en la algoritmos de búsqueda inteligente en la creación del crucigrama es la concordancia y creación del crucigrama es la concordancia y coherencia de las palabras contenidas en el coherencia de las palabras contenidas en el diccionario diccionario

El grado de complejidad puede estar limitado El grado de complejidad puede estar limitado por el tamaño del crucigrama ya que al ser por el tamaño del crucigrama ya que al ser de mayor orden será mas complicado poder de mayor orden será mas complicado poder ingresar las palabras con sus respectivas ingresar las palabras con sus respectivas intersecciones.intersecciones.

ObjetivoObjetivo

Crear un crucigrama en un lenguaje de Crear un crucigrama en un lenguaje de programación de alto nivel llamado LISP, programación de alto nivel llamado LISP, desde los más simples hasta los más desde los más simples hasta los más complejos, con la finalidad de armar complejos, con la finalidad de armar diferentes juegos.diferentes juegos.

Planteamiento del ProblemaPlanteamiento del Problema

En la creación del crucigrama es la En la creación del crucigrama es la concordancia y coherencia de las palabras concordancia y coherencia de las palabras contenidas en el diccionario es decir las contenidas en el diccionario es decir las palabras pueden ser ingresadas de izquierda a palabras pueden ser ingresadas de izquierda a derecha o de arriba abajo.derecha o de arriba abajo.

El grado de complejidad puede estar limitado El grado de complejidad puede estar limitado por el tamaño del crucigrama ya que al ser de por el tamaño del crucigrama ya que al ser de mayor orden será mas complicado poder mayor orden será mas complicado poder ingresar las palabras con sus respectivas ingresar las palabras con sus respectivas intersecciones.intersecciones.

Planteamiento del ProblemaPlanteamiento del Problema

Otro factor puede ser las palabras que Otro factor puede ser las palabras que contenga el diccionario ya que puede contenga el diccionario ya que puede darse el caso que no se pueda ingresar darse el caso que no se pueda ingresar las palabras con sus respectivas las palabras con sus respectivas intersecciones.intersecciones.

La creación de un crucigrama esto ira de La creación de un crucigrama esto ira de la mano con el tamaño (orden N x M) que la mano con el tamaño (orden N x M) que se haya definido. se haya definido.

Modelo de SoluciónModelo de Solución

El primer paso para resolver un El primer paso para resolver un crucigrama se representa la palabra, que crucigrama se representa la palabra, que significa interpretar y definir la palabra.significa interpretar y definir la palabra.

En nuestro trabajo lo que queremos En nuestro trabajo lo que queremos captar es el lenguaje de programación captar es el lenguaje de programación LISP para poder realizar el crucigrama LISP para poder realizar el crucigrama escogido, y hacerlo lo más sencillo escogido, y hacerlo lo más sencillo posible.posible.

SI

NO

SI

NO

SI

1.- Definición del tamaño de la cuadrilla.2.- Definición de las palabras del diccionario con longitud adecuada.

3.- Definir la ubicación de las palabras en las casillas (horizontal).

4.- Ubicación de las palabras de manera que la misma letra se encuentre en la intersección de las palabras (vertical).

5.- Definir estado inicial, estado final, operadores y costos.6.- Plantear el problema en LISP.

7.- Implementar las funciones en LISP (programa).

8.- Realizar pruebas al programa. (Funcionamiento)El programa

Corre?

10.-Presentación del Trabajo.

9.- Formulación del Informe.

NO

Desarrollo ExperimentalDesarrollo Experimental1.1. Planteamiento de la SoluciónPlanteamiento de la Solución

Para desarrollar este crucigrama, hemos Para desarrollar este crucigrama, hemos realizado uno de la dimensión de N x M realizado uno de la dimensión de N x M (3*6), para que no sea muy extenso con (3*6), para que no sea muy extenso con nuestro diccionario propuesto.nuestro diccionario propuesto.

Se va probando cada palabra de nuestro Se va probando cada palabra de nuestro diccionario, para ir resolviendo poco a diccionario, para ir resolviendo poco a poco.poco.

Desarrollo ExperimentalDesarrollo Experimental

La Búsqueda es para cada palabra del La Búsqueda es para cada palabra del diccionario, se utiliza la primera palabra y diccionario, se utiliza la primera palabra y así luego se hace la transpuesta para así luego se hace la transpuesta para colocarla en la columna que el programa colocarla en la columna que el programa ya lo realiza con alguna función ya lo realiza con alguna función determinada.determinada.

Diccionario: mesa, lápiz, parte, tía, poema, Diccionario: mesa, lápiz, parte, tía, poema, mouse, casa.mouse, casa.

Desarrollo ExperimentalDesarrollo Experimental2.2. Desarrollo ExperimentalDesarrollo Experimental(defun inicial (listh) (progn (prin1 " ")(defun inicial (listh) (progn (prin1 " ")(terpri) (prin1 "Crucigrama de 3 Horizontales y (terpri) (prin1 "Crucigrama de 3 Horizontales y

6 Verticales 6 Verticales = Casilla Negra " = Casilla Negra " ))(terpri)(prin1 (car listh))(terpri)(prin1 (car listh))(terpri) (prin1 (car (cdr listh)))(terpri) (prin1 (car (cdr listh)))(terpri) (prin1 (car (cdr (cdr listh)))))(terpri) (prin1 (car (cdr (cdr listh)))))(terpri)(terpri)(prin1 " ")(prin1 " ")))


- - En este pseucodigo se muestra el estado En este pseucodigo se muestra el estado inicial del crucigrama, el cual se encuentra inicial del crucigrama, el cual se encuentra sin rellenar los casilleros, encontrándose sin rellenar los casilleros, encontrándose en blanco:en blanco:

InicioInicio Declaración de la función inicial del estado Declaración de la función inicial del estado

inicial del crucigrama. inicial del crucigrama. Imprime Crucigrama de 3 horizontal y 6 Imprime Crucigrama de 3 horizontal y 6

vertical y describir casilla negra es vertical y describir casilla negra es realiza salto de línearealiza salto de línea


imprime la cabecera de lista ingresadaimprime la cabecera de lista ingresada realiza salto de línearealiza salto de línea imprime la cabecera del resto de la lista imprime la cabecera del resto de la lista

ingresada ingresada realiza salto de línearealiza salto de línea

imprime la cabecera del resto del resto de imprime la cabecera del resto del resto de la lista ingresada la lista ingresada

realiza salto de línearealiza salto de líneafinfin


3.- Implementación3.- Implementación

Este programa está realizado en un alto Este programa está realizado en un alto

nivel de un lenguaje de programación nivel de un lenguaje de programación

llamado LISP y las funciones que se realiza llamado LISP y las funciones que se realiza

son los códigos para que el programa corra son los códigos para que el programa corra

satisfactoriamentesatisfactoriamente..


El estado inicio para nuestro trabajo son El estado inicio para nuestro trabajo son las casilla blancas y nuestro estado meta las casilla blancas y nuestro estado meta son las casillas rellenadas o sino las son las casillas rellenadas o sino las palabras no llegan a rellenar todas las palabras no llegan a rellenar todas las casillas se pondrá una o varias casillas casillas se pondrá una o varias casillas negras como repetimos es ◘.negras como repetimos es ◘.


Este es un ejemplo, de un aspecto técnico Este es un ejemplo, de un aspecto técnico que luego se creó varias funciones que que luego se creó varias funciones que realice creaciones de matrices y como realice creaciones de matrices y como también se podría hacer suponiendo que también se podría hacer suponiendo que la matriz era N x M, como en nuestro la matriz era N x M, como en nuestro caso:caso:

Desarrollo ExperimentalDesarrollo Experimental Inicio del Programa CrucigramaInicio del Programa Crucigrama Función que muestra el estado inicial del crucigrama.Función que muestra el estado inicial del crucigrama.

(defun inicial (listh)(defun inicial (listh)

(progn (prin1 " ")(terpri) (prin1 "Crucigrama de 3 (progn (prin1 " ")(terpri) (prin1 "Crucigrama de 3 Horizontales y 6 Verticales Horizontales y 6 Verticales

◘ ◘ = Casilla Negra ")(terpri)(prin1 (car listh))(terpri) (prin1 = Casilla Negra ")(terpri)(prin1 (car listh))(terpri) (prin1 (car (cdr listh)))(terpri) (car (cdr listh)))(terpri)

(prin1 (car (cdr (cdr listh)))))(prin1 (car (cdr (cdr listh)))))

(terpri)(terpri)

(prin1 " ")(prin1 " ")

))

Desarrollo ExperimentalDesarrollo Experimental4 .- Análisis de Resultados4 .- Análisis de Resultadosejemplo1ejemplo1CL-USER 4 : 3 > (inicial '((◘ 0 0 0 0 0)CL-USER 4 : 3 > (inicial '((◘ 0 0 0 0 0)(0 0 0 0 0 ◘)(0 0 0 0 ◘ ◘)))(0 0 0 0 0 ◘)(0 0 0 0 ◘ ◘)))"Crucigrama de 3 Horizontales y 6 Verticales ◘ = "Crucigrama de 3 Horizontales y 6 Verticales ◘ =

Casilla Negra “Casilla Negra “ (◘ 0 0 0 0 0)(◘ 0 0 0 0 0) (0 0 0 0 0 ◘)(0 0 0 0 0 ◘) (0 0 0 0 ◘ ◘)(0 0 0 0 ◘ ◘) " "" " " "" "


CL-USER 5 : 3 > (crucigrama '((◘ l a p i z)CL-USER 5 : 3 > (crucigrama '((◘ l a p i z)(m o u s e ◘)(c a s a ◘ ◘)))" “(m o u s e ◘)(c a s a ◘ ◘)))" “"Crucigrama de 3 Horizontales y 6 Verticales "Crucigrama de 3 Horizontales y 6 Verticales ◘ ◘ = Casilla Negra “= Casilla Negra “ (◘ L A P I Z)(◘ L A P I Z) (M O U S E ◘)(M O U S E ◘) (C A S A ◘ ◘)(C A S A ◘ ◘) " "" " " "" "

Desarrollo ExperimentalDesarrollo Experimental Ejemplo 2Ejemplo 2

CL-USER 3 : 1 > (crucigrama '((◘ l a p i z)CL-USER 3 : 1 > (crucigrama '((◘ l a p i z)

(m o u s e ◘)(c a s a ◘ ◘)))(m o u s e ◘)(c a s a ◘ ◘)))

"Crucigrama de 3 Horizontales y 6 Verticales "Crucigrama de 3 Horizontales y 6 Verticales

◘ ◘ = Casilla Negra “= Casilla Negra “

(◘ L A P I Z)(◘ L A P I Z)

(M O U S E ◘)(M O U S E ◘)

(C A S A ◘ ◘)(C A S A ◘ ◘)

" "" "

" "" "

ConclusionesConclusiones

El problema se creó en LISP, que El problema se creó en LISP, que consistió en comparar la palabra consistió en comparar la palabra colocada desintegrando letra por letra colocada desintegrando letra por letra con la base de datos que se tiene, con el con la base de datos que se tiene, con el algoritmo realizado se ha tratado de algoritmo realizado se ha tratado de encontrar una solución lo mas sencilla encontrar una solución lo mas sencilla posible.posible.

ConclusionesConclusiones El trabajo que estamos realizando El trabajo que estamos realizando

permite la construcción de un crucigrama permite la construcción de un crucigrama de la dimensión N x M que más de la dimensión N x M que más adelante si se puede, se implementará adelante si se puede, se implementará algunos grados de dificultad.algunos grados de dificultad.

Nuestro diccionario para nosotros son Nuestro diccionario para nosotros son nuestras palabras claves para la nuestras palabras claves para la creación del crucigrama, sin ese creación del crucigrama, sin ese diccionario el programa saldría error.diccionario el programa saldría error.

RecomendacionesRecomendaciones

Se deberá definir bien el método de Se deberá definir bien el método de búsqueda que se implementará, ya que búsqueda que se implementará, ya que así se encontrará la solución mas sencilla así se encontrará la solución mas sencilla y corta.y corta.

Se deberá definir los estados posibles que Se deberá definir los estados posibles que se encontrara, para así poder solucionar se encontrara, para así poder solucionar el problema lo más rápido posible.el problema lo más rápido posible.

RecomendacionesRecomendaciones

El programa está realizado para una El programa está realizado para una matriz de N x M, tener en cuenta esa parte matriz de N x M, tener en cuenta esa parte para que luego no salga error.para que luego no salga error.

Se puede realizar diferentes diccionarios Se puede realizar diferentes diccionarios para este programa, siempre y cuando para este programa, siempre y cuando cambiarlo desde su inicio del programa. cambiarlo desde su inicio del programa.

universidad san martín de porres inteligencia artificial y robóticacrucigrama integrantes aguilar...

Documents