Consider the following light switching game. We begin with an n by n grid of square buttons, numbered 1–n2, initially dark, as shown below (left) for n = 4. Pressing any button will cause that button to light up, along with its immediate neighbours above, below, and to its left and right in the grid. For example, the result of pressing button 11 is depicted below (middle). Subsequent button presses will continue to light up nearby buttons, or switch them back off if they are already alight. For example, the result of pressing button 15 (after button 11) is shown below (right). Note that because buttons 15 and 11 were both alight, they became dark again. Note also that the grid does not ‘wrap around’: button 15 has no effect on button 3. The aim of the puzzle, given a particular light configuration, is to find a sequence of button-presses that will produce this configuration.
Your task is to write a Haskell program capable of solving this puzzle. Given a grid size n and a light configuration as input, your program must output a sequence of buttons which, when pressed in order, will produce the desired configuration. The answer to this challenge must be submitted through Grok, in the form of a function lights of type Int -> [Int] -> [Int] The first input parameter provides the dimensionality of the puzzle grid, n, and will always be a positive integer. The second input parameter represents the buttons to be switched on in the desired configuration (any buttons not listed are to be switched off). The return value should be a list representing the sequence of buttons to press in your solution to the puzzle, or, in case the configuration is impossible to achieve, the return value should be an empty list. For example, the input/output pair below corresponds to a 4 by 4 puzzle in which the desired configuration is the one above (right), and to one possible solution to this puzzle:
> lights 4 [7, 10, 12, 14, 16]
[11, 15]
Hint 1: Our suggested approach is for you to model the puzzle as a propositional satisfiability problem. In this way, the task becomes a simple translation from a puzzle description to a propositional formula, and you can use tools like those you have constructed in assessed worksheets 1 and 2 to solve the formula itself (we provide similar tools on Grok). The code required for this approach is minor compared to the code required to implement a puzzle-specific search algorithm.
Hint 2: There are many ways to approach this modelling task. To get you started on the right track, consider the following questions (assume n = 4): (1) What light configuration results from the sequence [15, 11]? How does this compare to the above example? (2) What light configuration results from the sequence [6, 1, 6]? How about [6, 1, 6, 6]? Is it ever useful to press a button more than once? (3) Could you determine the final state of a single button by looking at a long sequence of button presses, without simulating the whole sequence?