ArticlesIn my last article on the Circuit Game, I wrote:
In theory, there could exist a puzzle that this engine couldn’t solve, because it would see two possible ambiguous solutions (one false solution containing a cycle, and one without). In practice, I haven’t seen one. It remains an open challenge to come up with such a puzzle.
Then Jonathon posted an argument saying it didn’t exist.
Then I pointed out an error in his assumptions, and asked for time to come up with a counter-example, which I provide here.
Then while I was producing it, Jonathon posted his own counter-example in ASCII, which I am ignoring because I had already done the work to render in in PNG, dammit!
So here is an example of an ambiguous puzzle:
It was only solved by hand-manipulating the data. My engine couldn’t solve it. It only got this far:
The grey squares indicate partially solved. B = Bulb and T = Tee shape. The number (and the shade of grey) indicate how many options are left.
The solution that it was confused by was this one.
Again, it took hand-manipulating of the data to get it to find this “solution”. Note this solution is disjoint, and contains a cycle, neither of which the engine I wrote is qualified to detect.
Comment by Jonathon Duerig on September 17, 2008
There is an interesting aspect to the fact that your program didn’t find the tree solution. When I was manually solving the puzzles after your original post, I automatically made the assumption that terminals couldn’t connect to each other. I had assumed that this kind of reasoning was part of your system.
I think that the way you are doing things captures most of the little rules I was using. Can you think of any other purely local rules that you may have used during manual solutions that your automated solution does not capture?
-D
Comment by Julian on September 18, 2008
I expected the “power rules” (which I didn’t implement) to protect against disjoint solutions. Terminals (i.e. bulbs) not connecting to each other is a very specific case of such a rule. A terminal shouldn’t connect to a line that connects to a terminal, either (unless that is the entire circuit.)
I certainly had little rules that I followed that weren’t implemented directly, but were captured by the more general rule that was implemented. (e.g. Three bulbs in a row against the edge means the middle bulb points away from the edge. A line near an edge must run parallel to the edge.)
I focussed on edge pieces at the beginning as having the most promise. The automated solution doesn’t attempt to do this, but instead focuses on the squares whose neighbours have recently “learnt” something.
Apart from that, I am not aware of any such rules. (Compare that to Slitherlinks where I didn’t implement several of the “advanced techniques” that I used in manual solutions.)