Iyfjky

Question

So I was trying to implement BFS on a Sliding Blocks puzzle (number type). Now the main thing I noticed that is if you have a 4*4 board the number of states can be as large as 16! so I cannot enumerate all states beforehand.

So my question is how do I keep track of already visited states? (I am using a class board each class instance contains an unique board pattern and is created by enumerating all possible steps from the current step).

I searched on the net and apparently they do not go back to the just completed previous step, BUT we can go back to the previous step by another route too and then again re-enumerate all steps which has been previously visited. So how to keep track of visited states when all the states have not been enumerated already? (comparing already present states to the present step will be costly).

Side Note: I could not think of a more appropriate Stack to post this question. I am aware implementation details are generally not welcome in this Stack. — Aug 14 at 13:04
imo this is a great question for SE:AI because it's not just about implementation, but the concept itself. Not to mention, the question attracted 4 legit answers in a matter of hours. (Took the liberty of editing the title for search, and creating a BFS tag) — Aug 14 at 19:14

score 7 · Accepted Answer · 2018-08-14 14:13:50Z

You can use a set (in the mathematical sense of the word, i.e. a collection that cannot contain duplicates) to store states that you have already seen. The operations you'll need to be able to perform on this are:

inserting elements

testing if elements are already in there

Pretty much every programming language should already have support for a data structure that can perform both of these operations in constant ($O(1)$) time. For example:

set in Python

HashSet in Java

At first glance, it may seem like adding all the states you ever see to a set like this will be expensive memory-wise, but it is not too bad in comparison to the memory you already need for your frontier; if your branching factor is $b$, your frontier will grow by $b - 1$ elements per node that you visit (remove $1$ node from frontier to "visit" it, add $b$ new successors/children), whereas your set will only grow by $1$ extra node per visited node.

In pseudocode, such a set (let's name it closed_set, to be consistent with the pseudocode on wikipedia could be used in a Breadth-First Search as follows:

frontier = First-In-First-Out Queue
frontier.add(initial_state)

closed_set = set()

while frontier not empty:
 current = frontier.remove_next()

 if current == goal_state:
 return something

 for each child in current.generate_children()
 if child not in closed_set: // This operation should be supported in O(1) time regardless of closed_set's current size
 frontier.add(child)

 closed_set.add(current) // this should also run in O(1) time

(some variations of this pseudocode might work too, and be more or less efficient depending on the situation; for example, you could also take the closed_set to contain all nodes of which you have already added children to the frontier, and then entirely avoid the generate_children() call if current is already in the closed_set.)

What I described above would be the standard way to handle this problem. Intuitively, I suspect a different "solution" could be to always randomize the order of a new list of successor states before adding them to the frontier. This way, you do not avoid the problem of occasionally adding states that you've already previousl expanded to the frontier, but I do think it should significantly reduce the risk of getting stuck in infinite cycles.

Be careful: I do not know of any formal analysis of this solution that proves that it always avoids infinite cycles though. If I try to "run" this through my head, intuitively, I suspect it should kind of work, and it does not require any extra memory. There may be edge cases that I'm not thinking of right now though, so it also simply might not work, the standard solution described above will be a safer bet (at the cost of more memory).

I will be able to do that but the comparison time will start to increase exponentially — Aug 14 at 13:56
@DuttaA No the comparison time should not increase exponentially. These sets, hash sets, or whatever they happen to be called in your language of choice, should be able to test whether or not they contain any given state $S$ with constant computational complexity $O(1)$, regardless of how many elements they already contain. They're not lists, they don't test if they already contain $S$ by comparing to every currently-contained element. — Aug 14 at 13:59
@DuttaA I've added some pseudocode to describe exactly how the set would be used, hopefully that may clarify something. Note that we never ever loop through the entire closed_set, its size should never affect our (asymptotic) computation time. — Aug 14 at 14:15
Actually I was doing it using c++ I don't have any idea of hashing...Guess I'll use python now...Thanks for the answer — Aug 14 at 16:18
@DuttaA In C++ you'd probably want to use an std::unordered_set — Aug 14 at 16:52

score 14 · Answer 2 · 2018-09-01 12:08:56Z

Dennis Soemers' answer is correct: you should use a HashSet or a similar structure to keep track of visited states in BFS Graph Search.

However, it doesn't quite answer your question. You're right, that in the worst case, BFS will then require you to store 16! nodes. Even though the insertion and check times in the set will be O(1), you'll still need an absurd amount of memory.

To fix this, don't use BFS. It's intractable for all but the simplest of problems, because it requires both time and memory that are exponential in the distance to the nearest goal state.

A much more memory-efficient algorithm is iterative deepening. It has all the desirable properties of BFS, but uses only O(n) memory, where n is the number of moves to reach the nearest solution. It might still take a while, but you'll hit memory limits long before CPU-related limits.

Better still, develop a domain specific heuristic, and use A* search. This should require you to examine only a very small number of nodes, and allow the search to complete in something much closer to linear time.

yeah this is the more practically useful answer for people who want to efficiently solve the puzzle. My answer is the one for people who insist on using BFS (because they just want to see it in action, or learn how to implement it, or whatever reason). Note that BFS hopefully will not be required to store $16!$ nodes by the way; that's only the worst case, it might be able to find a solution before that time. — Aug 14 at 15:32
@DennisSoemers is correct..You are also correct..I was just trying to hone my skills... I'll move to more advanced search methods later on — Aug 14 at 16:20
are there cases where BFS can return acceptable local solutions? (I'm dealing with more like 81!*tbd-value and breadth-first seems optimal in that there are blocking factors that can be easy to miss without exhaustion. Right now we're not worried about truly strong play, rather "respectably weak" general performance over an array of unpredictable gameboard topologies.) — Aug 14 at 19:24
@DukeZhou BFS is usually used only when a complete solution is sought. To stop it early, you need a function that estimates the relative quality of different partial solutions, but if you have such a function, you can probably just use A* instead! — Aug 14 at 21:13
Instead of saying "the number of moves in the game", I'd recommend "the minimum number of moves to get to the goal". I'd think of the number of moves in the game as every move that takes you from one of the 16! states to any other, which is a lot more memory than iterative deepening uses. — Aug 14 at 22:18

Nathan S. 1513 · Answer 3 · 2018-08-15 04:31:38Z

While the answers given are generally true, a BFS in the 15-puzzle is not only quite feasible, it was done in 2005! The paper that describes the approach can be found here:

http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

A few key points:

In order to do this, external memory was required - that is the BFS used the hard drive for storage instead of RAM.

There are actually only 15!/2 states, since the state space has two mutually unreachable components.

This works in the sliding tile puzzle because the state spaces grows really slowly from level to level. This means that the total memory required for any level is far smaller than the full size of the state space. (This contrasts with a state space like Rubik's Cube, where the state space grows much more quickly.)

Because the sliding-tile puzzle is undirected, you only have to worry about duplicates in the current or previous layer. In a directed space you may generate duplicates in any previous layer of the search which makes things much more complicated.

In the original work by Korf (linked above) they didn't actually store the result of the search - the search just computed how many states were at each level. If you want to store the first results you need something like WMBFS (http://www.cs.du.edu/~sturtevant/papers/bfs_min_write.pdf)

There are three primary approaches to comparing states from the previous layers when states are stored on disk.
- The first is sorting-based. If you sort two files of successors, you can scan them in linear order to find duplicates.
- The second is hash-based. If you use a hash function to group successors into files, you can load files which are smaller than the full state space to check for duplicates. (Note that there are two hash functions here -- one to send a state to a file, and one to differentiate states within that file.)
- The third is structured duplicate detection. This is a form of hash-based detection, but it is done in a way that duplicates can be checked immediately when they are generated instead of after they have all been generated.

There is a lot more to be said here, but the paper(s) above give a lot more details.

It is a great answer..but not for noobs like me :)...I am not that expert of a programmer.. — Aug 15 at 5:50
How would undirected help you avoid duplicates in other layers? Surely you'd be able to get back to a node in another layer by moving 3 tiles in a circle. If anything, directed would help you avoid duplicates, because it's more restrictive. The linked paper talks about duplicate detection, but doesn't mention undirected or directed at all, nor seems to mention avoiding duplicates at different levels (but I could've missed that in my very brief scan of it). — Aug 15 at 13:27
@NotThatGuy In an undirected graph a parent and a child are at most distance 1 apart in the depth they are found in the BFS. This is because once one is found, the undirected edge guarantees that the other will be found immediately afterwards. But, in a directed graph, a state at depth 10 can generate children at depth 2, because the child at depth 2 doesn't have to have an edge back to the other state (this would make it depth 3 instead of depth 10). — Aug 15 at 19:10
@NotThatGuy If you move 3 tiles in a circle you create a cycle, but a BFS will explore that in both directions simultaneously, so it won't actually take you back to the much shallower depth. The full 3x2 sliding tile is shown in this demo, and you can track the cycles to see how they occur: movingai.com/SAS/IDA — Aug 15 at 19:34

Cort Ammon 1311 · Answer 4 · 2018-08-14 17:04:03Z

Ironically the answer is "use whatever system you want." A hashSet is a good idea. However, it turns out that your concerns over memory usage are unfounded. BFS is so bad at these sorts of problems, that it resolves this issue for you.

Consider that your BFS requires you to keep a stack of unprocessed states. As you progress into the puzzle, the states you deal with become more and more different, so you're likely to see that each ply of your BFS multiplies the number of states to look at by roughly 3.

This means that, when you're processing the last ply of your BFS, you have to have at least 16!/3 states in memory. Whatever approach you used to make sure that fit in memory will be sufficient to ensure your previously-visited list fits in memory as well.

As others have pointed out, this is not the best algorithm to use. Use an algorithm which is a better fit for the problem.

Manuel Rodriguez 1,08415 · Answer 5 · 2018-08-14 17:35:37Z

The 15-puzzle problem is played on a 4x4 board. Implementing this in sourcecode is done stepwise. At first, the game engine itself has to be programmed. This allows to play the game by a human operator. The 15-puzzle game has only one free element and on this element the actions are executed. The game engine accepts four possible commands: left, right, up and down. Other actions are not allowed, and it is possible to control the game only with these instructions.

The next layer for playing the game is a GUI. This is very important, because it allows to test the game engine and try to solve the game by hand. Also, a GUI is important because we need to figure out potential heuristics. And now we can talk about the AI itself. The AI has to send commands to the game engine (left, right, up and down). A naive approach for a solver would be a brute force search algorithm, which means, that the AI is sending random commands until the goal state is reached. A more advanced idea is to implement some kind of pattern database which reduces the state space. Breadth first search isn't directly a heuristics, but it is a beginning. It is equal to create a graph for testing out possible movements in a chronological way.

Tracking existing states can be done with a graph. Each state is a node, has an id and a parent id. The AI can add and delete nodes in the graph, and the planner can solve the graph for finding a path to the goal. From a programming perspective a game-engine of the 15 puzzle is the object and the list of many objects is a arraylist. They are stored in a graph class. Realizing this in source code is a bit tricky, usually the first trial will fail and the project will produce lots of errors. To manage the complexity, such a project is usually done in an academic project, that means, it is a topic for writing a paper about it which can have 100 pages and more.

FauChristian 709110 · Answer 6 · 2018-08-31 18:12:28Z

Approaches to the Game

It is true that the board has $16!$ possible states. It is also true that using a hash set is what students learn in a first year algorithms courses to avoid redundancy and endless looping when searching a graph that may contain graph cycles.

However, those trivial facts are not pertinent if the goal is to complete the puzzle in the fewest computing cycles. Breadth first search isn't a practical way to complete an orthogonal move puzzle. The very high cost of a breadth first search would only be necessary if number of moves is of paramount importance for some reason.

Sub-sequence Descent

Most of the vertices representing states will never be visited, and each state that is visited can have between two and four outgoing edges. Each block has an initial position and a final position and the board is symmetric. The greatest freedom of choice exists when the open space is one of the four middle positions. The least is when the open space is one of the four corner positions.

A reasonable disparity (error) function is simply the sum of all x disparities plus the sum of all y disparities and a number heuristically representing which of the three levels of freedom of movement exists because of the resulting placement of the open space (middle, edge, corner).

Although blocks may temporarily move away from their destinations to support a strategy toward completion requiring a sequence of moves, there is rarely a case where such a strategy exceeds eight moves, generating, on the average, 5,184 permutations for which the final states can be compared using the disparity function above.

If the empty space and positions of block 1 through 15 are encoded as an array of nibbles, only addition, subtraction, and bit-wise operations are needed, making the algorithm fast. Repeating the eight move brute force strategies can be repeated until disparity falls to zero.

Summary

This algorithm cannot cycle because there is always at least one of the permutations of eight moves that decreases disparity, regardless of the initial state, with the exception of a starting state that is already complete.

saadmrb 311 · Answer 7 · 2018-09-02 09:45:30Z

We can start with just the starting state in your queue and keep a track of the depth, and return the depth as answer once we arrive at the state with all lights switched off or return Ã¢ÂˆÂ’1once there are no more nodes left unvisited. To keep track of visited nodes, we can define a function which maps each state to an integer or string and use a map/dictionary/set to store visited states.

Following is a sample python code:

start = [[0,1,0],[1,0,0],[1,1,0]]
q = [start,]

def getStateVal(state):
val = 0
base = 1
for i in range(len(state)):
for j in range(len(state[0])):
val += base * state[i][j]
base = base * 2
return val

def toggle_bit(bit):
return 1 if bit == 0 else 0

def toggle(state, i, j):
new_state =
for r in state:
new_state.append([c for c in r])

new_state[i][j] = toggle_bit(new_state[i][j])
if i+1 < len(state):
 new_state[i+1][j] = toggle_bit(new_state[i+1][j])
if i-1 >= 0:
 new_state[i-1][j] = toggle_bit(new_state[i-1][j])
if j+1 < len(state[0]):
 new_state[i][j+1] = toggle_bit(new_state[i][j+1])
if j-1 >= 0:
 new_state[i][j-1] = toggle_bit(new_state[i][j-1])

return new_state

d =
depth = 0
while len(q) > 0:
state = q[0]
q.pop(0)
if len(state) == 0:
depth += 1
q.append(state)
else:
val = getStateVal(state)
if val == 0:
print depth
break
if val not in d:
d[val] = True
for i in range(len(state)):
for j in range(len(state)):
new_state = toggle(state, i, j)
q.append(new_state)

start represents the starting state of the board.
A value of 1 represents that the light in that position is on and 0 represents otherwise.
The empty list represents end of a level, it is used to keep track of the depth (no. of moves made to reach that position)
d is the dictionary which keeps track of visited nodes
getStateVal function maps a state to an integer, here each state is interpreted as a binary string and corresponding decimal value is treated as the integer mapped value.

score 7 · Accepted Answer · 2018-08-14 14:13:50Z

You can use a set (in the mathematical sense of the word, i.e. a collection that cannot contain duplicates) to store states that you have already seen. The operations you'll need to be able to perform on this are:

inserting elements

testing if elements are already in there

Pretty much every programming language should already have support for a data structure that can perform both of these operations in constant ($O(1)$) time. For example:

set in Python

HashSet in Java

At first glance, it may seem like adding all the states you ever see to a set like this will be expensive memory-wise, but it is not too bad in comparison to the memory you already need for your frontier; if your branching factor is $b$, your frontier will grow by $b - 1$ elements per node that you visit (remove $1$ node from frontier to "visit" it, add $b$ new successors/children), whereas your set will only grow by $1$ extra node per visited node.

In pseudocode, such a set (let's name it closed_set, to be consistent with the pseudocode on wikipedia could be used in a Breadth-First Search as follows:

frontier = First-In-First-Out Queue
frontier.add(initial_state)

closed_set = set()

while frontier not empty:
 current = frontier.remove_next()

 if current == goal_state:
 return something

 for each child in current.generate_children()
 if child not in closed_set: // This operation should be supported in O(1) time regardless of closed_set's current size
 frontier.add(child)

 closed_set.add(current) // this should also run in O(1) time

(some variations of this pseudocode might work too, and be more or less efficient depending on the situation; for example, you could also take the closed_set to contain all nodes of which you have already added children to the frontier, and then entirely avoid the generate_children() call if current is already in the closed_set.)

What I described above would be the standard way to handle this problem. Intuitively, I suspect a different "solution" could be to always randomize the order of a new list of successor states before adding them to the frontier. This way, you do not avoid the problem of occasionally adding states that you've already previousl expanded to the frontier, but I do think it should significantly reduce the risk of getting stuck in infinite cycles.

Be careful: I do not know of any formal analysis of this solution that proves that it always avoids infinite cycles though. If I try to "run" this through my head, intuitively, I suspect it should kind of work, and it does not require any extra memory. There may be edge cases that I'm not thinking of right now though, so it also simply might not work, the standard solution described above will be a safer bet (at the cost of more memory).

I will be able to do that but the comparison time will start to increase exponentially — Aug 14 at 13:56
@DuttaA No the comparison time should not increase exponentially. These sets, hash sets, or whatever they happen to be called in your language of choice, should be able to test whether or not they contain any given state $S$ with constant computational complexity $O(1)$, regardless of how many elements they already contain. They're not lists, they don't test if they already contain $S$ by comparing to every currently-contained element. — Aug 14 at 13:59
@DuttaA I've added some pseudocode to describe exactly how the set would be used, hopefully that may clarify something. Note that we never ever loop through the entire closed_set, its size should never affect our (asymptotic) computation time. — Aug 14 at 14:15
Actually I was doing it using c++ I don't have any idea of hashing...Guess I'll use python now...Thanks for the answer — Aug 14 at 16:18
@DuttaA In C++ you'd probably want to use an std::unordered_set — Aug 14 at 16:52

score 14 · Answer 9 · 2018-09-01 12:08:56Z

Dennis Soemers' answer is correct: you should use a HashSet or a similar structure to keep track of visited states in BFS Graph Search.

However, it doesn't quite answer your question. You're right, that in the worst case, BFS will then require you to store 16! nodes. Even though the insertion and check times in the set will be O(1), you'll still need an absurd amount of memory.

To fix this, don't use BFS. It's intractable for all but the simplest of problems, because it requires both time and memory that are exponential in the distance to the nearest goal state.

A much more memory-efficient algorithm is iterative deepening. It has all the desirable properties of BFS, but uses only O(n) memory, where n is the number of moves to reach the nearest solution. It might still take a while, but you'll hit memory limits long before CPU-related limits.

Better still, develop a domain specific heuristic, and use A* search. This should require you to examine only a very small number of nodes, and allow the search to complete in something much closer to linear time.

yeah this is the more practically useful answer for people who want to efficiently solve the puzzle. My answer is the one for people who insist on using BFS (because they just want to see it in action, or learn how to implement it, or whatever reason). Note that BFS hopefully will not be required to store $16!$ nodes by the way; that's only the worst case, it might be able to find a solution before that time. — Aug 14 at 15:32
@DennisSoemers is correct..You are also correct..I was just trying to hone my skills... I'll move to more advanced search methods later on — Aug 14 at 16:20
are there cases where BFS can return acceptable local solutions? (I'm dealing with more like 81!*tbd-value and breadth-first seems optimal in that there are blocking factors that can be easy to miss without exhaustion. Right now we're not worried about truly strong play, rather "respectably weak" general performance over an array of unpredictable gameboard topologies.) — Aug 14 at 19:24
@DukeZhou BFS is usually used only when a complete solution is sought. To stop it early, you need a function that estimates the relative quality of different partial solutions, but if you have such a function, you can probably just use A* instead! — Aug 14 at 21:13
Instead of saying "the number of moves in the game", I'd recommend "the minimum number of moves to get to the goal". I'd think of the number of moves in the game as every move that takes you from one of the 16! states to any other, which is a lot more memory than iterative deepening uses. — Aug 14 at 22:18

Nathan S. 1513 · Answer 10 · 2018-08-15 04:31:38Z

While the answers given are generally true, a BFS in the 15-puzzle is not only quite feasible, it was done in 2005! The paper that describes the approach can be found here:

http://www.aaai.org/Papers/AAAI/2005/AAAI05-219.pdf

A few key points:

In order to do this, external memory was required - that is the BFS used the hard drive for storage instead of RAM.

There are actually only 15!/2 states, since the state space has two mutually unreachable components.

This works in the sliding tile puzzle because the state spaces grows really slowly from level to level. This means that the total memory required for any level is far smaller than the full size of the state space. (This contrasts with a state space like Rubik's Cube, where the state space grows much more quickly.)

Because the sliding-tile puzzle is undirected, you only have to worry about duplicates in the current or previous layer. In a directed space you may generate duplicates in any previous layer of the search which makes things much more complicated.

In the original work by Korf (linked above) they didn't actually store the result of the search - the search just computed how many states were at each level. If you want to store the first results you need something like WMBFS (http://www.cs.du.edu/~sturtevant/papers/bfs_min_write.pdf)

There are three primary approaches to comparing states from the previous layers when states are stored on disk.
- The first is sorting-based. If you sort two files of successors, you can scan them in linear order to find duplicates.
- The second is hash-based. If you use a hash function to group successors into files, you can load files which are smaller than the full state space to check for duplicates. (Note that there are two hash functions here -- one to send a state to a file, and one to differentiate states within that file.)
- The third is structured duplicate detection. This is a form of hash-based detection, but it is done in a way that duplicates can be checked immediately when they are generated instead of after they have all been generated.

There is a lot more to be said here, but the paper(s) above give a lot more details.

It is a great answer..but not for noobs like me :)...I am not that expert of a programmer.. — Aug 15 at 5:50
How would undirected help you avoid duplicates in other layers? Surely you'd be able to get back to a node in another layer by moving 3 tiles in a circle. If anything, directed would help you avoid duplicates, because it's more restrictive. The linked paper talks about duplicate detection, but doesn't mention undirected or directed at all, nor seems to mention avoiding duplicates at different levels (but I could've missed that in my very brief scan of it). — Aug 15 at 13:27
@NotThatGuy In an undirected graph a parent and a child are at most distance 1 apart in the depth they are found in the BFS. This is because once one is found, the undirected edge guarantees that the other will be found immediately afterwards. But, in a directed graph, a state at depth 10 can generate children at depth 2, because the child at depth 2 doesn't have to have an edge back to the other state (this would make it depth 3 instead of depth 10). — Aug 15 at 19:10
@NotThatGuy If you move 3 tiles in a circle you create a cycle, but a BFS will explore that in both directions simultaneously, so it won't actually take you back to the much shallower depth. The full 3x2 sliding tile is shown in this demo, and you can track the cycles to see how they occur: movingai.com/SAS/IDA — Aug 15 at 19:34

Cort Ammon 1311 · Answer 11 · 2018-08-14 17:04:03Z

Ironically the answer is "use whatever system you want." A hashSet is a good idea. However, it turns out that your concerns over memory usage are unfounded. BFS is so bad at these sorts of problems, that it resolves this issue for you.

Consider that your BFS requires you to keep a stack of unprocessed states. As you progress into the puzzle, the states you deal with become more and more different, so you're likely to see that each ply of your BFS multiplies the number of states to look at by roughly 3.

This means that, when you're processing the last ply of your BFS, you have to have at least 16!/3 states in memory. Whatever approach you used to make sure that fit in memory will be sufficient to ensure your previously-visited list fits in memory as well.

As others have pointed out, this is not the best algorithm to use. Use an algorithm which is a better fit for the problem.

Manuel Rodriguez 1,08415 · Answer 12 · 2018-08-14 17:35:37Z

The 15-puzzle problem is played on a 4x4 board. Implementing this in sourcecode is done stepwise. At first, the game engine itself has to be programmed. This allows to play the game by a human operator. The 15-puzzle game has only one free element and on this element the actions are executed. The game engine accepts four possible commands: left, right, up and down. Other actions are not allowed, and it is possible to control the game only with these instructions.

The next layer for playing the game is a GUI. This is very important, because it allows to test the game engine and try to solve the game by hand. Also, a GUI is important because we need to figure out potential heuristics. And now we can talk about the AI itself. The AI has to send commands to the game engine (left, right, up and down). A naive approach for a solver would be a brute force search algorithm, which means, that the AI is sending random commands until the goal state is reached. A more advanced idea is to implement some kind of pattern database which reduces the state space. Breadth first search isn't directly a heuristics, but it is a beginning. It is equal to create a graph for testing out possible movements in a chronological way.

Tracking existing states can be done with a graph. Each state is a node, has an id and a parent id. The AI can add and delete nodes in the graph, and the planner can solve the graph for finding a path to the goal. From a programming perspective a game-engine of the 15 puzzle is the object and the list of many objects is a arraylist. They are stored in a graph class. Realizing this in source code is a bit tricky, usually the first trial will fail and the project will produce lots of errors. To manage the complexity, such a project is usually done in an academic project, that means, it is a topic for writing a paper about it which can have 100 pages and more.

FauChristian 709110 · Answer 13 · 2018-08-31 18:12:28Z

Approaches to the Game

It is true that the board has $16!$ possible states. It is also true that using a hash set is what students learn in a first year algorithms courses to avoid redundancy and endless looping when searching a graph that may contain graph cycles.

However, those trivial facts are not pertinent if the goal is to complete the puzzle in the fewest computing cycles. Breadth first search isn't a practical way to complete an orthogonal move puzzle. The very high cost of a breadth first search would only be necessary if number of moves is of paramount importance for some reason.

Sub-sequence Descent

Most of the vertices representing states will never be visited, and each state that is visited can have between two and four outgoing edges. Each block has an initial position and a final position and the board is symmetric. The greatest freedom of choice exists when the open space is one of the four middle positions. The least is when the open space is one of the four corner positions.

A reasonable disparity (error) function is simply the sum of all x disparities plus the sum of all y disparities and a number heuristically representing which of the three levels of freedom of movement exists because of the resulting placement of the open space (middle, edge, corner).

Although blocks may temporarily move away from their destinations to support a strategy toward completion requiring a sequence of moves, there is rarely a case where such a strategy exceeds eight moves, generating, on the average, 5,184 permutations for which the final states can be compared using the disparity function above.

If the empty space and positions of block 1 through 15 are encoded as an array of nibbles, only addition, subtraction, and bit-wise operations are needed, making the algorithm fast. Repeating the eight move brute force strategies can be repeated until disparity falls to zero.

Summary

This algorithm cannot cycle because there is always at least one of the permutations of eight moves that decreases disparity, regardless of the initial state, with the exception of a starting state that is already complete.

saadmrb 311 · Answer 14 · 2018-09-02 09:45:30Z

We can start with just the starting state in your queue and keep a track of the depth, and return the depth as answer once we arrive at the state with all lights switched off or return Ã¢ÂˆÂ’1once there are no more nodes left unvisited. To keep track of visited nodes, we can define a function which maps each state to an integer or string and use a map/dictionary/set to store visited states.

Following is a sample python code:

start = [[0,1,0],[1,0,0],[1,1,0]]
q = [start,]

def getStateVal(state):
val = 0
base = 1
for i in range(len(state)):
for j in range(len(state[0])):
val += base * state[i][j]
base = base * 2
return val

def toggle_bit(bit):
return 1 if bit == 0 else 0

def toggle(state, i, j):
new_state =
for r in state:
new_state.append([c for c in r])

new_state[i][j] = toggle_bit(new_state[i][j])
if i+1 < len(state):
 new_state[i+1][j] = toggle_bit(new_state[i+1][j])
if i-1 >= 0:
 new_state[i-1][j] = toggle_bit(new_state[i-1][j])
if j+1 < len(state[0]):
 new_state[i][j+1] = toggle_bit(new_state[i][j+1])
if j-1 >= 0:
 new_state[i][j-1] = toggle_bit(new_state[i][j-1])

return new_state

d =
depth = 0
while len(q) > 0:
state = q[0]
q.pop(0)
if len(state) == 0:
depth += 1
q.append(state)
else:
val = getStateVal(state)
if val == 0:
print depth
break
if val not in d:
d[val] = True
for i in range(len(state)):
for j in range(len(state)):
new_state = toggle(state, i, j)
q.append(new_state)

start represents the starting state of the board.
A value of 1 represents that the light in that position is on and 0 represents otherwise.
The empty list represents end of a level, it is used to keep track of the depth (no. of moves made to reach that position)
d is the dictionary which keeps track of visited nodes
getStateVal function maps a state to an integer, here each state is interpreted as a binary string and corresponding decimal value is treated as the integer mapped value.

Search This Blog

Iyfjky

Keeping track of visited states in Breadth-first Search

7 Answers
7

Your Answer

Post as a guest

7 Answers
7

7 Answers
7

Post as a guest

Comments

Post a Comment

Popular posts from this blog

What does second last employer means? [closed]

Installing NextGIS Connect into QGIS 3?

Confectionery

Category

Random preview

Keeping track of visited states in Breadth-first Search

7 Answers 7

Your Answer

Sign up or log in

Post as a guest

Post as a guest

7 Answers 7

7 Answers 7

Sign up or log in

Post as a guest

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Sign up or log in

Post as a guest

Comments

Post a Comment

Popular posts from this blog

What does second last employer means? [closed]

Installing NextGIS Connect into QGIS 3?

Confectionery

7 Answers
7

7 Answers
7

7 Answers
7