This post is about a fun puzzle called the number placement puzzle. I have provided an interactive console program that lets you explore it. I have also provided a couple of algorithms for solving the puzzle.

Interactive Number Placement Puzzle

Put the numbers provided in the correct positions to make all the inequalities true.

Brute Force Solution for the Number Placement Puzzle with Python

Now that you have had a go the puzzle, did you come with a repeatable method for solving it?

One approach, which is effective although not efficient at all, is to try all permutations of the numbers in different positions until you find one which makes all the inequalities true. The efficiency of this approach in the worst case is O(n!) if you know about such things, which is very bad, especially for larger puzzles. However it is interesting and instructive to try and implement this solution. Have a go yourself before looking at my version. You will have to think about how to represent the puzzle as well as how to solve it.

My first approach, which leaves a lot to be desired but at least I believe is correct, is shown below.

import random
from itertools import permutations

PUZZLE_SIZE = 3

# random.sample ensures no duplicates.
puzzle_nums = random.sample(range(100), PUZZLE_SIZE)
puzzle = []

for i in range(PUZZLE_SIZE - 1):
    puzzle.append("?")
    puzzle.append(">" if random.random() < .5 else "<")
puzzle.append("?")

# print("".join(puzzle)) # ?<?<?<?<?
# print(puzzle) # ['?', '<', '?', '<', '?', '<', '?']

number_positions = list(range(0, 2 * PUZZLE_SIZE - 1, 2))

perms = permutations(puzzle_nums)
for perm in list(perms):
    for i in range(PUZZLE_SIZE):
        puzzle[number_positions[i]] = str(perm[i])
    print(" ".join(puzzle), end="\t")
    print(eval("".join(puzzle)))

Transform-and-Conquer Solution for the Number Placement Puzzle with Python

The key to finding a better algorithm for solving the puzzle is to apply the Transform and Conquer algorithmic technique. You may have come up with this approach in your initial experimentation. If so, well done.

The key to the efficient solution of the puzzle is to sort the numbers first!

If you sort the numbers first, then a much more efficient algorithm is possible.

The algorithm makes use of the “two pointers” technique which is used in quite a few algorithms, and is very useful. We keep track of where we are in an array or list by having a low pointer and a high pointer (they are not really pointers in the programming sense as such – just variables containing the indices of the highest and lowest positions in the array at the current stage of the algorithm). You may have seen this technique before, for example in the famous Binary Search algorithm.

My implementation of this solution is shown below. Note that I simplified the representation of the puzzle, having noticed that in the first solution I was making life unnecessarily complicated. The benefit of hindsight!

The basic logic of the transform-and-conquer solution is this:

• Sort the puzzle numbers first
• Iterate through the inequality signs
• Use the largest remaining puzzle number if the sign is >, and the smallest remaining if <, and delete the puzzle number from list each time.
• The deleting works fine if solving the puzzle on paper/whiteboard. In a program it is probably better to implement this using the “two pointer” method, as described above.

Note: since we have stipulated that the puzzle numbers must by distinct, the puzzle will always have a solution. Phew!

import random

PUZZLE_SIZE = 10

# random.sample ensures no duplicates.
puzzle_nums = random.sample(range(100), PUZZLE_SIZE)
puzzle_symbols = []

for i in range(PUZZLE_SIZE - 1):
    puzzle_symbols.append(">" if random.random() < .5 else "<")

# Sort puzzle numbers first.
# Use largest remaining if greater than, smallest remaing if less than.

print(puzzle_nums)
print(puzzle_symbols)


sorted_puzzle_nums = sorted(puzzle_nums, reverse=True)
high = 0
low = PUZZLE_SIZE - 1
solution = []

for symbol in puzzle_symbols:
    if symbol == ">":
        solution.append(sorted_puzzle_nums[high])
        high += 1
    elif symbol == "<":
        solution.append(sorted_puzzle_nums[low])
        low -= 1
solution.append(sorted_puzzle_nums[high])
# print(solution)

# Convert solution to strings
solution = list(map(str, solution))

puzzle = [None]*(len(solution)+len(puzzle_symbols))
puzzle[::2] = solution  # Nifty slicing with step
puzzle[1::2] = puzzle_symbols
# print(puzzle)
print(" ".join(puzzle))
print(eval(" ".join(puzzle)))

This post has introduced the number placement puzzle and shown how to solve it algorithmically using Python. I hope you found it interesting and helpful. Happy computing!

Sharing is caring!