Jovian
⭐️
Sign In
Learn data science and machine learning by building real-world projects on Jovian

Queen's Attack II

This is the final project from the course "Data Structures and Algorithms in Python", from Jovian.

How to run the code and save your work

The recommended way to run this notebook is to click the "Run" button at the top of this page, and select "Run on Binder". This will run the notebook on mybinder.org, a free online service for running Jupyter notebooks.

This tutorial is an executable Jupyter notebook. You can run this tutorial and experiment with the code examples in a couple of ways: using free online resources (recommended) or on your computer.

Option 1: Running using free online resources (1-click, recommended)

The easiest way to start executing the code is to click the Run button at the top of this page and select Run on Binder. You can also select "Run on Colab" or "Run on Kaggle", but you'll need to create an account on Google Colab or Kaggle to use these platforms.

Option 2: Running on your computer locally

To run the code on your computer locally, you'll need to set up Python, download the notebook and install the required libraries. We recommend using the Conda distribution of Python. Click the Run button at the top of this page, select the Run Locally option, and follow the instructions.

Saving your work

Before staring the assignment, let's save a snapshot of the assignment to your Jovian profile, so that you can access it later, and continue your work.

In [1]:
project_name = '11-course-project-queen'
In [2]:
!pip install jovian --upgrade
Requirement already up-to-date: jovian in /opt/conda/lib/python3.8/site-packages (0.2.33) Requirement already satisfied, skipping upgrade: requests in /opt/conda/lib/python3.8/site-packages (from jovian) (2.24.0) Requirement already satisfied, skipping upgrade: click in /opt/conda/lib/python3.8/site-packages (from jovian) (7.1.2) Requirement already satisfied, skipping upgrade: pyyaml in /opt/conda/lib/python3.8/site-packages (from jovian) (5.3.1) Requirement already satisfied, skipping upgrade: uuid in /opt/conda/lib/python3.8/site-packages (from jovian) (1.30) Requirement already satisfied, skipping upgrade: chardet<4,>=3.0.2 in /opt/conda/lib/python3.8/site-packages (from requests->jovian) (3.0.4) Requirement already satisfied, skipping upgrade: urllib3!=1.25.0,!=1.25.1,<1.26,>=1.21.1 in /opt/conda/lib/python3.8/site-packages (from requests->jovian) (1.25.10) Requirement already satisfied, skipping upgrade: certifi>=2017.4.17 in /opt/conda/lib/python3.8/site-packages (from requests->jovian) (2020.6.20) Requirement already satisfied, skipping upgrade: idna<3,>=2.5 in /opt/conda/lib/python3.8/site-packages (from requests->jovian) (2.10)
In [3]:
import jovian
In [4]:
jovian.commit(project=project_name)
[jovian] Attempting to save notebook.. [jovian] Updating notebook "marcelo-freri/11-course-project-queen" on https://jovian.ai/ [jovian] Uploading notebook.. [jovian] Capturing environment.. [jovian] Committed successfully! https://jovian.ai/marcelo-freri/11-course-project-queen

Problem Statement

You will be given a square chess board with one queen and a number of obstacles placed on it. Determine how many squares the queen can attack.

A queen is standing on an n x n chessboard. The chess board's rows are numbered from 1 to n, going from bottom to top. Its columns are numbered from 1 to n, going from left to right. Each square is referenced by a tuple, (r,c), describing the row, r, and column, c, where the square is located.

The queen is standing at position (\(r_q,c_q\)). In a single move, she can attack any square in any of the eight directions (left, right, up, down, and the four diagonals). In the diagram below, the green circles denote all the cells the queen can attack from (4,4):

There are obstacles on the chessboard, each preventing the queen from attacking any square beyond it on that path. For example, an obstacle at location (3,5) in the diagram above prevents the queen from attacking cells (3,5), (2,6), and (1,7):

Given the queen's position and the locations of all the obstacles, find and print the number of squares the queen can attack from her position at \((r_q,c_q)\). In the board above, there are 24 such squares.

Source: https://www.hackerrank.com/challenges/queens-attack-2/problem

Solution

1. Identify the input & output formats.

While this problem is stated clearly enough, it's always useful to try and express in your own words, in a way that makes it most clear.


Problem

Given a chessboard of r x c boxes, a queen in position rq, cq, and a list of obstacles coordinates, find the number of boxes that the queen can attack.


Input

Rows and columns of the chessboard:

r = 8
c = 8

Queen's position:

rq = 4
cq = 4

List of obstacles:

obstacles = [(3, 5)]

Output

The number of boxes that the queen can attack:

movements = 24

Based on the above, we can now create a signature of our function:

In [5]:
def queenAttack(r, c, rq, cq, obstacles):
    pass

2. Example inputs & outputs.

Our function should be able to handle any set of valid inputs we pass into it. Here's a list of some possible variations we might encounter:

  1. The given case
  2. A chessboard with no obstacles
  3. A chessboard with three or more obstacles
  4. A chessboard of 2 by 2
  5. A queen surrounded by obstacles
  6. A very big chessboard with no obstacles
  7. A normal size chessboard with a lot of obstacles

We'll express our test cases as dictionaries, to test them easily. Each dictionary will contain 2 keys: input (a dictionary itself containing one key for each argument to the function and output (the expected result from the function).

In [6]:
test = {
    'input': {
        'r': 8,
        'c': 8,
        'rq': 4,
        'cq': 4,
        'obstacles': [(3, 5)]
    },
    'output': 24
}

We can test the function by passing the input to it directly or by using the evaluate_test_case function from jovian.

In [7]:
from jovian.pythondsa import evaluate_test_case
In [8]:
evaluate_test_case(queenAttack, test)
Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 4, 'obstacles': [(3, 5)]} Expected Output: 24 Actual Output: None Execution Time: 0.006 ms Test Result: FAILED
Out[8]:
(None, False, 0.006)

Create one test case for each of the scenarios listed above. We'll store our test cases in an array called tests.

In [9]:
tests = []
In [10]:
# The original statement
tests.append(test)
In [11]:
# A chessboard with no obstacles
tests.append({
    'input': {
        'r': 8,
        'c': 8,
        'rq': 4,
        'cq': 4,
        'obstacles': []
    },
    'output': 27
})
# A chessboard with three or more obstacles
tests.append({
    'input': {
        'r': 8,
        'c': 8,
        'rq': 4,
        'cq': 3,
        'obstacles': [(4,2), (2,3), (5,5)]
    },
    'output': 21
})
# A chessboard of 2 by 2
tests.append({
    'input': {
        'r': 2,
        'c': 2,
        'rq': 2,
        'cq': 1,
        'obstacles': [(1, 2)]
    },
    'output': 2
})
# A queen surrounded by obstacles
tests.append({
    'input': {
        'r': 2,
        'c': 2,
        'rq': 1,
        'cq': 1,
        'obstacles': [(1, 2), (2,1), (2,2)]
    },
    'output': 0
})
# A very big chessboard with no obstcles
tests.append({
    'input': {
        'r': 1000,
        'c': 1000,
        'rq': 500,
        'cq': 500,
        'obstacles': []
    },
    'output': 3995
})
# A normal size chessboard with a lot of obstacles
tests.append({
    'input': {
        'r': 8,
        'c': 8,
        'rq': 4,
        'cq': 4,
        'obstacles': [(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (1,7), (1,8),
                     (2,1), (3,1), (4,1), (5,1), (6,1), (7,1), (8,1), 
                     (2,8), (3,8), (4,8), (5,8), (6,8), (7,8), (8,8), 
                     (8,2), (8,3), (8,4), (8,5), (8,6), (8,7),
                     (2,2), (2,3), (2,4), (2,5), (2,6), (2,7),
                     (3,2), (4,2), (5,2), (6,2), (7,2), 
                     (3,7), (4,7), (5,7), (6,7), (7,7), 
                     (7,3), (7,4), (7,5), (7,6),
                     (3,3), (3,4), (3,5), (3,6),
                     (4,3), (5,3), (6,3),
                     (4,6), (5,6), (6,6),
                     (6,4), (6,5)]
    },
    'output': 3
})

Evaluate the function against all the test cases together using the evaluate_test_cases (plural) function from jovian.

In [12]:
from jovian.pythondsa import evaluate_test_cases
In [13]:
evaluate_test_cases(queenAttack, tests)
TEST CASE #0 Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 4, 'obstacles': [(3, 5)]} Expected Output: 24 Actual Output: None Execution Time: 0.005 ms Test Result: FAILED TEST CASE #1 Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 4, 'obstacles': []} Expected Output: 27 Actual Output: None Execution Time: 0.003 ms Test Result: FAILED TEST CASE #2 Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 3, 'obstacles': [(4, 2), (2, 3), (5, 5)]} Expected Output: 21 Actual Output: None Execution Time: 0.003 ms Test Result: FAILED TEST CASE #3 Input: {'r': 2, 'c': 2, 'rq': 2, 'cq': 1, 'obstacles': [(1, 2)]} Expected Output: 2 Actual Output: None Execution Time: 0.003 ms Test Result: FAILED TEST CASE #4 Input: {'r': 2, 'c': 2, 'rq': 1, 'cq': 1, 'obstacles': [(1, 2), (2, 1), (2, 2)]} Expected Output: 0 Actual Output: None Execution Time: 0.003 ms Test Result: FAILED TEST CASE #5 Input: {'r': 1000, 'c': 1000, 'rq': 500, 'cq': 500, 'obstacles': []} Expected Output: 3995 Actual Output: None Execution Time: 0.003 ms Test Result: FAILED TEST CASE #6 Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 4, 'obstacles': [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1,... Expected Output: 3 Actual Output: None Execution Time: 0.002 ms Test Result: FAILED SUMMARY TOTAL: 7, PASSED: 0, FAILED: 7
Out[13]:
[(None, False, 0.005),
 (None, False, 0.003),
 (None, False, 0.003),
 (None, False, 0.003),
 (None, False, 0.003),
 (None, False, 0.003),
 (None, False, 0.002)]

Verify that all the test cases were evaluated. We expect them all to fail, since we haven't implemented the function yet.

3. A correct solution for the problem in plain English.

Our first goal should always be to come up with a correct solution to the problem, which may not necessarily be the most efficient solution.

Go recursively in the eight directions that the queen can move, counting the boxes, until an obstacle or the border of the chessboard is found.

4. Recursive solution

In [14]:
def queenAttack1(r, c, rq, cq, obstacles):
    output = 0

    def queenAttackRecursive(r, c, rq, cq, obstacles, direction):
        if (rq, cq) in obstacles:
            return -1
        if direction == 'up':
            if rq >= r:
                return 0
            else:
                return 1 + queenAttackRecursive(r, c, rq+1, cq, obstacles, direction)
        elif direction == 'up-right':
            if rq >= r or cq >= c:
                return 0
            else:
                return 1 + queenAttackRecursive(r, c, rq+1, cq+1, obstacles, direction)
        elif direction == 'right':
            if cq >= c:
                return 0
            else:
                return 1 + queenAttackRecursive(r, c, rq, cq+1, obstacles, direction)
        elif direction == 'right-down':
            if rq <= 1 or cq >= c:
                return 0
            else:
                return 1 + queenAttackRecursive(r, c, rq-1, cq+1, obstacles, direction)
        elif direction == 'down':
            if rq <= 1:
                return 0
            else:
                return 1 + queenAttackRecursive(r, c, rq-1, cq, obstacles, direction)
        elif direction == 'down-left':
            if rq <= 1 or cq <= 1:
                return 0
            else:
                return 1 + queenAttackRecursive(r, c, rq-1, cq-1, obstacles, direction)
        elif direction == 'left':
            if cq <= 1:
                return 0
            else:
                return 1 + queenAttackRecursive(r, c, rq, cq-1, obstacles, direction)
        else: # left-up
            if rq >= r or cq <= 1:
                return 0
            else:
                return 1 + queenAttackRecursive(r, c, rq+1, cq-1, obstacles, direction)

    output += queenAttackRecursive(r, c, rq, cq, obstacles, 'up')
    output += queenAttackRecursive(r, c, rq, cq, obstacles, 'up-right')
    output += queenAttackRecursive(r, c, rq, cq, obstacles, 'right')
    output += queenAttackRecursive(r, c, rq, cq, obstacles, 'right-down')
    output += queenAttackRecursive(r, c, rq, cq, obstacles, 'down')
    output += queenAttackRecursive(r, c, rq, cq, obstacles, 'down-left')
    output += queenAttackRecursive(r, c, rq, cq, obstacles, 'left')
    output += queenAttackRecursive(r, c, rq, cq, obstacles, 'left-up')

    return output
In [15]:
results1 = evaluate_test_cases(queenAttack1, tests)
TEST CASE #0 Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 4, 'obstacles': [(3, 5)]} Expected Output: 24 Actual Output: 24 Execution Time: 0.027 ms Test Result: PASSED TEST CASE #1 Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 4, 'obstacles': []} Expected Output: 27 Actual Output: 27 Execution Time: 0.024 ms Test Result: PASSED TEST CASE #2 Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 3, 'obstacles': [(4, 2), (2, 3), (5, 5)]} Expected Output: 21 Actual Output: 21 Execution Time: 0.026 ms Test Result: PASSED TEST CASE #3 Input: {'r': 2, 'c': 2, 'rq': 2, 'cq': 1, 'obstacles': [(1, 2)]} Expected Output: 2 Actual Output: 2 Execution Time: 0.102 ms Test Result: PASSED TEST CASE #4 Input: {'r': 2, 'c': 2, 'rq': 1, 'cq': 1, 'obstacles': [(1, 2), (2, 1), (2, 2)]} Expected Output: 0 Actual Output: 0 Execution Time: 0.014 ms Test Result: PASSED TEST CASE #5 Input: {'r': 1000, 'c': 1000, 'rq': 500, 'cq': 500, 'obstacles': []} Expected Output: 3995 Actual Output: 3995 Execution Time: 2.45 ms Test Result: PASSED TEST CASE #6 Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 4, 'obstacles': [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1,... Expected Output: 3 Actual Output: 3 Execution Time: 0.059 ms Test Result: PASSED SUMMARY TOTAL: 7, PASSED: 7, FAILED: 0
In [16]:
results1
Out[16]:
[(24, True, 0.027),
 (27, True, 0.024),
 (21, True, 0.026),
 (2, True, 0.102),
 (0, True, 0.014),
 (3995, True, 2.45),
 (3, True, 0.059)]
In [17]:
times1 = []
for values in results1:
    times1.append(values[2])
In [18]:
times1
Out[18]:
[0.027, 0.024, 0.026, 0.102, 0.014, 2.45, 0.059]
In [19]:
times1.sort()
times1
Out[19]:
[0.014, 0.024, 0.026, 0.027, 0.059, 0.102, 2.45]

Lets visualize the times in a chart.

In [20]:
from matplotlib import pyplot as plt
In [21]:
plt.plot(times1, color='tab:red', label="Recursive")
plt.legend()
plt.show();
Notebook Image

5. Dynamic solution

In [22]:
def queenAttack2(r, c, rq, cq, obstacles):
    output = 0
    # Vertical up
    for i in range(1, r-rq+1):
        if (rq+i, cq) in obstacles:
            break
        else:
            output += 1
    # Vertical down
    for i in range(1, rq):
        if (rq-i, cq) in obstacles:
            break
        else:
            output += 1
    # Horizontal right
    for i in range(1, c-cq+1):
        if (rq, cq+i) in obstacles:
            break
        else:
            output += 1
    for i in range(1, cq):
        if (rq, cq-i) in obstacles:
            break
        else:
            output += 1
    # Diagonal ↗
    for i in range(1, min(c-cq, r-rq)+1):
        if (rq+i, cq+i) in obstacles:
            break
        else:
            output += 1
    for i in range(1, min(cq, rq)):
        if (rq-i, cq-i) in obstacles:
            break
        else:
            output += 1
    # Diagonal ↖
    for i in range(1, min(c-cq, rq-1)+1):
        if (rq-i, cq+i) in obstacles:
            break
        else:
            output += 1
    for i in range(1, min(cq-1, r-rq)+1):
        if (rq+i, cq-i) in obstacles:
            break
        else:
            output += 1
    return output
In [23]:
results2 = evaluate_test_cases(queenAttack2, tests)
TEST CASE #0 Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 4, 'obstacles': [(3, 5)]} Expected Output: 24 Actual Output: 24 Execution Time: 0.053 ms Test Result: PASSED TEST CASE #1 Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 4, 'obstacles': []} Expected Output: 27 Actual Output: 27 Execution Time: 0.035 ms Test Result: PASSED TEST CASE #2 Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 3, 'obstacles': [(4, 2), (2, 3), (5, 5)]} Expected Output: 21 Actual Output: 21 Execution Time: 0.027 ms Test Result: PASSED TEST CASE #3 Input: {'r': 2, 'c': 2, 'rq': 2, 'cq': 1, 'obstacles': [(1, 2)]} Expected Output: 2 Actual Output: 2 Execution Time: 0.016 ms Test Result: PASSED TEST CASE #4 Input: {'r': 2, 'c': 2, 'rq': 1, 'cq': 1, 'obstacles': [(1, 2), (2, 1), (2, 2)]} Expected Output: 0 Actual Output: 0 Execution Time: 0.014 ms Test Result: PASSED TEST CASE #5 Input: {'r': 1000, 'c': 1000, 'rq': 500, 'cq': 500, 'obstacles': []} Expected Output: 3995 Actual Output: 3995 Execution Time: 1.274 ms Test Result: PASSED TEST CASE #6 Input: {'r': 8, 'c': 8, 'rq': 4, 'cq': 4, 'obstacles': [(1, 1), (1, 2), (1, 3), (1, 4), (1, 5), (1, 6), (1,... Expected Output: 3 Actual Output: 3 Execution Time: 0.07 ms Test Result: PASSED SUMMARY TOTAL: 7, PASSED: 7, FAILED: 0
In [24]:
results2
Out[24]:
[(24, True, 0.053),
 (27, True, 0.035),
 (21, True, 0.027),
 (2, True, 0.016),
 (0, True, 0.014),
 (3995, True, 1.274),
 (3, True, 0.07)]
In [25]:
times2 = []
for values in results2:
    times2.append(values[2])
In [26]:
times2
Out[26]:
[0.053, 0.035, 0.027, 0.016, 0.014, 1.274, 0.07]
In [27]:
times2.sort()
times2
Out[27]:
[0.014, 0.016, 0.027, 0.035, 0.053, 0.07, 1.274]
In [28]:
boxes1 = [64, 64, 64, 4, 64, 1000000, 64]
boxes1.sort()
boxes1
Out[28]:
[4, 64, 64, 64, 64, 64, 1000000]
In [29]:
plt.plot(boxes1, times1, color='tab:red', label="Recursive")
plt.plot(boxes1, times2, color='tab:blue', label="Dynamic")
plt.legend()
plt.show();
Notebook Image

6. Algorithm's complexity and inefficiencies.

For both functions, the bottleneck seems associated to the size of the chessboard, but the recursive solution seems to be more affected by the number of boxes than the dynamic approach.

The time complexity of the recursion is O(N²). For the second algorithm, the time complexity is O(N).

7. Conclusion

For the Queen's Attack II problem, the dynamic solution is the more efficient.

In [ ]:
jovian.commit()
[jovian] Attempting to save notebook..