Tecnologia

ANALISÍS E IMPLEMENTACIÓN DEL ALGORITMO BUSQUEDA CON VUELTA ATRÁS PARA PSR PARA LA RESOLUCIÓN DEL SUDOKU

Ruth Hidalgo, Irina Veintimilla
rahidalgox@utpl.edu.ec, iaveintimilla@utpl.edu.ec

Resumen
El presente trabajo contiene aspectos importantes de los agentes inteligentes y la resolución de problemas. También Fijamos las características del agente requerido, definimos la arquitecturay realizamos pruebas reales llevadas a cabo en base a una implementación de un programa que utiliza de forma conjunta algunas de las técnicas de búsqueda y satisfacción de restricciones para el popular juego Sudoku.
*
1. INTRODUCCIÓN

El problema que se propone abordar en este trabajo es la resolución del juego Sudoku.
Sudoku es un pasatiempo que se popularizó en Japón en 1986,aunque es originario de Estados Unidos, y se dio a conocer en el ámbito internacional en el 2005. El objetivo es rellenar una cuadrícula de 9x9 celdas (81 casillas en total) subdividida en sectores de 3x3 (también llamadas cajas o regiones) con cifras de 1 a 9 partiendo de algunos números ya dispuestos en algunas de las celdas. No se requiere operar con los números y podrían ser reemplazados porcolores, letras, figuras o cualquier conjunto de nueve elementos bien diferenciados.
El motivo de usar números es que se memorizan mejor. No se debe repetir ninguna cifra en una misma fila, columna o región. Un sudoku está bien planteado si la solución es única. [1]

En nuestro trabajo partimos de un caso concreto es decir de un sudoku que hemos puesto por defecto (figura 1.1, pero tambiénresuelve cualquier Sudoku en general.

8 | 3 |   | 0 |   | 1 |   | 4 | 7 |
5 |   |   |   | 4 |   |   |   | 3 |
  |   | 1 | 3 |   | 2 | 0 |   |   |
  | 1 |   |   |   |   |   | 5 |   |
4 |   | 8 |   | 1 |   | 3 |   | 0 |
  | 5 |   |   |   |   |   | 7 |   |
  |   | 0 | 5 |   | 7 | 6 |   |   |
6 |   |   |   | 3 |   |   |   | 2 |
3 | 2 |   | 4 |   | 8 |   | 0 | 1 |
Figura 1.1
SudokuImplementado

2. OBJETIVOS

2.1 Objetivo General:

* Implementar el algoritmo de búsqueda para resolver el problema del juego sudoku.

2.1 Objetivos Específicos:

* Comprender el sistema y reglas del juego sudoku.
* Implementar el algoritmo Backtracking.
* Realizar pruebas para verificar la eficiencia.

3. TRABAJOS RELACIONADOS
*
* En la actualidad desde elpunto de vista de la inteligencia artificial existen muchos trabajos relacionados con el juego del Sudoku a continuación vamos a citar algunos de ellos.

4.1 Algoritmos Genéticos para la Resolución de Sudokus

Este proyecto propone definir un problema, que sea apropiado para ser resuelto con Algoritmos Genéticos, para luego implementarlo y ejecutarlo para encontrar la combinación deparámetros que haga el mejor resultado en la menor cantidad de generaciones.[2]
En la figura 1.2 se representa el flujo del algoritmo a utilizar.

Figura1.2: Flujo del algoritmo genético
Tomado de: http://www.lucianobello.com.ar/sudoku/sudoku.pdf

4.2 Sudoku Solver

Este es un proyecto muy interesante, consiste en robot cuya única tarea en este mundo es resolver este pasatiempojaponés, lo cual es muy impresionante, ya que antes de poder hacer algo, primero debe entender los números sobre la hoja. Al parecer, el pequeño Sudoku Solver no tiene ningún problema.

La máquina utiliza el algoritmo Backtracking (Vuelta atrás) para resolver el Sudoku y, aunque hoy no tiene ningún problema, su creador admite que tomó mucho trabajo optimizarlo debido a que el nivel de procesamiento esbastante lento. Verdaderamente un excelente trabajo por parte del inventor sueco, utilizando simples técnicas logró crear un robot con un impresionante y original propósito. [3]
*
*
4. AGENTES

¿Qué es un agente?

Para definir un concepto de un agente existen muchos, pero hemos citado en nuestro trabajo los más relevantes:

Según Russell y Norvig ‘’un agente es cualquier...