Several weeks ago, I started to doodle on the newspaper (The Times of India) whenever I saw the “Loop The Loop” puzzle. I liked it enough to research it a bit more.It is really a logic puzzle, and can vary in difficulty from very easy to very difficult. The rules are simple: You are given a grid of squares, with several cells having a number in them. You have to draw lines such that they form one loop. The number in each cell indicates the number of edges that the loop touches in that cell. There should only be one overall loop.
I found an online version here in http://www.puzzle-loop.com/. (You can choose the degree of difficulty from the left panel). Try it out.
For those of you who want the game to your PC (to play even when you are not connected to the Web) you can download) Loopy.
If you have tried it a few times, like the puzzles and are mathematically or logically inclined, then read on.
Preprocessing: Also, there is lots of preprocessing that is possible. It is pure pattern recognition. Two 3’s together mean something. A 0 next to a 3 is a fairly big hint. Also, by dividing the squares into corner squares, edge squares and interior squares, you can gain some additional insights to help you solve the problem.
Integer Program: This whole problem lends itself very nicely to be modeled as an integer program, with each edge being a 0/1 binary variable. It is a very good IP modeling exercise in itself. Since multiple loops are not allowed, the sub-tour elimination constraints make the model a little unwieldy.)
Composing: To compose one of these problems can be a fun challenge. (Think of it as the dual to solving the puzzle.) The fact that there is only one solution makes it a very challenging puzzle to compose: For a given loop, how to go about revealing only the least number of numbers in cells?
Related Post:
Flood-It
Ram
Posts
3 comments:
Machaan RamP, nice puzzle, and good to see the combinatorial optimization streak resurface in you!
-- Guess who?
@Poly,
Yes a good puzzle, and I think it really resonates with those who have an interest in optimization problems.
Not to hazard a guess in public, but there is only one guy who 1. invariable addresses me as "Machaan RamP," 2. Prefers fixed income to volatile equities and 3. is geeky enough to choose the handle Polyhedron.
Ram, Srini,
Wake up. Your aesthetic senses are dropping rather alarmingly you need an intervention of some form.
Math without beauty leads to more hummers and suv's. (Not to mention exotic derivatives)
Most IP's are just that - tweaking of endless nuts and bolts until a clunky cpu guzzler emerges. And more often than not the IP is forcibly stopped when there is no more gas and not because youve reached your destination.
Its not too late for you both to regain some of the good taste of your former selves. For an hour well spent look up any of Gilbert Strangs videos at MIT.
Arvind
Post a Comment