开发者

how to determine the number assigned to each letter in a cryptarithm?

开发者 https://www.devze.com 2023-03-05 19:30 出处:网络
I have an assignment that needs to solve a cryptarith开发者_如何学Cm. But I cant understand the algorithms that I saw in the internet. Could anybody explain how to do this in simple words?As a general

I have an assignment that needs to solve a cryptarith开发者_如何学Cm. But I cant understand the algorithms that I saw in the internet. Could anybody explain how to do this in simple words?


As a general case, most Constraint Satisfaction Algorithms are a two step process, where a guessing (or branching) phase is followed by a deductive phase, where as many assignments as possible are found without guessing. (Think Sudoku, for example)

Example:

  S E N D
  M O R E
M O N E Y

First step: guess D=1 (remaining guesses = ...)

  S E N 1  | D=1
  M O R E
M O N E Y

Guess E = 1 (Remaining guesses = ...)

  S 1 N 1  | D = 1 | E = 1
  M O R 1
M O N 1 Y

We can now deduce that Y = 2 and that the carry value in the second column is 0

      0
  S 1 N 1  | D = 1 | E = 1, Y = 2
  M O R 1
M O N 1 2

When you reach a dead end, backtrack


It's possible to solve this kind of problem with Genetic Algorithm, here is a solution using GA https://github.com/pauloremoli/cryptarithmetic

0

精彩评论

暂无评论...
验证码 换一张
取 消