# Magnet Puzzle

We are given set of bipolar magnets each domino-shaped. The objective is to place magnets on a M X N board which should meet a set of conditions where both N and M are not odd.

For instance, below given problem has solution on its right. Each 2 x 1 or 1 x 2 grid in the board can contain a magnet or can be empty. The blank entry will be indicated by X’s and the magnet will be represented by + and – (For positive and negative end respectively). The digits along the left and top sides of the board represent the count of + squares in corresponding rows or columns. Similarly, those along the right and bottom show the number of – signs in particular rows or columns. Rows and columns for which no number is mentioned can have any number of + or – signs. The puzzle solution must also satisfy the constraint that no two adjacent squares can have the same sign. But diagonally joined squares can have same sign.

Examples:

Here top[], bottom[], left[], right[] arrays indicates the count of + or – along the top (+), bottom (-), left (+) and right (-) edges respectively. Values of -1 indicates any number of + or – signs.

Rules[][] matrix can contain any one T, B, L or R characters. For a vertical slot in the board, T indicates its top end and B indicates the bottom end. For a horizontal slot in the board, L indicates left end & R indicates the right end.

Input:
top[] = {1, -1, -1, 2, 1, -1}
bottom[] = {2, -1, -1, 2, -1, 3}
left[] = {2, 3, -1, -1, -1}
right[] = {-1, -1, -1, 1, -1}

Rules[][] =
[L R L R T T]
[L R L R B B]
[T T T T L R]
[B B B B T T]
[L R L R B B]

Output:
+ – + – X –
– + – + X +
X X + – + –
X X – + X +
– + X X X –

Input:
top[] = [2, -1, -1]
bottom[] = [-1, -1, 2]
left[] = [-1, -1, 2, -1]
right[] = [0, -1, -1, -1]

Rules[][] =
[T T T]
[B B B]
[T L R]
[B L R]

Output:
+ X +
– X –
+ – +
– + –

The idea is to use backtracking. We start from the first cell of the rules matrix and check for every horizontal and vertical slot. If horizontal or vertical slot contains L and R or T and B respectively, we put (‘+’, ‘-‘) or (‘-‘, ‘+’) accordingly in the slot and recursively checks if they leads to the solution or not. If solution is found with required configuration, we print the solution matrix else if none of the above solutions work we return false from our function.

Below is C++/Java implementation of the idea –

## Java

Output:

+ – + – X –
– + – + X +
X X + – + –
X X – + X +
– + X X X –

This question is taken from http://www.cs.berkeley.edu/~hilfingr/programming-contest/f2012-contest.pdf     (1 votes, average: 5.00 out of 5) Loading...

Please use our online compiler to post code in comments. To contribute, get in touch with us.
Like us? Please spread the word and help us grow. Happy coding 🙂 Subscribe
Notify of Guest

It is not hard at all, it is just 300 lines of code. The hard bit is to do 0 mistakes while writing this without IDE. Guest

yes.. really good problem with an amazing solution.. Guest

This problem might be solved by dp Guest

How dude xD Guest

M N are not odd, and they are 5 6?
WTF? 5 is not odd?