HackerRank Problem - "Queen's attack II"

Question

I am new to python and coding in general and I recently found HackerRank. I have been mostly doing easy problems until now. Today, I saw the problem "Queen's Attack II" (https://www.hackerrank.com/challenges/queens-attack-2/problem), wrote my code, and it didn't execute in time for some of the testcases. I optimized it best to what I could and then I went in the discussions, where I found a code from u/Arviy which follows basically the same algorithm as mine but the implementation was a bit different. But it ran just fine comparing all the test cases.

I also compared them to best of my knowledge, and tried to time different portions of code using time.time() from import time. In the end, I got my code to pass the test cases but it still runs about 2x slower than the other code.

Problem Summary -
A queen is standing on an n times 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). There are obstacles on the chessboard, each preventing the queen from attacking any square beyond it on that path. 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.

Variables setup -

n, k = 100000, 100000
r_q, c_q = 1, 1
obstacles = [[1000, 1000], [714, 169], [619, 264], [609, 274], [809, 74], [819, 64], [714, 264], [714, 74], [952, 569], [623, 471], [256, 985], [934, 419], [745, 280], [926, 189], [159, 859], [106, 912], [509, 894], [170, 402], [476, 238], [173, 546], [674, 438], [539, 597], [215, 724], [675, 975], [128, 814], [789, 162], [492, 142], [694, 384], [206, 253], [347, 625], [491, 147], [243, 639], [408, 401], [850, 293], [310, 901], [925, 147], [138, 471], [610, 203], [571, 658], [724, 762], [456, 908], [710, 842], [203, 321], [972, 254], [527, 214], [945, 750], [103, 561], [374, 947], [439, 716], [958, 504], [830, 182], [902, 635], [901, 158], [804, 532], [903, 957], [126, 916], [418, 485], [493, 385], [410, 247], [217, 712], [936, 340], [805, 645], [940, 430], [194, 148], [719, 247], [872, 928], [251, 231], [136, 240], [609, 860], [401, 230], [168, 759], [531, 907], [546, 927], [729, 590], [648, 912], [407, 793], [917, 256], [671, 489], [926, 874], [438, 467], [602, 462], [239, 328], [104, 510], [260, 739], [864, 741], [837, 493], [418, 345], [798, 754], [841, 710], [169, 365], [954, 389], [160, 496], [183, 108], [741, 796], [753, 682], [159, 324], [417, 306], [261, 509], [587, 194], [805, 907], [218, 204], [591, 389], [916, 894], [963, 103], [461, 689], [937, 520], [350, 730], [436, 208], [381, 617], [546, 361], [719, 512], [305, 794], [509, 820], [915, 570], [408, 420], [609, 973], [872, 710], [465, 409], [459, 427], [918, 847], [142, 943], [457, 364], [360, 273], [276, 289], [427, 537], [317, 475], [864, 832], [845, 639], [463, 520], [741, 617], [762, 734], [160, 804], [192, 739], [289, 715], [340, 826], [827, 872], [186, 836], [967, 639], [145, 137], [581, 147], [479, 897], [203, 960], [967, 691], [891, 680], [593, 651], [172, 257], [258, 325], [351, 859], [153, 801], [705, 589], [832, 832], [718, 864], [971, 652], [567, 561], [715, 729], [689, 821], [178, 891], [962, 408], [829, 639], [561, 413], [401, 261], [491, 952], [831, 741], [271, 471], [826, 312], [482, 317], [413, 769], [231, 561], [579, 735], [769, 916], [184, 586], [820, 208], [476, 298], [587, 157], [194, 642], [341, 647], [478, 731], [951, 620], [401, 912], [837, 358], [249, 349], [158, 201], [195, 968], [294, 132], [291, 193], [158, 480], [849, 761], [832, 157], [364, 809], [293, 526], [164, 865], [193, 429], [158, 520], [342, 574], [409, 815], [627, 765], [413, 316], [426, 508], [902, 620], [278, 385], [587, 342], [982, 812], [753, 721], [176, 192], [289, 729], [845, 729], [698, 205], [597, 378], [570, 251], [853, 742], [903, 126], [546, 172], [792, 491], [160, 926], [321, 597], [835, 356], [894, 207], [153, 807], [106, 372], [716, 105], [638, 281], [814, 597], [970, 926], [175, 943], [135, 642], [372, 142], [701, 980], [720, 184], [695, 491], [682, 354], [371, 246], [421, 574], [803, 108], [429, 687], [465, 953], [157, 385], [624, 893], [201, 896], [975, 295], [635, 348], [351, 659], [127, 109], [705, 852], [471, 327], [915, 750], [720, 637], [126, 358], [506, 690], [317, 923], [285, 725], [957, 406], [372, 810], [971, 170], [920, 452], [756, 743], [791, 158], [698, 835], [576, 470], [209, 329], [902, 948], [854, 249], [347, 780], [386, 215], [713, 130], [516, 760], [964, 374], [781, 340], [763, 402], [408, 824], [476, 642], [752, 320], [605, 185], [231, 745], [941, 962], [354, 760], [927, 426], [340, 164], [809, 720], [465, 152], [487, 280], [386, 690], [401, 605], [351, 517], [421, 120], [571, 870], [409, 581], [647, 268], [254, 168], [290, 687], [982, 452], [184, 813], [942, 726], [829, 856], [305, 874], [759, 456], [623, 930], [813, 984], [297, 432], [609, 397], [257, 921], [320, 375], [109, 570], [126, 210], [763, 189], [798, 708], [803, 368], [971, 631], [967, 791], [962, 850], [906, 201], [849, 403], [905, 389], [284, 231], [726, 275], [742, 562], [754, 948], [724, 481], [903, 168], [523, 231], [735, 452], [930, 149], [503, 950], [572, 473], [561, 967], [296, 281], [352, 283], [638, 856], [760, 602], [801, 170], [598, 417], [841, 965], [479, 485], [859, 916], [293, 248], [457, 791], [238, 462], [725, 943], [821, 372], [543, 901], [473, 507], [982, 723], [726, 394], [418, 350], [834, 150], [218, 437], [584, 290], [934, 271], [294, 895], [543, 671], [623, 784], [485, 478], [276, 643], [513, 136], [957, 407], [621, 340], [972, 817], [971, 291], [950, 315], [674, 315], [451, 982], [327, 829], [294, 154], [732, 601], [739, 352], [529, 495], [240, 720], [918, 387], [597, 715], [186, 716], [824, 875], [190, 852], [524, 328], [531, 753], [392, 985], [164, 849], [715, 864], [438, 935], [591, 946], [528, 690], [296, 560], [210, 102], [458, 148], [513, 615], [561, 324], [594, 451], [546, 159], [506, 473], [367, 107], [172, 230], [651, 629], [345, 628], [627, 425], [973, 940], [923, 914], [603, 437], [986, 684], [679, 230], [560, 204], [102, 578], [154, 863], [241, 153], [107, 152], [109, 530], [154, 849], [610, 175], [753, 213], [852, 279], [328, 287], [952, 832], [487, 904], [869, 519], [915, 809], [704, 657], [843, 871], [371, 351], [645, 963], [925, 638], [692, 623], [492, 786], [692, 708], [945, 658], [176, 736], [369, 547], [578, 812], [873, 763], [620, 418], [589, 209], [906, 418], [426, 976], [120, 451], [475, 735], [831, 746], [908, 270], [246, 721], [541, 120], [352, 286], [128, 826], [210, 431], [865, 687], [817, 576], [139, 907], [674, 491], [671, 396], [536, 604], [809, 396], [284, 817], [941, 841], [712, 370], [649, 931], [395, 689], [429, 249], [869, 218], [370, 730], [570, 140], [475, 136], [408, 509], [958, 294], [874, 847], [362, 807], [401, 301], [892, 204], [874, 365], [549, 780], [487, 146], [432, 293], [270, 901], [968, 891], [386, 642], [812, 801], [834, 860], [987, 237], [568, 894], [562, 271], [189, 704], [230, 928], [501, 905], [870, 189], [980, 421], [258, 126], [960, 402], [531, 852], [450, 374], [327, 840], [172, 405], [960, 680], [279, 532], [284, 829], [230, 701], [289, 218], [423, 580], [865, 895], [635, 129], [831, 809], [934, 568], [234, 901], [639, 976], [265, 256], [347, 194], [204, 863], [275, 748], [274, 973], [653, 793], [854, 873], [741, 917], [981, 653], [194, 642], [897, 538], [542, 914], [579, 701], [983, 459], [342, 857], [398, 650], [139, 973], [214, 216], [240, 684], [135, 529], [128, 780], [638, 493], [513, 240], [428, 168], [615, 423], [317, 560], [821, 791], [973, 724], [431, 729], [521, 267], [740, 231], [519, 706], [273, 897], [269, 902], [284, 362], [859, 912], [178, 352], [432, 513], [250, 248], [368, 614], [527, 319], [341, 125], [481, 543], [932, 412], [398, 428], [237, 648], [698, 870], [760, 352], [279, 749], [194, 607], [972, 973], [865, 136], [198, 750], [312, 871], [793, 159], [985, 923], [913, 635], [726, 813], [940, 948], [294, 364], [913, 482], [239, 127], [457, 390], [407, 679], [820, 327], [372, 867], [238, 794], [637, 546], [374, 857], [416, 130], [650, 650], [306, 926], [810, 823], [431, 378], [562, 593], [931, 715], [925, 256], [831, 718], [132, 837], [153, 571], [613, 436], [712, 817], [819, 527], [497, 947], [917, 629], [648, 548], [835, 164], [854, 324], [829, 859], [970, 694], [478, 860], [528, 204], [397, 925], [126, 457], [735, 593], [910, 532], [967, 930], [462, 718], [932, 867], [712, 827], [794, 534], [546, 162], [213, 941], [750, 980], [487, 761], [219, 263], [139, 870], [573, 932], [194, 609], [278, 839], [201, 305], [159, 576], [250, 857], [350, 607], [350, 674], [386, 702], [835, 561], [361, 817], [974, 187], [194, 984], [257, 201], [846, 973], [597, 361], [745, 658], [192, 397], [463, 738], [935, 913], [167, 572], [324, 210], [178, 641], [436, 890], [705, 795], [548, 721], [745, 104], [450, 612], [106, 613], [796, 908], [586, 374], [410, 827], [348, 561], [867, 573], [371, 493], [951, 438], [130, 302], [367, 156], [635, 926], [912, 346], [596, 732], [163, 850], [495, 725], [935, 849], [617, 789], [254, 952], [592, 748], [598, 514], [869, 215], [503, 906], [856, 865], [671, 893], [203, 298], [618, 168], [610, 207], [150, 634], [159, 906], [318, 867], [413, 412], [985, 134], [180, 280], [403, 781], [462, 370], [895, 567], [431, 876], [702, 583], [536, 514], [518, 364], [467, 697], [872, 853], [435, 245], [420, 134], [746, 109], [329, 278], [432, 389], [156, 875], [981, 312], [876, 361], [417, 269], [670, 762], [180, 405], [270, 319], [846, 345], [839, 863], [524, 418], [923, 704], [523, 489], [561, 913], [723, 369], [156, 620], [519, 164], [689, 354], [754, 324], [795, 459], [531, 931], [761, 187], [280, 289], [130, 907], [340, 173], [174, 846], [307, 456], [409, 729], [129, 418], [925, 465], [684, 563], [932, 582], [350, 471], [496, 547], [825, 875], [306, 245], [130, 678], [932, 264], [180, 109], [140, 520], [937, 247], [648, 954], [423, 957], [578, 254], [917, 514], [382, 539], [406, 405], [354, 486], [182, 392], [547, 124], [245, 760], [574, 187], [413, 618], [906, 976], [709, 931], [637, 891], [759, 253], [307, 684], [215, 168], [427, 683], [751, 132], [924, 182], [149, 528], [794, 564], [305, 386], [350, 497], [215, 963], [841, 102], [829, 130], [641, 149], [185, 527], [402, 804], [840, 740], [635, 641], [896, 573], [916, 987], [149, 209], [408, 904], [379, 528], [243, 863], [319, 721], [923, 942], [285, 523], [746, 429], [609, 645], [538, 528], [265, 321], [502, 615], [314, 432], [316, 349], [312, 493], [694, 260], [908, 541], [950, 630], [482, 234], [760, 548], [963, 345], [675, 569], [628, 591], [509, 485], [832, 610], [761, 480], [486, 841], [153, 841], [902, 750], [204, 905], [894, 539], [608, 137], [156, 721], [146, 435], [345, 647], [736, 239], [987, 346], [247, 319], [752, 568], [597, 796], [378, 180], [872, 601], [816, 853], [489, 583], [591, 506], [764, 603], [963, 261], [964, 702], [569, 910], [817, 649], [841, 487], [146, 609], [453, 468], [914, 684], [721, 216], [261, 703], [736, 687], [369, 927], [720, 640], [829, 741], [671, 987], [934, 248], [105, 368], [987, 714], [973, 672], [890, 840], [906, 786], [134, 351], [250, 394], [457, 540], [289, 237], [537, 104], [837, 437], [148, 504], [409, 654], [485, 895], [804, 706], [816, 943], [234, 156], [
149, 206], [340, 542], [840, 691], [652, 514], [526, 942], [732, 347], [280, 541], [806, 521], [523, 629], [835, 359], [176, 702], [370, 732], [975, 586], [674, 857], [852, 364], [869, 376], [719, 591], [182, 469], [175, 132], [691, 417], [124, 294], [103, 809], [912, 214], [597, 203], [549, 385], [896, 970], [463, 691], [508, 701], [360, 183], [650, 471], [169, 249], [824, 198], [734, 312], [679, 308], [927, 513], [261, 384], [873, 451], [876, 972], [265, 604], [746, 594], [652, 863], [127, 608], [692, 493], [675, 958], [564, 584], [742, 206], [816, 563], [906, 209], [931, 694], [608, 203], [580, 405], [631, 315], [129, 950], [596, 496], [826, 583], [365, 928], [842, 902], [508, 497], [903, 127], [381, 916], [458, 721], [685, 469], [720, 875], [351, 319], [178, 296], [830, 740], [547, 365], [823, 679], [507, 950], [297, 395], [217, 460], [186, 354], [405, 402], [245, 641], [975, 153], [758, 604], [390, 172], [936, 672], [823, 271], [590, 462], [470, 302], [680, 837], [371, 463], [605, 560], [248, 172], [856, 813], [152, 795], [254, 739], [705, 285], [576, 968], [270, 214], [539, 793], [376, 560], [175, 843], [341, 148], [423, 458], [631, 659], [428, 640], [935, 649], [946, 105], [950, 103], [807, 964], [976, 456], [230, 607], [460, 829], [915, 489], [164, 761], [815, 395], [784, 385], [417, 412], [708, 124], [247, 716], [869, 695], [179, 795], [504, 982], [175, 497], [215, 467], [284, 638], [638, 295], [248, 510], [481, 895], [715, 528], [527, 549], [478, 875], [716, 764], [327, 168], [456, 526], [170, 356], [249, 219], [602, 850], [142, 194], [821, 609], [104, 564], [948, 842], [851, 537], [375, 823], [408, 792], [195, 465], [490, 241], [981, 235], [175, 265], [679, 347], [293, 473], [406, 259], [156, 397], [784, 360], [306, 139], [258, 689], [369, 964], [386, 172], [971, 475], [893, 286], [438, 842], [690, 249], [183, 643], [374, 150], [256, 147], [432, 346], [508, 465], [324, 546], [584, 985], [164, 160], [395, 865], [381, 971], [928, 742], [862, 715], [850, 296], [491, 214], [753, 650], [814, 256]]

My first approach -

def queensAttack(n, k, r_q, c_q, obstacles):
    direction_vectors = ((1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1))
    count = 0
    for i in range(8):
        r_q_temp, c_q_temp = r_q, c_q
        while True:
            r_q_temp += direction_vectors[i][0]
            c_q_temp += direction_vectors[i][1]
            if [r_q_temp,c_q_temp] in obstacles or not(0<r_q_temp<n+1) or not(0<c_q_temp<n+1):
                break
            count += 1
    return count
print(queensAttack(n, k, r_q, c_q, obstacles))

Now in u/Arviy 's code -

def move_queen(n, updated_row, updated_col, r , c, obs):
    p = 0
    while True:
        r = updated_row(r)
        c = updated_col(c)
        key = (r - 1) * n + c
        if (c < 1 or c > n or r < 1 or r > n) or (key in obstacles):
            return p
        p += 1
    return p


def queensAttack(n, k, r_q, c_q, obstacles):
    obs = {}
    for b in obstacles:
        obs[(b[0] - 1) * n + b[1]] = None

    p = 0
    dr = [-1, -1, -1, 0, 0 , 1 , 1,1]
    dc = [0, -1, 1, 1, -1 , 0 , 1,-1]

    for i in range(8):
        p += move_queen(n, (lambda r: r + dr[i]), (lambda c: c + dc[i] ), r_q, c_q, obs)

    return p

print(queensAttack(n, k, r_q, c_q, obstacles))

This code ran significantly faster than mine and I investigated and found that it was how he checked for obstacles, so I did the same it my code and it was immediate 10x speedup. But still my code runs about 2x slower than u/Alviy 's code. And I am unable to figure out 1. why there was a huge speedup the first time and 2. why my code is still slower?

My updated code -

def queensAttack(n, k, r_q, c_q, obstacles):
    direction_vectors = ((1,0), (1,1), (0,1), (-1,1), (-1,0), (-1,-1), (0,-1), (1,-1))
    count = 0
    obstacle_dir = {}
    for obstacle in obstacles:
        obstacle_dir[(obstacle[0] - 1) * n + obstacle[1]] = None
    for i in range(8):
        r_q_temp, c_q_temp = r_q, c_q
        while True:
            r_q_temp += direction_vectors[i][0]
            c_q_temp += direction_vectors[i][1]
            key = (r_q_temp - 1) * n + c_q_temp
            if key in obstacle_dir or not(0<r_q_temp<n+1) or not(0<c_q_temp<n+1):
                break
            count += 1
    return count

Answer 1

There are two main problems with your code.

1. Repeated Lookups
2. Unnecessary Calculations

Repeated Lookups

With a 100,000 x 100,000 chess board, when you begin moving in a particular direction, you lookup direction_vectors[i][0] and direction_vectors[i][1] and add those values to r_q_temp and c_q_temp. And on the next move you look up those values again. And on the move after that, you look up those values again.

To be clear, each time you look up those values, the Python interpreter must:

• Look up direction_vectors in the local symbol table for queensAttack,
• Look up i in the local symbol table for queensAttack,
• Index to the [i] entry,
• Index to the [0] entry of that,
• Look up direction_vectors in the local symbol table for queensAttack, again,
• Look up i in the local symbol table for queensAttack, again,
• Index to the [i] entry, again,
• Index to the [1] entry of that.

So all that happens on up to 100,000 iterations in each given direction! That is a lot of indexing & lookups. They are each very fast, but a hundred thousand iterations of very fast starts becoming slow.

First, let's speed that up.

Instead of indexing over the (hard coded) 8 direction indices, let's loop directly over the direction_vectors:

for direction in direction_vectors:
    r_q_temp, c_q_temp = r_q, c_q
    while True:
        r_q_temp += direction[0]
        c_q_temp += direction[1]
        ...

Two wins! First, we've eliminated that ugly hard-coded 8. If you repeat the same challenge with bishops or rooks, you don't have to remember that the number of direction vectors has changed. Second, we're no longer doing the [i] indexing operation twice per loop. Should be faster, since on each iteration we now only:

• Look up direction in the local symbol table for queensAttack,
• Index to the [0] entry of that,
• Look up direction in the local symbol table for queensAttack, again,
• Index to the [1] entry of that.

But why stop there? Let's get rid of the [0] and [1] indexing operations as well:

for dr, dc in direction_vectors:
    r_q_temp, c_q_temp = r_q, c_q
    while True:
        r_q_temp += dr
        c_q_temp += dc
        ...

Now, when we loop over the direction_vectors elements, we unpack the tuples directly into two local variables. Again, should be faster, since on each iteration we now only:

• Look up dr in the local symbol table for queensAttack,
• Look up dc in the local symbol table for queensAttack

So, how did u/Alviy's code avoid this?

    ..., (lambda r: r + dr[i]), (lambda c: c + dc[i]), ...

They are indexing dr[i] and dc[i] once per direction index, and constructing lambda functions from the values. Tricky, but it works. We're now doing effectively the same thing, just without the lambdas.

Unnecessary Calculations

Consider the statement:

if key in obstacle_dir or not(0<r_q_temp<n+1) or not(0<c_q_temp<n+1):

Let's assume for the moment that key in obstacle_dir is frequently False, so we need to evaluate not(0<r_q_temp<n+1) or not(0<c_q_temp<n+1). Since we spend a lot of the time examining moves which are on the board, we frequently have to fully evaluate 0<r_q_temp<n+1 and 0<c_q_temp<n+1.

So we need to evaluate n+1 ... twice ... per direction iteration. Hundreds of thousands of adding 1 to n, to get exactly the same value. Ouch.

Compiled languages can do data flow analysis, and move constant expressions outside of loops. As Python is interpreted, (insert technobabble here), it cannot. So you end up doing an expensive n+1 addition each iteration. Why expensive? Because, integers are objects, and adding one to a large integer requires allocating a new integer object for the result. Since it is not saved in a variable, this newly created integer becomes unreferenced and then discarded from the heap, only to be computed again (including allocation & freeing) a microsecond later. Hundreds of thousands of times!

Should we store n + 1 in a local variable? Sure, that would work. But so would changing the sub-expression to:

    not (0 < r_q_temp <= n) or not (0 < c_q_temp <= n)

Using "less than or equal to" instead of "less than" means the expensive n + 1 addition goes away.

---

Micro optimization: By De Morgan's Laws we know that not x or not y is equivalent to not (x and y), so we can write:

    not ((0 < r_q_temp <= n) and (0 < c_q_temp <= n))

which saves one not operation. Further, we can reverse the second sub-expression:

    not ((0 < r_q_temp <= n) and (n >= c_q_temp > 0))

which then allows us to chain the two subexpression, eliminating the second lookup of the n variable in the local symbol table:

    not (0 < r_q_temp <= n >= c_q_temp > 0)

---

There is another unnecessary calculation that is repeated over and over again, hundreds of thousands of times:

        key = (r_q_temp - 1) * n + c_q_temp

Specifically, r_q_temp - 1. Why are you subtracting 1 from r_q_temp? On a 10x10 grid, does it make any difference if (1,1) maps to 11 or 1, as long as it is the only coordinate that does so? Subtracting 1 just reduces the value of key by n for all key values. But you chose to create those key values here:

    obstacle_dir[(obstacle[0] - 1) * n + obstacle[1]] = None

All you need to do is use the same calculation ... removing the subtract 1 from that key calculation, and the obstacles will be stored under the new, more efficient-to-calculate key values. Since you are using a dictionary, the exact key values don't matter; only that they are unique.

But while we are looking at this obstacle_dir ... why is it a dictionary? The only value ever stored in it is None. You only ever test the existence of the key in the dictionary ... so you could use a set(), which is more memory efficient, and as such, could be faster.

Answer 2

To answer your first question of why there was such a big speedup when comparing your first version to your updated version (which took inspiration from Alviy's solution), it's because the first version is doing an expensive lookup within a loop that runs many times:

# obstacles is List[List[int]]
if [r_q_temp,c_q_temp] in obstacles  # [...]

In the above snippet, we are doing an \$O(k)\$ search (where \$k\$ is the length of obstacles) for [r_q_temp, c_q_temp] in obstacles, and we're doing this every time we advance the queen by one space!

The updated version uses a dictionary obstacle_dir, where lookup operations are on average \$O(1)\$, which makes a huge difference:

v1: 3.901795560005121 seconds per run (total 5 runs)
v2: 0.07246560000348837 seconds per run (total 5 runs)

v1 is the first version, and v2 is the updated version.

And actually, if we just make two small changes to your first version (let's call it v1_tweaked), it runs faster than your updated version:

1. Instead of an obstacle dictionary, create an obstacle set of (row, column) tuples. Like dictionaries, sets in Python also have an average \$O(1)\$ lookup time. In this case, a set is the more appropriate data structure because we only need to test membership; we don't need to map the board coordinates to anything.

   # Set[Tuple[int, int]]
   obstacles = {tuple(obstacle) for obstacle in obstacles}
   

2. Checking if a space contains an obstacle now looks like this:

   if (r_q_temp, c_q_temp) in obstacles # [...]
   

v1: 3.901795560005121 seconds per run (total 5 runs)
v2: 0.07246560000348837 seconds per run (total 5 runs)
v1_tweaked: 0.06353590001817792 seconds per run (total 5 runs)

---

EDIT: There appears to be some difference in the way you and I are timing the functions, because when I ran v2 (the updated version), v1_tweaked (my adjusted version of your v1), and Arviy's version, both v2 and v1_tweaked ran faster than Arviy's version:

from functools import partial
import timeit

n, k = 100000, 100000
r_q, c_q = 1, 1
obstacles = [[1000, 1000], [714, 169], ...]

v2 = partial(queensAttack_v2, n, k, r_q, c_q, obstacles)
v1_tweaked = partial(queensAttack_v1_tweaked, n, k, r_q, c_q, obstacles)
f_arviy = partial(queensAttack_Arviy, n, k, r_q, c_q, obstacles)

def measure(f, fname, num_trials=1):
    t = timeit.timeit(f'{fname}()', setup=f'from __main__ import {fname}', number=num_trials)
    print(f'{fname}: {t / num_trials} seconds per run (total {num_trials} runs)')

if __name__ == '__main__':
    TRIALS = 50
    measure(v2, 'v2', num_trials=TRIALS)
    measure(v1_tweaked, 'v1_tweaked', num_trials=TRIALS)
    measure(f_arviy, 'f_arviy', num_trials=TRIALS)

v2: 0.07151672399835661 seconds per run (total 50 runs)
v1_tweaked: 0.06288900200044736 seconds per run (total 50 runs)
f_arviy: 0.0828415279998444 seconds per run (total 50 runs)

I am using the timeit module, which is the recommended way to measure execution time of code snippets (more accurate than saving the time with time.time() before and after and calculating the difference).