HackerRank Queens on Board problem solution

In this HackerRank Queens on Board problem solution, we have given an N * M chessboard on which some squares are blocked out. In how many ways can you place one or more queens on the board, such that, no two queens attack each other? Two queens attack each other, if one can reach the other by moving horizontally, vertically, or diagonally without passing over any blocked square. At most one queen can be placed on a square. A queen cannot be placed on a blocked square.

Problem solution in Python.

from operator import __add__
from functools import reduce


class RowState(object):
    def __init__(self, rows, count):
        self.rows = rows
        self.count = count

    def __hash__(self):
        return hash(tuple(reduce(__add__, self.rows)))

    def __eq__(self, that):
        return self.rows == that.rows


def dfs(nmap, rowState, grid, x, M, depth, cur, h):
    if depth == M:
        testState = RowState(cur[:], rowState.count)
        if testState in nmap:
            nmap[testState].count += rowState.count
        else:
            nmap[testState] = testState
    else:
        if grid[x][depth] == '#':
            cur.append((False,) * 3)
            dfs(nmap, rowState, grid, x, M, depth + 1, cur, False)
            cur.pop()
        else:
            v, d, r = False, False, False
            if rowState.rows[depth][0]:
                v = True
            if depth > 0 and rowState.rows[depth - 1][1]:
                d = True
            if depth < M - 1 and rowState.rows[depth + 1][2]:
                r = True
            if not v and not d and not r and not h:
                cur.append((True,) * 3)
                dfs(nmap, rowState, grid, x, M, depth + 1, cur, True)
                cur.pop()
            cur.append((v, d, r))
            dfs(nmap, rowState, grid, x, M, depth + 1, cur, h)
            cur.pop()

def main():
    for _ in range(int(input())):
        N, M = map(int, input().split())
        grid = []
        for line in range(N):
            grid.append(input())

        tmp_map = {}
        rs = RowState([(False, )*3 for _ in range(M)], 1)
        tmp_map[rs] = rs

        for x in range(N):
            nmap = {}
            for state in tmp_map:
                dfs(nmap, state, grid, x, M, 0, [], False)
                tmp_map = nmap
        ans = 0
        for key in tmp_map:
            ans += key.count
        print((ans - 1) % 1000000007)

if __name__ == '__main__':
    main()

{"mode":"full","isActive":false}

Problem solution in Java.

import java.io.*;
import java.math.*;
import java.text.*;
import java.util.*;
import java.util.regex.*;

public class Solution {

  static int n, m;
  static String[] board;
  static Map<String, Long> state1 = new HashMap<>(), state2 = new HashMap<>(), tmp;
  static String[] rowConfigs;
  static String clearAttackVector, clearRow;
  
  static final long mod = (long)Math.pow(10,  9) + 7;
  
  static long calcWays() {
    state1.clear();
    state2.clear();
    
    int maxMask = (int)Math.pow(2, m) - 1;
    rowConfigs = new String[maxMask + 1];
    
    for(int i = 0; i <= maxMask; i++) {
      rowConfigs[i] = createRowConfig(i);
    }
    
    clearAttackVector = "";
    clearRow = "";
    
    for(int i = 0; i < m; i++) {
      clearAttackVector += "000";
      clearRow += "0";
    }
    
    for(int row = 0; row < n; row++) {
      
      for(int ndx = 1; ndx < rowConfigs.length; ndx++) {
        if (isValidRowConfig(rowConfigs[ndx], row)) {
          String vect = generateAttackVector(clearAttackVector, rowConfigs[ndx], row);
          state2.put(vect, (state2.getOrDefault(vect, 0L) + 1) % mod);
        }
      }

     
      for(int ndx = 0; ndx < rowConfigs.length; ndx++) {
        if (isValidRowConfig(rowConfigs[ndx], row)) {
          for(String state : state1.keySet()) {
            if (compatible(rowConfigs[ndx], state)) {
              String vect = generateAttackVector(state, rowConfigs[ndx], row);
              long tot = state1.getOrDefault(state, 0L);
              tot += state2.getOrDefault(vect, 0L);
              tot %= mod;
              state2.put(vect, tot);
            }
          }
        }
      }
      
      tmp = state1;
      state1 = state2;
      state2 = tmp;
      state2.clear();      
    }
    
    
    long result = 0;
    for(String state : state1.keySet()) {
      result += state1.get(state);
      result %= mod;
    }
    
    return result;
  }  
  
  
  public static void main(String[] args) {
    Scanner s = new Scanner(System.in);
    
    int t = s.nextInt();
    
    for(int i = 0; i < t; i++) {
      n = s.nextInt();
      m = s.nextInt();
      
      board = new String[n];
      
      for(int j = 0; j < n; j++) {
        board[j] = s.next();
      }
      
      System.out.println(calcWays());
    }

    s.close();
  }
  
  
  static String createRowConfig(int mask) {
    String rowConfig = Integer.toString(mask, 2);
    
    while(rowConfig.length() < m) {
      rowConfig = "0" + rowConfig;
    }
    
    return rowConfig;
  }
  
  
  static boolean isValidRowConfig(String rowConf, int row) {
    int count = 0;
    
    for(int i = 0; i < m; i++) {
      if (board[row].charAt(i) == '#') {
        if (hasQueen(rowConf, i)) {
          return false;
        }
        
        count = 0;
        continue;
      }
      
      if (hasQueen(rowConf, i)) {
        if (++count > 1) {
          return false;
        }
      }
    }
    
    return true;
  }
  
  
  
  
  static boolean compatible(String rowConf, String attVect) {
    for(int i = 0; i < m; i++) {
      if (!hasQueen(rowConf, i)) {
        continue;
      }
      
      if (attackedFromUpperLeft(i, attVect) ||
          attackedFromAbove(i, attVect) ||
          attackedFromUpperRight(i, attVect)) {
        return false;
      }
    }
    
    return true;
  }
  
  
  static boolean isOpenSpace(int row, int col) {
    if (row < 0 || row >= n) {
      return false;
    }
    
    if (col < 0 || col >= m) {
      return false;
    }
    
    return board[row].charAt(col) != '#'; 
  }
  
  
  static boolean hasQueen(String rowConf, int col) {
    if (col < 0 || col >= m) {
      return false;
    }
    
    return rowConf.charAt(col) == '1';
  }
  
  
  static boolean attackedFromUpperLeft(int col, String attVect) {
    if (col <= 0) {
      return false;
    }
    
    return attVect.charAt(col * 3) == '1';
  }
  
  
  static boolean attackedFromAbove(int col, String attVect) {
    return attVect.charAt((col * 3) + 1) == '1';
  }
  
  
  static boolean attackedFromUpperRight(int col, String attVect) {
    if (col >= m - 1) {
      return false;
    }
    
    return attVect.charAt((col * 3) + 2) == '1';
  }
  
  
  static String generateAttackVector(String prevVect, String prevRowConf, int row) {
    String vect = "";
    
    for(int i = 0; i < m; i++) {
     
      if (!isOpenSpace(row, i - 1)) {
        vect += "0";
      }
      else if (attackedFromUpperLeft(i - 1, prevVect) || 
               hasQueen(prevRowConf, i - 1)) {
        vect += "1";
      }
      else {
        vect += "0";
      }
      
      
      if (!isOpenSpace(row, i)) {
        vect += "0";
      }
      else if (attackedFromAbove(i, prevVect) ||
               hasQueen(prevRowConf, i)) {
        vect += "1";
      }
      else {
        vect += "0";
      }
      
     
      if (!isOpenSpace(row, i + 1)) {
        vect += "0";
      }
      else if (attackedFromUpperRight(i + 1, prevVect) || 
               hasQueen(prevRowConf, i + 1)) {
        vect += "1";
      }
      else {
        vect += "0";
      }
      
    }
    
    return vect;
  }
  

}

{"mode":"full","isActive":false}

Problem solution in C++.

#include <vector>
#include <string>
#include <algorithm>
#include <iostream>
#include <unordered_map>
#include <cassert>

using namespace std;

struct Solution2
{
    typedef basic_string<unsigned char> __Board;
    typedef __Board::value_type         __Row;
    long long solve(const vector<string> & B){
        if (B.empty() || B[0].empty())
            return 0;
        
        for (size_t i = 0; i < B.size(); ++i){
            __Row row = 0;
            for (size_t j = 0; j < B[i].size(); ++j){
                if ('.' == B[i][j])
                    row |= (1 << j);
            }
            row = ~row;
            board.push_back(row);
           
            __Board p;
            genPlacements(row, p, B[i].size());
            placements.push_back(p);
        }
        bmask = (1 << B[0].size()) - 1;
        return help(0, 0, 0, 0);
    }
private:
    static void genPlacements(__Row block, __Board & ret, int M){
        for (int i = 0; i < M; ++i){
            
            __Row p1 = 1 << i;
            if (0 != (p1 & block))
                continue;
            ret.push_back(p1);
            
            for (int j = i + 2; j < M; ++j){
                __Row p2 = p1 | (1 << j);
                if (0 != (p2 & block))
                    continue;
                __Row m2 = (1 << j) - (1 << (i + 1));
                if (0 == (m2 & block))
                    continue;   
                ret.push_back(p2);
                
                for (int k = j + 2; k < M; ++k){
                    __Row p3 = p2 | (1 << k);
                    if (0 != (p3 & block))
                        continue;
                    __Row m3 = (1 << k) - (1 << (j + 1));
                    if (0 == (m3 & block))
                        continue;   //there is not enough blocks between 3 Qs
                    ret.push_back(p3);
                }
            }
        }
    }
    __Row calcMask(__Row mask, __Row blocks){
        __Row b = mask & blocks;    
        mask &= ~b;
        return (mask & bmask);  
    }
    static int hash(size_t row, __Row lmask, __Row dmask, __Row rmask){
        int r = row;
        r <<= 8;
        r += lmask;
        r <<= 8;
        r += dmask;
        r <<= 8;
        r += rmask;
        return r;
    }
    long long help(size_t row, __Row lmask, __Row dmask, __Row rmask){
        if (row >= board.size())
            return 0;
        const int h = hash(row, lmask, dmask, rmask);
        unordered_map<int, long long>::const_iterator wh = save.find(h);
        if (wh != save.end())
            return wh->second;
        const __Row blocks = board[row];
        const __Row mask = lmask | dmask | rmask | blocks;    
        long long ret = 0;
       
        lmask = calcMask(lmask, blocks);
        dmask = calcMask(dmask, blocks);
        rmask = calcMask(rmask, blocks);
        if (__Row(-1) != mask){
            
            const __Board & ps = placements[row];
            for (size_t i = 0; i < ps.size(); ++i){
                const __Row p = ps[i];
                if (0 != (mask & p))
                    continue;   
                ++ret;
                
                ret += help(row + 1, (lmask | p) << 1, dmask | p, (rmask | p) >> 1);
            }
        }
        ret += help(row + 1, lmask << 1, dmask, rmask >> 1);
        return (save[h] = ret % 1000000007);
    }
    __Board board;  
    vector<__Board> placements;
    unordered_map<int, long long> save;
    __Row bmask;    
};

typedef Solution2 Solution;

int main()
{
   
    int t;
    cin >> t;
    while (t--){
        int n, m;
        cin >> n >> m;
        vector<string> b;
        for (int i = 0; i < n; ++i){
            string line;
            cin >> line;
            b.push_back(line);
        }
        cout << Solution().solve(b) << endl;
    }
    return 0;
}

{"mode":"full","isActive":false}

Problem solution in C.

#include <assert.h>
#include <limits.h>
#include <math.h>
#include <stdbool.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define MOD 1000000007

char* readline();
char** split_string(char*);

/*
 * Complete the queensBoard function below.
 */
int* queensBoard(int t, int* n_list, int* m_list, char*** board_list) {

    int ispossible[1<<5][1<<5];
    for(int i = 0; i < 1<<5; i++){
        for(int j = 0; j < 1<<5; j++){
            ispossible[i][j] = 1;
            if((i&j) != 0){
                ispossible[i][j] = 0;
            }
            int ison = 0;
            for(int k = 0; k < 5; k++){
                if(((j>>k)&1) == 1){
                    if(ison){
                        ispossible[i][j] = 0;
                    }
                    else{
                        ison = 1;
                    }
                }
                if(((i>>k)&1) == 1){
                    ison = 0;
                }
            }
        }
    }

    int baseattackmask[5] = {7, 7<<3, 7<<6, 7<<9, 7<<12};
    int attackmask[1<<5];
    for(int i = 0; i < 1<<5; i++){
        attackmask[i] = 0;
        for(int j = 0; j < 5; j++){
            if(((i>>j)&1) == 1){
                attackmask[i] |= baseattackmask[j];
            }
        }
    }

    int baseattacktrans[15] = {-1, 1, 5, 0, 4, 8, 3, 7, 11, 6, 10, 14, 9, 13, -1};
    int attacktrans[1<<15];
    for(int i = 0; i < 1<<15; i++){
        attacktrans[i] = 0;
        for(int j = 0; j < 15; j++){
            if(((i>>j)&1) == 1 && baseattacktrans[j] >= 0){
                attacktrans[i] |= 1<<baseattacktrans[j];
            }
        }
    }

    int* toreturn = malloc(t*sizeof(int));
    for(int i = 0; i < t; i++){
        int n = n_list[i];
        int m = m_list[i];
        char** board = board_list[i];
        toreturn[i] = 0;

        int blockmask[n + 1];
        for(int j = 0; j < n; j++){
            blockmask[j] = 0;
            for(int k = 0; k < m; k++){
                blockmask[j] += (board[j][k] == '#'? 1<<k : 0);
            }
            for(int k = m; k < 5; k++){
                blockmask[j] += 1<<k;
            }
        }
        blockmask[n] = (1<<5) - 1;

        long numways[1<<15];
    
        for(int k = 0; k < 1<<15; k++){
            numways[k] = 0;
        }
    
        numways[0] = 1;

        for(int j = 0; j < n + 1; j++){
            long nextnumways[1<<15];
            for(int k = 0; k < 1<<15; k++){
                nextnumways[k] = 0;
            }
            int nextblockmask = blockmask[j];
            for(int k = 0; k < 1<<15; k++){
                if(numways[k] != 0){
                    
                    for(int l = 0; l < 1<<5; l++){
                        if(ispossible[nextblockmask][l] && ((attacktrans[k]&attackmask[l]) == 0)){
                            nextnumways[(attacktrans[k]&(~attackmask[nextblockmask]))|attackmask[l]] += numways[k];
                        }
                    }
                }
            }

            for(int k = 0; k < 1<<15; k++){
                numways[k] = nextnumways[k]%MOD;
            }
            
        }
        
        toreturn[i] = numways[0] - 1;
    }
    return toreturn;
}

int main()
{
    FILE* fptr = fopen(getenv("OUTPUT_PATH"), "w");

    char* t_endptr;
    char* t_str = readline();
    int t = strtol(t_str, &t_endptr, 10);

    if (t_endptr == t_str || *t_endptr != '\0') { exit(EXIT_FAILURE); }

    int* n_list = malloc(t*sizeof(int));
    int* m_list = malloc(t*sizeof(int));
    char*** board_list = malloc(t*sizeof(char**));

    for (int t_itr = 0; t_itr < t; t_itr++) {
        char** nm = split_string(readline());

        char* n_endptr;
        char* n_str = nm[0];
        int n = strtol(n_str, &n_endptr, 10);

        if (n_endptr == n_str || *n_endptr != '\0') { exit(EXIT_FAILURE); }

        char* m_endptr;
        char* m_str = nm[1];
        int m = strtol(m_str, &m_endptr, 10);

        if (m_endptr == m_str || *m_endptr != '\0') { exit(EXIT_FAILURE); }

        char** board = malloc(n * sizeof(char*));

        for (int board_itr = 0; board_itr < n; board_itr++) {
            char* board_item = readline();

            *(board + board_itr) = board_item;
        }

        n_list[t_itr] = n;
        m_list[t_itr] = m;
        board_list[t_itr] = board;
    }
    int* result = queensBoard(t, n_list, m_list, board_list);
    for(int a = 0; a < t; a++){
        fprintf(fptr, "%d\n", result[a]);
    }

    fclose(fptr);

    return 0;
}

char* readline() {
    size_t alloc_length = 1024;
    size_t data_length = 0;
    char* data = malloc(alloc_length);

    while (true) {
        char* cursor = data + data_length;
        char* line = fgets(cursor, alloc_length - data_length, stdin);

        if (!line) { break; }

        data_length += strlen(cursor);

        if (data_length < alloc_length - 1 || data[data_length - 1] == '\n') { break; }

        size_t new_length = alloc_length << 1;
        data = realloc(data, new_length);

        if (!data) { break; }

        alloc_length = new_length;
    }

    if (data[data_length - 1] == '\n') {
        data[data_length - 1] = '\0';
    }

    data = realloc(data, data_length);

    return data;
}

char** split_string(char* str) {
    char** splits = NULL;
    char* token = strtok(str, " ");

    int spaces = 0;

    while (token) {
        splits = realloc(splits, sizeof(char*) * ++spaces);
        if (!splits) {
            return splits;
        }

        splits[spaces - 1] = token;

        token = strtok(NULL, " ");
    }

    return splits;
}

{"mode":"full","isActive":false}