UVa 167 - The Sultan's Successors

UVa Problem

This is a famous problem of how to arrange 8 queens on a chessboard without having any queen threaten another one (by sharing the same row, column, or diagonal).

This can be solved simply by using recursion and backtracking. We iterate through all rows and try to find a free column to insert the queen into by checking that the cell won't share the same column, left diagonal or right diagonal with another queen, then mark the column, left diagonal and right diagonal as non-free.

this problem has one additional requirement. Each cell on the board is given some value, and as there can be many valid solutions, we wish to find the solution which maximizes the sum of the values of the cells containing the queens.

Solution:

#include <iostream>
#include <algorithm>
#include <vector>
#include <cstdio>

using namespace std;

class GameSolver
{
public:
   GameSolver(const vector<vector<int> >& board) :
      mBoard(board), mBoardSize(board.size()),
      mCurrMaxScore(0)
   {
      mQueens.reserve(mBoardSize);

      for(int iCol = 0;
            iCol < mBoardSize;
            ++iCol)
         mFreeColumns.push_back(true);

      for(int iDiag = 0;
            iDiag < 2 * mBoardSize - 1;
            ++iDiag)
      {
         mFreeLeftDiags.push_back(true);
         mFreeRightDiags.push_back(true);
      }
   }

   int getMaxScore()
   {
      doSolve(0);
      return mCurrMaxScore;
   }
private:

   void doSolve(int iRow)
   {
      if(iRow == mBoardSize)
      {
         int score = 0;
         for(int i = 0; i < mBoardSize; ++i)
         {
            score += mBoard[i][mQueens[i]];
         }

         mCurrMaxScore = max(mCurrMaxScore, score);
         return;
      }

      for(int iCol = 0; iCol < mBoardSize; ++iCol)
      {
         if(mFreeColumns[iCol] &&
               mFreeLeftDiags
               [iRow - iCol + mBoardSize - 1] &&
               mFreeRightDiags[iRow + iCol])
         {
            mFreeColumns[iCol] = false;

            mFreeLeftDiags
            [iRow - iCol + mBoardSize - 1] = false;

            mFreeRightDiags[iRow + iCol] = false;

            mQueens[iRow] = iCol;
            doSolve(iRow+1);

            mFreeColumns[iCol] = true;
            mFreeLeftDiags
            [iRow - iCol + mBoardSize - 1] = true;
            mFreeRightDiags[iRow + iCol] = true;

         }

      }
   }

   int mBoardSize;
   const vector<vector<int> >& mBoard;
   vector<int> mQueens;
   vector<bool> mFreeColumns;
   vector<bool> mFreeLeftDiags;
   vector<bool> mFreeRightDiags;

   int mCurrMaxScore;

};


int main(int argc, char *argv[])
{
   const int boardSize = 8;

   vector<vector<int> > board;

   for(int iRow = 0; iRow < boardSize; ++iRow)
      board.push_back(vector<int>(boardSize, 0));

   int k;
   cin >> k;

   for(int iBoard = 0; iBoard < k; ++iBoard)
   {
      for(int iRow = 0; iRow < boardSize; ++iRow)
         for(int iCol = 0; iCol < boardSize; ++iCol)
            cin >> board[iRow][iCol];

      GameSolver game(board);
      int score = game.getMaxScore();

      printf("%5d\n", score);

   }

}