moyen efficace de résolution Cryptarithms
https://stackoverflow.com/questions/750984
-
09-09-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianQuestion
Salut je suis tombé sur ce casse-tête qui est un sous-ensemble de type célèbre de mot et les numéros de casse-tête à base appelés Cryptarithms . Disons que vous avez une expression comme
S E N D + M O R E = M O N E O
Maintenant la partie intéressante, il est que, chaque alphabet représente un chiffre unique, de 0-9. Je voulais écrire un solveur généralisé, mais je fini par écrire une solution forcée brute pour elle. Tous les preneurs que comment puis-je résoudre?
Je pense qu'il peut être résolu en utilisant la logique des prédicats ou la théorie des ensembles. Et je suis particulièrement intéressé à trouver C # ou Python solutions. Une.?
La solution
Autres conseils
Ceci est un petit problème qu'une solution force brute n'est pas une mauvaise méthode. En supposant que chaque lettre doit représenter un chiffre unique, (ie nous ne permettrons pas la solution S = 9, M = 1, * = 0) on voit que nombre de combinaisons à essayer est n , où n est le nombre de lettres uniques dans le cryptarithm. Le nombre maximum théorique de combinaisons pour évaluer est 10! = 3 628 800 , ce qui est vraiment petit nombre pour un ordinateur.
Si nous laissons plusieurs lettres pour représenter le même nombre, le nombre de combinaisons à essayer sera limitée par 10 ^ n , encore une fois n est le nombre de produits uniques des lettres. En supposant que MAJUSCULES anglais, nous avons un nombre maximum théorique de combinaisons de 10 ^ 26 , donc pour que le pire des cas théoriques, nous pourrions avoir besoin des heuristiques. cryptarithms les plus pratiques ont beaucoup moins de 26 lettres uniques, donc le cas normal sera probablement limitée par un n inférieur à 10, ce qui est encore assez raisonnable pour un ordinateur.
Eh bien, il essayer d'écrire une liste de fonctions:
SEND
MORE
----+
MONEY
Si je me souviens de mon mathématiques scolaire inférieur, cela devrait être:
Y = (D+E) mod 10
E = ((N+R) + (D+E)/10) mod 10
...
Voici une méthode de force brute efficace que les cycles à travers toutes les possibilités récursive, mais prend également note de la structure du problème particulier raccourci le problème.
Les premiers arguments de chaque méthode représentent des valeurs d'essai pour chaque branche, les arguments v1, v2, etc sont les valeurs encore à attribuer et peut être passé en toute ordre. la méthode est efficace parce qu'il a un maximum de solutions d'essai 8x7x5 possibles plutôt que les 10! / 2 solutions possibles par la force brute
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
namespace ConsoleApplication1
{
class Program
{
static void MESDYNR(int m, int s, int e, int d, int y, int n, int r, int v1, int v2, int v3)
{
// Solve for O in hundreds position
// "SEND" + "M?RE" = "M?NEY"
int carry = (10 * n + d + 10 * r + e) / 100;
int o = (10 + n - (e + carry))%10;
if ((v1 == o) || (v2 == o) || (v3 == o))
{
// check O is valid in thousands position
if (o == ((10 + (100 * e + 10 * n + d + 100 * o + 10 * r + e) / 1000 + m + s) % 10))
{
// "SEND" + "MORE" = "MONEY"
int send = 1000 * s + 100 * e + 10 * n + d;
int more = 1000 * m + 100 * o + 10 * r + e;
int money = 10000 * m + 1000 * o + 100 * n + 10 * e + y;
// Chck this solution
if ((send + more) == money)
{
Console.WriteLine(send + " + " + more + " = " + money);
}
}
}
}
static void MSEDYN(int m, int s, int e, int d, int y, int n, int v1, int v2, int v3, int v4)
{
// Solve for R
// "SEND" + "M*?E" = "M*NEY"
int carry = (d + e) / 10;
int r = (10 + e - (n + carry)) % 10;
if (v1 == r) MESDYNR(m, s, e, d, y, n, r, v2, v3, v4);
else if (v2 == r) MESDYNR(m, s, e, d, y, n, r, v1, v3, v4);
else if (v3 == r) MESDYNR(m, s, e, d, y, n, r, v1, v2, v4);
else if (v4 == r) MESDYNR(m, s, e, d, y, n, r, v1, v2, v3);
}
static void MSEDY(int m, int s, int e, int d, int y, int v1, int v2, int v3, int v4, int v5)
{
// Pick any value for N
MSEDYN(m, s, e, d, y, v1, v2, v3, v4, v5);
MSEDYN(m, s, e, d, y, v2, v1, v3, v4, v5);
MSEDYN(m, s, e, d, y, v3, v1, v2, v4, v5);
MSEDYN(m, s, e, d, y, v4, v1, v2, v3, v5);
MSEDYN(m, s, e, d, y, v5, v1, v2, v3, v4);
}
static void MSED(int m, int s, int e, int d, int v1, int v2, int v3, int v4, int v5, int v6)
{
// Solve for Y
// "SE*D" + "M**E" = "M**E?"
int y = (e + d) % 10;
if (v1 == y) MSEDY(m, s, e, d, y, v2, v3, v4, v5, v6);
else if (v2 == y) MSEDY(m, s, e, d, y, v1, v3, v4, v5, v6);
else if (v3 == y) MSEDY(m, s, e, d, y, v1, v2, v4, v5, v6);
else if (v4 == y) MSEDY(m, s, e, d, y, v1, v2, v3, v5, v6);
else if (v5 == y) MSEDY(m, s, e, d, y, v1, v2, v3, v4, v6);
else if (v6 == y) MSEDY(m, s, e, d, y, v1, v2, v3, v4, v5);
}
static void MSE(int m, int s, int e, int v1, int v2, int v3, int v4, int v5, int v6, int v7)
{
// "SE**" + "M**E" = "M**E*"
// Pick any value for D
MSED(m, s, e, v1, v2, v3, v4, v5, v6, v7);
MSED(m, s, e, v2, v1, v3, v4, v5, v6, v7);
MSED(m, s, e, v3, v1, v2, v4, v5, v6, v7);
MSED(m, s, e, v4, v1, v2, v3, v5, v6, v7);
MSED(m, s, e, v5, v1, v2, v3, v4, v6, v7);
MSED(m, s, e, v6, v1, v2, v3, v4, v5, v7);
MSED(m, s, e, v7, v1, v2, v3, v4, v5, v6);
}
static void MS(int m, int s, int v1, int v2, int v3, int v4, int v5, int v6, int v7, int v8)
{
// "S***" + "M***" = "M****"
// Pick any value for E
MSE(m, s, v1, v2, v3, v4, v5, v6, v7, v8);
MSE(m, s, v2, v1, v3, v4, v5, v6, v7, v8);
MSE(m, s, v3, v1, v2, v4, v5, v6, v7, v8);
MSE(m, s, v4, v1, v2, v3, v5, v6, v7, v8);
MSE(m, s, v5, v1, v2, v3, v4, v6, v7, v8);
MSE(m, s, v6, v1, v2, v3, v4, v5, v7, v8);
MSE(m, s, v7, v1, v2, v3, v4, v5, v6, v8);
MSE(m, s, v8, v1, v2, v3, v4, v5, v6, v7);
}
static void Main(string[] args)
{
// M must be 1
// S must be 8 or 9
DateTime Start = DateTime.Now;
MS(1, 8, 2, 3, 4, 5, 6, 7, 9, 0);
MS(1, 9, 2, 3, 4, 5, 6, 7, 8, 0);
Console.WriteLine((DateTime.Now-Start).Milliseconds);
return;
}
}
}
cette peut être d'une certaine aide
Modifier: la réponse sur le lien wiki que vous avez publié est également utile
