Jigsaw puzzle and its AI algorithm

Write a jigsaw puzzle, explore the relevant AI algorithm. The restoration of the jigsaw puzzle is also called the N digital problem.

Jigsaw puzzle N digital problem breadth first search bidirectional breadth first search A* search

Game settings

To achieve a jigsaw puzzle, so that it has the following functions:

  1. Free to choose favorite pictures to play
  2. Free space
  3. The space adjacent to the box can be moved, other boxes are not allowed to move
  4. Can identify whether the image is completed, the game gives feedback when victory
  5. A key shuffle, disturb the picture box
  6. Support restart game
  7. Difficulty level: high, medium and low
  8. With artificial intelligence, automatic recovery
  9. Several artificial intelligence algorithm: breadth first search, two-way breadth first search, A* search
  10. Save game progress
  11. Read game progress

    Jigsaw puzzle and its AI algorithm Puzzle Game.png

Automatically complete the puzzle recovery

Take a look at the effect. After the Auto button, the game will move the current puzzle step by step until the restoration of the picture.

Jigsaw puzzle and its AI algorithm
automatic recovery.Gif

Picture and box

The picture can be selected by taking pictures, selected from the album, or use the built-in default image.
because the game is in the square area, so if you want to have the best game effect, we need a square cut into the picture.

Jigsaw puzzle and its AI algorithm
intercept square area.Png

After selecting a picture, you need to cut the image into n x block n. Here each box PuzzlePiece is a UIButton.
because the picture will be broken and disrupted, so each box should remember its own original position on the original, here to add a property box ID, used to save.

@interface PuzzlePiece: UIButton / / / the box in the original position, starting from 0 number @property (nonatomic, assign) NSInteger + ID; / / / create an instance (instancetype) pieceWithID: (NSInteger) ID image: (UIImage * image); @end

Difficulty selection

After cutting the image block composed of a n x n matrix, that is, n order matrix. To change the difficulty of the game, we only need to change the order of the matrix can be.
design of three levels from low to high, corresponding to the 3 x 3, 4 x 4, 5 x 5 square.

Jigsaw puzzle and its AI algorithm
difficulty selection.Gif

If we take a moment in the game box sequence is called a state, so when the order number is n, the total state of the game is the number of N – factorial.
will have a very big difference in different difficulty of the game, whether it is manual games or AI games.

  • In the low difficulty, a total of 3*3 (362880), no more, even the slowest search algorithm can be found in a short time recovery path.
Search space of Jigsaw puzzle and its AI algorithm
3 order matrix.Png
  • In difficulty, the puzzle into a 4 order matrix, the number soared to puzzle state (4*4) = 20922789888000, 20 trillion. Extensive search algorithm has basically can not find out the results until the burst memory.
Jigsaw puzzle and its AI algorithm
search algorithm takes up a lot of memory.Gif
  • At high difficulty, the puzzle becomes a 5 order square, the number of States is an astronomical figure (5*5) = 1.551121004333098e25, 10 of the 25. At this point, whether it is wide search or two-way search have been powerless, and A* can be a war.
Jigsaw puzzle and its AI algorithm 5
matrix under high difficulty.Png

Square move

In the selected photo after the puzzle is intact, then let the first struck the box into space.
from the beginning of second to move the box will be struck, but only allowed space near the box move.
every move the box, in essence, is to allow the location of the box and the exchange of space. Thinking here need to turn a small bend, the space is not empty, it is also an object, but that is a blank. So we moved the box, whether you can think, in fact, is to move the space? The answer is yes, and thinking to turn around, it is more convenient to achieve code.

Jigsaw puzzle and its AI algorithm
box mobile.Gif

Block order

Here in order to disrupt the order of the puzzle after the solution, the use of a number of random moves to achieve a number of steps to shuffle.
for n order matrix, the number of random steps can be designed as: n * n * 10. In the actual test, the number of random moves is enough to make the puzzle completely disorderly order, even if the number of random steps to increase 10 times, the number of steps required for the recovery of its change little. The number of recovery steps is related to the order of the matrix, no matter how many times it is disturbed, the number of recovery steps tends to be stable.

Jigsaw puzzle and its AI algorithm
disrupt the box order.Gif
Jigsaw puzzle and its AI algorithm
random move a certain number of steps.Png

Puzzle state

We need to define a class to represent the state of the puzzle at a certain time.
a state should hold the following properties:

  • Matrix order
  • An array of arrays, in the order of the array to represent the current state of the order of the box
  • The location of the space, the value of the square array is displayed in the blank box

At the same time it should be able to provide a way to operate the box to evolve the game state.

  • Determine whether the space can be moved to a position
  • Move the space to a position
  • Remove all squares
  • Break all squares into a random state
  • Compare with another state object to determine whether the state is equal
Just said in the course of the game, a time, arrangement of all the squares: NSObject @interface PuzzleStatus < JXPathSearcherStatus, JXAStarSearcherStatus> / / / matrix order @property (nonatomic, assign) NSInteger matrixOrder; / / / box number according to the group, from top to bottom, from left to right, the order of @property (nonatomic, strong) NSMutableArray< PuzzlePiece; *> *pieceArray; / / / space position, no space for -1 @property (nonatomic, assign) NSInteger emptyIndex; / / / create an instance of matrixOrder, at least 3 non empty, image + (instancetype) statusWithMatrixOrder: (NSInteger) matrixOrder image: (UIImage * image); / / / copy of the instance - (instancetype) copyStatus; / / / if the same judge and another state - (BOOL): equalWithStatus (PuzzleStatus * status); / / / disrupted, number of moves into random - (void) shuffleCount: (NSInteger) count; / / / remove all squares - (void) removeAllPieces; / / / space can move to a position - (BOOL) canMoveToIndex: (NSInteger) index; / / / to the mobile space to a location - (void) moveToIndex: (NSInteger) index; @end

Make games with artificial intelligence (Artificial Intelligence, AI)

We call the arrangement of a puzzle at a time as a state, and once the box moves, a new state is created.
for each state, it can be changed by changing the location of the space derived from another state, and derived from the state can be derived from some other state. This behavior is very similar to the formation of a tree, of course, the tree here refers to the data structure of the tree structure.

Jigsaw puzzle and its AI algorithm
puzzle status tree.Png

The process of deducing the moving path is to derive the state according to the current state, and then to judge whether the new state is the state of the target. If you find the target, you can return to the original path, followed by the target to find all the state. Thus, each node in the
tree needs to provide the following properties and methods:

  • Parent node reference. In order to retrieve all the states that have been retrieved from the target state, each state is required to hold a reference to its previous state.
  • Unique identifier of a node. Used in the algorithm to identify the status of the same, as well as the hash strategy to re.
  • Generating method of child nodes. Used to derive a new node, the evolution of search.
@protocol JXPathSearcherStatus < / / / state protocol; NSObject> / / / parent state (nonatomic, strong) @property id< JXPathSearcherStatus> parentStatus; / / / this state - unique identification (NSString * statusIdentifier); / / / from all the neighboring state (state), exclude the parent state. Each state needs to be assigned to the parentStatus. (NSMutableArray< id< JXPathSearcherStatus> > *) childStatus; @end

For a path search algorithm, it should know where to start and where to end.
again, as a general algorithm, not only limited to puzzle game, it also need to pass a user algorithm comparator, to determine whether two search state is equal, because it is not clear that the search algorithm is what we don’t know how to determine whether the same state of any two.
defines the path search algorithm as follows:

The definition of typedef BOOL / / / comparator (^JXPathSearcherEqualComparator) (id< JXPathSearcherStatus> status1, id< JXPathSearcherStatus> status2); / / / @interface: NSObject / / / JXPathSearcher path search start state @property (nonatomic, strong) id< JXPathSearcherStatus> startStatus; / / / @property target state (nonatomic, strong) id< JXPathSearcherStatus> targetStatus; @property (nonatomic / / / comparator JXPathSearcherEqualComparator equalComparator, strong); / / / to start the search, the search results returned. Cannot search returns nil - Search (NSMutableArray *); / / / construction path. IsLast indicates whether the incoming status is the last element of the path - (NSMutableArray *) constructPathWithStatus: (id< JXPathSearcherStatus>) status isLast: (BOOL) isLast; @end

On the “search” of the word, in the code can be understood as holding a state compared with the target state, if the two states of the search success; if not, continue to take the comparison of another state and target state, so the cycle continues until the target and find a consistent state. The difference of
algorithm is that they have different search order in the search space.

Breadth first search (Breadth First Search, BFS)

Breadth first search is a blind search algorithm, it is considered that all the state (or node) are equivalent, there is no distinction between good and bad.

Jigsaw puzzle and its AI algorithm
nature breadth first search.Gif

If we look at the state of all the need to form a tree, the search is a search and then search the next layer, until the target node to find, or search for a complete tree.

  1. We can use a FIFO (First Input First Output, FIFO) of the queue to store to search the state of the queue can give it a name called open queue, it is the open list (Open List).
  2. Then you also need to record the status of all the searched down, to ensure no repeat expansion of the searched state, note here is derived from the extended sub state, corresponding to a move to the puzzle is blank.
    because each search to a state, need to take this state to have search records to check whether this condition exists, then search records to use storage mode of how to adapt to this high frequency search needs?
    if we use an array to store all of the records that have been searched, then each search needs to traverse the entire array. When there are 100 thousand data in the table, and then search for a new state, it is necessary to do a cycle of 100 thousand to determine the new state has never been searched. Obviously, the efficiency is very low.
    an efficient method is a hash strategy, Table (Hash) can be directly mapped to the target through the key mapping, eliminating the need to traverse the entire storage space. In the Cocoa framework, there is already a data structure that can satisfy this key mapping. Here I do not have to implement a hash table, but the use of NSMutableDictionary to store the search records. We can give the storage space a name to close the heap, and some people call it the List list (Close).
  3. The search begins when opening the queue is empty, then we put the initial state into the team, the open queue has a search for the state search cycle begins.
  4. The purpose of each cycle is to search for a state. The so-called search, the front has been said, can be understood as a comparison. We need to take a state from the open queue, and if the state has been compared, the cycle is abandoned until a state that has never been compared.
  5. Take out the new state, compared with the target state, if consistent, indicating that the path has been found. Why the path has been found? Because each state holds a reference to a parent state, meaning that it records of their own which is based on a derived state, so each state must know who is on a state, in addition to the start state.
  6. After finding the target state, you can build a path. The so-called path, that is, from the beginning of the state to the target state of the search process, the state of all the connected by the composition of the array. We can start from the end of the search, put it in an array, and then put the state of the state of the matrix into the array, and then put the ancestral state in the array, until the start of the state. How to identify the starting state? When a state is found to have no parent state, it is a start state. Finally, the algorithm builds the path as a result.
  7. In the fifth step, if the new state is not found to be a target state, a new state is required to advance the search. Call the method of generating sub state, the state was generated, are appended to the queue tail, the search team will state these in later cycle. The characteristics of FIFO queue, in the circulation process, will give priority to a state of sub state all out after, then out of the sub state sub state. Enqueueing and dequeueing two step search algorithm determines the order, here the operation to achieve a breadth first search.

Breadth first search:

- (NSMutableArray * search) {if (self.startStatus self.targetStatus || ||!!! Self.equalComparator) {return nil}; NSMutableArray *path = [NSMutableArray array]; / / close heap storage has searched the state of NSMutableDictionary *close [NSMutableDictionary = dictionary]; / / open queue, stored by the searched state does not extend out of state search NSMutableArray *open = [NSMutableArray array]; [open addObject:self.startStatus]; while (open.count > 0 ID status) {/ / column = [open firstObject]; [open removeObjectAtIndex:0]; / / exclusion has been searched the state of NSString *statusIdentifier = [status statusIdentifier]; if (close[statusIdentifier]) { Continue close[statusIdentifier] = status;}; / / if you find the target state if (self.equalComparator (self.targetStatus, status)) {path = [self constructPathWithStatus:status isLast:YES]; break;} / / otherwise, extended [open addObjectsFromArray:[status state childStatus]];} NSLog (@ "total search:% @ state, @ (close.count)); return path};

Construction path:

Public construction path. IsLast said the last element of the incoming status path - (NSMutableArray) constructPathWithStatus: (id< JXPathSearcherStatus> status) isLast: (BOOL) isLast *path array] {NSMutableArray = [NSMutableArray; if (! Status) {return path;} do {if (isLast) {[path} else {insertObject:status atIndex:0]; [path addObject:status]; status = [status parentStatus]}}; while (status); return path;}
Jigsaw puzzle and its AI algorithm
3 matrix, the average search requires a search of 100 thousand states

Bidirectional breadth first search (Bi-Directional Breadth First Search)

Bi directional breadth first search is the optimization of breadth first search.
search principle
bidirectional search is the start of the state and the target state at the same time to start the search, which will produce two search state tree. Let us imagine, starting from the start state of the tree growth from the top down, starting to let the target state tree from bottom to top growth, while the growth of state node space which is filled with one by one, waiting for the two trees extended to touch.
because any state is unique, when the two search trees have touched a certain state, the two trees appear cross, the search will end.
allows two trees from the cross state node to return to the original path to build the path, and then the algorithm to connect the two paths, which is the result of the path.
can be used for conditions of
puzzle game, already know the start state (a disordered state) and the target state (image restoration of the state), and the two state is interchangeable, can start the search from the target recovery state, reverse propulsion, until you find a disorderly state at the beginning of the puzzle the. So, our jigsaw puzzle is reversible, suitable for two-way search. Bidirectional

wide search thread to achieve bidirectional search, do not need to use two threads respectively from the start and destination state to start the search, the thread can be realized, the key is to let the two open queue alternate list of elements.
in each cycle, the length of the two open queues, each time the shortest queue for the search, giving priority to the smaller tree growing sub node. Doing so allows the two open queues to maintain approximately the same length and grow synchronously to achieve the effect of balancing the two search trees.

- (NSMutableArray * search) {if (self.startStatus self.targetStatus || ||!!! Self.equalComparator) {return nil}; NSMutableArray *path = [NSMutableArray array]; / / close heap storage has searched the state of NSMutableDictionary *positiveClose = [NSMutableDictionary dictionary]; NSMutableDictionary *negativeClose = [NSMutableDictionary dictionary]; / / open queue, stored by the searched state expansion the search is not NSMutableArray *positiveOpen = [NSMutableArray array]; NSMutableArray *negativeOpen = [NSMutableArray array]; [positiveOpen addObject:self.startStatus]; [negativeOpen addObject:self.targetStatus]; while (positiveOpen.count > negativeOpen.count > ||; 0; 0) {/ / short the extended queue NSMutableArray *open; / / close the shortest queue corresponding to the pile of NSMutableDictionary *close; / / the other side of a closed reactor NSMutableDictionary *otherClose; / / find the shortest queue if (positiveOpen.count & & (positiveOpen.count; < negativeOpen.count)) {open = positiveOpen; close = positiveClose; otherClose = negativeClose; {else} open = negativeOpen; close = negativeClose; otherClose = positiveClose;} / / id = [open status column firstObject]; [open removeObjectAtIndex:0]; / / exclusion has been searched the state of NSString *status Identifier = [status statusIdentifier]; if (close[statusIdentifier]) {continue}; close[statusIdentifier] = status; / / if the state also exists in another pile that has been checked, and two cross search tree search tree, the end of if (otherClose[statusIdentifier]) {NSMutableArray *positivePath = [self constructPathWithStatus:positiveClose[statusIdentifier] isLast:YES]; NSMutableArray *negativePath = [self constructPathWithStatus:negativeClose[statusIdentifier] isLast:NO]; / / spell the pros and cons of the two path [positivePath addObjectsFromArray:negativePath]; path = positivePath; break;} / / or extended [open addObjectsFromArray:[status state childStatus]];} NSLog (@ "total search number:% @, @ (positiveClose.count + negativeClose.count - 1)); return path;}
Jigsaw puzzle and its AI algorithm
3 order matrix, two-way search requires an average search for 3500 States

A* search (A Star)

Unlike blind search, the A* algorithm is a heuristic algorithm (Heuristic Algorithm).
mentioned above, the blind search is the same for all States to search nodes, so the search of a state when the blind search does not consider this state in the end is conducive towards the target, or from a target.
heuristic search and two words, it seems that this algorithm is not feeling a little smarter? That is, heuristic search to search for the state of judgment of the judgement, will result in a sequential search algorithm plays a heuristic role, will be more excellent to get higher priority search.
we call the method for judging the state of the merits of the heuristic function, by evaluating a search cost to quantify the heuristic value.
heuristic function should be designed for different use scenarios, then in the jigsaw puzzle game, how to assess the merits of a state? There are two kinds of rough evaluation methods:

  1. You can think of a state, its position in the box more, it can restore the hope of more, this state is more outstanding, it can reduce the invalid priority search through it and deduction to the target price will be small. So we can find out the state of a state of all the number of squares as an assessment of the value of the dislocation, the less the dislocation, the better the state.
  2. If each square puzzle can pass through the adjacent blocks, freely move to the target location, then each is not in the correct position of the box from the correct position there will be a moving distance, the non linear distance is the distance of Manhattan (Manhattan Distance), we put each block from its correct position the Manhattan distance adds up, seek and can be used as the search cost value, the smaller the value will be considered more outstanding.

In fact, these two methods are only on the current state of distance of the target state cost evaluation, we also missed the point, this is the beginning of the search distance of state state is already very far, i.e. state node depth value.
in the jigsaw puzzle, we are path search, if a mobile search path out of the number of steps required very much, even if the final can puzzle restoration, it is not the path we hope. Therefore, there is an optimal solution to the problem of path search, the less the number of steps needed to move the search path, the better.
A* algorithm for the evaluation of a state node, we should take into account the cost of this node and the distance from the beginning of the cost of the target node. The total valuation formula can be expressed as:

F (n) = g (n) + H (n)

N means that a node, f (n), said the evaluation of a node, the value is equal to the node distance from the beginning of the node known price g (n) plus the estimated value of the target node H (n). Why does
say that G (n) values are identified? The g value of the child state should be +1 on the basis of its parent state at each time the child node is generated, which means that the starting state of the distance is increased by one step. Therefore, the g value of each state does not need to be estimated. The key point that
affects the efficiency of the algorithm lies in the calculation of H (n). The calculation of H value by different methods will make the algorithm have great difference.

  • When the weight of H increases, which makes H value far exceeds the g value, the algorithm tends to quickly find the target state, while ignoring the path length, so it is very difficult to search out the optimal solution is guaranteed, could mean that some more around the number of detours, step toward the goal state will be more.
  • When the weight of H is reduced, and the amount of heuristic information is reduced, the algorithm will pay more attention to the depth of search. When h (n) is 0, the A* algorithm has been reduced to the breadth first search. This is a convenient view of the above. Rigorous argument should be degraded to the Dijkstra algorithm, in this game, wide search can be equated to the Dijkstra algorithm, on the Dijkstra here do not conduct in-depth. )

The following is the valuation method of puzzle state node PuzzleStatus, in the actual test, use the square for the number of dislocation valuation effect is not obvious, so I only use Manhattan as the distance h (n) value, has been able to achieve good efficiency of the algorithm.

Just from the current state to the target state estimation of price - (NSInteger) estimateToTargetStatus: (id< JXPathSearcherStatus> targetStatus) {PuzzleStatus *target = (PuzzleStatus * targetStatus); / / calculate every square distance it right where the distance of Manhattan from NSInteger / / manhattanDistance = 0; for = 0 (NSInteger index; index < self.pieceArray.count; index + +) {/ / if (index space skip = = self.emptyIndex) {continue}; PuzzlePiece *currentPiece = self.pieceArray[index] PuzzlePiece; *targetPiece = target.pieceArray[index]; manhattanDistance = ABS ([self rowOfIndex:currentPiece.ID] - [target + ABS ([self colOfIndex: rowOfIndex:targetPiece.ID]) CurrentPiece.ID] - [target colOfIndex:targetPiece.ID]);} / / increase weight return 5 * manhattanDistance;}

The state estimation is responsible by the state class, the A* algorithm only asked state valuation results, and f (n) = g (n) + H (b) operation, to ensure that each search, are to be found in the smallest space cost, namely f minimum state.
so the question is, how do you get the smallest F value each time after each state is calculated and given the F value?
has been previously mentioned, all new state expansion will open out into the queue, if the A* algorithm is also widely found that like only put on the queue tail, then only take the first team to search for the element, then f value completely to no avail.
in fact, because each state has a f value, they have the merits of high points, the queue in the access when they should be according to their F values are carried out. At this time, need to use a priority queue (Priority Queue), it can be out of the highest priority element every time.
on the priority queue to explain and achieve, you can refer to another article, with the help of a complete two fork tree, priority queue and heap sort, here is no longer discussed.
is the following A* search algorithm code:

- (NSMutableArray * search) {if (self.startStatus self.targetStatus || ||!!! Self.equalComparator) {return nil}; NSMutableArray *path = [NSMutableArray array]; [(id< JXAStarSearcherStatus> [self) startStatus] setGValue:0]; / / close heap, storage has searched NSMutableDictionary *close = [NSMutableDictionary dictionary]; / / open queue, stored by search the state did not extend out of the search / priority queue using JXPriorityQueue *open = [JXPriorityQueue queueWithComparator:^NSComparisonResult (id< JXAStarSearcherStatus> obj1, id< JXAStarSearcherStatus> obj2) {if ([obj1 fValue] = [obj2 fValue]) {return NSOrderedSame;} / / F value The smaller, the higher the priority return [obj1 fValue] < [obj2 fValue]? NSOrderedDescending: NSOrderedAscending;}]; [open enQueue:self.startStatus]; while (open.count > 0 ID status) {/ / column = [open deQueue]; / / exclusion has been searched the state of NSString *statusIdentifier = [status statusIdentifier]; if (close[statusIdentifier]) {continue}; close[statusIdentifier] = status; if you find the target state (if / / self.equalComparator (self.targetStatus, status)) {path = [self constructPathWithStatus:status isLast:YES]; break;} / / otherwise, extended sub state NSMutableArray *childStatus = [st Atus childStatus]; / / the sub form for cost estimation [childStatus (id< enumerateObjectsUsingBlock:^ JXAStarSearcherStatus> _Nonnull obj, NSUInteger IDX, BOOL * _Nonnull stop) {/ / sub state the actual costs of state 1 [obj setGValue:[status than gValue] + 1]; / / estimate to the target state price [obj setHValue:[obj estimateToTargetStatus:self.targetStatus]]; / / price = cost + known unknown [obj setFValue:[obj + [obj gValue] cost hValue]]; / / [open.}]; enQueue:obj];} NSLog (@ "% @ @ total search:" (close.count)); return path;}

You can see that the code is based on the extensive search for modules, joined the f (n) = g (n) + H (b) operation, and the use of a priority queue as an open table, so after the improvement, the efficiency of the algorithm is not the same.

Jigsaw puzzle and its AI algorithm
3 order matrix, A* algorithm requires an average search for 300 States

Finally, the difficulty is still stuck in the battle of the explosive table A* algorithm renderings:

Jigsaw puzzle and its AI algorithm
A* search algorithm under Jigsaw puzzle and its AI algorithm
5 order square matrix

Source code

Puzzle Game:https://github.com/JiongXing/PuzzleGame