srli · February 9, 2017 04:43 · Feb 9, 2017 · Feb 9, 2017 · Feb 7, 2017 · Feb 7, 2017
diff --git a/tour.py b/tour.py
@@ -47,9 +47,6 @@ def __init__(self, size, rules):
     def generate_board(self):
         """
         Creates a nested list to represent the game board
-        Each element is a two element tuple (x1, x2) where:
-        x1: what step of tour landed on this square
-        x2: square is reserved in rules/no
         """
         for i in range(self.h):
             self.board.append([0]*self.w)

diff --git a/tour.py b/tour.py
@@ -5,8 +5,8 @@
 around a chessboard with user-specified dimensions
 
 Written by Sophie Li, 2017
-http://blog.justsophie.com/python-knights-tour-revisited/
- """
+http://blog.justsophie.com/algorithm-for-knights-tour-in-python/
+"""
 import sys
 import time
 
@@ -33,25 +33,36 @@ def __init__(self, size, rules):
         """
         self.w = size[0]
         self.h = size[1]
+        self.initial_pos = (0, 0)
 
         self.rules = rules
+        self.reserved_positions = []
+
         self.closed_tour = False
+        self.closed_positions = []
 
         self.board = []
         self.generate_board()
 
     def generate_board(self):
         """
         Creates a nested list to represent the game board
+        Each element is a two element tuple (x1, x2) where:
+        x1: what step of tour landed on this square
+        x2: square is reserved in rules/no
         """
         for i in range(self.h):
             self.board.append([0]*self.w)
 
+        for k in rules.keys():
+            self.reserved_positions.append(rules[k])
+
     def print_board(self):
         print "  "
         print "------"
         for elem in self.board:
             print elem
+            # print [x for (x,y) in elem]
         print "------"
         print "  "
 
@@ -91,7 +102,7 @@ def sort_lonely_neighbors(self, to_visit):
 
         for neighbor in neighbor_list:
             np_value = self.board[neighbor[0]][neighbor[1]]
-            if np_value == 0:
+            if (np_value == 0) and (neighbor not in self.reserved_positions):
                 empty_neighbours.append(neighbor)
 
         scores = []
@@ -135,7 +146,6 @@ def tour(self, n, path, to_visit):
                 raise PathFound
         else:
             rule_location = self.rules.get(n+1, None)
-
             if rule_location is None:
                 sorted_neighbours = self.sort_lonely_neighbors(to_visit)
                 for neighbor in sorted_neighbours:
@@ -155,11 +165,13 @@ def tour(self, n, path, to_visit):
 
     def find_path(self, n, path, start):
         try:
+            if self.closed_tour:
+                self.closed_positions = self.generate_legal_moves(self.initial_pos)
             self.tour(n, path, start)
         except PathFound:
             if GUI_ON:
                 pygame.init()
-                size = (480, 480)
+                size = (60*self.w, 60*self.h)
 
                 model = Model(self.w, self.h, path)
 
@@ -176,5 +188,7 @@ def find_path(self, n, path, start):
     #Define the size of grid. We are currently solving for an 8x8 grid
     kt = KnightsTour(size=(8, 8), rules=rules)
     # kt.closed_tour = True #uncomment if you want a closed tour
-    kt.find_path(1, [], (0,0))
+    kt.initial_pos = (0,0)
+
+    kt.find_path(1, [], kt.initial_pos)
     kt.print_board()
diff --git a/tour_visualizer.py b/tour_visualizer.py
@@ -4,8 +4,7 @@
 import random
 
 class View(object):
-    """ Provides a view of the brick breaker model in a pygame
-        window """
+    """ Provides a view of the chessboard with specified model """
     def __init__(self, model, size):
         """ Initialize with the specified model """
         self.model = model
@@ -15,7 +14,6 @@ def __init__(self, model, size):
 
     def draw(self):
         """ Draw the game to the pygame window """
-        # draw all the bricks to the screen
         self.screen.fill(pygame.Color('white'))
 
         for j in self.model.chessboard:
@@ -29,17 +27,17 @@ def center_pixel(self, r):
         return c_pix
 
     def color_square(self, prev_square, square):
-        i = square[0]
-        j = square[1]
+        i = square[1]
+        j = square[0]
 
         r = self.model.chessboard[i][j]
 
         pygame.draw.rect(self.screen, (255, 204, 255), r)
         pygame.draw.rect(self.screen, pygame.Color('black'), r, 1)
 
         if prev_square != None:
-            i_p = prev_square[0]
-            j_p = prev_square[1]
+            i_p = prev_square[1]
+            j_p = prev_square[0]
             r_p = self.model.chessboard[i_p][j_p]
 
             c_pix_p = self.center_pixel(r_p)
@@ -54,13 +52,13 @@ def color_square(self, prev_square, square):
 
 
     def animate_path(self):
-
         running = True
         while running:
             self.draw()
             self.color_square(None, self.model.path[0])
 
             i = 1
+            print "LENGTH PATH: ", len(self.model.path)
             while i < (len(self.model.path)):
                 for e in pygame.event.get():
                     if e.type == pygame.QUIT:
@@ -69,26 +67,45 @@ def animate_path(self):
                         running = False
 
                 self.color_square(self.model.path[i-1], self.model.path[i])
+
+                if i == (len(self.model.path) - 2):
+                    self.color_square(self.model.path[i], self.model.path[i+1])
+
                 i += 1
                 time.sleep(0.25)
-
             running = False
-            
+
         j = raw_input("Press enter to end")
 
 class Model(object):
-    """ Represents the game state for brick breaker """
+    """ Represents the state of the chessboard"""
     def __init__(self, w, h, path):
         self.w = w
         self.h = h
         self.path = path
 
-        self.box_height = 480/self.h
+        self.box_height = 60
         self.chessboard = []
 
-        for i in range(self.h):
+        for i in range(self.w):
             row = []
-            for j in range(self.w):
+            for j in range(self.h):
                 r = pygame.Rect(i*self.box_height, j*self.box_height, self.box_height, self.box_height)
                 row.append(r)
             self.chessboard.append(row)
+
+
+if __name__ == '__main__':
+    #Define the size of grid.
+    m = int(raw_input("M dimension: "))
+    n = int(raw_input("N dimension: "))
+
+    kt = KnightsTour(m, n)
+    kt.initial_pos = (0,0)
+
+    #Flip the following variables depending use case
+    kt.closed_tour = True
+    kt.visualize = True
+
+    kt.closed_positions = kt.generate_legal_moves(kt.initial_pos)
+    kt.tour(1, [], kt.initial_pos)
diff --git a/tour_visualizer.py b/tour_visualizer.py
@@ -71,7 +71,9 @@ def animate_path(self):
                 self.color_square(self.model.path[i-1], self.model.path[i])
                 i += 1
                 time.sleep(0.25)
-
+
+            running = False
+
         j = raw_input("Press enter to end")
 
 class Model(object):

diff --git a/tour.py b/tour.py
@@ -0,0 +1,180 @@
+#!/usr/bin/env python
+
+"""
+This code generates the path required for a knight's tour
+around a chessboard with user-specified dimensions
+
+Written by Sophie Li, 2017
+http://blog.justsophie.com/python-knights-tour-revisited/
+ """
+import sys
+import time
+
+try:
+    import pygame
+    from tour_visualizer import Model, View
+    GUI_ON = True
+except ImportError:
+    GUI_ON = False
+
+class PathFound(RuntimeError):
+    pass
+
+class KnightsTour:
+    def __init__(self, size, rules):
+        """
+        size = size of the chessboard
+        rules = rules the tour must follow. Type is a dictionary where the key is
+        the move number (int) and the value is the location of the square.
+
+        i.e:
+
+        rules = {1: (0,0), 5: (4,5)} etc..
+        """
+        self.w = size[0]
+        self.h = size[1]
+
+        self.rules = rules
+        self.closed_tour = False
+
+        self.board = []
+        self.generate_board()
+
+    def generate_board(self):
+        """
+        Creates a nested list to represent the game board
+        """
+        for i in range(self.h):
+            self.board.append([0]*self.w)
+
+    def print_board(self):
+        print "  "
+        print "------"
+        for elem in self.board:
+            print elem
+        print "------"
+        print "  "
+
+    def generate_legal_moves(self, cur_pos):
+        """
+        Generates a list of legal moves for the knight to take next
+        """
+        possible_pos = []
+        move_offsets = [(1, 2), (1, -2), (-1, 2), (-1, -2),
+                        (2, 1), (2, -1), (-2, 1), (-2, -1)]
+
+        for move in move_offsets:
+            new_x = cur_pos[0] + move[0]
+            new_y = cur_pos[1] + move[1]
+
+            if (new_x >= self.h):
+                continue
+            elif (new_x < 0):
+                continue
+            elif (new_y >= self.w):
+                continue
+            elif (new_y < 0):
+                continue
+            else:
+                possible_pos.append((new_x, new_y))
+
+        return possible_pos
+
+    def sort_lonely_neighbors(self, to_visit):
+        """
+        It is more efficient to visit the lonely neighbors first,
+        since these are at the edges of the chessboard and cannot
+        be reached easily if done later in the traversal
+        """
+        neighbor_list = self.generate_legal_moves(to_visit)
+        empty_neighbours = []
+
+        for neighbor in neighbor_list:
+            np_value = self.board[neighbor[0]][neighbor[1]]
+            if np_value == 0:
+                empty_neighbours.append(neighbor)
+
+        scores = []
+        for empty in empty_neighbours:
+            score = [empty, 0]
+            moves = self.generate_legal_moves(empty)
+            for m in moves:
+                if self.board[m[0]][m[1]] == 0:
+                    score[1] += 1
+            scores.append(score)
+
+        scores_sort = sorted(scores, key = lambda s: s[1])
+        sorted_neighbours = [s[0] for s in scores_sort]
+        return sorted_neighbours
+
+    def tour(self, n, path, to_visit):
+        """
+        Recursive definition of knights tour. Inputs are as follows:
+        n = current depth of search tree
+        path = current path taken
+        to_visit = node to visit
+        """
+        self.board[to_visit[0]][to_visit[1]] = n
+        path.append(to_visit) #append the newest vertex to the current point
+        print "Visiting: ", to_visit
+
+        if n == self.w * self.h: #if every grid is filled
+            if self.closed_tour:
+                if path[-1] in self.closed_positions:
+                    self.path = path
+                    raise PathFound
+                else:
+                    print "Not a tour"
+                    self.board[to_visit[0]][to_visit[1]] = 0
+                    try:
+                        path.pop()
+                    except IndexError:
+                        raise Exception("No successful path was found")
+            else:
+                self.path = path
+                raise PathFound
+        else:
+            rule_location = self.rules.get(n+1, None)
+
+            if rule_location is None:
+                sorted_neighbours = self.sort_lonely_neighbors(to_visit)
+                for neighbor in sorted_neighbours:
+                    self.tour(n+1, path, neighbor)
+            else:
+                if rule_location in self.generate_legal_moves(to_visit):
+                    print "Obeying rule: ", rule_location
+                    self.tour(n+1, path, rule_location)
+
+            #If we exit this loop, all neighbours failed so we reset
+            self.board[to_visit[0]][to_visit[1]] = 0
+            try:
+                path.pop()
+                print "Going back to: ", path[-1]
+            except IndexError:
+                raise Exception("No successful path was found")
+
+    def find_path(self, n, path, start):
+        try:
+            self.tour(n, path, start)
+        except PathFound:
+            if GUI_ON:
+                pygame.init()
+                size = (480, 480)
+
+                model = Model(self.w, self.h, path)
+
+                view = View(model, size)
+                view.animate_path()
+
+            return self.path
+
+if __name__ == '__main__':
+    # rules = {2:(2,1), 3:(3,3)} #example possible ruleset
+    # rules = {2:(2,1), 3:(4,4)} #example impossible ruleset
+    rules = {}
+
+    #Define the size of grid. We are currently solving for an 8x8 grid
+    kt = KnightsTour(size=(8, 8), rules=rules)
+    # kt.closed_tour = True #uncomment if you want a closed tour
+    kt.find_path(1, [], (0,0))
+    kt.print_board()
diff --git a/tour_visualizer.py b/tour_visualizer.py
@@ -0,0 +1,92 @@
+import pygame
+from pygame.locals import QUIT, KEYDOWN
+import time
+import random
+
+class View(object):
+    """ Provides a view of the brick breaker model in a pygame
+        window """
+    def __init__(self, model, size):
+        """ Initialize with the specified model """
+        self.model = model
+        self.screen = pygame.display.set_mode(size)
+
+        self.lines = []
+
+    def draw(self):
+        """ Draw the game to the pygame window """
+        # draw all the bricks to the screen
+        self.screen.fill(pygame.Color('white'))
+
+        for j in self.model.chessboard:
+            for r in j:
+                pygame.draw.rect(self.screen, pygame.Color('black'), r, 1)
+
+        pygame.display.update()
+
+    def center_pixel(self, r):
+        c_pix = (r.x+(self.model.box_height/2), r.y+(self.model.box_height/2))
+        return c_pix
+
+    def color_square(self, prev_square, square):
+        i = square[0]
+        j = square[1]
+
+        r = self.model.chessboard[i][j]
+
+        pygame.draw.rect(self.screen, (255, 204, 255), r)
+        pygame.draw.rect(self.screen, pygame.Color('black'), r, 1)
+
+        if prev_square != None:
+            i_p = prev_square[0]
+            j_p = prev_square[1]
+            r_p = self.model.chessboard[i_p][j_p]
+
+            c_pix_p = self.center_pixel(r_p)
+            c_pix = self.center_pixel(r)
+
+            self.lines.append((c_pix_p, c_pix))
+
+            for l in self.lines:
+                pygame.draw.line(self.screen, pygame.Color('black'), l[0], l[1], 3)
+
+        pygame.display.update()
+
+
+    def animate_path(self):
+
+        running = True
+        while running:
+            self.draw()
+            self.color_square(None, self.model.path[0])
+
+            i = 1
+            while i < (len(self.model.path)):
+                for e in pygame.event.get():
+                    if e.type == pygame.QUIT:
+                        running = False
+                    if e.type == pygame.KEYDOWN and e.key == pygame.K_ESCAPE:
+                        running = False
+
+                self.color_square(self.model.path[i-1], self.model.path[i])
+                i += 1
+                time.sleep(0.25)
+
+        j = raw_input("Press enter to end")
+
+class Model(object):
+    """ Represents the game state for brick breaker """
+    def __init__(self, w, h, path):
+        self.w = w
+        self.h = h
+        self.path = path
+
+        self.box_height = 480/self.h
+        self.chessboard = []
+
+        for i in range(self.h):
+            row = []
+            for j in range(self.w):
+                r = pygame.Rect(i*self.box_height, j*self.box_height, self.box_height, self.box_height)
+                row.append(r)
+            self.chessboard.append(row)