I enjoy logic puzzles, so this week I thought I’d challenge myself to solve a New Scientist logic puzzle using code, and share with you the process I went through to do this.
The Puzzle
The puzzle is New Scientist puzzle #97, Cabinet reshuffle:
The Ruritanian prime minister is in a fix. Thanks to a series of incompetent policy decisions, all five of her senior ministers need to be axed from their posts. However, the PM cannot afford to sack them completely, because they will wreak havoc if moved to the back benches.
She has a solution: a reshuffle! She will move each of the five ministers to one of the other top posts, but no two of them will directly swap with each other. Anerdine will move to the department of the person who will become chancellor. Brinkman will replace the person who will be the new home secretary. Crass will take over the post being vacated by the person who will take Eejit’s job. Dyer will be become health secretary even though he has been lobbying to become chancellor. The current defence secretary will get the department of the person who is becoming the education secretary.
Can you figure out who currently has which job, and where they are moving to?
Step 1: Pull out key information
The text of a logic puzzle contains key information that we will need to work out the solution. Sometimes the information is presented in a subtle way, so you have to have your wits about you!
Here’s the key information:
- Each of the five ministers is moving to a different post, previously occupied by another of the five ministers
- No two ministers will directly swap with each other
- Anerdine will displace the minister who will become chancellor
- Brinkman will displace the minister who will become home secretary
- Crass will displace the minister who will take Eejit’s current post
- Dyer will become health secretary
- Dyer has been lobbying to become chancellor
- The current defense secretary will displace the minister who will become the education secretary
Step 2: From the key information, make logical inferences
This is a tricky but crucial step. What information can we infer from the key information given?
Key information item 2 states that ‘no two ministers will directly swap with each other’. This also means that ministers can’t swap jobs in a chain of three, e.g. Anerdine swaps with Brinkman who swaps with Crass who swaps with Anerdine. In that scenario, Dyer and Eejit would have to swap with each other, which is not allowed. Likewise, ministers can’t swap jobs in a chain of four, as that would leave one minister unable to swap with anyone. Therefore, the only possible swapping chain is one of five, e.g. Anerdine swaps with Brinkman who swaps with Crass who swaps with Dyer who swaps with Eejit who swaps with Anerdine. This will be important when we construct our code solver.
Key information item 7 states that ‘Dyer has been lobbying to become chancellor’. This means that Dyer’s current post can’t be chancellor.
So the key logical inferences are:
- The ministers must swap in a chain of five
- Dyer’s current post isn’t chancellor
Step 3: The solving algorithm
Before we write any code, we need to have some idea of the steps we need to take to solve the puzzle, i.e. what algorithm we are going to use.
The final solution is going to be a chain of ministers and posts. At each position in the chain, there will be a minister and post. This will represent the current post for each minister. The post each minister is moving to is the next post along the chain. The minister at the end of the chain will move to the post at the start of the chain.
It will look something like this:
| Minister (?) | Minister (?) | Minister (?) | Minister (?) | Minister (?) |
| Post (?) | Post (?) | Post (?) | Post (?) | Post (?) |
The job of our solver will be to determine which ministers and which posts belong in each position in the chain.
The key information we have been given allows us to construct partial chains.
From key information 3, Anerdine will displace the minister who will become chancellor:
| Anerdine | Minister (?) | Minister (?) | Minister (?) | Minister (?) |
| Post (?) | Post (?) | chancellor | Post (?) | Post (?) |
From key information 4, Brinkman will displace the minister who will become home secretary:
| Brinkman | Minister (?) | Minister (?) | Minister (?) | Minister (?) |
| Post (?) | Post (?) | home secretary | Post (?) | Post (?) |
From key information 5, Crass will displace the minister who will take Eejit’s current post:
| Crass | Minister (?) | Eejit | Minister (?) | Minister (?) |
| Post (?) | Post (?) | Post (?) | Post (?) | Post (?) |
From key information 6, Dyer will become health secretary:
| Dyer | Minister (?) | Minister (?) | Minister (?) | Minister (?) |
| Post (?) | health secretary | Post (?) | Post (?) | Post (?) |
From key information 8, The current defense secretary will displace the minister who will become the education secretary:
| Minister (?) | Minister (?) | Minister (?) | Minister (?) | Minister (?) |
| defense secretary | Post (?) | education secretary | Post (?) | Post (?) |
From laying out these partial chains, we can see that each post is only mentioned once and only in one partial chain, and each minister is only mentioned once and only in one partial chain.
We can lay out our partial chains one under the other, so we get a ‘matrix’ of rows and columns.
This means our solving algorithm will need to ‘rotate’ the partial chains until they line up in such a way that:
a). There is only one minister in each ‘column’
b). There is only one post in each ‘column’
c). In the column that contains the minister Dyer, the column must not also contain the post ‘chancellor’
By ‘rotate’, I mean take the minister/post combination at the last position in the chain and put it at the first position in the chain, so that each minister/post combination moves along by one.
For example, the partial chain above (from key information 8), when rotated by one, would look like:
| Minister (?) | Minister (?) | Minister (?) | Minister (?) | Minister (?) |
| Post (?) | defense secretary | Post (?) | education secretary | Post (?) |
The solution will then be the result of combining all the chains into one, so the one minister and post in each column becomes the minister and post of that chain position. The resulting chain will represent the ministers’ current posts, and the posts they are moving to are the next posts in the chain.
Step 4: The Code
Now we need to put the algorithm into code. I’m going to use python for this example, but any programming language could be used. First, let’s set up the variables for the ministers and posts, and create the partial chains as lists. Then we can combine them into one list ready for iteration.
# The Ministers Minister_A = 'Anerdine' Minister_B = 'Brinkman' Minister_C = 'Crass' Minister_D = 'Dyer' Minister_E = 'Eejit' # The Posts Post_1 = 'Chancellor' Post_2 = 'Home Secretary' Post_3 = 'Defense Secretary' Post_4 = 'Education Secretary' Post_5 = 'Health Secretary' # Our initial information, expressed as partially filled-in chains. chain_0 = [[Minister_A, None], [None, None], [None, Post_1], [None, None], [None, None]] chain_1 = [[Minister_B, None], [None, None], [None, Post_2], [None, None], [None, None]] chain_2 = [[Minister_C, None], [None, None], [Minister_E, None], [None, None], [None, None]] chain_3 = [[Minister_D, None], [None, Post_5], [None, None], [None, None], [None, None]] chain_4 = [[None, Post_3], [None, None], [None, Post_4], [None, None], [None, None]] # Add all sub-chains to one list for iteration chains = list() chains.append(chain_0) chains.append(chain_1) chains.append(chain_2) chains.append(chain_3) chains.append(chain_4)
Now we enter our main algorithm loop. It will iterate over the partial chains, and then iterate over each position in the partial chain, checking our conditions at each step. If the conditions pass, we move on to the next iteration. If the conditions fail, we rotate the partial chain. If we finish iterating through all the partial chains, we check if the matrix configuration passes our conditions. If it doesn’t, we iterate through the partial chains again. If the matrix configuration passes our conditions, we’ve found the solution, so we break out of the while loop.
solution_found = False
while not solution_found:
# j is partial chain no
for j in range(1, 5):
# k is partial chain index
for k in range(5):
if not check_conditions(chains, k):
rotate_chain(chains, j)
solution_found = check_solution(chains)
Next we fill in the functions check_conditions, rotate_chain and check_solution.
def check_conditions(chains, k):
# Check the conditions at chain index k
minister_count = count_ministers(chains, k)
post_count = count_posts(chains, k)
if minister_count > 1 or post_count > 1:
return False
# Check Dyer is not Chancellor
minister = get_minister(chains, k)
post = get_post(chains, k)
if minister == Minister_D and post == Post_1:
return False
return True
def rotate_chain(chains, j):
# Rotate the partial chain by one, to try a new configuration
chains[j].insert(0, chains[j].pop())
def check_solution(chains):
# k is chain index
for k in range(5):
if not check_conditions(chains, k):
return False
return True
Note that these functions have introduced new functions count_ministers, count_posts, get_minister, get_post. So we add these in next:
def count_ministers(chains, i):
# Count the ministers at a chain position (column)
ministers = 0
for chain in chains:
if chain[i][0] is not None:
ministers += 1
return ministers
def count_posts(chains, i):
# Count the posts at a chain position (column)
posts = 0
for chain in chains:
if chain[i][1] is not None:
posts += 1
return posts
def get_minister(chains, i):
# Get the minister at a chain position (column)
for chain in chains:
if chain[i][0] is not None:
return chain[i][0]
return None
def get_post(chains, i):
# Get the post at a chain position (column)
for chain in chains:
if chain[i][1] is not None:
return chain[i][1]
return None
Finally we need some code to take the final matrix of partial chains and extract the solution from it:
def print_chains(chains):
print(chains[0])
print(chains[1])
print(chains[2])
print(chains[3])
print(chains[4])
print("===========================================")
print("Solution is:")
print_chains(chains)
print("==")
for i in range(5):
minister = get_minister(chains, i)
post = get_post(chains, i)
print(f"{minister} is {post}")
print("==")
for i in range(5):
minister = get_minister(chains, i)
# Use a modulo number for the index here, so if we go off the end of the list, we go back to the start
index = (i+1)%5
post = get_post(chains, index)
print(f"{minister} moves to {post}")
The entire script, all together, is below:
# The Ministers
Minister_A = 'Anerdine'
Minister_B = 'Brinkman'
Minister_C = 'Crass'
Minister_D = 'Dyer'
Minister_E = 'Eejit'
# The Posts
Post_1 = 'Chancellor'
Post_2 = 'Home Secretary'
Post_3 = 'Defense Secretary'
Post_4 = 'Education Secretary'
Post_5 = 'Health Secretary'
# Our initial information, expressed as partially filled-in chains.
chain_0 = [[Minister_A, None], [None, None], [None, Post_1], [None, None], [None, None]]
chain_1 = [[Minister_B, None], [None, None], [None, Post_2], [None, None], [None, None]]
chain_2 = [[Minister_C, None], [None, None], [Minister_E, None], [None, None], [None, None]]
chain_3 = [[Minister_D, None], [None, Post_5], [None, None], [None, None], [None, None]]
chain_4 = [[None, Post_3], [None, None], [None, Post_4], [None, None], [None, None]]
# Add all sub-chains to one list for iteration
chains = list()
chains.append(chain_0)
chains.append(chain_1)
chains.append(chain_2)
chains.append(chain_3)
chains.append(chain_4)
def count_ministers(chains, i):
# Count the ministers at a chain position (column)
ministers = 0
for chain in chains:
if chain[i][0] is not None:
ministers += 1
return ministers
def count_posts(chains, i):
# Count the posts at a chain position (column)
posts = 0
for chain in chains:
if chain[i][1] is not None:
posts += 1
return posts
def get_minister(chains, i):
# Get the minister at a chain position (column)
for chain in chains:
if chain[i][0] is not None:
return chain[i][0]
return None
def get_post(chains, i):
# Get the post at a chain position (column)
for chain in chains:
if chain[i][1] is not None:
return chain[i][1]
return None
def check_conditions(chains, k):
# Check the conditions at chain index k
minister_count = count_ministers(chains, k)
post_count = count_posts(chains, k)
if minister_count > 1 or post_count > 1:
return False
# Check Dyer is not Chancellor
minister = get_minister(chains, k)
post = get_post(chains, k)
if minister == Minister_D and post == Post_1:
return False
return True
def rotate_chain(chains, j):
# Rotate the partial chain by one, to try a new configuration
chains[j].insert(0, chains[j].pop())
def check_solution(chains):
# k is chain index
for k in range(5):
if not check_conditions(chains, k):
return False
return True
def print_chains(chains):
print(chains[0])
print(chains[1])
print(chains[2])
print(chains[3])
print(chains[4])
print("===========================================")
solution_found = False
while not solution_found:
# j is partial chain no
for j in range(1, 5):
# k is partial chain index
for k in range(5):
if not check_conditions(chains, k):
rotate_chain(chains, j)
solution_found = check_solution(chains)
print("Solution is:")
print_chains(chains)
print("==")
for i in range(5):
minister = get_minister(chains, i)
post = get_post(chains, i)
print(f"{minister} is {post}")
print("==")
for i in range(5):
minister = get_minister(chains, i)
# Use a modulo number for the index here, so if we go off the end of the list, we go back to the start
index = (i+1)%5
post = get_post(chains, index)
print(f"{minister} moves to {post}")
If we run the script, we get the following output:
Solution is: [['Anerdine', None], [None, None], [None, 'Chancellor'], [None, None], [None, None]] [[None, None], [None, None], ['Brinkman', None], [None, None], [None, 'Home Secretary']] [[None, None], ['Crass', None], [None, None], ['Eejit', None], [None, None]] [[None, 'Health Secretary'], [None, None], [None, None], [None, None], ['Dyer', None]] [[None, None], [None, 'Defense Secretary'], [None, None], [None, 'Education Secretary'], [None, None]] =========================================== == Anerdine is Health Secretary Crass is Defense Secretary Brinkman is Chancellor Eejit is Education Secretary Dyer is Home Secretary == Anerdine moves to Defense Secretary Crass moves to Chancellor Brinkman moves to Education Secretary Eejit moves to Home Secretary Dyer moves to Health Secretary
The first part of the output is our final partial chain matrix, which should now pass all the conditions we set for it, with only one minister/post in each column, and with Dyer not as chancellor. As represented as a full chain, it is:
| Anerdine | Crass | Brinkman | Eejit | Dyer |
| health secretary | defense secretary | chancellor | education secretary | home secretary |
The second and third parts of the output show who has which post now, and which posts the ministers will be moving to. The latter is calculated simply by assigning each minister to the next post in the final chain.
There are probably other ways this logic puzzle could be solved with code, but this seemed to me to be the simplest. Feel free to try your own way and let me know how you get on!
Very impressive!
Thanks Simon! 🙂