Back to index

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

List of all members.

Public Member Functions

def __init__
def coords2index
def index2coords
def solve
def printsolution

Public Attributes

 n
 succs
 lastij
 final
 squaregenerators

Private Member Functions

def _init_board

Detailed Description

Definition at line 1136 of file test_generators.py.


Constructor & Destructor Documentation

def test.test_generators.Knights.__init__ (   self,
  m,
  n,
  hard = 0 
)

Definition at line 1137 of file test_generators.py.

01137 
01138     def __init__(self, m, n, hard=0):
01139         self.m, self.n = m, n
01140 
01141         # solve() will set up succs[i] to be a list of square #i's
01142         # successors.
01143         succs = self.succs = []
01144 
01145         # Remove i0 from each of its successor's successor lists, i.e.
01146         # successors can't go back to i0 again.  Return 0 if we can
01147         # detect this makes a solution impossible, else return 1.
01148 
01149         def remove_from_successors(i0, len=len):
01150             # If we remove all exits from a free square, we're dead:
01151             # even if we move to it next, we can't leave it again.
01152             # If we create a square with one exit, we must visit it next;
01153             # else somebody else will have to visit it, and since there's
01154             # only one adjacent, there won't be a way to leave it again.
01155             # Finelly, if we create more than one free square with a
01156             # single exit, we can only move to one of them next, leaving
01157             # the other one a dead end.
01158             ne0 = ne1 = 0
01159             for i in succs[i0]:
01160                 s = succs[i]
01161                 s.remove(i0)
01162                 e = len(s)
01163                 if e == 0:
01164                     ne0 += 1
01165                 elif e == 1:
01166                     ne1 += 1
01167             return ne0 == 0 and ne1 < 2
01168 
01169         # Put i0 back in each of its successor's successor lists.
01170 
01171         def add_to_successors(i0):
01172             for i in succs[i0]:
01173                 succs[i].append(i0)
01174 
01175         # Generate the first move.
01176         def first():
01177             if m < 1 or n < 1:
01178                 return
01179 
01180             # Since we're looking for a cycle, it doesn't matter where we
01181             # start.  Starting in a corner makes the 2nd move easy.
01182             corner = self.coords2index(0, 0)
01183             remove_from_successors(corner)
01184             self.lastij = corner
01185             yield corner
01186             add_to_successors(corner)
01187 
01188         # Generate the second moves.
01189         def second():
01190             corner = self.coords2index(0, 0)
01191             assert self.lastij == corner  # i.e., we started in the corner
01192             if m < 3 or n < 3:
01193                 return
01194             assert len(succs[corner]) == 2
01195             assert self.coords2index(1, 2) in succs[corner]
01196             assert self.coords2index(2, 1) in succs[corner]
01197             # Only two choices.  Whichever we pick, the other must be the
01198             # square picked on move m*n, as it's the only way to get back
01199             # to (0, 0).  Save its index in self.final so that moves before
01200             # the last know it must be kept free.
01201             for i, j in (1, 2), (2, 1):
01202                 this  = self.coords2index(i, j)
01203                 final = self.coords2index(3-i, 3-j)
01204                 self.final = final
01205 
01206                 remove_from_successors(this)
01207                 succs[final].append(corner)
01208                 self.lastij = this
01209                 yield this
01210                 succs[final].remove(corner)
01211                 add_to_successors(this)
01212 
01213         # Generate moves 3 thru m*n-1.
01214         def advance(len=len):
01215             # If some successor has only one exit, must take it.
01216             # Else favor successors with fewer exits.
01217             candidates = []
01218             for i in succs[self.lastij]:
01219                 e = len(succs[i])
01220                 assert e > 0, "else remove_from_successors() pruning flawed"
01221                 if e == 1:
01222                     candidates = [(e, i)]
01223                     break
01224                 candidates.append((e, i))
01225             else:
01226                 candidates.sort()
01227 
01228             for e, i in candidates:
01229                 if i != self.final:
01230                     if remove_from_successors(i):
01231                         self.lastij = i
01232                         yield i
01233                     add_to_successors(i)
01234 
01235         # Generate moves 3 thru m*n-1.  Alternative version using a
01236         # stronger (but more expensive) heuristic to order successors.
01237         # Since the # of backtracking levels is m*n, a poor move early on
01238         # can take eons to undo.  Smallest square board for which this
01239         # matters a lot is 52x52.
01240         def advance_hard(vmid=(m-1)/2.0, hmid=(n-1)/2.0, len=len):
01241             # If some successor has only one exit, must take it.
01242             # Else favor successors with fewer exits.
01243             # Break ties via max distance from board centerpoint (favor
01244             # corners and edges whenever possible).
01245             candidates = []
01246             for i in succs[self.lastij]:
01247                 e = len(succs[i])
01248                 assert e > 0, "else remove_from_successors() pruning flawed"
01249                 if e == 1:
01250                     candidates = [(e, 0, i)]
01251                     break
01252                 i1, j1 = self.index2coords(i)
01253                 d = (i1 - vmid)**2 + (j1 - hmid)**2
01254                 candidates.append((e, -d, i))
01255             else:
01256                 candidates.sort()
01257 
01258             for e, d, i in candidates:
01259                 if i != self.final:
01260                     if remove_from_successors(i):
01261                         self.lastij = i
01262                         yield i
01263                     add_to_successors(i)
01264 
01265         # Generate the last move.
01266         def last():
01267             assert self.final in succs[self.lastij]
01268             yield self.final
01269 
01270         if m*n < 4:
01271             self.squaregenerators = [first]
01272         else:
01273             self.squaregenerators = [first, second] + \
01274                 [hard and advance_hard or advance] * (m*n - 3) + \
01275                 [last]

Here is the caller graph for this function:


Member Function Documentation

def test.test_generators.Knights._init_board (   self) [private]

Definition at line 1285 of file test_generators.py.

01285 
01286     def _init_board(self):
01287         succs = self.succs
01288         del succs[:]
01289         m, n = self.m, self.n
01290         c2i = self.coords2index
01291 
01292         offsets = [( 1,  2), ( 2,  1), ( 2, -1), ( 1, -2),
01293                    (-1, -2), (-2, -1), (-2,  1), (-1,  2)]
01294         rangen = range(n)
01295         for i in range(m):
01296             for j in rangen:
01297                 s = [c2i(i+io, j+jo) for io, jo in offsets
01298                                      if 0 <= i+io < m and
01299                                         0 <= j+jo < n]
01300                 succs.append(s)

Here is the call graph for this function:

Here is the caller graph for this function:

def test.test_generators.Knights.coords2index (   self,
  i,
  j 
)

Definition at line 1276 of file test_generators.py.

01276 
01277     def coords2index(self, i, j):
01278         assert 0 <= i < self.m
01279         assert 0 <= j < self.n
01280         return i * self.n + j

Here is the call graph for this function:

Here is the caller graph for this function:

def test.test_generators.Knights.index2coords (   self,
  index 
)

Definition at line 1281 of file test_generators.py.

01281 
01282     def index2coords(self, index):
01283         assert 0 <= index < self.m * self.n
01284         return divmod(index, self.n)

Here is the call graph for this function:

Here is the caller graph for this function:

Definition at line 1307 of file test_generators.py.

01307 
01308     def printsolution(self, x):
01309         m, n = self.m, self.n
01310         assert len(x) == m*n
01311         w = len(str(m*n))
01312         format = "%" + str(w) + "d"
01313 
01314         squares = [[None] * n for i in range(m)]
01315         k = 1
01316         for i in x:
01317             i1, j1 = self.index2coords(i)
01318             squares[i1][j1] = format % k
01319             k += 1
01320 
01321         sep = "+" + ("-" * w + "+") * n
01322         print(sep)
01323         for i in range(m):
01324             row = squares[i]
01325             print("|" + "|".join(row) + "|")
01326             print(sep)

Here is the call graph for this function:

Definition at line 1302 of file test_generators.py.

01302 
01303     def solve(self):
01304         self._init_board()
01305         for x in conjoin(self.squaregenerators):
01306             yield x

Here is the call graph for this function:

Here is the caller graph for this function:


Member Data Documentation

Definition at line 1203 of file test_generators.py.

Definition at line 1183 of file test_generators.py.

Definition at line 1138 of file test_generators.py.

Definition at line 1270 of file test_generators.py.

Definition at line 1142 of file test_generators.py.


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