#!/usr/bin/env ruby
	# Solves problems of form xxx + xxx = xxx
	# Where the numbers 1-9 are used at least and only once
	# Input:
	# Ex. 1xx + xxx = 469
	# Array of the form [1, 0, 0, 0, 0, 0, 4, 6, 8]
	# Where 0 = x
	# Output:
	# Ex. 193 + 275 = 468
	# Array of the form [1, 9, 3, 2, 7, 5, 4, 6, 8]
 
	def mathagram_solver(input)
		if input.length != 9 then
			raise ArgumentError "Input is not of the correct form, refer to code"
		end
		solution = Array.new(9, 0)
		available_nums = (1..9).to_a
		input.each_with_index do |chk, i|
			if chk < 0 || chk > 9 || chk.class != Fixnum then
				raise ArgumentError "Input is not of the correct form, refer to code"
			end
			# Copy input into solution if != 0 at i
			solution[i] = input[i] if 
			available_nums.delete(chk)
		end
		available_nums.permutation.to_a.each do |perm|
			# Clone solution array
			temp = solution.clone
			# Copy permutation into solution
			perm.each do |i|
				first_zero = temp.index(0)
				if first_zero.nil? then
					puts temp.inspect
				end
				temp[first_zero] = i
			end
			# Check if actual solution
			viable = temp[0..2].join('').to_i + temp[3..5].join('').to_i == temp[6..8].join('').to_i
			if viable then
				solution = temp
				break
			end
		end
		puts "#{solution[0..2].join('')} + #{solution[3..5].join('')} = #{solution[6..8].join('')}"
	end
 
	mathagram_solver([1, 0, 0, 0, 0, 0, 4, 6, 8])
	mathagram_solver([0, 0, 0, 0, 8, 1, 9, 0, 4])
	mathagram_solver([0, 0, 0, 5, 0, 1, 8, 6, 0])
	mathagram_solver([0, 0, 0, 3, 9, 0, 0, 7, 5])

IyEvdXNyL2Jpbi9lbnYgcnVieQoJIyBTb2x2ZXMgcHJvYmxlbXMgb2YgZm9ybSB4eHggKyB4eHggPSB4eHgKCSMgV2hlcmUgdGhlIG51bWJlcnMgMS05IGFyZSB1c2VkIGF0IGxlYXN0IGFuZCBvbmx5IG9uY2UKCSMgSW5wdXQ6CgkjIEV4LiAxeHggKyB4eHggPSA0NjkKCSMgQXJyYXkgb2YgdGhlIGZvcm0gWzEsIDAsIDAsIDAsIDAsIDAsIDQsIDYsIDhdCgkjIFdoZXJlIDAgPSB4CgkjIE91dHB1dDoKCSMgRXguIDE5MyArIDI3NSA9IDQ2OAoJIyBBcnJheSBvZiB0aGUgZm9ybSBbMSwgOSwgMywgMiwgNywgNSwgNCwgNiwgOF0KCglkZWYgbWF0aGFncmFtX3NvbHZlcihpbnB1dCkKCQlpZiBpbnB1dC5sZW5ndGggIT0gOSB0aGVuCgkJCXJhaXNlIEFyZ3VtZW50RXJyb3IgIklucHV0IGlzIG5vdCBvZiB0aGUgY29ycmVjdCBmb3JtLCByZWZlciB0byBjb2RlIgoJCWVuZAoJCXNvbHV0aW9uID0gQXJyYXkubmV3KDksIDApCgkJYXZhaWxhYmxlX251bXMgPSAoMS4uOSkudG9fYQoJCWlucHV0LmVhY2hfd2l0aF9pbmRleCBkbyB8Y2hrLCBpfAoJCQlpZiBjaGsgPCAwIHx8IGNoayA+IDkgfHwgY2hrLmNsYXNzICE9IEZpeG51bSB0aGVuCgkJCQlyYWlzZSBBcmd1bWVudEVycm9yICJJbnB1dCBpcyBub3Qgb2YgdGhlIGNvcnJlY3QgZm9ybSwgcmVmZXIgdG8gY29kZSIKCQkJZW5kCgkJCSMgQ29weSBpbnB1dCBpbnRvIHNvbHV0aW9uIGlmICE9IDAgYXQgaQoJCQlzb2x1dGlvbltpXSA9IGlucHV0W2ldIGlmIAoJCQlhdmFpbGFibGVfbnVtcy5kZWxldGUoY2hrKQoJCWVuZAoJCWF2YWlsYWJsZV9udW1zLnBlcm11dGF0aW9uLnRvX2EuZWFjaCBkbyB8cGVybXwKCQkJIyBDbG9uZSBzb2x1dGlvbiBhcnJheQoJCQl0ZW1wID0gc29sdXRpb24uY2xvbmUKCQkJIyBDb3B5IHBlcm11dGF0aW9uIGludG8gc29sdXRpb24KCQkJcGVybS5lYWNoIGRvIHxpfAoJCQkJZmlyc3RfemVybyA9IHRlbXAuaW5kZXgoMCkKCQkJCWlmIGZpcnN0X3plcm8ubmlsPyB0aGVuCgkJCQkJcHV0cyB0ZW1wLmluc3BlY3QKCQkJCWVuZAoJCQkJdGVtcFtmaXJzdF96ZXJvXSA9IGkKCQkJZW5kCgkJCSMgQ2hlY2sgaWYgYWN0dWFsIHNvbHV0aW9uCgkJCXZpYWJsZSA9IHRlbXBbMC4uMl0uam9pbignJykudG9faSArIHRlbXBbMy4uNV0uam9pbignJykudG9faSA9PSB0ZW1wWzYuLjhdLmpvaW4oJycpLnRvX2kKCQkJaWYgdmlhYmxlIHRoZW4KCQkJCXNvbHV0aW9uID0gdGVtcAoJCQkJYnJlYWsKCQkJZW5kCgkJZW5kCgkJcHV0cyAiI3tzb2x1dGlvblswLi4yXS5qb2luKCcnKX0gKyAje3NvbHV0aW9uWzMuLjVdLmpvaW4oJycpfSA9ICN7c29sdXRpb25bNi4uOF0uam9pbignJyl9IgoJZW5kCgoJbWF0aGFncmFtX3NvbHZlcihbMSwgMCwgMCwgMCwgMCwgMCwgNCwgNiwgOF0pCgltYXRoYWdyYW1fc29sdmVyKFswLCAwLCAwLCAwLCA4LCAxLCA5LCAwLCA0XSkKCW1hdGhhZ3JhbV9zb2x2ZXIoWzAsIDAsIDAsIDUsIDAsIDEsIDgsIDYsIDBdKQoJbWF0aGFncmFtX3NvbHZlcihbMCwgMCwgMCwgMywgOSwgMCwgMCwgNywgNV0p