python/Demo/scripts/queens.py at master · pylee/python · GitHub

History

executable file

85 lines (69 loc) · 2.19 KB

Raw

#! /usr/bin/env python

"""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 set, 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()

python/Demo/scripts/queens.py at master · pylee/python · GitHub

Expand file tree

Breadcrumbs

queens.py

Latest commit

History

Breadcrumbs

queens.py

File metadata and controls