Polynomial algorithm for finding CNF assignment

Question

I'm trying to solve the following task

Let $C(\phi)$ be a polynomial-time algorithm that, given a 3-CNF $\phi$, decides whether $\phi$ has an assignment that makes true exactly one literal in each clause. Show that, in this case, there is a polynomial-time algorithm $D(\phi)$ that finds such an assignment if it exists and reports that it does not exist otherwise

I thought of some recurrent algorithm that takes only first $i$ clauses and tries to find such assignment iteratively, but i am stuck on how to unite outputs for $i$ and $i+1$ clause (or may be i am completely wrong). Can you help me please?

Answer 1

To be clear, $C(\phi)$ decides whether such an assignment exists and we need to construct $D(\phi)$ that yields the actual assignment.

You are correct in the use of an iterative approach, but you are incorrect that it'll be over the set of clauses. It will be over the set of variables.

Define $D(\phi)$ like this, assuming that $v_i \in V$ is an enumeration of the variables and $a_i \in \{T, F\}$ be their assignments.

1. If $C(\phi)$ is unsatisfiable, the assignment is unsatisfiable.
2. If $C(\phi \land v_0)$ is satisfiable, then $a_0 = T$ else $a_0 = F$.
3. If $C(\phi \land (v_0 \leftrightarrow a_0) \land v_1)$ is satisfiable, then $a_1 = T$ else $a_1 = F$.
4. If $C(\phi \land (v_0 \leftrightarrow a_0) \land (v_1 \leftrightarrow a_1) \land v_2)$ is satisfiable, then $a_2 = T$ else $a_2 = F$.
5. ...

In the case that both $\displaystyle C(\phi \land \big[\bigwedge_{i \lt n}(v_i \leftrightarrow a_i)\big] \land v_n)$ and $\displaystyle C(\phi \land \big[\bigwedge_{i \lt n}(v_i \leftrightarrow a_i)\big] \land !v_n)$ are satisfiable, you can make an arbitrary choice for $a_n$.