CODEWITHSUNDEEP
logicsolversatsatisfiabilitycnf
johanDa9u
johanDa9u

Reputation: 63

Sat solver for Lights Out game

I have a school project where I have to find solutions of the game "Lights Out" ( https://en.wikipedia.org/wiki/Lights_Out_(game) ) with a SAT Solver but I am having troubles trying to set a conjuctive normal form of the game.

The game consists of a 5 by 5 grid of lights. Pressing any of the lights will toggle it and the four adjacent lights. The goal of the puzzle is to switch all the lights off.

How I tried until now:

For a 3x3 grid (to begin with), I set 9 terms (for each button) thus:

C11 : the button at the position 1,1 is lighten up C12 : the button at the position 1,2 is lighten up C13 : the button at the position 1,3 is lighten up. [...]

Since the button at 1,1 lights off the button at the position 1,2 and 2,1

I did C11 => C12 and C21 the button at 1,2 lights off the button at the position 1,1 and 1,3 and 2,2 I did C12 => C11 and C13 and C22

and continued for the other:

C13 => C12 and C23
C21 => C11 and C22 and C31
C22 => C12 and C21 and C23 and C32
C23 => C13 and C22 and C33
C31 => C21 and C32
C32 => C31 and C33 and C22
C33 => C23 and C32

then I just converted these to CNF to get the clauses I need for the sat solver, but it seems that what I did was wrong..

can Anyone help me to write this game into CNF form ?

Thank you very much !

Here is the game if you need to understand it better:

https://www.geogebra.org/m/JexnDJpt#material/KArehWn8

Upvotes: 0

Views: 702

Answers (2)

Marco
Marco

Reputation: 336

A way to solve the problem is to encode the sequence of actions needed to reach your goal.

One way of doing this is to consider that it takes K moves to solve the puzzle. You will then encode for each step the select cell, and the impact on the related cells, and ask the solver for a model such that the K-th configuration has all lights off.

This technique is called bounded model checking, and you should find several explanations on how to convert to sat.

Upvotes: 1

Tim
Tim

Reputation: 1098

The wikipedia article you posted cites something that looks like a pretty good solution: Marlow Anderson, Todd Feil (1998). "Turning Lights Out with Linear Algebra" (PDF). Mathematics Magazine. 71 (4): 300–303. You will need to understand the math in the paper and how to encode Z_2 operations into CNF. (IMO less implementation effort than BMC.) Best of luck on the assignment!

Upvotes: 2

Related Questions