Problem description at: http://azspcs.com/Contest/BaltosPuzzle/ My code for it is at: http://sedcore.eu.org/azspcs/2024-10.tar.gz Released in the public domain. 1 - how to use: =============== edit solve.h, set N to wanted value (between 3 and 27), then run make then run ./game then type: v (to solve all but last inner ring) then type: t (to solve inner ring, may fail) if after 't' game is not solved, do: type: z (to "solve" endgame, does not work, but then 's' and 't' seems to work) then type: s (to basic-solve, so that then 't' works) then type: t (for final inner ring) This procedure works for all games (as far as I remember). Press 'd' to dump the moves to /tmp/moves.txt Then you can run: ./translate-move < /tmp/moves.txt > /tmp/sol and submit /tmp/sol to the azspcs website. The game is also playable manually. Move the mouse to a border of the hole and click (or press 'enter'). You can press 'space' to reverse rotation (may create invalid solutions, only to be used at the beginning). Press 'c' to center the display (put the hole at center of view). 2 - how it works: ================= It's all breadth-first search! Solve stones one by one. Put the stone at its final position. Then never move it again. Order of stones is important. Solve ring by ring from outter to inner (probably bad logic). Use breadth-first search to move a stone to its position. 's' is the fastest method (but may fail, so then you need some manual moves). It chooses a shortest path of a stone, only counting the moves of the stone itself, so an actual movement of the stone from position A to position B involves several true moves, which are found by a different breadth-first search, taking care not to move previous stones that are already at their final position. 's' is bad. This notion of "shortest path of a stone" is not true because it forces the 'hole' to move a lot. But it's very fast (few seconds, even for big boards). 'v' is much better. And slower. Still breadth-first search, but the search is from the current position of a stone to its final position. (Took like more than 24 hours for the big board.) 't' is perfect. If the inner ring can reach the solution position, it gives the shortest path. 'z' is a hack, using the last ring and two stones below, which I thought would be enough to solve the last ring. We try a unrestricted breadth-first search (all involved stones can move) to reach the final position. But there is a bug in the code! In endgame.c, the line: if (memcpy(unring_stones, unring_end, 3 * sizeof(int))) { should be: if (!memcpy(unring_stones, unring_end, 3 * sizeof(int))) { So 'z' actually messes up the game. But then running 's' gives a good position of the game so that 't' works. 3 - conclusion: =============== My goal was to solve all problems, with a reasonably fast program. Goal achieved. The whole process was fun. I first wrote a GUI (graphical user interface) to play the game manually. Then I included the automatic solvers into it. This was a good idea. When I was younger, I played puzzle 15 a lot, and wrote a solver for it, running on my pocket calculator (TI85). I applied the knowledge gained at the time to this problem, which was nice. It brought back some good memories. That being said, those techniques are bad, compared to others. I finish 51 (over 169). My solutions are 3 to 4 times longer (3.8 on average) than the best submitted. My code is very dirty. I tried to structure it a bit, but the result is not clean. I did better than previous contests I would say, but it's still not it. Why is the code so bad? For one, I use techniques and algorithms I rarely use in my usual programming. I'm not familiar enough to write clean code for those. I don't know what is good practice. Second, this is a competition. We have a time limit. For azspcs contests, we have months of time available, but still, there is a limit. And you face others. You want to do good. These are sources of pressure and stress, which is not compatible (in my case) with good quality work. Also, I spend a lot of time fixing stupid bugs. Breadth-first search is very classical technique, but still, I mess up here and there and in the end I don't have much trust of the produced code, leading to fear of changing it because when something more or less works, and you don't really understand why, the risk is to break everything when you change something. And you may well introduce new bugs in the process. What to do to improve? Easy: practice more. Write various kind of software to solve various problems. Without pressure. Just for the fun of it. Find out what "stuff" is easy to write, easy to understand, easy to modify. Build good habits so that when you face the next contest, your programming tools, your "mental map", are better and you write valid software from start ("valid" meaning it implements the idea you have in mind; if the idea is bad, of course the end result will be bad, but at least it will implement the idea faithfully). I should also spend time implementing well known algorithms to get familiar with them. Face bugs in a relaxed setup.