5 queens

[Dennis Lee Bieber]

How would you write a function that will populate a list with a list
of numbers with all the possibilities? For example a list of 3 numbers
taken among 4 [0,1,2,3] without duplicates. The result should be:
[0,1,2]
[0,1,3]
[0,2,3]
[1,2,3]

Simplistically? By looping to remove one element from the list, then
recursing to obtain the possibilities of n-1 from the remaining list.
Finally putting together the removed element with all the subpart
candidates... When the recurse is down to wanting 1-element responses,
convert each item in the input list into a 1-element sublist and return
it as each item is a valid last term in the result.


-=-=-=-=-=-=-=-
"""
Brute force m of n
"""

M = 4
N = 8
LST = range(N)

def process(data, elements):
if elements == 1:
return [[d] for d in data]
else:
results = []
for pos, itm in enumerate(data):
nest = data[os] + data[pos + 1:]
tmp = process(nest, elements - 1)
for part in tmp:
candidate = [itm]
candidate.extend(part)
candidate.sort()
if candidate not in results:
results.append(candidate)
return results

import pprint
pprint.pprint(process(LST, M))
-=-=-=-=-=-=-
Note I set it for four digits out of a range of 8, it is not tied to 3
out of 4

pythonw -u "mofn.py"

[[0, 1, 2, 3],
[0, 1, 2, 4],
[0, 1, 2, 5],
[0, 1, 2, 6],
[0, 1, 2, 7],
[0, 1, 3, 4],
[0, 1, 3, 5],
[0, 1, 3, 6],
[0, 1, 3, 7],
[0, 1, 4, 5],
[0, 1, 4, 6],
[0, 1, 4, 7],
[0, 1, 5, 6],
[0, 1, 5, 7],
[0, 1, 6, 7],
[0, 2, 3, 4],
[0, 2, 3, 5],
[0, 2, 3, 6],
[0, 2, 3, 7],
[0, 2, 4, 5],
[0, 2, 4, 6],
[0, 2, 4, 7],
[0, 2, 5, 6],
[0, 2, 5, 7],
[0, 2, 6, 7],
[0, 3, 4, 5],
[0, 3, 4, 6],
[0, 3, 4, 7],
[0, 3, 5, 6],
[0, 3, 5, 7],
[0, 3, 6, 7],
[0, 4, 5, 6],
[0, 4, 5, 7],
[0, 4, 6, 7],
[0, 5, 6, 7],
[1, 2, 3, 4],
[1, 2, 3, 5],
[1, 2, 3, 6],
[1, 2, 3, 7],
[1, 2, 4, 5],
[1, 2, 4, 6],
[1, 2, 4, 7],
[1, 2, 5, 6],
[1, 2, 5, 7],
[1, 2, 6, 7],
[1, 3, 4, 5],
[1, 3, 4, 6],
[1, 3, 4, 7],
[1, 3, 5, 6],
[1, 3, 5, 7],
[1, 3, 6, 7],
[1, 4, 5, 6],
[1, 4, 5, 7],
[1, 4, 6, 7],
[1, 5, 6, 7],
[2, 3, 4, 5],
[2, 3, 4, 6],
[2, 3, 4, 7],
[2, 3, 5, 6],
[2, 3, 5, 7],
[2, 3, 6, 7],
[2, 4, 5, 6],
[2, 4, 5, 7],
[2, 4, 6, 7],
[2, 5, 6, 7],
[3, 4, 5, 6],
[3, 4, 5, 7],
[3, 4, 6, 7],
[3, 5, 6, 7],
[4, 5, 6, 7]]

Exit code: 0

--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[Dennis Lee Bieber]

Making one small change:

M = 3
#~ N = 8
#~ LST = range(N)
LST = [ "John",
"Paul",
"George",
"Ringo",
"Peter",
"Paul S",
"Mary" ]

gives a list of the trios one could get from the Beatles mixed with
Peter, Paul, & Mary...

[['George', 'John', 'Paul'],
['John', 'Paul', 'Ringo'],
['John', 'Paul', 'Peter'],
['John', 'Paul', 'Paul S'],
['John', 'Mary', 'Paul'],
['George', 'John', 'Ringo'],
['George', 'John', 'Peter'],
['George', 'John', 'Paul S'],
['George', 'John', 'Mary'],
['John', 'Peter', 'Ringo'],
['John', 'Paul S', 'Ringo'],
['John', 'Mary', 'Ringo'],
['John', 'Paul S', 'Peter'],
['John', 'Mary', 'Peter'],
['John', 'Mary', 'Paul S'],
['George', 'Paul', 'Ringo'],
['George', 'Paul', 'Peter'],
['George', 'Paul', 'Paul S'],
['George', 'Mary', 'Paul'],
['Paul', 'Peter', 'Ringo'],
['Paul', 'Paul S', 'Ringo'],
['Mary', 'Paul', 'Ringo'],
['Paul', 'Paul S', 'Peter'],
['Mary', 'Paul', 'Peter'],
['Mary', 'Paul', 'Paul S'],
['George', 'Peter', 'Ringo'],
['George', 'Paul S', 'Ringo'],
['George', 'Mary', 'Ringo'],
['George', 'Paul S', 'Peter'],
['George', 'Mary', 'Peter'],
['George', 'Mary', 'Paul S'],
['Paul S', 'Peter', 'Ringo'],
['Mary', 'Peter', 'Ringo'],
['Mary', 'Paul S', 'Ringo'],
['Mary', 'Paul S', 'Peter']]

Exit code: 0

Looks cluttered as the input list was not sorted, but the sublists
on output /are/...
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/

 

[cf29]

def combinations(seq, n):
    if n == 0:
        yield []
    else:
        for i in xrange(len(seq)):
            for cc in combinations(seq[i+1:], n-1):
                yield [seq]+cc

...     print c
Steven

Thank you Steven, it works. I am so new to Python that I don't
understand fully how this function works to be able to adapt it to my
original problem. I wish I had a teacher

Merry Xmas

 

[Steven D'Aprano]

def combinations(seq, n):
    if n == 0:
        yield []
    else:
        for i in xrange(len(seq)):
            for cc in combinations(seq[i+1:], n-1):
                yield [seq]+cc

for c in combinations(range(4), 3):

...     print c
Steven

Thank you Steven, it works. I am so new to Python that I don't
understand fully how this function works to be able to adapt it to my
original problem. I wish I had a teacher

(1) Read up on generators. Google is your friend.

(2) Experiment in an interactive Python session. For example, look at
this pair of functions:

.... L = []
.... for i in (x, y, z):
.... L.append(i)
.... return L
........ for i in (x, y, z):
.... yield i
....

print function(1, 2, 3) [1, 2, 3]
print generator(1, 2, 3)

for i in function(1, 2, 3):

.... print i
....
1
2
3.... print i
....
1
2
3


Now imagine, instead of returning three items, suppose you had a function
that needed to return millions of items. A function using return would
need to produce all of those items before it could make them available to
you. A generator using yield can feed them to you one at a time, as soon
as they're ready.


(3) Read up on recursion, when a function calls itself.



Hope that helps.

 

[George Sakkis]

def combinations(seq, n):
if n == 0:
yield []
else:
for i in xrange(len(seq)):
for cc in combinations(seq[i+1:], n-1):
yield [seq]+cc

... print c
...
[0, 1, 2]
[0, 1, 3]
[0, 2, 3]
[1, 2, 3]

Or if you only need to iterate over each combination once instead of
keeping around more than one of them, below is a more efficient
version that reuses the same list for all combinations. Also it
doesn't require the input sequence to implement slicing so it can be
used e.g. with xrange:

def itercombos(seq, n):
def ifill(combo, i, start, end=len(seq), seq=seq, n=n):
if i == n:
yield combo
else:
i1 = i+1
for j in xrange(start,end):
combo = seq[j]
for combo in ifill(combo, i1, j+1):
yield combo
for combo in ifill(n*[None],0,0):
yield combo

[0, 1, 2]
[0, 1, 3]
[0, 2, 3]
[1, 2, 3]

Traceback (most recent call last):
File "combs.py", line 54, in <module>
for c in combinations(xrange(4), 3): print c
File "combs.py", line 12, in combinations
for cc in combinations(seq[i+1:], n-1):
TypeError: sequence index must be integer, not 'slice'


George

 

[Dennis Lee Bieber]

Just for completeness, as the subject migrated over to email...
Still not the most economical of algorithms -- best would be to combine
the last validation with the generation of candidates...

-=-=-=-=-=-
"""
Rudimentary (non-optimized) Queens problem
"""
import pprint
import time

QUEENS = 5
SIDE = 8
BOARD = [ divmod(n, 8) for n in range(SIDE * SIDE) ]
COVERED = [ [True] * SIDE for x in range(SIDE) ]

BOARD.sort()

def genCandidate(data, elements, end):
# print "\t" * (QUEENS - elements), "Generating positions for queen:
", QUEENS - elements
if elements == 1:
#placing last queen, all places are applicable, so return all
return [[d] for d in data]
else:
results = []
#loop over each candidate position for this queen
for itm in data:
#don't bother checking any rows past the potential last for
this element
if itm[0] > end: break
#itm is "current level's queen" position
#nest is the list of available cells to pass to the next
queen
nest = []
#trim the remaining cells by removing any that are in same
column, row, or diagonal
for othr in data:
if ((itm[0] < othr[0]) #skip any prior to this queen
also
and (itm[1] != othr[1])
and ((itm[0] - othr[0] != itm[1] - othr[1])
and (itm[0] - othr[0] != othr[1] - itm[1]))):
nest.append(othr)
#if no uncovered cells in "nest", skip to next queen
position as there are
#no places for the next lower queen to be placed
if not nest: continue
#then obtain a set of partial candidates based on one less
queen and the
#thinned available cells
tmp = genCandidate(nest, elements - 1, end + 1)
#for each subcandidate, create this level candidate by
prefacing with
#this queen's position.
for part in tmp:
candidate = [itm]
candidate.extend(part)
candidate.sort()
#if this candidate is not a duplicate, save it
if candidate not in results:
results.append(candidate)
return results

tstart = time.clock()
candidates = genCandidate(BOARD, QUEENS, 3)

print
print "Candidate solutions %s -- need coverage test" % len(candidates)
#pprint.pprint(candidates)

if SIDE != QUEENS:
#need to validate full board coverage
#for SIDE == QUEENS it is the "8-queens" problem
#and any candidate IS a full coverage solution
solution = []
for can in candidates:
#initialize a blank coverage board
cov = [ [False] * SIDE for x in range(SIDE) ]
#for each queen (position) in a candidate solution
for q in can:
#loop over the coverage board, and if the queen covers the
#row, column, or diagonal, set the square to True (covered)
for r in range(SIDE):
for c in range(SIDE):
if (q[0] == r
or q[1] == c
or (q[0] - r == q[1] - c
or q[0] - r == c - q[1])):
cov[c][r] = True
if cov == COVERED: solution.append(can)
else:
solution = candidates

print
print "Final solutions %s " % len(solution)
pprint.pprint(solution)
tstop = time.clock()
print "Run time: %s sec (%s min)" % (tstop - tstart, (tstop -
tstart)/60.0)
-=-=-=-=-=-=-=-
--
Wulfraed Dennis Lee Bieber KD6MOG
(e-mail address removed) (e-mail address removed)
HTTP://wlfraed.home.netcom.com/
(Bestiaria Support Staff: (e-mail address removed))
HTTP://www.bestiaria.com/