如何在c++中使用约束满足实现密码算法

我将通过一个例子来解释什么是密码问题:

T W O
+ T W O
F O U R

我们必须为每个字母分配一个数字[0-9]，使没有两个字母共享相同的数字，并满足上述方程。

上述问题的一个解决方案是:

7 6 5   
+  7 6 5       
1 5 3 0

有两种方法来解决这个问题，一种是蛮力，这将工作，但它不是最优的方式。另一种方法是使用约束满足。

使用约束满足的解
我们知道R总是偶数因为它是2 * O
这将O的定义域缩小到{0,2,4,6,8}
我们还知道F只能是1，因为F不是两个字母的加法，它的值一定是由T + T = O
这也意味着T + T>
这告诉我们T>4{5,6,7,8,9}
当我们继续这样做时，我们不断缩小域，这有助于我们大大减少时间复杂度。

这个概念看起来很简单，但是我在c++中实现它时遇到了麻烦。特别是我们为每个变量生成约束/域的部分。请记住，这里也涉及进位。

编辑:我正在寻找一种方法来生成每个变量使用我所说的概念域。

这类问题是通用约束编程包(如Google的开源OR-Tools)的一个很好的应用。(参见https://developers.google.com/optimization和https://developers.google.com/optimization/cp/cryptarithmetic)。

这个包是用c++编写的，所以它应该是一个很好的匹配。

然后编程问题就像这样简单(对不起，因为我在c#中使用OR-Tools，这是c#代码，但c++代码看起来几乎相同)

public void initModel(CpModel model)
{
// Make variables
T = model.NewIntVar(0, 9, "T");
W = model.NewIntVar(0, 9, "W");
O = model.NewIntVar(0, 9, "O");
F = model.NewIntVar(0, 9, "F");
U = model.NewIntVar(0, 9, "U");
R = model.NewIntVar(0, 9, "R");
// Constrain the sum
model.Add((2 * (100 * T + 10 * W + O)) == (1000 * F + 100 * O + 10 * U + R));
// Make sure the variables are all different
model.AddAllDifferent(decisionVariables);
// The leading digit shouldn't be 0
model.Add(T != 0);
model.Add(F != 0);
}

，然后调用Solve方法。

在求和的约束中，操作符* +和==都在包中被覆盖，以创建可被模型用来强制约束的对象。

这是输出的开始，它列举了解决方案

Solution #0: time = 0,00 s;
T = 8
W = 6
O = 7
F = 1
U = 3
R = 4
Solution #1: time = 0,01 s;
T = 8
W = 4
O = 6
F = 1
U = 9
R = 2
Solution #2: time = 0,01 s;
T = 8
W = 3
O = 6
F = 1
U = 7
R = 2
Solution #3: time = 0,01 s;
T = 9
W = 3
O = 8
F = 1
U = 7
R = 6

下面是完整的代码，包括打印解决方案和执行的Main方法:

using Google.OrTools.Sat;
using System;
using System.IO;
namespace SO69626335_CryptarithmicPuzzle
{
class Program
{
static void Main(string[] args)
{
try
{
Google.OrTools.Sat.CpModel model = new CpModel();
ORModel myModel = new ORModel();
myModel.initModel(model);
IntVar[] decisionVariables = myModel.decisionVariables;
// Creates a solver and solves the model.
CpSolver solver = new CpSolver();
VarArraySolutionPrinter solutionPrinter = new VarArraySolutionPrinter(myModel.variablesToPrintOut);
solver.SearchAllSolutions(model, solutionPrinter);
Console.WriteLine(String.Format("Number of solutions found: {0}",
solutionPrinter.SolutionCount()));
}
catch (Exception e)
{
Console.WriteLine(e.Message);
Console.WriteLine(e.StackTrace);
throw;
}
Console.WriteLine("OK");
Console.ReadKey();
}
}
class ORModel
{
IntVar T;
IntVar W;
IntVar O;
IntVar F;
IntVar U;
IntVar R;
public void initModel(CpModel model)
{
// Make variables
T = model.NewIntVar(0, 9, "T");
W = model.NewIntVar(0, 9, "W");
O = model.NewIntVar(0, 9, "O");
F = model.NewIntVar(0, 9, "F");
U = model.NewIntVar(0, 9, "U");
R = model.NewIntVar(0, 9, "R");
// Constrain the sum
model.Add((2 * (100 * T + 10 * W + O)) == (1000 * F + 100 * O + 10 * U + R));
// Make sure the variables are all different
model.AddAllDifferent(decisionVariables);
// The leading digit shouldn't be 0
model.Add(T != 0);
model.Add(F != 0);
}
public IntVar[] decisionVariables
{
get
{
return new IntVar[] { T, W, O, F, U, R };
}
}
public IntVar[] variablesToPrintOut
{
get
{
return decisionVariables;
}
}
}
public class VarArraySolutionPrinter : CpSolverSolutionCallback
{
private int solution_count_;
private IntVar[] variables;
public VarArraySolutionPrinter(IntVar[] variables)
{
this.variables = variables;
}
public override void OnSolutionCallback()
{
// using (StreamWriter sw = new StreamWriter(@"C:tempGoogleSATSolverExperiments.txt", true, Encoding.UTF8))
using (TextWriter sw = Console.Out)
{
sw.WriteLine(String.Format("Solution #{0}: time = {1:F2} s;",
solution_count_, WallTime()));
foreach (IntVar v in variables)
{
sw.Write(
String.Format(" {0} = {1}rn", v.ShortString(), Value(v)));
}
solution_count_++;
sw.WriteLine();
}
if (solution_count_ >= 10)
{
StopSearch();
}
}
public int SolutionCount()
{
return solution_count_;
}
}
}

完整的解决方案方式超出了一个简单的SO问题的范围，但我可以概述您需要的内容。

首先，为进位生成新的字母:

0 T W O
0 T W O
+  Z Y X V
F O U R

然后您可以生成包含所有选项的std::map<char, std::set<int>>。字母的标准范围是{0..9}， V为{0}，Z为{1}，Y和X为{0..1}。

接下来，需要将添加的内容编码为一组子句。

enum class Op { Equal, SumMod10, SumDiv10, Even, Odd };
struct clause { Op op; std::vector<Var> children; };
std::vector<clause> clauses{
{Equal, { 'Z' , 'F'}},
{SumMod10, {'O', 'T', 'T', 'Y'}}, // O = (T+T+Y) mod 10
{SumMod10, {'U', 'W', 'W', 'X'}},
{SumMod10, {'R', 'O', 'O', 'V'}},
{SumDiv10, {'F', 'T', 'T', 'Y'}}, // F is the carry of T+T+Y
{SumDiv10, {'O', 'W', 'W', 'X'}},
{SumDiv10, {'U', 'O', 'O', 'V'}},
};

然后有趣的部分开始了:您需要创建一个计算，它将尝试使用它所拥有的知识来简化约束。如{SumMod10, {'U', 'O', 'O', 'V'}}由V=0可简化为{SumMod10, {'U', 'O', 'O', 0}}。有时子句可以缩小变量的范围，例如{Equal, {'Z', 'F'}}约束可以立即将F的范围缩小到{0,1}。

接下来，你需要教你的系统基本的代数等式，以便进一步简化，比如:{SumMod10, {A, 0, C}} === {SumMod10, {A, C, 0}} === {Equal, {A,C}}还有更抽象的东西，比如"如果A>= 5, B>= 5，那么A+B>= 10";或者"如果A是偶数，B是偶数，那么A + B也是偶数"。

最后，你的系统需要能够假设并反驳它们，或者证明一个假设无论如何都是正确的，就像你在你的帖子中所做的那样。例如，假设R是奇数就意味着O + O是奇数，这只有在O同时是奇数和偶数时才会发生。因此R一定是偶数

在一天结束的时候，你将不仅实现了一个正式的系统来描述和评估数字领域的布尔子句，你还将有一个目标驱动的解决方案引擎。如果这不仅仅是一个空闲的思考，我强烈建议采用SMT系统来为您解决这个问题，或者至少学习Prolog并在那里表达您的问题。

我是这样解决的

我的方法是巧妙地暴力破解它，我递归地为每个字母分配每个可能的值[0-9]，并检查是否有任何矛盾。

矛盾可以是下列之一:

两个或两个以上的字母最终具有相同的值。
字母总和与结果字母的值不匹配。
字母的总和已经分配给某个字母。

一旦出现矛盾，该特定组合的递归结束。

#include <bits/stdc++.h>
using namespace std;
vector<string> words, wordOg;
string result, resultOg;
bool solExists = false;
void reverse(string &str){
reverse(str.begin(), str.end());
}
void printProblem(){
cout<<"n";
for(int i=0;i<words.size();i++){
for(int j=0;j<words[i].size();j++){
cout<<words[i][j];
}
cout<<"n";
}
cout<<"---------n";
for(int i=0;i<result.size();i++){
cout<<result[i];
}
cout<<"n";
}
void printSolution(unordered_map<char, int> charValue){
cout<<"n";
for(int i=0;i<words.size();i++){
for(int j=0;j<words[i].size();j++){
cout<<charValue[wordOg[i][j]];
}
cout<<"n";
}
cout<<"---------n";
for(int i=0;i<result.size();i++){
cout<<charValue[resultOg[i]];
}
cout<<"n";
}
void solve(int colIdx, int idx, int carry, int sum,unordered_map<char, int> charValue, vector<int> domain){

if(colIdx<words.size()){
if(idx<words[colIdx].size()){
char ch = words[colIdx][idx];
if(charValue.find(ch)!=charValue.end()){
solve(colIdx + 1, idx, carry, sum + charValue[ch], charValue, domain);
}
else{
for(int i=0;i<10;i++){
if(i==0 && idx==words[colIdx].size()-1) continue;
if(domain[i]==-1){
domain[i] = 0;
charValue[ch] = i;
solve(colIdx + 1, idx, carry, sum + i, charValue, domain);
domain[i] = -1;
}
}
}
}
else solve(colIdx + 1, idx, carry, sum, charValue, domain);
}
else{
if(charValue.find(result[idx])!=charValue.end()){
if(((sum+carry)%10)!=charValue[result[idx]]) return;
}
else{
if(domain[(sum + carry)%10]!=-1) return;
domain[(sum + carry)%10] = 0;
charValue[result[idx]] = (sum + carry)%10;
}
carry = (sum+carry)/10;
if(idx==result.size()-1 && (charValue[result[idx]]==0 || carry == 1)) return;
if(idx+1<result.size()) solve(0, idx+1, carry, 0, charValue, domain);
else{
solExists = true;
printSolution(charValue);
}
}
}
int main() {
unordered_map<char, int> charValue;
vector<int> domain(10,-1);
int n;
cout<<"nEnter number of input words: ";
cin>>n;
cout<<"nEnter the words: ";
for(int i=0;i<n;i++){
string inp;
cin>>inp;
words.push_back(inp);
}
cout<<"nEnter the resultant word: ";
cin>>result;
printProblem();
wordOg = words;
resultOg = result;
reverse(result);
for(auto &itr: words) reverse(itr);
solve(0, 0, 0, 0, charValue, domain);
if(!solExists) cout<<"nNo Solution Exists!";
return 0;
}

相关内容

最新更新

热门标签：