test post 2

In the broad field of artificial intelligence, there is the exciting branch of state-space search problems that is filled with all of your favorite puzzles: Sudokus, sliding puzzles, also known as 8-puzzles, 15-puzzles, …, the Tower of Hanoi (recursion lecture flashbacks, anyone?), the pancake sorting problem that we use as an example later, the n queens problem and many more. Maybe you had to write algorithms to solve some of these or other search problems of that style. Chances are also that you had a uniquely tailored algorithm for each of these problems, which is quite tedious. In this article, I want to show you how these (and other) problems are connected and how to write a meta-algorithm that solves all of them. SPOILER: Find the code on my Github. State-Space Search Problems The problems — which I will also call games from now — above are not as complex as chess, Go, or any advanced computer game. Still, they are interesting to study, and solving some of them can be NP-hard already, i.e. probably there exist no polynomial-time algorithms to solve them in general. Let me sketch which kind of games we will solve now. Games have several game states, one of them being the initial state that we will find when we start the problem. A game state is just all the essential information about the status of the game. In a Sudoku, this might be the field including all of the numbers. it can be conveniently represented as a 9×9 matrix filled with digits, with a 0 for empty fields, for example. From Wikipedia. You can take an action to change one game state to another game state. In a Sudoku, filling in numbers are the only actions you can take. You have to specify an empty cell and a number, and then write the number into the specified cell, changing the game state. Edited by the Author. Number 4 was written into a cell. There is also a goal state that we try to reach, that lets us win the game. In a Sudoku, each row, column and block have to show all digits 1–9 exactly once. Solving Search Problems Okay, if you have taken a look into some of the above problems and puzzles, you have probably noticed that they all seem quite different. How can we combine them into a single framework? Well, the following is the only secret: Solving search problems boils down to graph traversal. So, what does that mean? I hope that you have heard about algorithms like depth-first search (DFS) and breadth-first search (BFS). These algorithms allow you to walk through a graph systematically, just like we want to systematically solve these puzzles. If you are new to this, just read on because you will learn about them now. Let us use the pancake sorting problem as an example because it is less complex than Sudoku and you can see a different setting for game states and actions. Pancake Sorting 🥞 The problem can be described like this: You have a disordered stack of n pancakes of different sizes. You want to sort this pile (smallest pancake on top, largest one at the bottom) using a spatula by flipping parts of the stack. See the following picture as one example of one possible action: From Wikipedia. Let us number the pancakes according to their size, 1 being the smallest and 6 the biggest. In the picture above, we are in the game state (2, 1, 4, 6, 3, 5), top to bottom. Using the action “Flip at position 3”, we can turn the old game state into the new one (4, 1, 2, 6, 3, 5), i.e. the order of the top 3 pancakes is reversed. Systematic Solution For 4 Pancakes Let us assume that we start in the initial game state (4, 2, 1, 3). Again, 4 is the largest pancake, and 1 is the smallest. I record the game state from top to bottom.