星期五的鏡子多尼莫斯問題


6

幫助四個鬼在一個鬼屋裡互相發現。我剛剛添加了一個我的多米諾拼圖和遊戲集合Donimoes的新拼圖,所以我以為我會在這裡發布一些獎金問題。難題是《鏡子多尼莫斯》,鬼是四隻在多米諾骨牌上走來走去的棋子找到對方。每個多米諾骨牌都是房子裡的一個房間,鬼魂不能走通過關閉的門。他們可以穿過鏡子。詭異!

有關完整規則和示例解決方案,請參見Monday's問題。

今天的問題比Wednesday's更大,更具挑戰性,它使用完整的雙六個多米諾骨牌。祝您好運,並將您的解決方案發佈為回答。

Friday problem

4

There ended up being a LOT of pictures. Instead of just posting them in a giant block, I'm going to make up a story. It's not going to be one about ghosts because my brain sees the dominoes as boats for some reason. This is going to be long.

Rook was feeling quite sad, as he was quarantined. "I can't leave here at all!" he cried. "Oh, how sad to be stuck in a corner with no friends around"

Pawn, Rook's best friend, decided to organize some fellows to cheer him up. "But how will I get down there?" she wondered. "Perhaps I should go to Bishop for advice". She used a trick of shifting each boat upwards in turn.

"Hallo, Bishop!" Pawn said. "I'm trying to get down to Rook, could you help me?"
"Why certainly, young padawan!" said the kindly Bishop. "In fact, I'll go with you on my boat to Knight. He always knows how to get around Rook's place". They boarded Bishop's boat together and sailed off to the edge of the world.

They saw Knight dozing with a book. "Knight! Knight! Knight!" Bishop yelled to get his attention. "We need to get to Rook! He's having a bad day".
Knight jerked awake. "I have a good boat for getting there but... well... this doesn't make sense right now, but the boat you're on, the 06 - it has to move to the left another spot before you get down here". Bishop and Pawn, sure that Knight had a plan in mind, complied. Bishop went to 03 and moved it left, and then Pawn moved 06 and joined Bishop.

"But how do we get to Knight?" wondered Bishop. "Pawn, do you know?". Pawn did know - just adapt her trick to get to Bishop, from the start, to accommodate having two on the same boat.

Knight's boat, like all the others, could only fit 2 at once. "Bishop, ride with me up; I'll get off at the dock to make room".

"Okay, Pawn, move your boat RIGHT! NOW!" yelled Knight. Pawn quickly did so.
"But now the boat can't go down to pick me up!" Pawn complained.
"Oh, no, that doesn't matter" said Knight. "You're going to go UP to the the boat. And Bishop, you're going to have to get off to the left and open up a dock for Pawn".

"What was that all about?" asked Pawn as she and Bishop walked over to Knight.
"Well, you know how it's VERY BAD to have boats by themselves, right? The next steps remove linkages to the outside world. The boat 65 provides a linkage point."

"Okay, everyone move right one spot. Then Pawn, you come down on my boat here". Knight blathered on. "If you don't move right now, then later when the boats in my row have to go right 2 spaces they'll fall off the edge of the world".

Knight got off at the dock. "Pawn, now go pick up Bishop. Then come back; we need one of us on each of the boat in this row".
"I don't have a clue what this is supposed to do" confided Pawn in Bishop. "I mean, why all the shifting? Why one on each boat? I guess he'll explain soon enough."

"Time for the main event!" Knight was quite excited. "If we all move our boats right twice - first Bishop, then Pawn, then me - we'll open up a pathway down to Rook!".

"Rook, we're coming!" They rushed so that, in a line, all were connected to Rook's front yard. He came out and was quite happy to see them all.

Please, edit any typos if you see them. Also I probably miscounted the # of moves at some point, but I've been setting up the pictures for over an hour and am too lazy to check.


2

Wrap-up: The Making Of Mirror Donimoes

This is not a solution to the puzzle, but provides notes from its poser. This type of answer has been approved by the community.

Caution: This post may contain spoilers.


Inspiration

I was one of the many people blown away by boboquack's Magic Maze Puzzle, and I'm always looking for puzzle ideas to add to my Donimoes collection, so I tried to come up with a simplified version of his puzzle that could be played with dominoes and pawns. I thought it might be more approachable, because it didn't require the solver to print out and assemble the pieces. See the evolution section below for all the ideas that didn't work before I got to this one, but I always kept the core idea of four pawns walking around on top of the dominoes, along with the goal of forming them into one connected group. What changed were the restrictions on movement.

Creative steps

One challenge with this puzzle was adding diagrams that showed where the pawns were on top of the dominoes. These diagrams highlighted what I think is a big weakness of this puzzle: the pawns hide the domino numbers underneath them.

I experimented with a few ideas, but I ended up drawing a mini version of the pips inside the pawn's circle, like this:

Example diagram

I'm still annoyed that the domino movement arrow sometimes interferes with a pawn label, but it's not a huge problem.

When I work on these diagrams, I use the live turtle graphics feature of my Live Coding in Python tool, and I find that really helpful for designing graphics with Python code. It makes my Python code as responsive as a drawing program like InkScape would be.

Logistical steps

As with most of my domino puzzles, I designed the rules, and then I wrote a program to solve a problem given the starting layout. Then I used evolutionary search to randomly shuffle the dominoes and find the most interesting layouts.

Because this puzzle uses pawns and has more flexible moves than most of my other puzzles, I noticed two things:

  1. The larger layouts had too many moves for my program to solve. It would just run out of memory.
  2. The moves were clear enough that I could actually design layouts by hand.

As a result, I just designed all the largest layouts by hand, and wrote a separate program to check the solutions instead of solving them automatically. I was surprised when I found a problem that took almost 400 moves to solve. I included it as the final problem in the Donimoes collection, and I hope it's not too frustrating to solve. As I said, I think the moves are clear enough that you can see the long-term strategy, and it just takes a lot of moves to get there.

Resources

I already had most of the code for modeling domino layouts, evolutionary search, and drawing the diagrams from previous domino puzzles, but I had to add features for moving pawns around on top of the dominoes. When searching for solutions, I switched from Dijkstra's algorithm to A* search.

Evolution

I started out very close to the inspiration of boboquack's Magic Maze puzzle, with its cycle of move types. I called it Ladder Donimoes, and the pawns had to move onto a 1, then a 2, then a 3, and so on. I wrote up the software, and generated some puzzles, but the moves were just too hard to see. Also, if you made the wrong move, it was hard to back out. I prefer to design puzzles with reversible moves, so you can safely explore them. Ladder Donimoes felt close, but not fun yet. Before I abandoned it, though, I added the rules for moving a domino only when it has a pawn on it. That brought domino movement into play, but restricted it enough to keep it interesting. It also made it feel like one pawn is helping another out of a tight spot.

After Ladder Donimoes, I tried to come up with a reversible set of movement rules. Partner Donimoes used the number at the other end of the domino as a pawn's "partner", and the pawn could move to another domino only if it kept the same partner. I chose the number at the other end of the domino, so the pawn wouldn't hide anything important underneath itself. However, that meant that it was hard to see where the possible moves were. You could see where each pawn could move right now, but looking ahead to future moves was really hard. Again, it felt close, but it wasn't fun.

Finally, I came up with the idea of just matching the number the pawn was standing on. That was much easier to see, even though you had to lift the pawn to see what number was under it.