SHARE
TWEET

Jumper Puzzle Solver

a guest Jan 7th, 2014 370 Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
  1. FORCED_MOVE_ENABLED = True
  2. SIZE = 10
  3. BOARD_SIZE = SIZE*SIZE
  4.  
  5. is_occupied = [False]*BOARD_SIZE
  6.  
  7. move_locations = [-1]*BOARD_SIZE
  8. move_tried = [-1]*BOARD_SIZE
  9. move_index = 0
  10. move_locations[0] = 0
  11. turn = 0
  12. print "initialized"
  13.  
  14. move_list = [(-2,2),(-2,-2),(2,-2),(2,2),(3,0),(0,3),(-3,0),(0,-3)]
  15. move_count = len(move_list)
  16.  
  17. def Get_xy(var):
  18.     x = var%SIZE
  19.     y = var/SIZE
  20.     return (x,y)
  21.    
  22. def Get_Location(x,y):
  23.     if(x<0 or x>=SIZE or y<0 or y>= SIZE):
  24.         return False
  25.     else:
  26.         return SIZE*y+x
  27.        
  28. best_so_far = 1
  29.  
  30.  
  31. def print_board(move_locations, write_to_file):
  32.     if write_to_file:
  33.         f = open('output.txt', 'w')
  34.     board_text = ["  "]*BOARD_SIZE
  35.     for i in range(0,BOARD_SIZE):
  36.         location_moved_to = move_locations[i]
  37.         if(location_moved_to != -1):
  38.             if(i <10):
  39.                 board_text[location_moved_to] = "0" + str(i)
  40.             else:
  41.                 board_text[location_moved_to] = str(i)
  42.     for y in range(0,SIZE):
  43.         print_string = ""
  44.         for x in range(0,SIZE):
  45.             print_string = print_string + board_text[SIZE*y+x] + "|"
  46.         print print_string
  47.         if(write_to_file):
  48.             f.write(print_string + "\n")
  49.     print " "
  50.    
  51. def make_move(current_x, current_y, move):
  52.     move_x, move_y = move
  53.     new_x = current_x+move_x
  54.     new_y = current_y+move_y
  55.     return Get_Location(new_x,new_y)
  56.    
  57. def get_forced_moves(current_location):
  58.     global move_list, is_occupied
  59.     current_x,current_y = Get_xy(current_location)
  60.     forced_moves = []
  61.     for move in move_list:
  62.         new_location = make_move(current_x,current_y, move)
  63.         if(new_location and not is_occupied[new_location]):
  64.             exits = 0
  65.             new_x, new_y = Get_xy(new_location)
  66.             for move_2 in move_list:
  67.                 dest = make_move(new_x, new_y, move_2)
  68.                 if dest and not is_occupied[dest]:
  69.                     exits +=1
  70.             if(exits <= 1):
  71.                 forced_moves = forced_moves +[new_location]
  72.     return forced_moves        
  73.        
  74. while(turn >= 0):
  75.     current_location = move_locations[move_index]
  76.     current_x, current_y = Get_xy(current_location)
  77.     if(move_tried[move_index] == move_count-1): #tried all directions so go backward
  78.         is_occupied[current_location] = False
  79.         move_locations[move_index] = -1
  80.         move_tried[move_index] = -1
  81.         move_index-=1
  82.         turn -= 1
  83.     else:
  84.         move_tried[move_index]+=1 #try next direction
  85.         #print move_tried[move_index]
  86.         current_move = move_list[move_tried[move_index]]
  87.         new_location = make_move(current_x, current_y,current_move)
  88.         if(new_location and not is_occupied[new_location]):
  89.             turn+=1
  90.             move_index+=1
  91.             is_occupied[new_location] = True
  92.             move_locations[move_index] = new_location
  93.             has_forced_moves = FORCED_MOVE_ENABLED
  94.             while(has_forced_moves and turn < BOARD_SIZE - SIZE*2): #fairly arbitrary stopping point
  95.                 forced_moves = get_forced_moves(new_location)
  96.                 if(len(forced_moves) == 0):
  97.                     has_forced_moves = False
  98.                 elif(len(forced_moves) > 2): #multiple forced moves = failure
  99.                     has_forced_moves = False
  100.                     move_tried[move_index] == move_count-1 #count as though I tried every move
  101.                 else: #exactly 1 or 2 forced moves
  102.                     move_tried[move_index] == move_count-1 #count as though I tried every move
  103.                     turn+=1
  104.                     move_index+=1
  105.                     new_location = forced_moves[0]
  106.                     is_occupied[new_location] = True
  107.                     move_locations[move_index] = new_location
  108.             #print_board(move_locations, False)
  109.     if turn > best_so_far:
  110.         print "better board", turn+1
  111.         print_board(move_locations, False)
  112.         best_so_far = turn
  113.     if turn == BOARD_SIZE-1:
  114.         print "tour found"
  115.         print_board(move_locations, True)
  116.         break #stop since we found a tour (remove this to find multiple tours)
  117.        
  118. print "done"
RAW Paste Data
Want to get better at Python?
Learn to code Python in 2017
Top