Queens on Board
Problem Statement :
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 109+7.
Solution :
Solution in C :
In C++ :
#include<stdio.h>
#include<string.h>
#define MOD 1000000007
int n,m,bit[1 << 10] ;
char g[52][52] ;
int memo2[1 << 15] ;
int spread(int mask)
{
if(memo2[mask] != -1) return memo2[mask] ;
int nmask = 0 ;
for(int i = 0;i < m;i++)
{
if(mask & 1 << 3 * i) if(i > 0) nmask |= 1 << 3 * i - 3 ;
if(mask & 1 << 3 * i + 1) nmask |= 1 << 3 * i + 1 ;
if(mask & 1 << 3 * i + 2) if(i + 1 < m) nmask |= 1 << 3 * i + 5 ;
}
return memo2[mask] = nmask ;
}
int good[50][1 << 8],szg[50],block[50] ;
int memo[50][1 << 15] ;
int solve(int x,int mask)
{
if(x == n) return 1 ;
mask &= ~block[x] ;
if(memo[x][mask] != -1) return memo[x][mask] ;
int ret = 0 ;
for(int i = 0;i < szg[x];i++) if(!(good[x][i] & mask))
{
int cret = solve(x + 1,spread(good[x][i] | mask)) ;
ret += cret ;
if(ret >= MOD) ret -= MOD ;
}
return memo[x][mask] = ret ;
}
int solve()
{
for(int i = 0;i < n;i++)
{
block[i] = 0 ;
int cmask = 0 ;
for(int j = 0;j < m;j++) if(g[i][j] == '#')
{
cmask |= 1 << j ;
block[i] |= 7 << 3 * j ;
}
szg[i] = 0 ;
for(int j = 0;j < 1 << m;j++) if((j & cmask) == 0)
{
bool valid = true ;
for(int k = 0;k < m;k++) if(j & 1 << k)
for(int kk = k + 1;kk < m && g[i][kk] != '#';kk++)
if(j & 1 << kk)
valid = false ;
if(!valid) continue ;
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]++ ;
}
}
memset(memo,255,sizeof memo) ;
memset(memo2,255,sizeof memo2) ;
int ret = solve(0,0) ;
return ret ;
}
int main()
{
for(int i = 1;i < 1 << 10;i++) bit[i] = bit[i >> 1] + (i & 1) ;
int runs ;
scanf("%d",&runs) ;
while(runs--)
{
scanf("%d%d",&n,&m) ;
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 ;
}
In Java :
import java.io.*;
import java.util.*;
import java.text.*;
import java.math.*;
import java.util.regex.*;
class Solution {
static int NS = 50;
static int MS = 5;
static int K = 32;
static int[][][][]s = new int[NS][K][K][K];
static int AK;
static int[][] mp= new int[NS][MS];
static int n;
static int m;
static int dp(int c, int b1, int b2, int b3) {
if (c == n) return 1;
if (s[c][b1][b2][b3] >= 0) return s[c][b1][b2][b3];
/*
System.out.print(c);System.out.print(' ');
System.out.print(b1);System.out.print(' ');
System.out.print(b2);System.out.print(' ');
System.out.print(b3);System.out.print(' ');
System.out.println();
*/
int sum = 0;
for (int i = 0; i < AK; i++) {
if (check(c,i,b1,b2,b3)){
int[] mask = mask(c,i,b1,b2,b3);
/*
System.out.print(c);
System.out.println(i);
*/
sum = (sum+dp(c+1, mask[0],mask[1],mask[2]))%1000000007;
}
}
s[c][b1][b2][b3] = sum;
return sum;
}
static boolean check(int c, int i, int b1, int b2, int b3) {
int[] loc = {1,2,4,8,16};
boolean selfblock = false;
//check other block
for (int li = 0; li < m; li++) {
if ((i&loc[li]) != 0) {
if (mp[c][li] == 0) return false;
if (selfblock == true) return false;
if ((b1&loc[li]) !=0 || (b2&loc[li]) !=0|| (b3&loc[li]) !=0) return false;
selfblock = true;
}
if (mp[c][li] == 0) selfblock = false;
}
return true;
}
static int[] mask(int c, int i, int b1, int b2, int b3){
int[] loc = {1,2,4,8,16};
int[] mask = new int[3];
mask[0] = b1|i;
mask[1] = ((b2 << 1) % K) | ((i << 1) % K);
mask[2] = (b3 >> 1) | (i >> 1);
for (int li = 0; li < m; li++){
if(mp[c][li] == 0) {
mask[0] = mask[0] & (~loc[li]);
mask[1] = mask[1] & (~(loc[li] << 1)%K);
mask[2] = mask[2] & (~(loc[li] >> 1));
}
}
return mask;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int TN = in.nextInt();
for (int ti = 0; ti < TN; ti++) {
n = in.nextInt();
m = in.nextInt();
String str[] = new String[n];
for(int i=0; i<n; i++)
str[i] = in.next();
for (int i = 0; i < n; i++)
for (int j = 0; j < m; j++) {
mp[i][j] = 1;
if (str[i].charAt(j) == '#')
mp[i][j] = 0;
}
for (int i1 = 0; i1 < n; i1++)
for (int i2 = 0; i2 < K; i2++)
for (int i3 = 0; i3 < K; i3++)
for (int i4 = 0; i4 < K; i4++)
s[i1][i2][i3][i4] = -1;
AK = 1;
for (int i =0; i< m; i++)
AK = AK *2;
int r = dp(0,0,0,0);
System.out.println((r+1000000007-1) % 1000000007);
}
}
}
In C:
#include <stdio.h>
#define MAX_N 50
#define MAX_M 5
#define MAX_CACHE 1000
typedef struct cache_data cache_data;
struct cache_data {
char b[MAX_N * MAX_M + 1];
int s, v; /* safe cells, value */
cache_data *next;
};
cache_data cache[MAX_CACHE];
int solv(char *b, int n, int m) {
}
void init_cache() {
int i;
for (i = 0; i < MAX_CACHE; i++) {
cache[i].next = NULL;
}
}
void clear_cache() {
int i;
cache_data *p, *next;
for (i = 0; i < MAX_CACHE; i++) {
for (p = cache[i].next; p; p = next) {
next = p->next;
free(p);
}
cache[i].next = NULL;
}
}
unsigned int calc_cache_key(char *b) {
unsigned int k = 0;
char *p = b;
for (; *p; p++) {
k *= 23;
if (*p == '.') k += 1;
else k += 2;
}
return k % MAX_CACHE;
}
int get_cache(char *b, int s) {
cache_data *p = cache[calc_cache_key(b)].next;
for (; p; p = p->next) {
if (s == p->s && strcmp(b, p->b) == 0) return p->v;
}
return -1;
}
int main() {
int t, n, m, i, j;
char b[MAX_N * MAX_M + 1];
scanf("%d", &t);
init_cache();
for (i = 0; i < t; i++) {
scanf("%d %d", &n, &m);
for (j = 0; j < n; j++) {
scanf("%s\n", b + j * m);
}
printf("%d\n", solv(b, n, m) % 1000000007);
clear_cache();
}
return 0;
}
In Python3 :
from __future__ import print_function
import collections
QUEEN = 'q'
BLOCK = '#'
SigBlock = collections.namedtuple('SigBlock', 'left middle right')
ROW_QUEENS = {
'.....': [[], [0], [1], [2], [3], [4]],
'#....': [[], [1], [2], [3], [4]],
'.#...': [[], [0], [2], [3], [4], [0, 2], [0, 3], [0, 4]],
'..#..': [[], [0], [1], [3], [4], [0, 3], [0, 4], [1, 3], [1, 4]],
'...#.': [[], [0], [1], [2], [4], [0, 4], [1, 4], [2, 4]],
'....#': [[], [0], [1], [2], [3]],
'##...': [[], [2], [3], [4]],
'#.#..': [[], [1], [3], [4], [1, 3], [1, 4]],
'#..#.': [[], [1], [2], [4], [1, 4], [2, 4]],
'#...#': [[], [1], [2], [3]],
'.##..': [[], [0], [3], [4], [0, 3], [0, 4]],
'.#.#.': [[], [0], [2], [4], [0, 2], [0, 4], [2, 4], [0, 2, 4]],
'.#..#': [[], [0], [2], [3], [0, 2], [0, 3]],
'..##.': [[], [0], [1], [4], [0, 4], [1, 4]],
'..#.#': [[], [0], [1], [3], [0, 3], [1, 3]],
'...##': [[], [0], [1], [2]],
'###..': [[], [3], [4]],
'##.#.': [[], [2], [4], [2, 4]],
'##..#': [[], [2], [3]],
'#.##.': [[], [1], [4], [1, 4]],
'#.#.#': [[], [1], [3], [1, 3]],
'#..##': [[], [1], [2]],
'.###.': [[], [0], [4], [0, 4]],
'.##.#': [[], [0], [3], [0, 3]],
'.#.##': [[], [0], [2], [0, 2]],
'..###': [[], [0], [1]],
'####.': [[], [4]],
'###.#': [[], [3]],
'##.##': [[], [2]],
'#.###': [[], [1]],
'.####': [[], [0]],
'#####': [[]],
'....': [[], [0], [1], [2], [3]],
'#...': [[], [1], [2], [3]],
'.#..': [[], [0], [2], [3], [0, 2], [0, 3]],
'..#.': [[], [0], [1], [3], [0, 3], [1, 3]],
'...#': [[], [0], [1], [2]],
'##..': [[], [2], [3]],
'#.#.': [[], [1], [3], [1, 3]],
'#..#': [[], [1], [2]],
'.##.': [[], [0], [3], [0, 3]],
'.#.#': [[], [0], [2], [0, 2]],
'..##': [[], [0], [1]],
'###.': [[], [3]],
'##.#': [[], [2]],
'#.##': [[], [1]],
'.###': [[], [0]],
'####': [[]],
'...': [[], [0], [1], [2]],
'#..': [[], [1], [2]],
'.#.': [[], [0], [2], [0, 2]],
'..#': [[], [0], [1]],
'##.': [[], [2]],
'#.#': [[], [1]],
'.##': [[], [0]],
'###': [[]],
'..': [[], [0], [1]],
'#.': [[], [1]],
'.#': [[], [0]],
'##': [[]],
'.': [[], [0]],
'#': [[]],
}
def sig_str(sig):
return ''.join(
'./'[s.left] + '.|'[s.middle] + '.\\'[s.right]
for s in sig
)
def print_sig_counts(sig_counts):
for sig, count in sig_counts.items():
print('\t{0}: {1}'.format(sig_str(sig), count))
QUEEN_SIG = SigBlock(1, 1, 1)
def transform(sig, row):
m = len(sig)
def new_sig():
for i in range(m):
if row[i] == BLOCK:
yield SigBlock(0, 0, 0)
else:
middle = sig[i].middle
left = sig[i+1].left if i < m-1 else 0
right = sig[i-1].right if i > 0 else 0
yield SigBlock(left, middle, right)
base = list(new_sig())
for queen_pos in ROW_QUEENS[row]:
copy = list(base)
for i in queen_pos:
if any(base[i]): break
copy[i] = QUEEN_SIG
else:
yield tuple(copy)
def base_sig(m):
return tuple([SigBlock(0, 0, 0)] * m)
def count_ways(m, rows):
sig_counts = {base_sig(m): 1}
for row in rows:
transformed = collections.defaultdict(int)
for sig, count in sig_counts.items():
for new_sig in transform(sig, row):
transformed[new_sig] += count
sig_counts = transformed
#print('row:', repr(row))
#print_sig_counts(sig_counts)
return sum(sig_counts.values()) - 1 # no queens doesn't count
def read_input_boards():
import sys
stdin = iter(sys.stdin)
line = lambda: next(stdin).strip()
t = int(line())
for _ in range(t):
n, m = [int(i) for i in line().split()]
rows = [line() for _ in range(n)]
yield m, rows
if __name__ == '__main__':
for m, rows in read_input_boards():
print(count_ways(m, rows) % (10 ** 9 + 7))
View More Similar Problems
Find Merge Point of Two Lists
This challenge is part of a tutorial track by MyCodeSchool Given pointers to the head nodes of 2 linked lists that merge together at some point, find the node where the two lists merge. The merge point is where both lists point to the same node, i.e. they reference the same memory location. It is guaranteed that the two head nodes will be different, and neither will be NULL. If the lists share
View Solution →Inserting a Node Into a Sorted Doubly Linked List
Given a reference to the head of a doubly-linked list and an integer ,data , create a new DoublyLinkedListNode object having data value data and insert it at the proper location to maintain the sort. Example head refers to the list 1 <-> 2 <-> 4 - > NULL. data = 3 Return a reference to the new list: 1 <-> 2 <-> 4 - > NULL , Function Description Complete the sortedInsert function
View Solution →Reverse a doubly linked list
This challenge is part of a tutorial track by MyCodeSchool Given the pointer to the head node of a doubly linked list, reverse the order of the nodes in place. That is, change the next and prev pointers of the nodes so that the direction of the list is reversed. Return a reference to the head node of the reversed list. Note: The head node might be NULL to indicate that the list is empty.
View Solution →Tree: Preorder Traversal
Complete the preorder function in the editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's preorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the preOrder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the tree's
View Solution →Tree: Postorder Traversal
Complete the postorder function in the editor below. It received 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's postorder traversal as a single line of space-separated values. Input Format Our test code passes the root node of a binary tree to the postorder function. Constraints 1 <= Nodes in the tree <= 500 Output Format Print the
View Solution →Tree: Inorder Traversal
In this challenge, you are required to implement inorder traversal of a tree. Complete the inorder function in your editor below, which has 1 parameter: a pointer to the root of a binary tree. It must print the values in the tree's inorder traversal as a single line of space-separated values. Input Format Our hidden tester code passes the root node of a binary tree to your $inOrder* func
View Solution →
