python - Change Breadth First Search to Depth First Search, N- Queen Solver -

i appreciate if helps me understand how change breadth first search depth first search, or steps need follow.

the algorithm in next functions:

1. canplace
2. getpositions
3. loopboard

code:

import sys import copy os import system  #set console title system("title michael fiford - breadth first n-queen solver")  class queensolver:     #store amount of queens we're placing, or table size     tablesize = 0      #the alphabet, nice cell referencing on output     alphabet = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i', 'j', 'k', 'l', 'm', 'n', 'o', 'p', 'q', 'r', 's', 't', 'u', 'v', 'w', 'x', 'y', 'z']      #the queue of possible moves create , loop through     queue = []      #whether or not solver can ran     canrun = false      def setup(self, queennumber):         #set number of queens/table size         self.tablesize = queennumber          #can run, long there no errors         self.canrun = true          #show error if there no solution, or take long         if queennumber < 4:             print "error: solution not available few number of queens"             self.canrun = false         elif queennumber > 13:             print "error: solution take long calculate, , computer run out of memory first!"             self.canrun = false      #create empty table     def blanktable(self):         table = []         row in xrange(self.tablesize):             new = []             col in xrange(self.tablesize):                 new.append(0);             table.append(new)         return table      #place queen in table     def placequeen(self, table, row, col):         #copy table, python annoying , change both         t2 = copy.deepcopy(table)         t2[row][col] = 1         return t2      #the main program loop     def loopboard(self):         #the column looking @         col = 1         #loop while queue isn't empty, , there still move possibilities explore         while len(self.queue):             #create new empty queue             queue2 = []             #update status             print col, "queens placed"             #loop queue, looking positions each status             #s array containing current queen positions status             s in self.queue:                 #get moves available status                 availablemoves = self.getpositions(s, col)                 #if placing last queen, , there solutions available, finish                 if col == self.tablesize -1 , len(availablemoves):                     #clear queue                     self.queue = []                     #get solution (or 1 of them, care first one)                     s = availablemoves[0]                     break;                 #add possible moves new queue                 #this table containing queens placed                 if len(availablemoves):                     queue2 += availablemoves             #replace old queue new 1             self.queue = queue2             #increase queen/col counter             col += 1         self.finish(s, col)      #get array of moves available, given info current table, , current column     def getpositions(self, table, col):                 #create row counter, , array contain our position info         row = 0         possiblepositions = []          #loop rows on board         while row < self.tablesize:             #if can place in space             if self.canplace(table, row, col):                 #add table newly added queen list of possible moves                 possiblepositions.append(self.placequeen(table, row, col))             row += 1         return possiblepositions      #check whether or not can place queen in position, given table , row , col of desired position     #return true if space available     def canplace(self, table, row, col):         # - direction         # check left/right         x = 0         #loop across table         while x < self.tablesize:             if table[x][col]:                 return false             x += 1          # | direction         #check up/down         y = 0         #loop down table         while y < self.tablesize:             if table[row][y]:                 return false             y += 1           # / direction         #check right diagonal         #we can start in cell 1 , 1 right of cell in question, have checked actual cell in above 2 checks         x = row + 1         y = col + 1         #loop up/right through table         while x < self.tablesize , y < self.tablesize:             if table[x][y]:                 return false                         x += 1             y += 1         #check down left diagonal         #again, not starting in cell specified         x = row - 1         y = col - 1         #loop down/left through table         while x >= 0 , y >= 0:             if table[x][y]:                 return false             x -= 1             y -= 1          # \ direction         #check left diagonal         #again, not starting in cell specified         x = row - 1         y = col + 1         #loop left through table         while x >= 0 , y < self.tablesize:             if table[x][y]:                 return false             x -= 1             y += 1         #check down right diagonal         #again, not starting in cell specified         x = row + 1         y = col - 1         #loop down right through table         while x < self.tablesize , y >= 0:             if table[x][y]:                 return false             x += 1             y -= 1          return true      #output table user, looking pretty     def display(self, table):         #max number length, can indent our table nicely later         mnl = len(str(len(table)))          #new line         print ""          #top of table, e.g "     b c d"         print " "*mnl, "  ",         x in range(self.tablesize):             print self.alphabet[x],         #new line         print ""         #row spacer, e.g "   * - - - - *         print " " * mnl, " *",         x in range(self.tablesize):             print "-",         print "*"          #row counter         #print actual table, queens 1's, empty space 0         #also prefixed row number, e.g " 3 | 0 1 0 0 |         x = 1         row in table:             #if numbers shorter largest number, give them spaces rows still line             extrapadding = mnl - len(str(x))             #show number prefix, spaces, , | symbol, e.g " 6  | "             print "", x, " "*int(extrapadding) + "|",             #show value of cell (1 or 0)             col in row:                 print col,             #end of row             print "|"             #next row             x += 1         #show same row spacer @ top of table, e.g "   * - - - - *         print " " * mnl, " *",         x in range(self.tablesize):             print "-",         print "*"      #we're done! show output user     def finish(self, table, col):         #if found right number of queens         if col == self.tablesize:             print ""             print "total of", self.tablesize, "queens placed!"             print "solution:"             self.display(table)         else:             print ""             print "error: not place queens unknown reason =["      #run script     def run(self):         if not self.canrun:             print "error: can not run"         else:             print ""             print "working..."             print ""             self.queue = self.getpositions(self.blanktable(), 0)             self.loopboard()  #ask user how many queens want use def ask():     while true:         print ""         print "how many queens use?  [8]"         input = raw_input()         #check if input given integer         if input.isdigit():             return int(input)         #if no input given, use standard 8         elif input == "":             return 8;         print "error: invalid input"  #run program def run():     #instantiate solver     qs = queensolver()     #while ask hasn't given valid input     while(not qs.canrun):         qs.setup(ask())     print ""     #go!     qs.run()  #prompt user if want run program again def prompt():     #has valid input been received?     while true:         print ""         print "would run script again? please enter y/n  [n]"         input = raw_input()         #check if input given y or n         if input == "y" or input == "y":             return true         #also accept empty string in place of n         elif input == "n" or input == "n" or input == "":             return false         print "error: invalid input"  if __name__ == "__main__":     print ""     print ""     print "  #######################################"     print "  ## breadth first search queen solver ##"     print "  ## by: michael fiford - comf3        ##"     print "  ## date: 03/12/2013                  ##"     print "  #######################################"      #run script, , prompt them after if want run again     shouldrun = true     while(shouldrun):         run()         shouldrun = prompt() 

the difference between dfs , bfs in way exploring nodes of graph. in dfs algorithm, first exploring last node added stack (last in first out) whereas in bfs algorithm, exploring on basis of first in first out (queue).

the resulting change code shoud quite small: in bfs algorithm, use list implement stack, appending new node @ top of stack , exploring them:

l=[] while len(l)>0:     new_node=l.pop()     l.extend(new_node.get_neighbors()) 

the change quite small switch bfs algorithm: switch stack queue. implemented in python in collections module deque (with efficient implementation of popleft (getting first item of list , remove it) , append (appending item @ end of queue):

import collections l=collections.deque() while len(l)>0:     new_node=l.popleft()     l.extend(new_node.get_neighbors()) 

your code can rewritten fit previous description:

while len(self.queue):         #create new empty queue         #queue2 = []         #update status         print col, "queens placed"         #loop queue, looking positions each status         #s array containing current queen positions status         s=queue.pop()         #get moves available status         availablemoves = self.getpositions(s, col)         #if placing last queen, , there solutions available, finish         if col == self.tablesize -1 , len(availablemoves):             #clear queue             self.queue = []             #get solution (or 1 of them, care first one)             s = availablemoves[0]             break;         #add possible moves new queue         #this table containing queens placed         #if len(availablemoves):         #    queue2 += availablemoves         queue.extend(availablemoves)         #replace old queue new 1         #self.queue = queue2         #increase queen/col counter         col += 1 

let me know if need more explanations. hope helps.