How to guess the positions of the queens in a chess game

Question

I recently participated in a programming competition and I was able to answer six out of seven questions in time. the last question was: "take a number from the user and make a chess board by the power of the given number and put as many queens as given and arrange the queens in a way so that they wouldn't threat each other horizontally, vertically and diagonally." So for example if the user entered 4 there would be 4 queens in a 4x4 (16) chess board. Well for the vertical and horizontal part I was able to check if they are in the same column or not and for the diagonal part I used a very awful combination of while loops and then added all the reserved places in the chess game to a list. The problem is that I use the random module to generate the indexes and then check if they are in the reserved numbers and then try again until it is not there so what happens is that there are only a few combinations of this chess game and if the beginning index is wrong the program gets pretty much stuck in the while loops forever. I had a thought of going from the last row to the first but even then I am still using a random index. How can I make the program calculate the places of the queens instead of just randomly putting a number and seeing if it works or not? My code: (if there other things wrong with my code please be kind to point it out):

import random

# in the program you had to put '1' as the position of the queens and put '0' as the empty places on the board
# and also, if the user entered a number less than 4 the combination would not have been possible

num = int(input("Enter number: "))
if num >= 4:
    arr = [[0 for _ in range(num)] for _ in range(num)]
    reserved_num = []
    oblique = []
    for i in range(num):
        j = random.randint(0, num - 1)
        while [i, j] in reserved_num:
            j = random.randint(0, num - 1)
        arr[i][j] = 1
        for rows in range(num):
            reserved_num.append([rows, j])
        if i < num-1:
            inc = 0
            if j == num-1:
                while j-inc > 0 and i+inc < num-1:
                    inc += 1
                    oblique.append([i+inc, j-inc])
                else:
                    inc = 0
            elif j == 0:
                while j+inc < num-1 and i+inc < num-1:
                    inc+= 1
                    oblique.append([i+inc, j+inc])
                else:
                    inc = 0
            else:
                while j+inc < num-1 and i+inc < num-1:
                    inc+= 1
                    oblique.append([i+inc, j+inc])
                else:
                    inc = 0
                while j-inc > 0 and i+inc < num-1:
                    inc += 1
                    oblique.append([i+inc, j-inc])
                else:
                    inc = 0
        for res in oblique:
            reserved_num.append(res)

    for items in arr:
        print(items)
else:
    print("Not Possible! ")

Answer 1

This is quite a famous puzzle, known as the N Queens Problem. It's the general case of the Eight queens puzzle.

There are a few solutions in Python on Rosetta Code, including this very elegant one from Raymond Hettinger:

from itertools import permutations
 
n = 8
cols = range(n)
for vec in permutations(cols):
    if n == len(set(vec[i]+i for i in cols)) \
         == len(set(vec[i]-i for i in cols)):
        print ( vec )

Raymond explains how this works:

With the solution represented as a vector with one queen in each row, we don't have to check to see if two queens are on the same row. By using a permutation generator, we know that no value in the vector is repeated, so we don't have to check to see if two queens are on the same column. Since rook moves don't need to be checked, we only need to check bishop moves.

The technique for checking the diagonals is to add or subtract the column number from each entry, so any two entries on the same diagonal will have the same value (in other words, the sum or difference is unique for each diagnonal). Now all we have to do is make sure that the diagonals for each of the eight queens are distinct. So, we put them in a set (which eliminates duplicates) and check that the set length is eight (no duplicates were removed).

Any permutation with non-overlapping diagonals is a solution. So, we print it and continue checking other permutations.