def nqueens_problem(n:int):
 
    board = [['-']*n for i in range(n)]
    ans = []
 
    def bactrack(row, cols, diagonals, anti_diagonals):
        #base condition
        if row == n:
            #append to solution to ans
            board_copy = [ ",".join(row) for row in board]
            ans.append(board_copy)
            return 
 
 
        for col in range(n):
            cur_diagonal = row- col
            cur_antidiagonal = row+col
 
            if col in cols or cur_diagonal in diagonals or cur_antidiagonal in anti_diagonals: 
                continue
 
            cols.add(col)
            diagonals.add(cur_diagonal)
            anti_diagonals.add(cur_antidiagonal)
            # place the Queen
            board[row][col] = 'Q'
            bactrack(row+1,cols,diagonals,anti_diagonals)
            #backtrack
            cols.remove(col)
            diagonals.remove(cur_diagonal)
            anti_diagonals.remove(cur_antidiagonal)
            board[row][col] = '-'
 
 
    bactrack(0,set(),set(),set())
    return ans
 
ans = nqueens_problem(5)
print('*'*50)
 
# print(ans)
 
for val in ans:
    for row in val:
        print(row)
    print('*'*20)

ZGVmIG5xdWVlbnNfcHJvYmxlbShuOmludCk6CgogICAgYm9hcmQgPSBbWyctJ10qbiBmb3IgaSBpbiByYW5nZShuKV0KICAgIGFucyA9IFtdCgogICAgZGVmIGJhY3RyYWNrKHJvdywgY29scywgZGlhZ29uYWxzLCBhbnRpX2RpYWdvbmFscyk6CiAgICAgICAgI2Jhc2UgY29uZGl0aW9uCiAgICAgICAgaWYgcm93ID09IG46CiAgICAgICAgICAgICNhcHBlbmQgdG8gc29sdXRpb24gdG8gYW5zCiAgICAgICAgICAgIGJvYXJkX2NvcHkgPSBbICIsIi5qb2luKHJvdykgZm9yIHJvdyBpbiBib2FyZF0KICAgICAgICAgICAgYW5zLmFwcGVuZChib2FyZF9jb3B5KQogICAgICAgICAgICByZXR1cm4gCgoKICAgICAgICBmb3IgY29sIGluIHJhbmdlKG4pOgogICAgICAgICAgICBjdXJfZGlhZ29uYWwgPSByb3ctIGNvbAogICAgICAgICAgICBjdXJfYW50aWRpYWdvbmFsID0gcm93K2NvbAoKICAgICAgICAgICAgaWYgY29sIGluIGNvbHMgb3IgY3VyX2RpYWdvbmFsIGluIGRpYWdvbmFscyBvciBjdXJfYW50aWRpYWdvbmFsIGluIGFudGlfZGlhZ29uYWxzOiAKICAgICAgICAgICAgICAgIGNvbnRpbnVlCgogICAgICAgICAgICBjb2xzLmFkZChjb2wpCiAgICAgICAgICAgIGRpYWdvbmFscy5hZGQoY3VyX2RpYWdvbmFsKQogICAgICAgICAgICBhbnRpX2RpYWdvbmFscy5hZGQoY3VyX2FudGlkaWFnb25hbCkKICAgICAgICAgICAgIyBwbGFjZSB0aGUgUXVlZW4KICAgICAgICAgICAgYm9hcmRbcm93XVtjb2xdID0gJ1EnCiAgICAgICAgICAgIGJhY3RyYWNrKHJvdysxLGNvbHMsZGlhZ29uYWxzLGFudGlfZGlhZ29uYWxzKQogICAgICAgICAgICAjYmFja3RyYWNrCiAgICAgICAgICAgIGNvbHMucmVtb3ZlKGNvbCkKICAgICAgICAgICAgZGlhZ29uYWxzLnJlbW92ZShjdXJfZGlhZ29uYWwpCiAgICAgICAgICAgIGFudGlfZGlhZ29uYWxzLnJlbW92ZShjdXJfYW50aWRpYWdvbmFsKQogICAgICAgICAgICBib2FyZFtyb3ddW2NvbF0gPSAnLScKCiAgICAKICAgIGJhY3RyYWNrKDAsc2V0KCksc2V0KCksc2V0KCkpCiAgICByZXR1cm4gYW5zCgphbnMgPSBucXVlZW5zX3Byb2JsZW0oNSkKcHJpbnQoJyonKjUwKQoKIyBwcmludChhbnMpCgpmb3IgdmFsIGluIGFuczoKICAgIGZvciByb3cgaW4gdmFsOgogICAgICAgIHByaW50KHJvdykKICAgIHByaW50KCcqJyoyMCk=