CODEWITHSUNDEEP
rubyrecursiondata-structuresbinary-search-treegraph-algorithm
imperial_isms
imperial_isms

Reputation: 55

Knight's Travails and Binary Search Tree

Here is some context if you're unfamiliar with Knight's Travails.

Your task is to build a function knight_moves that shows the simplest possible way to get from one square to another by outputting all squares the knight will stop on along the way.

I know where to find complete solutions to this exercise, but I'm trying to mostly work through it on my own.

Where I'm stuck is how to set up a binary tree, or, specifically, what is the relationship between all the next possible moves a knight can make from its current location?

As I understand a BST, the defining property is that a tree(and any of its subtrees and leaves) store keys that are larger to the root node to the right, and smaller keys to the left of the root node.

How do I represent the value of the knight's current location and its possible(valid) moves?

It would be more valuable if the answer provided is a more of a guiding principle (philosophy?) when thinking about BST keys/values and defining parent-child relationships.

Thank you.

Upvotes: 3

Views: 1798

Answers (1)

Prune
Prune

Reputation: 77837

This is not a BST problem. Attack this as a graph search problem with backtracking. Start by learning and understanding Dijkstra's algorithm, treating the squares of the board as nodes in a graph. For instance, a1 connects to b3 and c2; all moves have a cost of 1 (which simplifies the algorithm a little).

You'll need to build your graph either before you start, connecting all possible moves; or on the fly, generating all possibilities from the current square. Most students find that doing it on the fly is easier for them.

Also, changing from algebraic chess notation to (row, col) notation helps. If the knight is currently at (row, col), then the legal next moves are

(row+-2, col +-1) and
(row+-1, col +-2)

... where x and y are both in the range 0-7 (throw out moves that take the knight past the board's edge).

Maintain a global list of squares you've already visited, and another of squares you need to visit (one move from those you've visited). You'll also need an array of least cost (number of moves) to get to each square. Initialize that to 100, and let the algorithm reduce it as it walks through the search.

Is that enough to get you moving?

Upvotes: 3

Related Questions