line puzzles.

[IIAOPSW]

morning everyone.

You all seem like clever, young, competent and sexy professionals that solve puzzles the way I eat breakfast (yes literally)!

So on that note, I present to you this series of progressively more difficult logic puzzles that I shoved together.

http://www.kongregate.com/games/IIAOPSW/lines

Remember, there is no* shame in failure.



*I lie sometimes.

[mfb]

Even my computer can solve it!
I didn't compare programming time to solving times, running time versus (human) solving time would be unfair .

Nice puzzle idea.

Edit: I did not search for the shortest possible solution, is there a "short" one for 17?
Edit2: There is really short one for 19.
Press here to celebrate!

[skeptical scientist]

Edit: I did not search for the shortest possible solution, is there a "short" one for 17?

What's "short"? I have a 7-move solution I found by hand.

[mfb]

Spoiler:

I think it had 8 or 9, I can check that later.
All other puzzles have shorter solutions, usually ~3-5 steps.

[IIAOPSW]

all of them can be solved in a number of moves <= the number of buttons.

this is an artifact of the level generator.

the fact that some of you are programming solvers means we now have computers solving problems made by other computers. you know what this means?


Computers have reached full employment!!!

[mfb]

all of them can be solved in a number of moves <= the number of buttons.

That leads me to a question I found while testing the solver: What is the maximal number of required moved for n lines and m allowed operations? If the puzzle is solvable, it is smaller than 2^n and (at least for n>m) larger than m. I think that it is smaller than 2^m, but I cannot prove it.

[mike-l]

It's less than or equal to mn. I will show that any move X is not needed more than m times.

Note that any combination of moves is still in the form of a move. We'll replace any sequence of non-X moves with a single move (which may or may not be an original move)

Suppose we have a sequence S = T1 X T2 X ... X T(m+2) involving m+1 iterations of the move X. For each line p, let i_p be the greatest i such that Ti has a fixed output for line p (ie it makes it vertical or horizontal, as opposed to doing nothing or swapping it). By the pigeonhole principle, there is some k < m+2 which is not i_p for any p. I claim then that S' = T1 X T2 X ... T(k-1) Tk T(k+1) X ... X T(m+2) has the same result as S. For any p that has i_p > k, the results is clear since the position of p is set after the modification. Similarly for any p which is set by X. For p that has i_p < k, every transformation after i_p either does nothing or flips it, so they commute. There are the same Ts after, and the number of Xs is equal to the number of Xs - 2, and since X doesn't set it, any even number of Xs has no effect.

Thus any sequence of m+1 Xs can be rewritten as a sequence with fewer Xs. Since X is arbitrary, the longest possible sequence is at most mn. (By the pigeonhole principle)

Edit: A bit of case analysis gets this down to mn-n pretty easily, I only had to use mn because the general case didn't allow the excluded k to be the final one, but this is only an issue if X and T(m+2) don't set any positions, in which case they commute and the last 2 Xs aren't needed either.

Edit 2:
Ok, I can do much better, 2n.

Suppose T1 T2 -- Tk is a minimal solve. Reorder the lines so that the final transformation that 'sets' that line does not occur later than the final operation that sets the line to its right. Ie if o means swap, x means nothing, | means make verticle and - means make horizontal, then we would reorder the lines if the minimal solve was (- |) (o -) (o -), since the fist line is fixed only in the first move and the second line is fixed in every move.

We thus have two (possibly empty) groups of lines, the first of which are at some point 'set' during the solve and the second of which are only ever 'swapped'. Note that the states and moves of the second group correspond to a vector space over F_2 so any attainable orientation can be obtained at one move per line.

We will solve the first group at at most 2 moves per line. Starting from the left, solve the line. Use the last move that set this line to set it, and if a rotation is required, select one of the subsequent moves from the final solve. Repeat this for each line going left to right, always using the final 'setting' move from the original solve, and a subsequent rotation if necessary. This guarantees that one will always exist.

After doing this, the position of the second group is again attainable because we used moves from the original solve, and so can be obtained with 1 move per line. Thus we have a solve with at most 2 moves per line =2n.