Advertisement
Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- student_name = "Joshua Remba"
- ############################################################
- # Imports
- ############################################################
- # Include your imports here, if any are used.
- #import collections
- #import itertools
- #import math
- import random
- #import time
- #import numpy
- import copy
- ############################################################
- # Section 1: Tile Puzzle
- ############################################################
- def create_tile_puzzle(rows, cols):
- board = []
- counter = 1
- for i in range(rows):
- new_row = []
- for j in range(cols):
- new_row.append(counter)
- counter=counter+1
- if new_row[cols-1]==rows*cols:
- new_row[cols-1]=0
- board.append(new_row)
- return TilePuzzle(board)
- class TilePuzzle(object):
- # Required
- def __init__(self, board):
- self.board = board
- self.rows = len(board)
- self.cols = len(board[0])
- for i in range(len(board)):
- for j in range(len(board[0])):
- if not board[i][j]:
- self.mt = (i,j)
- def get_board(self):
- return self.board
- def perform_move(self, direction):
- mt_row = self.mt[0]
- mt_col = self.mt[1]
- if direction=='up':
- #print('tried to go up')
- if mt_row>0:
- self.board[mt_row][mt_col]=self.board[mt_row-1][mt_col]
- self.board[mt_row-1][mt_col] = 0
- self.mt=(mt_row-1,mt_col)
- #print('did go up')
- return True
- else:
- return False
- elif direction=='down':
- #print('tried to go down')
- if mt_row<self.rows-1:
- self.board[mt_row][mt_col]=self.board[mt_row+1][mt_col]
- self.board[mt_row+1][mt_col] = 0
- self.mt=(mt_row+1,mt_col)
- # print('did go down')
- return True
- else:
- return False
- elif direction=='left':
- #print('tried to go left')
- if mt_col>0:
- self.board[mt_row][mt_col]=self.board[mt_row][mt_col-1]
- self.board[mt_row][mt_col-1] = 0
- self.mt=(mt_row,mt_col-1)
- # print('did go left')
- return True
- else:
- return False
- elif direction=='right':
- #print('tried to go right')
- if mt_col<self.cols-1:
- self.board[mt_row][mt_col]=self.board[mt_row][mt_col+1]
- self.board[mt_row][mt_col+1] = 0
- self.mt=(mt_row,mt_col+1)
- # print('did go right')
- return True
- else:
- return False
- else:
- return False
- def scramble(self, num_moves):
- for i in range(num_moves):
- self.perform_move(random.choice(['up','down','left','right']))
- def is_solved(self):
- starting_board = create_tile_puzzle(self.rows, self.cols)
- if self.board==starting_board.board:
- return True
- else:
- return False
- def copy(self):
- new_copy = copy.deepcopy(self.board)
- return TilePuzzle(new_copy)
- def successors(self):
- for i in ['up','down','left','right']:
- #print(i)
- x = self.copy()
- x.perform_move(i)
- #print(type(x))
- if x.get_board()==self.get_board():
- pass
- else:
- #print(i)
- #print(x)
- yield i, x
- #
- # # Required
- # def find_solutions_iddfs(self,limit=0,moves=[],counter=0,visited=[[]]):
- ## while True:
- #
- # while limit<10:
- # if visited==[[]]:
- # visited = [self.board]
- # limit = limit + 1
- # print(limit)
- # if self.is_solved():
- # #print(self.board)
- # yield moves
- # elif counter<limit:
- # #continue to recurse if you haven't hit the depth limit
- ## if self.board==[[1,2,3],[4,5,6],[7,0,8]]:
- ## if [[1,2,3],[4,5,6],[7,0,8]] in visited:
- ## print('uh oh')
- ## if limit==7:
- ## print(visited)
- # for move, new_p in self.successors():
- ## print('new board to check: ', new_p.get_board())
- ## print('what was already visited: ',visited)
- # # print('visited so far:')
- # # print(visited)
- # # print('new board to add')
- # # print(new_p.board)
- # if new_p.board==[[1,2,3],[4,5,6],[7,8,0]]:
- # print('hmmmm')
- # if new_p.board not in visited:
- # moves_temp = moves+[move]
- # # print('moves: ',moves)
- # # print('moves_temp: ', moves_temp)
- # # print(new_p)
- # visited.append(new_p.board)
- # yield from self.find_solutions_iddfs(limit,moves_temp,counter+1,visited)
- # #print('after the helper call')
- # #return x
- def iddfs_helper(self,limit,moves,counter,visited):
- if self.board==[[1,2,3],[4,5,6],[7,8,0]]:
- print('it is actually solved, but it is saying it is not solved')
- if self.is_solved():
- #print(self.board)
- yield moves
- elif counter<limit:
- #continue to recurse if you haven't hit the depth limit
- # if self.board==[[1,2,3],[4,5,6],[7,0,8]]:
- # if [[1,2,3],[4,5,6],[7,0,8]] in visited:
- # print('uh oh')
- # if limit==7:
- # print(visited)
- for move, new_p in self.successors():
- # print('new board to check: ', new_p.get_board())
- # print('what was already visited: ',visited)
- # print('visited so far:')
- # print(visited)
- # print('new board to add')
- # print(new_p.board)
- if new_p.board==[[1,2,3],[4,5,6],[7,8,0]]:
- print('hmmmm')
- if new_p.board not in visited:
- moves_temp = moves+[move]
- # print('moves: ',moves)
- # print('moves_temp: ', moves_temp)
- # print(new_p)
- visited.append(new_p.board)
- yield from new_p.iddfs_helper(limit,moves_temp,counter+1,visited)
- # Required
- def find_solutions_iddfs(self):
- limit = 0
- moves=[]
- # while True:
- while limit<10:
- limit = limit + 1
- print(limit)
- yield from self.iddfs_helper(limit, moves,0,[self.board])
- #print('after the helper call')
- #return x
- #b = [[4,1,2], [0,5,3], [7,8,6]]
- #p = TilePuzzle(b)
- #solutions = p.find_solutions_iddfs()
- ##solutions = p.iddfs_helper(3,[],0)
- #print(next(solutions))
- b = [[1,2,3], [4,0,8], [7,6,5]]
- p = TilePuzzle(b)
- list(p.find_solutions_iddfs())
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement