 # Jumper Puzzle Solver

a guest
Jan 7th, 2014
1,102
0
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
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
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"