You may have been grinding all those algorithms question on various platforms for your next interview, ever wonder when can we actually use them. Well, I got to finally see them in action while creating a board game called 8 Puzzle. It is played on a 3-by-3 grid with 8 square tiles labeled 1 through 8 and a blank square. Your goal is to rearrange the tiles so that they are in order. You can check out my implementation to get a better idea . here Count Inversion So the catch is that not all boards are solvable so how do we generate aboard for the player to be playable?. One thing is to just solve the board but how do we solve the board? more on solving the board later cause there’s a better way to find if the given board is solvable and yes without even solving it. Let’s look carefully at what each move does with respect to changing relative positions between tiles. To be more specific about these changing positions we come up with a concept of inversion. An inversion is a pair of tiles where the one appearing first is larger than the after. Formally, an is any pair of tiles and where < but appears after when considering the board in row-major order. By row-major we mean scanning row first and then the bottom. inversion i j i j i j Alright, what about inversion. The thing is that a swipe left or right does not change the number of inversions. The interesting case is though for up and down swipes, any vertical move changes the inversion by even numbers you can see it in the below example. Well so if we can change the inversion by an even number only that implies if we start with odd number of inversions we cannot reach 0 inversion which is the desirable state as odd +/- even is odd. So all we need to do is count the inversion if its odd the board is not solvable. How do we count the number of inversions? well, that’s a good question that comes up in interview. If you look closely the inversion is closely related to the sorting problem (in comparison model). The simple approach is to just look at every element greater than i and see if it is smaller. The approach is O(n²) we can take a fast sorting method like merge sort and make it more fast. It is a good length article on itself so I suggest you think about it for a bit and then google for count inversion using merge sort. A* Search (Solver) Now given a board and you are bored can you make the computer solve it for you, well you can. Just generate all board configurations until you find the correct one, good but It will take forever the idea is to make it smart by forcing it to work on the ones that are close to the solution and not working on the already generated boards obviously. How do we determine that a given board is close to the solution. The idea here is that we can calculate the distance of each tile from its actual position and assign priority with that. So the board with half of the tiles in place will have less value than one with all out of the place. By assigning higher priority to the less value board we can focus on better board smart isn’t it. The algorithm works like this the board with the highest priority is picked and it generates its children puts them in a queue and repeat until queue is empty or we find the correct board. Just keep pointers to regenerate the solution. Click play and then on solve to see it in . action Tech Stack I made it in React where I maintain the board as a state here’s the sorry though for redability, I didn’t use to focus on redabilty back then. repo reference: this Princeton . assignment find more of my projects here Also published at https://medium.com/@rishav.21m/games-and-algorithms-f10c28df0bc3
