Width of the first object traversal

Question

I make a program that solves the puzzle, and finds all possible movements on the board and puts all possible resulting boards in the object. Then he finds all possible steps for the resulting boards, etc. The object will look something like this:

{ "board": { "starts": [[0,0],[0,3]], "blocks": [[3,0],[3,3]], "ends": [[2,4]] }, "possibleMoves": [ { "board": { "starts": [[0,0],[2,3]], "blocks": [[3,0],[3,3]], "ends": [[2,4]] }, "possibleMoves":[ { "board": {}, "possibleMoves": [{}] } ] }, { "board": { "starts": [[0,3]], "blocks": [[3,0],[3,3]], "ends": [[2,4]] }, "possibleMoves":[{}] }] } 

I can understand how to add possible moves from the top-level board, but I can’t understand how to sort through all the boards received at the second level and calculate their possible moves, and then scroll through all the boards of the third level, etc. How can I add possible movements and cross an object using a width search?

Answer 1

Recursion.

 function traverse(state) { handle(state.board); if (state.possibleMoves) { $.each(state.possibleMoves, function(i, possibleMove) { traverse(possibleMove); }); } } 

EDIT: For a breadth-first search, try something like this. It does not use recursion, but instead iterates over a growing queue.

 function traverse(state) { var queue = [], next = state; while (next) { if (next.possibleMoves) { $.each(next.possibleMoves, function(i, possibleMove) { queue.push(possibleMove); }); } next = queue.shift(); } } 

Answer 2

Not fully tested:

 var oo = { board: { starts: [[0,0],[0,3]], blocks: [[3,0],[3,3]], ends: [[2,4]] }, possibleMoves: [{ board: { starts: [[0,0],[2,3]], blocks: [[3,0],[3,3]], ends: [[2,4]] }, }], }; function traverseObject (o) { for (var prop in o) { if (typeof o[prop] == "array" || typeof o[prop] == "object") { traverseObject(o[prop]); console.log(prop); } else { console.log(prop, "=", o[prop]); } } } traverseObject(oo); 

Answer 3

I don't have a JavaScript description, but I usually do this by keeping a queue of unexplored nodes.

• Start with the root node in the queue.
• Place an item from the front of the queue
• Investigate this, add all the nodes found during the investigation, in the opposite direction of the queue.
• Check if there are any nodes in the queue if they return to step 2
• Made by

There are also a few pseudopods on the Wikipedia page, as well as some explanations HERE

In addition, a quick Google search showed a similar algorithm that could be aimed towards the goal HERE