N QueensProblem

Implements a solution for N-queens problem, where N could be any number between 4 and 10.

In [ ]:

from aigyminsper.search.CSPAlgorithms import SubidaMontanha
from aigyminsper.search.CSPAlgorithms import SubidaMontanhaEstocastico
from aigyminsper.search.Graph import State
import numpy as np
import random
import time

from aigyminsper.search.CSPAlgorithms import SubidaMontanha from aigyminsper.search.CSPAlgorithms import SubidaMontanhaEstocastico from aigyminsper.search.Graph import State import numpy as np import random import time

In [ ]:

class N_QueensProblem(State):

    def __init__(self, size, board):
        self.size = size
        self.board = board

    def env(self):
        return self.board
    
    def successors(self):
        sucessores = []
        for i in range(0,self.size):
            for j in range(0,self.size):
                if(self.board[i][j] == 1):
                    #move up
                    if((i - 1) >=0 and self.board[i-1][j] == 0):
                        temp = self.board.copy()
                        temp[i][j] = 0
                        temp[i-1][j] = 1
                        sucessores.append(N_QueensProblem(self.size, temp))
                    #move down
                    if((i + 1) < self.size and self.board[i+1][j] == 0):
                        temp = self.board.copy()
                        temp[i][j] = 0
                        temp[i+1][j] = 1
                        sucessores.append(N_QueensProblem(self.size, temp))
                    #move left
                    #if((j - 1) >=0 and self.board[i][j-1] == 0):
                    #    temp = self.board.copy()
                    #    temp[i][j] = 0
                    #    temp[i][j-1] = 1
                    #    sucessores.append(N_QueensProblem(self.size, temp))
                    #move right
                    #if((j + 1) < self.size and self.board[i][j+1] == 0):
                    #    temp = self.board.copy()
                    #    temp[i][j] = 0
                    #    temp[i][j+1] = 1
                    #    sucessores.append(N_QueensProblem(self.size, temp))
        return sucessores
                      
    def is_goal(self):
        if self.h() == 0:
            return True
        return False
    
    def description(self):
        return "Queens Problem"
    
    def cost(self):
        return 1
    
    def h(self):
        #TODO
        pass

    def randomState(self):
        self.board = self.generateBoard()
        while not self.validBoard():
            self.board = self.generateBoard()

    def generateBoard(self):
        board = np.zeros( (self.size,self.size) )
        for i in range(0,self.size):
            line = random.randrange(0, self.size)
            #column = random.randrange(0, self.size)
            board[line,i] = 1
        return board

    def validBoard(self):
        if np.sum(self.board) != self.size:
            return False
        return True

class N_QueensProblem(State): def __init__(self, size, board): self.size = size self.board = board def env(self): return self.board def successors(self): sucessores = [] for i in range(0,self.size): for j in range(0,self.size): if(self.board[i][j] == 1): #move up if((i - 1) >=0 and self.board[i-1][j] == 0): temp = self.board.copy() temp[i][j] = 0 temp[i-1][j] = 1 sucessores.append(N_QueensProblem(self.size, temp)) #move down if((i + 1) < self.size and self.board[i+1][j] == 0): temp = self.board.copy() temp[i][j] = 0 temp[i+1][j] = 1 sucessores.append(N_QueensProblem(self.size, temp)) #move left #if((j - 1) >=0 and self.board[i][j-1] == 0): # temp = self.board.copy() # temp[i][j] = 0 # temp[i][j-1] = 1 # sucessores.append(N_QueensProblem(self.size, temp)) #move right #if((j + 1) < self.size and self.board[i][j+1] == 0): # temp = self.board.copy() # temp[i][j] = 0 # temp[i][j+1] = 1 # sucessores.append(N_QueensProblem(self.size, temp)) return sucessores def is_goal(self): if self.h() == 0: return True return False def description(self): return "Queens Problem" def cost(self): return 1 def h(self): #TODO pass def randomState(self): self.board = self.generateBoard() while not self.validBoard(): self.board = self.generateBoard() def generateBoard(self): board = np.zeros( (self.size,self.size) ) for i in range(0,self.size): line = random.randrange(0, self.size) #column = random.randrange(0, self.size) board[line,i] = 1 return board def validBoard(self): if np.sum(self.board) != self.size: return False return True

In [ ]:

def main():
    N = int(input("Digite o tamanho do tabuleiro (4-10): "))
    state = N_QueensProblem(size = N, board = None)
    state.randomState()
    algorithm = SubidaMontanhaEstocastico()
    print("Initial state with h = "+str(state.h()))
    start = time.time()
    result = algorithm.search(state)
    end = time.time()
    if result != None:
        print(result.env())
        print('Final state with h = '+str(result.h()))
        print('Duration in seconds = '+str(end-start))
    else:
        print('Nao achou solucao')

def main(): N = int(input("Digite o tamanho do tabuleiro (4-10): ")) state = N_QueensProblem(size = N, board = None) state.randomState() algorithm = SubidaMontanhaEstocastico() print("Initial state with h = "+str(state.h())) start = time.time() result = algorithm.search(state) end = time.time() if result != None: print(result.env()) print('Final state with h = '+str(result.h())) print('Duration in seconds = '+str(end-start)) else: print('Nao achou solucao')

In [ ]:

if __name__ == '__main__':
    main()

if __name__ == '__main__': main()