Editing 2-satisfiability (section)

===Discrete tomography===
[[File:Nonogram_wiki.svg|thumb|Example of a nonogram puzzle.]]
[[Tomography]] is the process of recovering shapes from their cross-sections. In [[discrete tomography]], a simplified version of the problem that has been frequently studied, the shape to be recovered is a [[polyomino]] (a subset of the squares in the two-dimensional [[square lattice]]), and the cross-sections provide aggregate information about the sets of squares in individual rows and columns of the lattice. For instance, in the popular [[nonogram]] puzzles, also known as paint by numbers or griddlers, the set of squares to be determined represents the dark [[pixel]]s in a [[binary image]], and the input given to the puzzle solver tells him or her how many consecutive blocks of dark pixels to include in each row or column of the image, and how long each of those blocks should be. In other forms of digital tomography, even less information about each row or column is given: only the total number of squares, rather than the number and length of the blocks of squares. An equivalent version of the problem is that we must recover a given [[0-1 matrix]] given only the sums of the values in each row and in each column of the matrix.

Although there exist polynomial time algorithms to find a matrix having given row and column sums,<ref>{{citation|first=R. A.|last=Brualdi|author-link=Richard A. Brualdi|title=Matrices of zeros and ones with fixed row and column sum vectors|journal=Linear Algebra Appl.|volume=33|year=1980|pages=159–231|doi=10.1016/0024-3795(80)90105-6|doi-access=free}}.</ref> the solution may be far from unique: any submatrix in the form of a 2&nbsp;×&nbsp;2 [[identity matrix]] can be complemented without affecting the correctness of the solution. Therefore, researchers have searched for constraints on the shape to be reconstructed that can be used to restrict the space of solutions. For instance, one might assume that the shape is connected; however, testing whether there exists a connected solution is NP-complete.<ref>{{citation|first=G. J.|last=Woeginger|author-link= Gerhard J. Woeginger |title=The reconstruction of polyominoes from their orthogonal projections|series=Technical Report SFB-65|publisher=TU Graz|location=Graz, Austria|year=1996}}.</ref> An even more constrained version that is easier to solve is that the shape is [[orthogonal convexity|orthogonally convex]]: having a single contiguous block of squares in each row and column.
Improving several previous solutions, {{harvtxt|Chrobak|Dürr|1999}} showed how to reconstruct connected orthogonally convex shapes efficiently, using 2-SAT.<ref>{{citation|first1=Marek|last1=Chrobak|first2=Christoph|last2=Dürr|title=Reconstructing hv-convex polyominoes from orthogonal projections|journal=[[Information Processing Letters]]|volume=69|issue=6|year=1999|pages=283–289|doi=10.1016/S0020-0190(99)00025-3|arxiv=cs/9906021|bibcode=1999cs........6021D|s2cid=6799509}}.</ref> The idea of their solution is to guess the indexes of rows containing the leftmost and rightmost cells of the shape to be reconstructed, and then to set up a 2-satisfiability problem that tests whether there exists a shape consistent with these guesses and with the given row and column sums. They use four 2-satisfiability variables for each square that might be part of the given shape, one to indicate whether it belongs to each of four possible "corner regions" of the shape, and they use constraints that force these regions to be disjoint, to have the desired shapes, to form an overall shape with contiguous rows and columns, and to have the desired row and column sums. Their algorithm takes time {{math|O(''m''<sup>3</sup>''n'')}} where {{math|''m''}} is the smaller of the two dimensions of the input shape and {{math|''n''}} is the larger of the two dimensions.  The same method was later extended to orthogonally convex shapes that might be connected only diagonally instead of requiring orthogonal connectivity.<ref>{{citation|first1=Attila|last1=Kuba|first2=Emese|last2=Balogh|title=Reconstruction of convex 2D discrete sets in polynomial time|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=283|issue=1|year=2002|pages=223–242|doi=10.1016/S0304-3975(01)00080-9|doi-access=free}}; {{citation|first1=Sara|last1=Brunetti|first2=Alain|last2=Daurat|title=An algorithm reconstructing convex lattice sets|journal=[[Theoretical Computer Science (journal)|Theoretical Computer Science]]|volume=304|issue=1–3|pages=35–57|year=2003|doi=10.1016/S0304-3975(03)00050-1|s2cid=2803842 |url=http://hal.archives-ouvertes.fr/docs/00/06/61/77/PDF/tomoqconv_els.pdf}}.</ref>

A part of a solver for full nonogram puzzles, {{harvs|last1=Batenburg|last2=Kosters|year=2008|year2=2009|txt}} used 2-satisfiability to combine information obtained from several other [[heuristic]]s. Given a partial solution to the puzzle, they use [[dynamic programming]] within each row or column to determine whether the constraints of that row or column force any of its squares to be white or black, and whether any two squares in the same row or column can be connected by an implication relation. They also transform the nonogram into a digital tomography problem by replacing the sequence of block lengths in each row and column by its sum, and use a [[maximum flow]] formulation to determine whether this digital tomography problem combining all of the rows and columns has any squares whose state can be determined or pairs of squares that can be connected by an implication relation. If either of these two heuristics determines the value of one of the squares, it is included in the partial solution and the same calculations are repeated. However, if both heuristics fail to set any squares, the implications found by both of them are combined into a 2-satisfiability problem and a 2-satisfiability solver is used to find squares whose value is fixed by the problem, after which the procedure is again repeated. This procedure may or may not succeed in finding a solution, but it is guaranteed to run in polynomial time. Batenburg and Kosters report that, although most newspaper puzzles do not need its full power, both this procedure and a more powerful but slower procedure which combines this 2-satisfiability approach with the limited backtracking of {{harvtxt|Even|Itai|Shamir|1976}}<ref name="EIS76"/> are significantly more effective than the dynamic programming and flow heuristics without 2-satisfiability when applied to more difficult randomly generated nonograms.<ref>{{citation|first1=K. Joost|last1=Batenburg|first2=Walter A.|last2=Kosters|contribution=A reasoning framework for solving Nonograms|title=Combinatorial Image Analysis, 12th International Workshop, IWCIA 2008, Buffalo, NY, USA, April 7–9, 2008, Proceedings|series=Lecture Notes in Computer Science|volume=4958|year=2008|publisher=Springer-Verlag|pages=372–383|doi=10.1007/978-3-540-78275-9_33|isbn=978-3-540-78274-2|doi-access=free}}; {{citation|first1=K. Joost|last1=Batenburg|first2=Walter A.|last2=Kosters|title=Solving Nonograms by combining relaxations|journal=Pattern Recognition|volume=42|issue=8|year=2009|pages=1672–1683|doi=10.1016/j.patcog.2008.12.003|bibcode=2009PatRe..42.1672B |citeseerx=10.1.1.177.76}}.</ref>