这是一份Swansea大学的硕士论文代写成功案例。
学生的论文项目方向是关于通过SAT-3寻找数独问题和图论染色问题之间的关系。如果在理科的论文dissertation代写上需要帮助。欢迎随时联系我们，我们为您提供优质的论文辅导代写服务！
我们这次的客户在研究的过程中需要通过SAT-3布尔形式表达式寻找数独问题和图论染色问题之间的关系，实际上我们有
数独谜题$(n \times n)$的图k-着色问题的3-SAT布尔表达式化
图k-着色问题有两个局限性：
- 每个顶点必须至少被赋予一种颜色。
- 相邻顶点不能有相同的颜色。
为了在 3-SAT 中表示这些限制，我们可以使用布尔变量 $V_{i j}$，其中 $1 \leq i \leq|V|$ 和 $1 \leq j \leq k$。如果颜色 $\mathrm{j}$ 分配给顶点 $V_i$ ，变量 $V_{i j}$ 为真。要为这两个限制生成条款，我们可以按照以下步骤进行。 - 每个顶点必须至少分配一种颜色。
第一个限制规定，每个顶点必须至少有一种颜色。这可以用 SAT 表达如下：
$$
\Lambda_{i=1}^{|V|} V_{j=1}^{k=V_{i j}}
$$
这样就为图中的所有顶点生成了 SAT 条款。在此表示法中，生成的条款总数等于相应图中顶点的总数 $(|\mathrm{V}|)$，所有条款的长度为 $\mathrm{n}$。数独谜题$(\mathrm{n} \times \mathrm{n})$对应的图有$n^2$个顶点，因此可以计算出该限制条件下产生的条款总数$left(C_{text {limitation } 1}\right)$ ：
$$
C_{\text {limitation } 1}=n^2
$$
接下来，我们使用一种定义明确的非递归方法（类似于第 3 节中描述的方法），将生成的 SAT 子句转换为 3-SAT 子句。显然，每个包含 $n$ 字面量（其中 $n>3$ ）的 SAT 子句都可以转换成 $(n-2)$ 3-SAT 子句，每个子句的长度为 3，并且需要 $(\mathrm{n}-3)$ 额外的变量。我们可以得到以下结果：
限制 1 引起的 3-SAT 子句总数: $n^2(n-2)$
由限制
1 引起的所需新变量：n^2(n-3)$
2.相邻顶点的颜色不能相同。
第二个限制要求每一对相邻顶点的颜色都不同。
对于每一条边 $\left(V_i,V_j/right)$，如果 $V_i$ 被分配了颜色 X，那么颜色 $\mathrm{X}$ 就不能被分配给顶点 $V_j$。这种限制可以用 SAT 表示如下：
$$
\left(\neg V_{t, \text { color } x} \vee \neg V_{text {f,color } x}\right)
$$
从 SAT 表示中可以看出，该限制的所有子句长度都是 2。此外，在所有边 E 上的所有 n 种颜色都会生成条款。因此，该限制产生的条款数量为 ( $n|E|$ )。使用，为该限制生成的条款数量可表示为 $C_{\text {limitation2. }}$
$$
C_{\text {limitation } 2}=n \frac{n^2}{2}(3 n-2 \sqrt{n}-1)=\frac{n^3}{2}(3 n-2 \sqrt{n}-1)
$$
为这一限制生成的子句已经是 3-SAT 形式，这些子句不需要额外的变量。除了从这两个限制条件中得到的子句之外，数独谜题中还为静态数预设了一些额外的单元子句。如果$mathrm{m}$是静态数的个数，那么数独谜题$(n \times n)$的SAT子句($|T C|)$的总数可以通过还原成图形k-着色问题计算如下：
$$
\begin{aligned}
|T C|=C_{\text {limitation } 1}+C_{text {limitation2 }}+m （＋m
& |T C|=n^2+frac{n^2}{2}(3 n-2 \sqrt{n}-1)+m
\end{aligned}
$$
与数独谜题 $(\mathrm{n} \times\mathrm{n})$ 相对应的图形 k-Colouring 问题的 3-SAT 简化所需的 3-SAT 条款总数 (T3C) 和额外变量总数 $(|\mathrm{NV}|)$ 可以计算如下：
$$
\开始
|T 3 C|=n^2(n-2)+\frac{n^3}{2}(3 n-2 \sqrt{n}-1)+m （m
& |N V|=n^2(n-3)
\end{aligned}
$$
我们的表述清楚地表明，通过使用图形k-着色问题，我们实现了数独谜题$(\mathrm{n} \times \mathrm{n})$的多项式3-SAT缩减。此外，我们还观察到使用图形k-着色问题对数独谜题$(n \times n)$进行3-SAT还原所生成的子句数少于第3节中的方法所生成的子句数。生成的 3-SAT 子句通过 MiniSat 网络界面求解，该界面给出了子句的可满足值。可满足值表示为每个顶点分配的颜色。因此，具有相同颜色的顶点代表数独谜题中相应单元中填入的相同数字。这样，通过利用数独谜题中已有的固定数字，我们就可以完成所有剩余的单元格。
