UVa 861 - Little Bishops

Problem

Here is the problem description: UVa 861 - Little Bishops

Idea

I first tried this problem with backtrack as it is quite similar to the eight queens problem, but it turned out to be TLE. Then after searching over internet, I found that most people use dp for this problem but most explainations are not easy to follow.

The main idea to solve the problem with dp is to separate all positions on black and white, and rotate the board 45 degrees to count them independently.

Let x be black position and o white position. As the bishops on black positions can never attack those on white positions, we can solve two problems separately then sum the results.

               x
       o      o o
x     x x    x x x
       o      o o
               x

From left to right it corresponds to board 1x1 to board 3x3.

Code

The code to implement the idea is as following