# Algorithms – Encoding the reachability in a diagram with walls as a SAT problem

Suppose we have a diagram that represents a grid of cells. We get a cell to start with, and a cell that's the target. There are cells that we can not enter and are called walls. Finally, we can only go to neighboring cells (diagonal movements are not allowed).

My question is how to code this problem in CNF to be solved by a SAT solver?

For example, let the chart represent the following 2 x 3 grid:

``````0 1 0
0 0 0
``````

Where 0-cells are cells in which we are or to which we move are 1-cell walls. Suppose we start with (0, 0) and want to switch to (0, 2). Then there is a way.

On the contrary, consider another 2 x 3 grid with the same starting and ending positions:

``````0 1 0
0 1 0
``````

Then this diagram has no path from start to finish.

Of course, we can do BFS in the graph, and if there is a path, we can code it as a trivially satisfying CNF, or if it does not exist, we can code it as a trivially unsatisfactory CNF. For example, $$A$$, or, $$A land neg A$$, The purpose of my exercise, however, is to code the path existence in CNF.

This is indeed part of my homework. I'm stuck for a while now. Some help to this problem would be very grateful.

Posted on Categories Articles