CODEWITHSUNDEEP
pythonlistn-queens
Robin Andrews
Robin Andrews

Reputation: 3794

Check Illegal Positions for N-Queens Problem with Board Stored in 1D List in Python

I'm making a GUI version of the N-Queens problem with Python. Currently I have the board stored in a 1D list. I know I could convert the 1D list to a 2D one by using a formula like grid_2d[i][j] = grid_1d[i * NUM_COLUMNS + j], but I'd rather find a way to check for illegal moves by finding a relationship within the 1D indices.

I've made a start with the functions provided below, but I think there's probably a much better way to go about this that I'm missing. Also, the checking diagonals part has me stumped.

Any suggestions for sensible ways to check for queen-collisions in a 1D list representation of a board please?

def get_rows(board_size):
    results = []
    for i in range(board_size):
        new_row = []
        for j in range(board_size):
            new_row.append(i * board_size + j)
        results.append(new_row)

    return results

def get_columns(board_size):
    results = []
    for j in range(board_size):
        new_column = []
        for i in range(board_size):
            new_column.append(j + board_size * i)
        results.append(new_column)

    return results


print(get_rows(3)) # [[0, 1, 2], [3, 4, 5], [6, 7, 8]] 
print(get_columns(3)) # [[0, 3, 6], [1, 4, 7], [2, 5, 8]]

Upvotes: 0

Views: 93

Answers (1)

Nathan
Nathan

Reputation: 3648

First, make a list of all the queens:

lst_queens =[(0, 3), (5,7) ...]

Where the first item is the row and the second is the column.

Then make a list of all the rows/columns the queens cover, wg:

lst_rows = [i[0] for i in lst_queens]

All values should be unique. Same for the columns.

For the diagonals, realize either both row and column increase as you travel down the diagonal, or one increases and one decreases. So you can list all the diagonals using:

diagonals_1 = [i[0] - i[1] for i in lst_queens]
diagonals_2 = [i[0] + i[1] for i in lst_queens]

And again, both lists shouldn't have any doubles.

Upvotes: 1

Related Questions