Practice NQueens soln

nqueens.cpp

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;

typedef vector<int> Queens;
typedef pair<int, int> Position;

void fmtQueens(Queens board, int n)
{
  for (auto it : board)
    {
      for (int i = 0; i < n; ++i){
        if (i == it) cout << " x ";
        else cout << " - ";
      }
      cout << endl;
    }
}

bool isValid(Queens board) {
  unordered_map<int, int> board_map;
  int i = 0;
  for (auto it : board)
    {
      if (!board_map[it])
        {
          board_map[it] = i;
          i++;
        }
      else
        {
          return false;
        }
    }
  for (auto it1 : board_map){
    for (auto it2 : board_map)
      {
        if (it1 != it2 && abs(it1.first - it2.first) == abs(it1.second - it2.second))
          {
            return false;
          }
      }
  }
  return true;
};

bool canInsert(Queens board, int col) {
  int i = 0;
  unordered_map<int, int> board_map;
  for (auto it : board)
    {
      board_map[i] = it;
      if (it == col) return false;
      else i++;
    }
  for (auto it1 : board_map){
    for (auto it2 : board_map)
      {
        if (it1 != it2 && abs(it1.first - it2.first) == abs(it1.second - it2.second))
          {
            return false;
          }
      }
  }
  return true;
};

void testCases() {
  // let's check the zero board;

  vector<int> board;
  cout << "is the zero board valid? " << isValid(board) << endl;
  board.resize(2);
  board[0] = 0;
  board[1] = 0;
  cout << "is board 1 valid? " << isValid(board) << endl;

  /*    - x - -
   *    - - - x
   *    x - - -
   *    - - x -
   */
  board.resize(4);
  board[0] = 1;
  board[1] = 3;
  board[2] = 0;
  board[3] = 2;
  cout << "is board 2 valid? " << isValid(board) << endl;
  /*    - x - - -
   *    - - - x -
   *    x - - - -
   *    - - x - -
   *    - - - - -
   * let's see where we can insert this....
   */
  for (int i = 0; i < 5; ++i){
    cout << "can i insert at col " << i << " in row 5? " << canInsert(board, i) << endl;
  }
  fmtQueens(board, 4);
};


vector<Queens> solveNQueens(int n, Queens board){
  /* - x - -
   * - - - -
   * - - - -
   * - - - -
   */
  vector<Queens> solns;
  for (int i = 0; i < n; ++i)
    {
      if (canInsert(board, i))
        {
          Queens newBoard = board;
          newBoard.push_back(i);
          vector<Queens> newSolns = solveNQueens(n, newBoard);
          solns.insert(solns.end(), begin(newSolns), end(newSolns));
        }
    }
  if (board.size() == n && isValid(board)) {
    cout << "new board" << endl;
    fmtQueens(board, n);
    cout << endl;
    solns.push_back(board);
  }
  return solns;
}

int main()
{
  Queens board;
  solveNQueens(8, board);
}