[SOLVED] algorithm game Haskell Consider the following light switching game. We begin with an n by n grid of square buttons, numbered 1n2, 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 o 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 eect on button 3. The aim of the puzzle, given a particular light conguration, is to nd a sequence of button-presses that will produce this conguration.

Consider the following light switching game. We begin with an n by n grid of square buttons, numbered 1n2, 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 o 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 eect on button 3. The aim of the puzzle, given a particular light conguration, is to nd a sequence of button-presses that will produce this conguration.

Your task is to write a Haskell program capable of solving this puzzle. Given a grid size n and a light conguration as input, your program must output a sequence of buttons which, when pressed in order, will produce the desired conguration. The answer to this challenge must be submitted through Grok, in the form of a function lights of type Int -> [Int] -> [Int] The rst 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 conguration (any buttons not listed are to be switched o). The return value should be a list representing the sequence of buttons to press in your solution to the puzzle, or, in case the conguration 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 conguration 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 satisability 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-specic 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 conguration results from the sequence [15, 11]? How does this compare to the above example? (2) What light conguration 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 nal state of a single button by looking at a long sequence of button presses, without simulating the whole sequence?