Choose list of lists element unique to row and column (N Queens)

213 views Asked by At

I have a list of lists of - characters which acts as a grid.

I want to change one - to a Q per col and row.

Here's what I've got so far:

   import pprint 
   import random # I import these classes
   grid = [['-'] for n in range(8)]
   for i in range (8):
       for j in range(8):
           inserPoint = random.randrange(8,8)
           if (j == inserPoint or i == inserPoint) and (grid[j] != 'Q' or grid[i] != 'Q'):
               grid[i][j] = ('Q')
   pprint.pprint(grid) #/ how to print one queen per line 

this is my output. As you can see there are too many Qs on the grid:

[['-','-','-','-','-','-','Q','-'],
 ['-','-','-','-','Q','Q','-','-']
 ['-','-','-','-','Q','-','-','-']
 ['Q','Q','-','-','-','Q','Q','-']
 ['-','-','Q','-','Q','-','-','-'].
1

There are 1 answers

8
LondonRob On BEST ANSWER

A few things:

  1. You've got one too many loops. You can loop over the first index i, then just insert the Q where randrange tells you.
  2. Your randrange call is wrong. It should have a start and a stop. In fact, rangerange is not the right tool here if you want your Qs to be unique in row and column.
  3. Your grid set up doesn't actually produce what you show it producing.

Here's all three things fixed:

In [34]: size = 8
In [35]: grid = [['-' for m in range(size)] for n in range(size)]
In [36]: insertPoints = range(size) # = list(range(size)) in Python 3
In [37]: random.shuffle(insertPoints)
In [38]: for i in range(size):
   ....:     grid[i][insertPoints[i]] = "Q"

Which gives:

In [39]: grid
Out[39]: 
[['-', '-', '-', 'Q', '-', '-', '-', '-'],
 ['-', 'Q', '-', '-', '-', '-', '-', '-'],
 ['-', '-', '-', '-', '-', '-', 'Q', '-'],
 ['-', '-', '-', '-', '-', 'Q', '-', '-'],
 ['Q', '-', '-', '-', '-', '-', '-', '-'],
 ['-', '-', '-', '-', 'Q', '-', '-', '-'],
 ['-', '-', '-', '-', '-', '-', '-', 'Q'],
 ['-', '-', 'Q', '-', '-', '-', '-', '-']]

(See this for why shuffling a range doesn't work in Python 3)