Thank you for reading! The first section of this article discuss the game and strategy to the puzzle Flow Free. As you continue to the second section in this article I will describe the algorithm and a walk through the key components of the Python implementation for the solution for any 5x5 Flow Free puzzle.
Objective of Flow Free
The objective in the game Flow Free, is to connect each dot of the same color in a continuous line. The path of the line can not cross or overlap to a color dot/path that is not the same color. Finally before the level is complete, you cant leave a single piece of the grid uncovered.
Once you start working your way though the game, each level will gradually become unlocked. I found it extremely useful to work each level in order. As the levels increase, each level pack will becoming bigger. This will increase the grid size and also add additional dots.
No worries, if you find yourself blitzing through each level in a staggering pace, you can buy new level packs from in the app store. So you can play the Flow Free game FOREVER. With the general overview of the game, let me explain how a simple puzzle peaked my interest.
As I started to understand how to play, this directly correlated with the amount of levels I was able to complete. This encouraged me to progress further through each Flow Free level. I would often catch myself finishing a level and rework it to see how many possibilities there could be for each level, or passing the game on to a friend and see how they would solve the level. So I also want to thank my friends letting me overwhelm them with my vast amount of question on how they solved the level.
My Observations
Many of my observational questions I would ask my friends and also myself were based around the the strategy, reasoning and basic principles for succeeding each level?
Initially I would ask: "Why did you chose to start at that particular dot?"
Easy Dots First.
Was the chosen dot the closest to it's corresponding dot? If this was the case, this strategy could suggest to solve the puzzle, one must connect the closest corresponding dots together first and then continue to the next closest dots, etc.
Outside Inside.
Was the chosen dot on the outside also with its corresponding dot on an outside edge. This could suggest the strategy some what like the old snake game. In order to be successful one must complete the outside-most dots first to ensure an easy possible pathway for the inner most dots.
I Liked The Dot Color.
Nuff said. Sometimes one must go on their intuition and know that completing their favorite color dots first, delivered confidence that the level was less difficult. All games are mental, just like a baseball player who's team is on a winning streak and wears the same pair of boxers to the ballpark the next day to ensure that his team keeps winning. Or maybe they just told me this so I wont ask any further questions and let them play the game without converse. They know I love them.
While examining how different the everyone's strategy was, it only motivated me more to find the answer. My first stop was Google which lead me to my first theory. Theory 1: Teacher is Always Right. Considering that the entire population of my observations were still attending college, I put myself in their shoes. How can we prove who complete the puzzle correctly? Is it possible to have multiple correct answers? To answer this, I went online and looked up the cheat codes per level to see who's path matched the solution. In school, the teachers solution is always right (supposedly). Analyzing the results to everyone's strategy, there still wasn't a consistent strategy that proved to baron higher respect over the others. And provided that finding a solution cannot be solved by looking at the answers because it doesn't matter if the teacher's path and my path are the same. All that matters is if the problem has been solved with the requirements met. The answer must be on the how, and the best way to find the order of operations is by constructing an algorithm.
One of my friends, Sarah told me that she stayed up all night one day bustling through each level, she was on a mission. There comes a time when something challenging peaks your interest that challenges you to see how far you can go. Have you ever had the notion to see how far out you can swim in an open body of water?
My basic strategy for succeeding in Free Flow is as follows:
Objective: Find out the most efficient way of finding the shortest path between 2 nodes in a graph with a connecting edge cost that goes through the subset of nodes.
Solution: Return a list with the tiles coordinates searched when looking for goal node.
Color Connect Algorithm [CCA]: A Recursive Walk
My strategy was use a nested list of integers to represent the map locations maze as an adjacent matrix.
Identify and map each dot and their corresponding dot.
- Path1 list = starting point
- Path2 list = ending point
Use a nested list of numbers to visualize as the Flow Free map.
- The values used in the maze are the following:
- 0: empty cells
- -1: Noncurrent starting or ending points
- 1: Starting Point
- 'x': Ending Point
Start from the current starting point that is set to '1' and move recursively to all of its 0 neighbors and set to '2'. Append to all 2's to the list. Then mark all of the '0' neighbors of '2' to '3' and append to the list. This will recursively happen until the destination of cell 'x' is reached.
When cell 'x' has been reached, we know have found the path from our starting dot to the ending dot. To find our way back we will again recursively move from 'x'-1 until we have reached 1=1. There should only be one cell that is marked with a '1'.
Save path and move to the next starting and ending point in the list still path1|2 is empty.
It took me a whole month to develop, research, implement, and code this algorithm. Using a recursive algorithm isn't the most efficient algorithm. However, now that I have my first program and algorithm under my belt, my idea list has definitely grown. Solving problems now utilizing a newly discovered and developed algorithmic mind, critically solving problems have become interesting.
Here is my code that can be viewed and forked on GitHub: https://github.com/plhale/Flow-Free.py
Color Connect Algorithm [Detailed]
Objective: Here I am explaining my algorithm in an in depth analysis. One reason I am doing this is for my knowledge purposes. Writing my understanding of the different parts will help me solidify some of the fundamental principles that I have learned creating this algorithm.
Please note, efficiently in the CCA was not my objective but the execution of solving a problem by implementing an algorithm. I encourage all feedback please. But I ask as this is my first algorithm post and explanation I ask for a note of positive feedback after explaining any non-positive assessment/criticism/evaluation. :) Thanks PH
Discovering the fundamentals of algorithms, as a beginner there isn't perfect algorithm, just scale of most effective to not as effective. I will start my in depth analysis of the CC Algorithm by showing the final output first as an overall understanding to ease the explanation from the beginning. Funny, because if we break down the essences of the CC Algorithm objective and my last sentence they are essentially the same. I am identifying the starting and end to find the shortest-path|clear-explanation. Guess this proves algorithms are all around us. Lets start!
Intro to the CCA Solution
All 3 pictures are visuals of the final path of each corresponding point that represents solution of which the CCA will solve.
Every great idea has to be drawn out. It is important to visualize a problem to understand the essential point. The CCA assumes that the problem is a 5x5 matrix. However in code a 5x5 matrix is actually a 4x4 matrix with each cell starting from 0:4.
1. Identify and map each dot and their corresponding dot.
CCA will initialize the user with a 5x5 adjacent list that will assist in successfully locating neighbours over the number of nodes with will be linear. With the assumption that a 5x5 Flow Free Level has at most 5 corresponding dots.
The user will first identify and plot the starting dot location on the CCA map and then plot the ending corresponding dot's location. Each plot placement will initialize the callback() function that maps the location to 3 different list. Explanation of each list as follows :- b: list connected to user display using Python module tkinter with callback() function for proper formatting for visualisation (ie color)
- states: location of the users identified dots
- default: copy of states list for recursive map cleanings to original states
In addition, as each dot identified, Path1 and Path2 list will append the location of each starting and destination dots respectively. This will assist us with understanding the paths for each respective flow.
2. Use a nested list of numbers to visualize as the Flow Free map.
When the user has finished mapping the starting dot (Path1 list) and destination|ending dot (Path2 list). Function startQueue will initialize and will create a empty new list called pathway that will be contain the complete list of the CCA paths for each corresponding points.
For my readers who aren't Python or coders, essentially this the functionality of the startQueue function.
- Identify the number of paths the user has selected. If Path1 and Path2 length do not equal the algorithm will terminate. If path1 and path2 are the same length we can assume the in the CCA map there is a starting point for every ending point. With this understanding, the startQueue will continue to identify the starting and destination nodes until there are no more left to connect.
The states list that contains all of the coordinates of the each point will be named Maze.
Where to start? Well with my observation and analyse that led to the CCA solution. Starting and ending points are irrelevant as long as they exist within the realm of the required rules. The starting point will be where the user has select as the starting point.
The algorithm will extract the coordinates of the starting dot [x,y = path1.pop(0)] (row, column) and place it in queue. The starting x,y accordance will be given the value = '1' on the Maze. As a receptive piece which I can probably figure an efficient way, we will take the same steps to take the first coordinate [x,y = path2.pop(0)] that is located in Path2 list to sequence the destination dot. The x,y coordinate for path2 will be given the value of 'x' in the Maze.
Recursive, recursive, recursive.
We now have the starting and ending values and coordinate placed on the Maze. Note: we copied the states list with MAZE so now we have all of the necessary blocks in place to find the first path. The starting point will call a sequence of function, described as follows:
- le () function will set x,y to the starting point and will call the move function
- move () function will add the neighbors of x,y to the queue and mark it will cost. The cost to take one step to more from here to there will always b the current cost + 1. To move to an adjacent available cell the moves() function is called.
- moves() function returned the coordinate of each possible one step move from current x,y position. This will return a list of coordinate that will then be looped through the neighbor of the value of MAZE x and y coordinates. remember initially if the user did not identify the cell as a dot, the cell start off with a value of '0'.
- if the x and y coordinates received form moves is returned TRUE by function valid()
- valid() function returns a True of False statements identifying if the neighbor x,y on maze are with int the boundaries of the 5x5 matrix.
- if valid = true
- we look at the value of x,y on the maze to identify if that neighbor's value equals a '0' or a 'x'.
- if neighbor x,y = '0' we will put the neighbor into the end of the queue and change the cost from 0 to value +1 in this case it is 2. Taking one step going from the starting cell value of '1'.
- if the neighbor x,y value on the Maze = 'x' we have found the destination and will note the neighbor of the final +1 cost and will exit the queue to by noting found = False to prevent any continuing moves.
Until 'x' has been found steps 2-4 will continue to travel and return the +1 steps.
Pathway to home.
Now, perspectively speaking, we are sitting at the destination dot. Similar to the previous recursive explanation to find 'x', CCA will again use this method to from the starting point. CCA will then initiate the leSteps() function which will use the destination coordinates, the pathway list, and create a new list called steps that will added a new location to the list as the retrace function is called. As the x,y values in maze is less than '1', the retrace function will continue to take one step back and add location to steps. Based on the maze values, the beginning cell will always be 1 and the destination cell will always be the number of steps from 1. Function retrace will loop through each adjacent cell in maze x,y that has a value equal to 1-current cell value.
When x,y finally moves though all the neighbors to find the only value in the maze as '1' the loop will terminate and a function will reverse all the items in list since we started at the destination cell and add this list of path in the pathway list.
Found a path on to the next identified start and destination dots.
The maze will then be cleared and given its original values from the default list to start on the new set of starting and destination coordinates and paths.
All Paths Found.
When the final starting and destination points have been found and paths added to the list of all paths in pathways. All that is left is to party. The CCA will loop though each set of starting/correlated path/ending points from the pathway list and plot them in b list which gives the solution to the maze connecting all respective paths.
Conclusion
I am incredibly happy with everything noted above. I have a notebook full of 'lesson learns' and just though this written analysis I have discovered many things that will be applied to future project. For right now, I am finished with the CC Algorithm and on to the next problem to solve. Some future applications that I am considering using some functionality to the CC Algorithm is introducing sensors and optics. Now that I can identify the shortest path between 2 nodes, this knowledge will be applied everywhere. The ability to connect 2 components together strategically is a great obstacle to overcome and to understand.
No comments:
Post a Comment