Knights Travails problem (Odin project) Computer Science

Knights Travails problem (Odin project)
A short series of posts about encoding problems as Satisfiability problems
Volunteer to help high schools across the U.S. build and grow their computer science programs!
Postman API Network Exploration: Log files analysis using natural language processing

Posted: 04 May 2018 07:35 PM PDT

So I haven't reached this section yet.....but I will be, and I want to make sure I "somewhat" understand it first.

https://www.theodinproject.com/courses/ruby\-programming/lessons/data\-structures\-and\-algorithms#project\-2\-knight\-s\-travails (For a link if anyone needs).

Anyways the "concept" of the problem makes enough sense, but im getting stuck on one small part. Im simplifying of course but lets pretend were working with a 2-d array for the "board" and lets pretend that each "node" has an x coordinate and a y coordinate.

From my understanding, i'll have my "Node" with an x,y coordinate and then it's children (which is every possible move the knight could make, (up to 8 moves potentially)). I'll probably need a parent too.

So in the "checking if knight has reached end loop":

(Pretending I have a "Queue" that stores all the possible "nodes/moves"

Check if Node is at the finish node (Starting with root node)
If yes then great! go through that nodes parents all the way back to the start
If no then we produce all the possible "children" moves and store it at that nodes "children" variable which holds the array of all children moves
We pop off that beginning of the queue.

Here is where I am confused....Do we then go through all the children to see if any of the children is the "finish node" or do we start with the first child and then repeat the same (essentially recursively creating every possible move from that child).

Probably a confusing explanation so let me pretend we have some simple code like this ( in Ruby, it's psuedocode for right now):

class Node

@x #x coord

@y #y coord

@children = [] #array of children for this node/move

@parent #(nil at first for the root node, but other "children" will have a parent

end

check_loop

queue = [] #empty queue

if node.x && node.y == finish.x && finish.y

#do backtracking to find all the steps to get to the end

else

make_children(node) #make all the children for that node, and fill in @children with those 'moves'

put children into queue

queue.shift #pop off the beginning node

end

Probably makes no sense. But I guess am I asking, when Im checking a node.....and it's not the "ending" node. I make all the children for that node and push them into the queue....then pop off the beginning.....and then I start again at what would be that nodes first neighbor?

Would I be building out all the children of the first neighbor and so on? Essentially doing every move off the first nodes neighbor for infinity? Maybe im misunderstanding BFS though. it seems to me I would produce all the children for that node (if the node was NOT the finish node) and then go through each child to see if the node was a finish node and THEN if none of them were i'd build children out for each one of those and go through the whole queue again (after removing each of the original queues children.

submitted by /u/mercfh85
[link] [comments]

A short series of posts about encoding problems as Satisfiability problems

Posted: 04 May 2018 10:09 AM PDT

submitted by /u/rvprasad
[link] [comments]

Volunteer to help high schools across the U.S. build and grow their computer science programs!

Posted: 04 May 2018 03:27 PM PDT

submitted by /u/tealsk12
[link] [comments]

Postman API Network Exploration: Log files analysis using natural language processing

Posted: 04 May 2018 07:28 AM PDT

submitted by /u/SummarizeDev
[link] [comments]