HackerRank Queens on Board Problem Solution

In this post, we will solve HackerRank Queens on Board Problem Solution.

Queens on Board

You have 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.

Input Format

The first line contains the number of test cases T. T test cases follow. Each test case contains integers N and M on the first line. The following N lines contain M characters each, and represent a board. A ‘#’ represents a blocked square and a ‘.’ represents an unblocked square.

Constraints

1 <= T <= 100
1 <= N <= 50
1 <= M <= 5

Output Format

Output T lines containing the required answer for each test case. As the answers can be really large, output them modulo 10⁹+7.

Sample Input

4  
3 3  
...  
...  
...  
3 3  
.#.  
.#.  
...  
2 4  
.#..  
....  
1 1  
#

Sample Output

HackerRank Queens on Board Problem Solution

Queens on Board C Solution

#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;
}

Queens on Board C++ Solution

#include <cstdio>
#include <cstring>
#define MOD 1000000007

// Solution uses memoization of a brute-force solving of all permutations.

// Number of rows and columns.
int n, m;
// Character representation of the grid.
char g[50][5];
// Valid configurations for row i (up to 2**5 of them).
int good[50][1 << 5];
// Number of valid configurations in row i.
int szg[50];
// Array of N bitmasks containing 111 for each M.
int block[50];
// Number of solutions for a given row and bitmask.
int memo[50][1 << 15];
// The next bitmask, given a particular bitmask.
int memo2[1 << 15];

// Get the next bitmask with queen attack vectors accounted for.
int spread(int mask)
{
  // Solutions been found before, use it.
  if (memo2[mask] != -1) return memo2[mask];

  int nmask = 0;
  // For each square
  for (int i = 0; i < m; i++) {
    // If a left-angling attack vector exists and we're not at the left edge,
    // extend it into the left-diagonal square.
    if (mask & 1 << 3 * i && i > 0) {
      nmask |= 1 << 3 * i - 3;
    }
    // If a vertical attack vector exists, extend it into the square below.
    if (mask & 1 << 3 * i + 1) {
      nmask |= 1 << 3 * i + 1;
    }
    // If a right-angling attack vector exists and we're not at the right edge,
    // extend it into the right-diagonal square.
    if (mask & 1 << 3 * i + 2 && i + 1 < m) {
      nmask |= 1 << 3 * i + 5;
    }
  }
  return memo2[mask] = nmask;
}

// Solve for row x, with a mask for squares that are blocked by earlier queens.
int solve (int x, int mask)
{
  // We've reached the end of a solution, so return.
  if (x == n) return 1;

  // Adjust the mask for squares that are already blocked.
  mask &= ~block[x];
  // If we've already solved this, return the result.
  if (memo[x][mask] != -1) return memo[x][mask];

  // If not, count solutions.
  int ret = 0;
  // For each configuration of this row
  for (int i = 0; i < szg[x]; i++) {
    // If we haven't tried all configurations yet
    if (!(good[x][i] & mask)) {
      // Try the next row, with rows blocked by queens masked out.
      ret += solve(x + 1, spread(good[x][i] | mask));
      // Don't let the number get too big.
      if(ret >= MOD) ret -= MOD;
    }
  }
  return memo[x][mask] = ret;
}

int solve()
{
  // For each row in N
  for (int i = 0; i < n; i++) {
    block[i] = 0;
    int cmask = 0;
    for (int j = 0; j < m; j++) {
      if (g[i][j] == '#') {
        // Create bitmask for #, like 01001
        cmask |= 1 << j;
        // Create bitmask with 111111111111111 (for M==5)
        block[i] |= 7 << 3 * j;
      }
    }

    szg[i] = 0;
    // For each 2**M permutations of queens on this row
    for (int j = 0; j < 1 << m; j++) {
      // If the queen is not on a #
      if ((j & cmask) == 0) {
        bool valid = true;
        // For each column in M
        for (int k = 0; k < m; k++) {
          // If a queen is in that column, and another queen is on the same row
          // before another #, then that position isn't valid.
          if (j & 1 << k) {
            for (int kk = k + 1; kk < m && g[i][kk] != '#'; kk++) {
              if (j & 1 << kk) {
                valid = false;
              }
            }
          }
        }
        if (!valid) continue;

        // If this is a valid configuration of queens for this row, create a
        // bitmask with 111 where a queen is. Add it to the good matrix at row i
        // and increment the size of that row (szg).
        int sp = 0;
        for (int k = 0; k < m; k++) {
          if (j & 1 << k) {
            sp |= 7 << 3 * k;
          }
        }
        good[i][szg[i]] = sp;
        szg[i]++;
      }
    }
  }

  // Initialize memoization tables to -1 for each entry.
  memset(memo,255,sizeof memo);
  memset(memo2,255,sizeof memo2);
  // Solve recursively.
  return solve(0,0);
}

int main()
{
  int runs;
  scanf("%d",&runs);
  while (runs--) {
    scanf("%d%d",&n,&m);
    // Initialize board.
    for (int i = 0;i < n;i++) scanf("%s",g[i]);
    int ret = solve();
    ret = (ret - 1 + MOD) % MOD;
    printf("%d\n",ret);
  }
  return 0;
}

Queens on Board C Sharp Solution

using System;
using System.Collections.Generic;
using System.IO;
class Solution {
    const int MOD = 1000000007;
    static void Main(String[] args) {
        int _tc_ = int.Parse(Console.ReadLine());
        while (_tc_-- > 0) {
            var tmp = Console.ReadLine().Trim().Split(' ');
            int n = int.Parse(tmp[0]);
            int m = int.Parse(tmp[1]);
            bool[,] map = new bool[n, m];
            int[] badmasks = new int[n];
            for (int i = 0; i < n; i++) {
                var _t = Console.ReadLine();
                for (int j = 0; j < m; j++) {
                    if (_t[j] == '.') continue;
                    map[i, j] = true;
                    badmasks[i] = setBitOn(badmasks[i], j);
                }
                badmasks[i] = ~badmasks[i];
            }

            int[] board = new int[n];
            Dictionary<long, long>[] cache = new Dictionary<long, long>[n];
            for (int i = 0; i < n; i++) cache[i] = new Dictionary<long, long>();


            long ans = longLiveTheQueen(0, 0, n, m, map, 0, false, badmasks, board, cache);
            Console.WriteLine(ans);
        }
    }

    static long longLiveTheQueen(int x, int y, int n, int m, bool[,] map, 
                                 int mask, bool mv, int[] badmasks, int[] board, Dictionary<long, long>[] cache) {

        if (x == n) return 0;
        long ans = 0;
        long key = mask;
        int z = x;
        for (int i = 0; i < m; i++, z--) {
            key = key * 100;
            if (z >= 0) { key += board[z]; }
        }

        if (cache[x].ContainsKey(key)) return cache[x][key];

        for (int i = y; i < m; i++) {
            if (map[x, i]) { mv = false; continue; }
            if (mv || isOn(mask, i)) continue;

            bool bad = false;
            int u = x - 1, v = i - 1;
            for (int j = 0; j < m && u >= 0 && v >= 0; j++, u--, v--) {
                if (map[u, v]) {
                    bad = false; break;
                } else if (isOn(board[u], v)) {
                    bad = true; break;
                }
            }
            if (bad) continue;

            u = x - 1; v = i + 1;
            for (int j = 0; j < m && u >= 0 && v < m; j++, u--, v++) {
                if (map[u, v]) {
                    bad = false; break;
                } else if (isOn(board[u], v)) {
                    bad = true; break;
                }
            }
            if (bad) continue;

            int res = board[x];

            board[x] = setBitOn(board[x], i);
            ans += 1 + longLiveTheQueen(x, i + 1, n, m, map,
                                        badmasks[x] & setBitOn(mask, i), true, badmasks, board, cache);
            board[x] = res;

        }

        ans += longLiveTheQueen(x + 1, 0, n, m, map,
                                badmasks[x] & mask, false, badmasks, board, cache);
        ans %= MOD;

        cache[x][key] = ans;
        return ans;
    }

    public static int setBitOn(int a, int i) { return a |= (1 << i); }

    public static bool isOn(int a, int i) { return ((a >> i) & 1) == 1; }
}

Queens on Board Java Solution

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;
  }
  

}

Queens on Board Python Solution

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()

c C# C++ HackerRank Solutions java python C cpp CSharp Hackerrank Solutions java python