Setup
In the game of Lights Out, a 5x5 board of lights is given with some lights on and some lights off. The goal of someone playing this game is to turn all the lights out.
Each light is also a button. When a button is pressed, it toggles the on/off state of that button and the (2, 3 or 4) buttons immediately adjacent to it. For example, the three boards below show what happens when the button with the bold border is pressed.
Given a board, your job is to find a sequence of button presses which will make the lights go out.
Notes:
If you make up your own boards and try to solve them, be aware that only one in four light arrangements are solvable. So the best way to generate solvable patterns is to start with a blank board and make a hundred or so.legal moves.
Also, it is never necessary to press a button more than once during a solution, though you are certainly allowed to do so in your solutions.
Your solution, however, should use no more than 200 button presses.
Challenge
The first line of input will be the number of boards. Each board will be given on five lines of five characters each. “X” will stand for a light which is on, and a hyphen will stand for a light which is off. The boards will be separated by a blank line.
For each board, you should return an integer saying how many moves your solution takes, followed by the sequence of moves, separated by spaces, which will make all the lights go off. Each solution should be on a new line. Your sequence should be of numbers from 1 to 25, where the buttons are numbered row-by-row, left-to-right, from the top down.
Sample Input
2
XX---
X----
-----
----X
---XX
-XXX-
X-X-X
-XXX-
-----
-----
Sample Output
2 1 25
3 7 8 9
Deadline
The deadline for submission is Monday, November 7, 2005
Many contests and challenges offer cash awards to the winners, leaving them feeling cheap, as if their talent was available to anyone at any time
for a price! This challenges offers you points! Each team or individual submitting a program is eligible for points. See rules for details.
Submission
Email code to:
challenge@cs.ecu.edu
Please see the rules page for more information.