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.

  magnet-puzzle

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 its C++ implementation –
 

Download   Run Code

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

 
Thanks for reading.




Please use ideone or C++ Shell or any other online compiler link to post code in comments.
Like us? Please spread the word and help us grow. Happy coding 🙂
 





Leave a Reply

Notify of
avatar
wpDiscuz