Some simple boards like

  11111111
  22222222
  33333333
  44444444
  55555555
  66666666
  77777777
  88888888

  11112222
  11112222
  33334444
  33334444
  55556666
  55556666
  77778888
  77778888

To consider a solver, start with the stupid-simple option:

Step 1. For each open square, copy the board, place a queen there, and recursively call the solver until an option results in 8 placed queens. This will obviously work, but is about as bad as the solution can get. Starting with this means you have an easy test case for every improved version.

To make it better, you want to bail out of that recursion as early and often as you can.

Step 2. Sort the regions by number of open squares, and iterate over the open squares from least-number-of-possibilities to most.

This will naturally place queens for colors that have only one remaining open square first, folllowed by the ones where the odds of hitting the correct square is highest, and so will usually drive down the combinatorical explosion a lot.

Step 3. To improve on this further, at the start of the solve function, check if the board is in an invalid state. That is, the number of regions with open squares must match the number of queens yet to be placed.

This will prune any sub-trees you want to test that would place the board in an invalid state.

Any pruned sub-tree should then cause that square to be marked unavailable before you continue.

Step 4. At the start of the solver mark as many squares that can't have queens as possible. The set of rules you can apply here is pretty big, but you can probably make do with very few. E.g. simple to implement rules would include:

* if any color is present in only one row or column, mark all other squares (of other colors) in that row or column as unavailable.

* if any color is the only color present in a given row or column, mark all squares of that color in other rows / columns as unavailable.

(you can extend the first above to: if any open squares of n colors are present in the same n rows or columns, mark all other squares (of other colors) in those rows or columns as unavailable, but I'm not sure if that will cut down on the recursion enough to be worth the hassle)

There are probably much more elegant solutions, but I think I'd end up with something like this pseudo-code:

    # Find a (possibly/likely incomplete) set of positions to mark as unavailable
    # because they're either impossible due to the current position, or because you
    # can place a queen with certainty
    #
    mark(board)
      while changes during execution:
        for each open square:
          for each color without placed queen:
            if open squares in only one row, mark all other squares of other colors in that row unavailable
            if open squares in only one column, mark all other squares of other colors in that column unavailable
            for each row/for each column: if only one color has open square, place queen.
            # Apply more rules here if you should need it; my hunch - but it is a hunch only - is that the above will prune the tree enough
      return true if still open squares, false if no open squares.

    # Check if the current board is invalid. That is, each color without a placed
    # queen must still have at least one open square.
    #
    invalid(board):
       for each color without placed queen:
          if no open square of this color, then return true
       return false

    pick_square(board):
        color = color with the smallest number of open squares.
        return first open square for "color"

    solve(board):
       while mark(board) and not invalid(board)
          square = pick_square(board)
          copy board.
          place queen on the chosen square on the copied board.
          if solve(copied board) returned solution, then return solution
          else mark square unavailable.
       if all queens placed, return solution,
       else return unsolvable

And these colored regions can be of any size.