SOLUCION DE PROBLEMAS CON BÚSQUEDAS

FORMALIZACION DE PROBLEMAS UTILIZANDO ALGORITMOS DE BÚSQUEDAS

1.       MISIONEROS Y CANÍBALES

“Tres misioneros y tres caníbales están en la orilla de un rio con una canoa. Todos quieren llegar al otro lado. La canoa solamente puede llevar un máximo de dos personas al mismo tiempo. En ningún momento debe haber más caníbales que misioneros en el mismo lado del rio puesto que los caníbales se comerían al misioneros”

1.        SUDOKU

“El sudoku es un rompecabezas que consiste en llenar una cuadrícula de 9x9 con los dígitos del 1 al 9 de manera que cumplan las siguientes reglas:

-          Ningún dígito puede aparecer más de una vez en una línea.

-          Ningún dígito puede aparecer más de una vez en una fila.

-          Ningún dígito puede repetirse en el mismo cuadrito de 3x3.

ESTADO INICIAL

Una cuadricula de 81 cuadritos divididos en 9 cuadros de 3x3 con números en algunos cuadros.

Operadores.

•  El programa usará el método de suposición en cada celda para resolver la matriz del sudoku.

Pero antes de realizar tal suposición, debe de aplicar el método del escaneo (por fila, por columna, por bloque) para obtener las lista de dígitos candidatos a usar en la toma de dígitos supuestos.

Se deben de tener funciones que validen si un sudoku está formado correctamente y si es resoluble para a siguiente iteración.

Así pues, se pueden obtener 81 operadores cada uno tomando como suposición un digito de los candidatos disponibles en cada celda no llenada.  Si la celda ya contiene un digito fijado, no se hace ninguna suposición.

• Estos 81 operadores son reducibles a un solo operador si es que no fuera por la restricción impuesta por las funciones de búsqueda no informada e informada que ha entregado el profesor.

ESTADO FINAL

El estado objetivo es cuando cada una de los 81 cuadritos tiene un número escrito que cumpla que ese número no se repita en su misma columna, su misma fila y su mismo cuadrito de 3x3. (Hay 9 cuadritos de 3x3)

2.       RUBIK

“El Cubo de Rubik es un rompecabezas tridimensional que consiste en un cubo donde cada cara está dividida en una cuadricula de 3x3 y cada cuadro está pintado de un color. 

ESTADO INICIAL

Cada nodo es sustituible por cualquier otro

6caras ! 3casillasx ! 3casillasy ! 6colores = 324nodos

ESTADO FINAL

Todas las caras pintadas del mismo color.