<tex> 0 \le y_{i} \le 1 </tex>
<tex> -b[i][j] \le (-1)^i x_{j} + (-1)^j y_{i} \le 1 - b[i][j] </tex>

Este uşor acum să transformăm acest sistem într-o formulă booleană în {'formă normal conjunctivă':2-sat#forme-normale} în care fiecare expresie are cel mult $2$ literali. Fiecare relaţie o putem înmulţi sau nu cu $-1$ astfel ca părţile constante ale relaţiei să fie pozitive. Observăm că <tex> | b[i][j] | \le 2 </tex>, altfel nu avem soluţie. Dacă <tex> | b[i][j] | = 2 </tex> atunci ambele variabile au valori fixe, iar dacă <tex> | b[i][j] | = 1 </tex> sau <tex> | b[i][j] | = 0 </tex> atunci relaţia o putem scrie ca o disjuncţie logică cu doi literali.

Este uşor acum să transformăm acest sistem într-o formulă booleană în {'formă normal conjunctivă':2-sat#forme-normale} în care fiecare expresie are cel mult $2$ literali. Fiecare relaţie o putem înmulţi sau nu cu $-1$ astfel ca părţile constante ale relaţiei să fie pozitive. Observăm că <tex> -2 \le b[i][j] \le 3 </tex>, altfel nu avem soluţie. Dacă partea constantă minimă din relaţii este $2$ atunci ambele variabile au valori fixe, iar dacă este $1$ sau $0$ atunci relaţia o putem scrie ca o disjuncţie logică cu doi literali.

O relaţie precum <tex> 0 \le x + y \le 1 </tex> poate fi tansformată logic în <tex> \sim x \vee \sim y </tex>, astfel <tex> x </tex> şi <tex> y </tex> nu vor fi în acelaşi timp <tex> 1 </tex>, una de genul <tex> 1 \le x + y \le 2 </tex> va fi transformată în <tex> (x \vee y) </tex>, astfel cel puţin <tex> x </tex> sau <tex> y </tex> va fi egal cu <tex> 1 </tex>, alta de tipul <tex> 0 \le x - y \le 1 </tex> poate fi scrisă ca <tex> x \vee \sim y </tex>, una de tipul <tex> 2 \le x + y \le 3 </tex> în <tex> x \wedge y </tex>, iar una de tipul <tex> 0 \le -x -y \le 1 </tex> în <tex> \sim x \wedge \sim y </tex>, una de tipul <tex> 1 \le x - y  \le 2 </tex> în <tex> x \wedge \sim y </tex>.

Astfel am redus problema la rezolvarea unei instanţe de $2-SAT$. Avem $N+M-1$ necunoscute şi {$(N-1)$}{$(M-1)$} propoziţii. Folosind a treia metodă de rezolvare vom obţine un algoritm de complexitate $O(N * M)$ care soluţionează problema noastră.

Astfel am redus problema la rezolvarea unei instanţe de $2-SAT$. Avem $N+M-1$ necunoscute şi {$(N-1)*(M-1)$} propoziţii. Folosind a treia metodă de rezolvare vom obţine un algoritm de complexitate $O(N * M)$ care soluţionează problema noastră.

Să vedem cum merge acestă rezolvare pe exemplul din problemă: