One of my favorite puzzles as a kid was the 15 puzzle. For those unfamiliar, it involves changing the orientation of 15 tiles in a 4x4 square with only 1 space. At first, I was proud I could figure out a pattern to solve the puzzle consistently on my own. With practice, I can do it without hardly thinking and quickly get it into any pattern or prove it was physically impossible... and I never gave up and popped the tiles out like my friends would.
After understanding the logic behind solving the board, I also learned ti was a great challenge for mathematicians and computer scientists to work on. At it's base, it is a path finding problem solved by swapping two tiles at a time. Unlike basic path finding used in maze finding or transportation problems in my college classes, this has more possible positions than current computers can store. Researchers have found ways to get close solutions, but can never guarantee it's the absolute shortest path.
For my program, I read what others had done and implemented some of the steps I follow when solving the puzzle myself. Without a super-computer, my goal is limiting the total puzzle positions explored for the fastest time and least amount of memory. Currently 4x4 puzzles are solved in about 0.02 - 0.03 seconds with 10 - 160 moves and most 10x10 puzzles can be solved in just over a minute.
To study how well my algorithm performs the C++ output is written to .csv files that are read and plotted with python. Using this, it is clear the final 2 rows are a weakness where more possibilities are explored than earlier on. Improving this area would likely allow the model to consistently solve larger boards and have less slow outliers in run times.
Git-Hub Code:
Yorumlar