Back to index

python3.2  3.2.2
Public Member Functions | Public Attributes
test.test_generators.Queens Class Reference

List of all members.

Public Member Functions

def __init__
def solve
def printsolution

Public Attributes

 n
 rowgenerators
 used

Detailed Description

Definition at line 1081 of file test_generators.py.


Constructor & Destructor Documentation

def test.test_generators.Queens.__init__ (   self,
  n 
)

Definition at line 1082 of file test_generators.py.

01082 
01083     def __init__(self, n):
01084         self.n = n
01085         rangen = range(n)
01086 
01087         # Assign a unique int to each column and diagonal.
01088         # columns:  n of those, range(n).
01089         # NW-SE diagonals: 2n-1 of these, i-j unique and invariant along
01090         # each, smallest i-j is 0-(n-1) = 1-n, so add n-1 to shift to 0-
01091         # based.
01092         # NE-SW diagonals: 2n-1 of these, i+j unique and invariant along
01093         # each, smallest i+j is 0, largest is 2n-2.
01094 
01095         # For each square, compute a bit vector of the columns and
01096         # diagonals it covers, and for each row compute a function that
01097         # generates the possiblities for the columns in that row.
01098         self.rowgenerators = []
01099         for i in rangen:
01100             rowuses = [(1 << j) |                  # column ordinal
01101                        (1 << (n + i-j + n-1)) |    # NW-SE ordinal
01102                        (1 << (n + 2*n-1 + i+j))    # NE-SW ordinal
01103                             for j in rangen]
01104 
01105             def rowgen(rowuses=rowuses):
01106                 for j in rangen:
01107                     uses = rowuses[j]
01108                     if uses & self.used == 0:
01109                         self.used |= uses
01110                         yield j
01111                         self.used &= ~uses
01112 
01113             self.rowgenerators.append(rowgen)

Here is the caller graph for this function:


Member Function Documentation

def test.test_generators.Queens.printsolution (   self,
  row2col 
)

Definition at line 1120 of file test_generators.py.

01120 
01121     def printsolution(self, row2col):
01122         n = self.n
01123         assert n == len(row2col)
01124         sep = "+" + "-+" * n
01125         print(sep)
01126         for i in range(n):
01127             squares = [" " for j in range(n)]
01128             squares[row2col[i]] = "Q"
01129             print("|" + "|".join(squares) + "|")
01130             print(sep)
01131 
01132 # A conjoin-based Knight's Tour solver.  This is pretty sophisticated
01133 # (e.g., when used with flat_conjoin above, and passing hard=1 to the
01134 # constructor, a 200x200 Knight's Tour was found quickly -- note that we're
01135 # creating 10s of thousands of generators then!), and is lengthy.

Definition at line 1115 of file test_generators.py.

01115 
01116     def solve(self):
01117         self.used = 0
01118         for row2col in conjoin(self.rowgenerators):
01119             yield row2col

Here is the call graph for this function:

Here is the caller graph for this function:


Member Data Documentation

Definition at line 1083 of file test_generators.py.

Definition at line 1097 of file test_generators.py.

Definition at line 1107 of file test_generators.py.


The documentation for this class was generated from the following file: