Python script to solve the 8 tile game, start state and end state can both be defined. Each game state is represented as a string of numbers like "123456780", where 0 represents the empty tile. It calculates solvability by doing parity check for given input.
To solve this problem, BFS algorithm is implemented. BFS has O(bd) time complexity, where b is branching factor and d is maximal tree depth - which are 3 and 31 in this case. This can be optimized by running 2 separate BFS, one from start state and another from end state. This reduces the time complexity to O(bd/2+bd/2), but introduces intesection checking to check if the trees have a common element.
When using FIFO stack to traverse the tree, intersection checking has O(m*n) time complexity. This can be optimized by using sorted arrays to store processed game states, which gives us O(m+n). But using hashmaps, we can achieve O(m) time complexity (we need to check all elements of one tree).
*typ0 - FIFO, typ2 - sorted arrays, typ3 - hashmap
**y-axis - time in seconds, x-axis - number of moves to solve the game
- translate code to english