Python Recursion with Lists code not functioning properly

Question

I am attempting to create a recursive algorithm in order to solve the "Knight's Journey" chess-based riddle, where you try to visit each space of a chessboard exactly once with a knight. My code uses recursion to split into each possible next move every time the knight is supposed to move again, but I am experiencing an error where the knight does not move for one turn, then continues on the next turn. Here is my code:

def recursivePlay(board, knightSpot, myMoves):

    if(len(board) == 63):
        print("FOUND IT\n")
        print("the seed is: ")
        print(myMoves+"\n")
        print(board)

    for i in range(8):
        moving = bash(i)
        x = moving.x + knightSpot.x
        y = moving.y + knightSpot.y

        if(not(steppedOn(board,x,y)) and validMove(knightSpot,x,y)):


            board.append(knightSpot)

            knightSpot = Spot(x,y)

            myMoves.append(i)

            recursivePlay(board,knightSpot,myMoves)

def bash(num):
    if(num < 4):
        num += 2
        return Spot(2*((-1)**int(num/2)), (-1)**int(num))
    else:
        num -= 2
        return Spot((-1)**int(num), 2*((-1)**int(num/2)))   

def validMove(knightSpot, x, y):
    tempx = knightSpot.x
    tempy = knightSpot.y

    if(tempx == x and tempy == y):
        return False

    if(abs(tempx-x) == 2):
        return (abs(tempy-y) == 1)

    if(abs(tempy-y) == 2):
        return (abs(tempx-x) == 1)


def steppedOn(myList, mySpotX, mySpotY):

    if(mySpotX < 0 or mySpotX > 7 or mySpotY < 0 or mySpotY > 7):
        return True

    check = False

    for i in myList:
        if(i.compare(mySpotX, mySpotY)):
            check = True

    return check

class Spot(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return ("{"+str(self.x)+", "+str(self.y)+"}")

    def compare(self, compx, compy):
        return self.x == compx and self.y == compy

When I run the method recursivePlay, my output is:

    FOUND IT

    the seed is: 

    [2, 0, 2, 0, 2, 0, 2, 3, 2, 4, 0, 0, 1, 3, 1, 3, 1, 3, 1, 6, 0, 2, 0, 2, 0, 4,
 2, 0, 3, 1, 1, 3, 1, 3, 2, 2, 0, 2, 5, 0, 2, 0, 2, 0, 5, 3, 1, 3, 1, 7, 2, 0, 2,
 6, 6, 4, 0, 1, 0, 5, 1, 6, 3]


    Spaces visited: 

    [{0, 0}, {2, 1}, {0, 2}, {2, 3}, {0, 4}, {2, 5}, {0, 6}, {2, 7}, {4, 6}, 
{6, 7}, {7, 5}, {5, 6}, {3, 7}, {1, 6}, {3, 5}, {1, 4}, {3, 3}, {1, 2}, {3, 1},
 {1, 0}, {2, 2}, {0, 3}, {2, 4}, {0, 5}, {2, 6}, {0, 7}, {1, 5}, {3, 6}, {3, 6},
 {5, 5}, {3, 4}, {1, 3}, {3, 2}, {1, 1}, {3, 0}, {5, 1}, {7, 2}, {5, 3}, {7, 4},
 {6, 2}, {4, 3}, {6, 4}, {4, 5}, {6, 6}, {6, 6}, {5, 4}, {7, 3}, {5, 2}, {7, 1},
 {5, 0}, {4, 2}, {6, 3}, {4, 4}, {6, 5}, {6, 5}, {5, 2}, {6, 0}, {4, 1}, {2, 0},
 {7, 3}, {6, 1}, {4, 5}, {5, 7}]

As you can see it repeats a spot at row 5 spot 5 of spaces visited and row 6 spot 5 of spaces visited. The bash function should never return 0, i.e. a lack of movement, and the validMove function also contains a conditional to prevent this. Can anyone tell me why this is happening?

cdlane · Accepted Answer · 2016-05-15 18:06:15Z

The primary problem is you're not handling recursion correctly -- you set up temporary state and recur but don't deal with potential failure of the recursion and unwinding the temporary state before trying another possibility. That's why you accumulate duplicates and quit too soon due to total length. I've reworked your code but read my note that follows regarding a larger issue:

def recursivePlay(layout, board, knightSpot, moves):

    if len(board) == layout.x * layout.y - 1:
        return True

    for i in range(8):
        newSpot = bash(i)

        newSpot.x += knightSpot.x
        newSpot.y += knightSpot.y

        if not steppedOn(board, newSpot) and validMove(layout, knightSpot, newSpot):

            board.append(knightSpot)
            knightSpot = newSpot
            moves.append(i)

            if recursivePlay(layout, board, knightSpot, moves):
                return True

            knightSpot = board.pop()
            moves.pop()

    return False

def bash(num):
    if num < 4:
        num += 2
        return Spot(2 * (-1)**(num // 2), (-1)**num)
    num -= 2
    return Spot((-1)**num, 2 * (-1)**(num // 2))

def validMove(layout, knightSpot, spot):

    if spot.x < 0 or spot.x >= layout.x or spot.y < 0 or spot.y >= layout.y:
        return False

    if abs(knightSpot.x - spot.x) == 2:
        return abs(knightSpot.y - spot.y) == 1

    if abs(knightSpot.y - spot.y) == 2:
        return abs(knightSpot.x - spot.x) == 1

    return False

def steppedOn(used_spots, spot):

    for used_spot in used_spots:
        if used_spot == spot:
            return True

    return False

class Spot(object):
    def __init__(self, x, y):
        self.x = x
        self.y = y

    def __repr__(self):
        return "{" + str(self.x) + ", " + str(self.y) + "}"

    def __eq__(self, other):
        return self.x == other.x and self.y == other.y

myMoves = []
myBoard = []
myLayout = Spot(5, 5)

if recursivePlay(myLayout, myBoard, Spot(0, 0), myMoves):

    print("FOUND IT FOR", myLayout, "\n")
    print("the seed is: ")
    print(myMoves, "\n")
    print(myBoard)

I've added the ability to specify board size. Your solution is brute force. If you read the Wikipedia article on Knight's Tour, specifically brute-force algorithms, you'll see that you can't expect this code to return a result in short order for an 8 x 8 board. I've left the code set for a 5 x 5 board, which your algorithm solves quickly, and you can increase that as patience allows and/or you add heuristics.

Collectives™ on Stack Overflow

Python Recursion with Lists code not functioning properly

1 Answer 1

1 Comment

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

1 Comment

Your Answer

Sign up or log in

Post as a guest

Related