Cryptarithmetic - Revision history

Admin at 08:32, 17 July 2017

2017-07-17T08:32:27Z

← Older revision		Revision as of 08:32, 17 July 2017
Line 1:		Line 1:
	Cryptarithmetic example: ~~https://developers.google.com/optimization/puzzles/cryptarithmetic~~		Cryptarithmetic example:

	<pre>		<pre>
Line 41:		Line 41:
	which puts this problem squarely in the ballpark of problem sizes that can be solved. In particular, this constrained programming approach can be solved using a [[Algorithms/Combinatorics_and_Heuristics\|Combinatorics and Heuristics]]-based method. While this problem may have some local structure to the digit relationships, they are complicated - so we can treat this solution space as random. There are also many solutions - 72 solutions, to be exact.		which puts this problem squarely in the ballpark of problem sizes that can be solved. In particular, this constrained programming approach can be solved using a [[Algorithms/Combinatorics_and_Heuristics\|Combinatorics and Heuristics]]-based method. While this problem may have some local structure to the digit relationships, they are complicated - so we can treat this solution space as random. There are also many solutions - 72 solutions, to be exact.

			Can also use Google's Operations Research (optimization tools) package: https://developers.google.com/optimization/puzzles/cryptarithmetic

	[[Category:Algorithms]]		[[Category:Algorithms]]

Admin at 08:31, 17 July 2017

2017-07-17T08:31:58Z

← Older revision		Revision as of 08:31, 17 July 2017
Line 40:		Line 40:

	which puts this problem squarely in the ballpark of problem sizes that can be solved. In particular, this constrained programming approach can be solved using a [[Algorithms/Combinatorics_and_Heuristics\|Combinatorics and Heuristics]]-based method. While this problem may have some local structure to the digit relationships, they are complicated - so we can treat this solution space as random. There are also many solutions - 72 solutions, to be exact.		which puts this problem squarely in the ballpark of problem sizes that can be solved. In particular, this constrained programming approach can be solved using a [[Algorithms/Combinatorics_and_Heuristics\|Combinatorics and Heuristics]]-based method. While this problem may have some local structure to the digit relationships, they are complicated - so we can treat this solution space as random. There are also many solutions - 72 solutions, to be exact.


			[[Category:Algorithms]]

Admin at 08:21, 17 July 2017

2017-07-17T08:21:18Z

← Older revision		Revision as of 08:21, 17 July 2017
Line 26:		Line 26:

	We can also limit the search space by constraining C, I, F, T to be nonzero.		We can also limit the search space by constraining C, I, F, T to be nonzero.

			We have 10 letters total, CPISFUNTRE, and of those 6 that are possibly (0 through base) and 4 which are possibly (1 through base), for a total search space of

			<math>
			b^6 (b-1)^4
			</math>

			For radix 10, that's:

			<math>
			10^6 \times 9^4 = 6,561,000,000 = 6.56 \times 10^9
			</math>

			which puts this problem squarely in the ballpark of problem sizes that can be solved. In particular, this constrained programming approach can be solved using a [[Algorithms/Combinatorics_and_Heuristics\|Combinatorics and Heuristics]]-based method. While this problem may have some local structure to the digit relationships, they are complicated - so we can treat this solution space as random. There are also many solutions - 72 solutions, to be exact.

Admin at 08:13, 17 July 2017

2017-07-17T08:13:55Z

← Older revision		Revision as of 08:13, 17 July 2017
Line 20:		Line 20:

	<math>		<math>
	F ~~\times~~ r^2 + (C+I+U) ~~\times~~ r + (P+S+N) = T ~~\times~~ r^3 + R ~~\times~~ r^2 + U ~~\times~~ r + E		F r^2 + (C+I+U) r + (P+S+N) = T r^3 + R r^2 + U r + E
	</math>		</math>

	where r is the radix.		where r is the radix.

			We can also limit the search space by constraining C, I, F, T to be nonzero.

Admin at 08:12, 17 July 2017

2017-07-17T08:12:20Z

← Older revision		Revision as of 08:12, 17 July 2017
Line 20:		Line 20:

	<math>		<math>
	F \times ~~base~~^2 + (C+I+U) \times ~~base~~ + (P+S+N) = T \times ~~base~~^3 + R \times ~~base~~^2 + U \times ~~base~~ + E		F \times r^2 + (C+I+U) \times r + (P+S+N) = T \times r^3 + R \times r^2 + U \times r + E
	</math>		</math>

			where r is the radix.

Admin at 08:11, 17 July 2017

2017-07-17T08:11:44Z

← Older revision		Revision as of 08:11, 17 July 2017
Line 11:		Line 11:
	The challenge is to find integers to swap out for each letter such that the equation holds true. This is a constrained programming problem, and can be re-cast in terms of an arbitrary radix as follows:		The challenge is to find integers to swap out for each letter such that the equation holds true. This is a constrained programming problem, and can be re-cast in terms of an arbitrary radix as follows:

	The "~~tens~~" place ~~becomes the expression <math>\mbox{(C+I+F)}\times(\mbox{base})</math>~~ on the left side and <math>\mbox{T}~~\times(\mbox{base})~~</math> on the right.		The "thousands" place has nothing on the left side, and a <math>\mbox{T}</math> on the right side.

	The "ones" place becomes the expression <math>~~\mbox{~~P+S+N}</math> on the left and <math>~~\mbox{~~E}</math> on the right, which, combining, gives:		The "hundreds" place has an <math>F</math> on the left side and a <math>\mbox{R}</math> on the right side.

			The "tens" place becomes the expression <math>(C+I+U) \times base</math> on the left side and <math>U \times base</math> on the right.

			The "ones" place becomes the expression <math>P+S+N</math> on the left and <math>E</math> on the right, which, combining, gives:

	<math>		<math>
	\~~mbox{~~(C+I+F)}\times~~(\mbox{~~base}) + ~~\mbox{~~P+S+N} = ~~\mbox{~~T}\times(\~~mbox{~~base}) + \~~mbox{~~E}		F \times base^2 + (C+I+U) \times base + (P+S+N) = T \times base^3 + R \times base^2 + U \times base + E
	</math>		</math>

Admin: Created page with "Cryptarithmetic example: https://developers.google.com/optimization/puzzles/cryptarithmetic

       CP +     IS +    FUN -------- =   TRUE

The challenge is to fin..."

2017-07-17T08:08:40Z

Created page with "Cryptarithmetic example: https://developers.google.com/optimization/puzzles/cryptarithmetic <pre> CP + IS + FUN -------- = TRUE </pre> The challenge is to fin..."

New page

Cryptarithmetic example: https://developers.google.com/optimization/puzzles/cryptarithmetic

<pre>
CP
+ IS
+ FUN
--------
= TRUE
</pre>

The challenge is to find integers to swap out for each letter such that the equation holds true. This is a constrained programming problem, and can be re-cast in terms of an arbitrary radix as follows:

The "tens" place becomes the expression <math>\mbox{(C+I+F)}\times(\mbox{base})</math> on the left side and <math>\mbox{T}\times(\mbox{base})</math> on the right.

The "ones" place becomes the expression <math>\mbox{P+S+N}</math> on the left and <math>\mbox{E}</math> on the right, which, combining, gives:

<math>
\mbox{(C+I+F)}\times(\mbox{base}) + \mbox{P+S+N} = \mbox{T}\times(\mbox{base}) + \mbox{E}
</math>