ÿØÿàJFIFÿþ ÿÛC       ÿÛC ÿÀÿÄÿÄ"#QrÿÄÿÄ&1!A"2qQaáÿÚ ?Øy,æ/3JæݹÈ߲؋5êXw²±ÉyˆR”¾I0ó2—PI¾IÌÚiMö¯–þrìN&"KgX:Šíµ•nTJnLK„…@!‰-ý ùúmë;ºgµŒ&ó±hw’¯Õ@”Ü— 9ñ-ë.²1<yà‚¹ïQÐU„ہ?.’¦èûbß±©Ö«Âw*VŒ) `$‰bØԟ’ëXÖ-ËTÜíGÚ3ð«g Ÿ§¯—Jx„–’U/ÂÅv_s(Hÿ@TñJÑãõçn­‚!ÈgfbÓc­:él[ðQe 9ÀPLbÃãCµm[5¿ç'ªjglå‡Ûí_§Úõl-;"PkÞÞÁQâ¼_Ñ^¢SŸx?"¸¦ùY騐ÒOÈ q’`~~ÚtËU¹CڒêV  I1Áß_ÿÙ#! /usr/bin/python2.7 """N queens problem. The (well-known) problem is due to Niklaus Wirth. This solution is inspired by Dijkstra (Structured Programming). It is a classic recursive backtracking approach. """ N = 8 # Default; command line overrides class Queens: def __init__(self, n=N): self.n = n self.reset() def reset(self): n = self.n self.y = [None] * n # Where is the queen in column x self.row = [0] * n # Is row[y] safe? self.up = [0] * (2*n-1) # Is upward diagonal[x-y] safe? self.down = [0] * (2*n-1) # Is downward diagonal[x+y] safe? self.nfound = 0 # Instrumentation def solve(self, x=0): # Recursive solver for y in range(self.n): if self.safe(x, y): self.place(x, y) if x+1 == self.n: self.display() else: self.solve(x+1) self.remove(x, y) def safe(self, x, y): return not self.row[y] and not self.up[x-y] and not self.down[x+y] def place(self, x, y): self.y[x] = y self.row[y] = 1 self.up[x-y] = 1 self.down[x+y] = 1 def remove(self, x, y): self.y[x] = None self.row[y] = 0 self.up[x-y] = 0 self.down[x+y] = 0 silent = 0 # If true, count solutions only def display(self): self.nfound = self.nfound + 1 if self.silent: return print '+-' + '--'*self.n + '+' for y in range(self.n-1, -1, -1): print '|', for x in range(self.n): if self.y[x] == y: print "Q", else: print ".", print '|' print '+-' + '--'*self.n + '+' def main(): import sys silent = 0 n = N if sys.argv[1:2] == ['-n']: silent = 1 del sys.argv[1] if sys.argv[1:]: n = int(sys.argv[1]) q = Queens(n) q.silent = silent q.solve() print "Found", q.nfound, "solutions." if __name__ == "__main__": main()