Prueba 1

# -*- coding: UTF-8 -*-

# AIA: practica-03.py
# Problemas de Satisfaccion de Restricciones
# Dpto. de C. de la Computacion e I.A. (Univ. de Sevilla)
#==============================================================================

# En esta practica vamos a programar el algoritmo de backtracking para
# resolver PSRs, usando "forward checking" y la heuristica MRV para decidir la
#siguiente variable a asignar (ver tema 1 de teoria).

import random

#==============================================================================
# Parte I: Representacion de problemas de satisfaccion de restricciones
#==============================================================================

# En esta parte vamos a definir una clase que servira para representar
# problemas desatisfaccion de restricciones.

#------------------------------------------------------------------------------
# Ejercicio 1
#------------------------------------------------------------------------------

# Definir en python una clase PSR que represente un problema de satisfacción
# de restricciones. La clase debe tener cuatro atributos:
# - variables: una lista con las variablesdel problema.
# - dominios: un diccionario que asocia a cada variable su dominio,
# representado como una lista de posibles valores.
# - restricciones: un diccionario que asigna a cada tupla de variables la
# restriccion que relaciona a esas variables.
# - vecinos: un diccionario que asigna a cada variables una lista de las
# variables con las que tiene una restricción asociada (esdecir, una
# representacion del grafo asociado a un PSR).

# El constructor de la clase recibe solamente "dominios" y "restricciones".
# Los otros dos atributos se definen a traves de estos.

# NOTA IMPORTANTE: Por simplificar, supondremos en adelante que todas las
# restricciones son binarias y que existe a lo sumo una restriccion por cada
# par de variables.

class PSR():def __init__(self, dominios, restricciones):

self.dominios = dominios
self.restricciones = restricciones
self.variables = list (dominios.keys())

vecinos = dict()

for var in self.variables:
conjuntoR = set()
for p in restricciones.keys():
if var in p:conjuntoR.update(p)
conjuntoR.remove(var)
vecinos[var] = list (conjuntoR)
self.vecinos = vecinos








#------------------------------------------------------------------------------
# Ejercicio 2#------------------------------------------------------------------------------

# Definir una funcion n_reinas(n), que recibiendo como entrada un numero
# natural n, devuelva una instancia de la clase PSR, correspondiente al
# problema de las n-reinas.

def n_reinas_restriccion(x, y):
return lambda u, v: (abs(x - y) != abs(u - v) and u != v)

def n_reinas(n):

dominios = {x: list(range(1, n + 1)) for x in range(1, n + 1)}
#dominios = dict()
# for x in range(1,n+1):
# dominios [x] = list(range(1,n+1))

restricciones = dict()
for x in range(1, n):
for y in range(x + 1, n + 1):
restricciones [(x, y)] = n_reinas_restriccion(x, y)

return PSR(dominios, restricciones)


# Ejemplos:

# >>> psr_n4 = n_reinas(4)
# >>> psr_n4.variables
# [1, 2, 3, 4]
#>>> psr_n4.dominios
# {1: [1, 2, 3, 4], 2: [1, 2, 3, 4], 3: [1, 2, 3, 4], 4: [1, 2, 3, 4]}
# >>> psr_n4.restricciones
# {(1, 2): ,
# (1, 3): ,
# (1, 4): ,
# (2, 3): ,
# (3, 4): ,
# (2, 4): }
# >>> psr_n4.vecinos
# {1: [2, 3, 4], 2: [1, 3, 4], 3: [1, 2, 4], 4: [1, 2, 3]}
# >>> psr_n4.restricciones[(1,4)](2,3)
# True
# >>> psr_n4.restricciones[(1,4)](4,1)
# False...