Rooks on a rampage def safe_squares_rooks(n, rooks): A generalized n-by-n chessboard has been invaded by a parliament of rooks, each rook represented as a two-tuple (row, column) of the row and the column of the square that the rook is in. Since we are again computer programmers instead of chess players and other normal folks, our rows and columns are numbered from 0 to n - 1. A chess rook covers all squares that are in the same row or in the same column. Given the board size n and the list of rooks on that board, count the number of empty squares that are safe, that is, are not covered by any rook. To achieve this in reasonable time and memory, you should count separately how many rows and columns on the board are safe from any rook. Because permuting the rows and columns does not change the answer to this question, you can imagine all these safe rows and columns to have been permuted to form an empty rectangle at the top left corner of the board. The area of that safe rectangle is then obviously the product of its known width and height. n rooks Expected result 10 [] 100 4 [(2, 3), (0, 1)] 4 8 [(1, 1), (3, 5), (7, 0), (7, 6)] 20 2 [(1, 1)] 1 6 [(r, r) for r in range(6)] 0 100 [(r, (r*(r-1))%100) for r in range(0, 100, 2)] 3900 106 [(r, r) for r in range(106)] 0

Database System Concepts

7th Edition

ISBN:9780078022159

Author:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Publisher:Abraham Silberschatz Professor, Henry F. Korth, S. Sudarshan

Chapter1: Introduction

Section: Chapter Questions

Problem 1PE

See similar textbooks

Related questions

Question

Rooks on a rampage

def safe_squares_rooks(n, rooks):

A generalized n-by-n chessboard has been invaded by a parliament of rooks, each rook represented as a two-tuple (row, column) of the row and the column of the square that the rook

is in. Since we are again computer programmers instead of chess players and other normal folks, our rows and columns are numbered from 0 to n - 1. A chess rook covers all squares that are in the same row or in the same column. Given the board size n and the list of rooks on that board, count the number of empty squares that are safe, that is, are not covered by any rook.

To achieve this in reasonable time and memory, you should count separately how many rows and columns on the board are safe from any rook. Because permuting the rows and columns does not change the answer to this question, you can imagine all these safe rows and columns to have been permuted to form an empty rectangle at the top left corner of the board. The area of that safe rectangle is then obviously the product of its known width and height.

n	rooks	Expected result
10	[]	100
4	[(2, 3), (0, 1)]	4
8	[(1, 1), (3, 5), (7, 0), (7, 6)]	20
2	[(1, 1)]	1
6	[(r, r) for r in range(6)]	0
100	[(r, (r*(r-1))%100) for r in range(0, 100, 2)]	3900
10**6	[(r, r) for r in range(10**6)]	0

Expert Solution

Trending now

This is a popular solution!

Step by step

Solved in 3 steps

SEE SOLUTION Check out a sample Q&A here

Knowledge Booster

Learn more about

Need a deep-dive on the concept behind this application? Look no further. Learn more about this topic, computer-science and related others by exploring similar questions and additional content below.

Similar questions