## 8-queens problem hill climbing python implementation

October 31, 2009 1 Comment

It was written in an AI book I’m reading that the hill-climbing algorithm finds about 14% of solutions. I implemented a version and got 18%, but this could easily be due to different implementations – like starting in random columns rather than random places on the board, and optimizing per column. Anyway, here is the program.

README

This program is a hillclimbing program solution to the 8 queens problem. The algorithm is silly in some places, but suits the purposes for what I was working on I think. It was tested with python 2.6.1 with psyco installed. If big runs are being tried, having psyco may be important to maintain sanity, since it will speed things up significanlty. Otherwise, you may want to stick to –numrun being less than around 50.

The board is simply defined as a two dimensional list, with the occupied elements stored as “Q” and empty emements as 0. The initial board is generated by picking a random row and column to place a queen, although the class structure allows for predefined boards to be manually passed in. If the spot on the board is occupied, then another spot is randomly chosen.

Violations are calculated by iterating through every queen and checking horizontally, vertically, and diagonally for other queens. Each violation is totalled up, and at the end they are divided by 2 since violations were overcounted. This could certainly be optimized further.

The hill solution works by checking every possible single move and returning the best of these. Obviously, this could also be improved upon. The book’s algorithm (which was not available while programming this) simply attempts to move every space within a column rather than every open spot on the board – which would speed up the process by an order of magnitude and also decrease the likelihood of finding a solution by a small percentage. Also, it appears that the random initial state only contains one queen per column, which is also different from this implementation. The assignment specification mentions a randomly generated board, which is what this implementation was based on. If an implementation closer to that of the book is desired, please let me know, as it would only be a minor adjustment.

With this algorithm, every queen on the board tries to move to every spot on the board, and violations are re-calculated. A move with the least violations is chosen and the process repeats until there is no improvement. It there is no improvement after every queen has had a go, there is no solution found and the algorithm returns. If there is an improvement, the algorithm continues for another go-around.

The biggest run so far is just 1000 nodes. It returned 175 successes, which is fairly close to the book’s given percentage or .14.

Here is sample usage:

mopey-mackey:hillclimb user$ python eight_queen.py –help

Usage: eight_queen.py [options]Options:

-h, –help show this help message and exit

-q, –quiet Don’t print all the moves… wise option if using large

numbers

–numrun=NUMRUN Number of random Boardsmopey-mackey:hillclimb user$ python eight_queen.py –numrun=1000 –quiet

Total Runs: 1000

Total Success: 175

Success Percentage: 0.175

Average number of steps: 3.83mopey-mackey:hillclimb user$ python eight_queen.py

====================

BOARD 0

====================

Board Violations 7

0 0 Q 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 Q 0 0

Q 0 0 0 0 0 0 0

0 0 0 0 Q 0 0 0

Q Q 0 0 0 0 Q 0

0 0 0 0 0 0 0 0

0 0 0 0 Q 0 0 0Board Violations 4

0 0 Q 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 Q 0 0

Q 0 0 0 0 0 0 0

0 0 0 0 Q 0 0 0

Q Q 0 0 0 0 0 0

0 0 0 0 0 0 0 Q

0 0 0 0 Q 0 0 0Board Violations 3

0 0 Q 0 0 0 0 0

Q 0 0 0 0 0 0 0

0 0 0 0 0 Q 0 0

0 0 0 0 0 0 0 0

0 0 0 0 Q 0 0 0

Q Q 0 0 0 0 0 0

0 0 0 0 0 0 0 Q

0 0 0 0 Q 0 0 0Board Violations 2

0 0 Q 0 0 0 0 0

Q 0 0 0 0 0 0 0

0 0 0 0 0 Q 0 0

0 Q 0 0 0 0 0 0

0 0 0 0 Q 0 0 0

0 Q 0 0 0 0 0 0

0 0 0 0 0 0 0 Q

0 0 0 0 Q 0 0 0NO SOLUTION FOUND

Total Runs: 1

Total Success: 0

Success Percentage: 0.0

Average number of steps: 4.0mopey-mackey:hillclimb user$ python eight_queen.py –numrun=4

====================

BOARD 0

====================

Board Violations 3

0 0 Q 0 0 0 0 0

Q 0 0 0 Q 0 0 0

0 0 0 0 0 0 0 Q

0 0 0 Q 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 Q 0

0 Q 0 0 0 0 0 0

0 0 0 0 0 0 0 QBoard Violations 1

0 0 Q 0 0 0 0 0

Q 0 0 0 Q 0 0 0

0 0 0 0 0 0 0 Q

0 0 0 Q 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 Q 0

0 Q 0 0 0 0 0 0

0 0 0 0 0 Q 0 0Board Violations 0

0 0 Q 0 0 0 0 0

0 0 0 0 Q 0 0 0

0 0 0 0 0 0 0 Q

0 0 0 Q 0 0 0 0

Q 0 0 0 0 0 0 0

0 0 0 0 0 0 Q 0

0 Q 0 0 0 0 0 0

0 0 0 0 0 Q 0 0SOLUTION FOUND

====================

BOARD 1

====================

Board Violations 8

Q 0 0 0 0 0 0 Q

0 0 0 0 0 0 Q 0

0 0 Q 0 Q 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 Q 0 0

0 0 0 0 0 0 0 0

0 Q 0 0 Q 0 0 0

0 0 0 0 0 0 0 0Board Violations 5

Q 0 0 0 0 0 0 Q

0 0 0 0 0 0 Q 0

0 0 Q 0 Q 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 Q 0 0

0 0 0 0 0 0 0 0

0 0 0 0 Q 0 0 0

0 Q 0 0 0 0 0 0Board Violations 3

0 0 0 0 0 0 0 Q

0 0 0 0 0 0 Q 0

0 0 Q 0 Q 0 0 0

Q 0 0 0 0 0 0 0

0 0 0 0 0 Q 0 0

0 0 0 0 0 0 0 0

0 0 0 0 Q 0 0 0

0 Q 0 0 0 0 0 0Board Violations 2

0 0 0 0 0 0 0 Q

0 0 0 0 0 0 Q 0

0 0 Q 0 0 0 0 0

Q 0 0 0 0 0 0 0

0 0 0 0 0 Q 0 0

Q 0 0 0 0 0 0 0

0 0 0 0 Q 0 0 0

0 Q 0 0 0 0 0 0NO SOLUTION FOUND

====================

BOARD 2

====================

Board Violations 5

0 Q 0 Q 0 0 0 0

0 0 0 0 0 Q 0 Q

Q 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

Q 0 0 0 0 0 0 0

Q 0 0 0 0 0 0 0

0 0 0 0 0 0 Q 0

0 0 0 0 0 0 0 0Board Violations 3

0 Q 0 Q 0 0 0 0

0 0 0 0 0 Q 0 Q

0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

Q 0 0 0 0 0 0 0

Q 0 0 0 0 0 0 0

0 0 0 0 0 0 Q 0

0 0 0 0 Q 0 0 0Board Violations 2

0 Q 0 Q 0 0 0 0

0 0 0 0 0 Q 0 0

0 0 0 0 0 0 0 Q

0 0 0 0 0 0 0 0

Q 0 0 0 0 0 0 0

Q 0 0 0 0 0 0 0

0 0 0 0 0 0 Q 0

0 0 0 0 Q 0 0 0Board Violations 1

0 Q 0 Q 0 0 0 0

0 0 0 0 0 Q 0 0

0 0 0 0 0 0 0 Q

0 0 Q 0 0 0 0 0

Q 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0

0 0 0 0 0 0 Q 0

0 0 0 0 Q 0 0 0Board Violations 0

0 Q 0 0 0 0 0 0

0 0 0 0 0 Q 0 0

0 0 0 0 0 0 0 Q

0 0 Q 0 0 0 0 0

Q 0 0 0 0 0 0 0

0 0 0 Q 0 0 0 0

0 0 0 0 0 0 Q 0

0 0 0 0 Q 0 0 0SOLUTION FOUND

====================

BOARD 3

====================

Board Violations 5

0 0 0 Q Q 0 0 0

0 0 0 0 0 0 0 Q

0 0 0 0 0 0 0 0

0 0 0 0 0 Q 0 0

0 0 0 0 0 0 0 Q

0 Q 0 0 0 0 0 0

0 0 0 0 Q 0 0 0

0 0 Q 0 0 0 0 0Board Violations 3

0 0 0 0 Q 0 0 0

0 0 0 0 0 0 0 Q

0 0 0 Q 0 0 0 0

0 0 0 0 0 Q 0 0

0 0 0 0 0 0 0 Q

0 Q 0 0 0 0 0 0

0 0 0 0 Q 0 0 0

0 0 Q 0 0 0 0 0Board Violations 1

0 0 0 0 Q 0 0 0

Q 0 0 0 0 0 0 0

0 0 0 Q 0 0 0 0

0 0 0 0 0 Q 0 0

0 0 0 0 0 0 0 Q

0 Q 0 0 0 0 0 0

0 0 0 0 Q 0 0 0

0 0 Q 0 0 0 0 0Board Violations 0

0 0 0 0 Q 0 0 0

Q 0 0 0 0 0 0 0

0 0 0 Q 0 0 0 0

0 0 0 0 0 Q 0 0

0 0 0 0 0 0 0 Q

0 Q 0 0 0 0 0 0

0 0 0 0 0 0 Q 0

0 0 Q 0 0 0 0 0SOLUTION FOUND

Total Runs: 4

Total Success: 3

Success Percentage: 0.75

Average number of steps: 4.0

And here is the source

#!/usr/bin/python import random,sys,copy from optparse import OptionParser try: import psyco psyco.full() except ImportError: pass """ cowboy code, but seems to work USAGE: python prog <numberruns=1> <verbocity=False> """ class board: def __init__(self, list=None): if list == None: self.board = [[0 for i in range(0,8)] for j in range(0,8)] #initialize queens at random places for i in range(0,8): while 1: rand_row = random.randint(0,7) rand_col = random.randint(0,7) if self.board[rand_row][rand_col] == 0: self.board[rand_row][rand_col] = "Q" break #TODO raise errors if board is not right format or dimension #define how to print the board def __repr__(self): mstr = "" for i in range(0,8): for j in range(0,8): mstr = mstr + str(self.board[i][j]) + " " mstr = mstr + "n" return (mstr) class queens: def __init__(self, numruns, verbocity, passedboard=None): #TODO check options self.totalruns = numruns self.totalsucc = 0 self.totalnumsteps = 0 self.verbocity = verbocity for i in range(0,numruns): if self.verbocity == True: print "====================" print "BOARD",i print "====================" self.mboard = board(passedboard) self.cost = self.calc_cost(self.mboard) self.hill_solution() def hill_solution(self): while 1: currViolations = self.cost self.getlowercostboard() if currViolations == self.cost: break self.totalnumsteps += 1 if self.verbocity == True: print "Board Violations", self.calc_cost(self.mboard) print self.mboard if self.cost != 0: if self.verbocity == True: print "NO SOLUTION FOUND" else: if self.verbocity == True: print "SOLUTION FOUND" self.totalsucc += 1 return self.cost def printstats(self): print "Total Runs: ", self.totalruns print "Total Success: ", self.totalsucc print "Success Percentage: ", float(self.totalsucc)/float(self.totalruns) print "Average number of steps: ", float(self.totalnumsteps)/float(self.totalruns) def calc_cost(self, tboard): #these are separate for easier debugging totalhcost = 0 totaldcost = 0 for i in range(0,8): for j in range(0,8): #if this node is a queen, calculate all violations if tboard.board[i][j] == "Q": #subtract 2 so don't count self #sideways and vertical totalhcost -= 2 for k in range(0,8): if tboard.board[i][k] == "Q": totalhcost += 1 if tboard.board[k][j] == "Q": totalhcost += 1 #calculate diagonal violations k, l = i+1, j+1 while k < 8 and l < 8: if tboard.board[k][l] == "Q": totaldcost += 1 k +=1 l +=1 k, l = i+1, j-1 while k < 8 and l >= 0: if tboard.board[k][l] == "Q": totaldcost += 1 k +=1 l -=1 k, l = i-1, j+1 while k >= 0 and l < 8: if tboard.board[k][l] == "Q": totaldcost += 1 k -=1 l +=1 k, l = i-1, j-1 while k >= 0 and l >= 0: if tboard.board[k][l] == "Q": totaldcost += 1 k -=1 l -=1 return ((totaldcost + totalhcost)/2) #this function tries moving every queen to every spot, with only one move #and returns the move that has the leas number of violations def getlowercostboard(self): lowcost = self.calc_cost(self.mboard) lowestavailable = self.mboard #move one queen at a time, the optimal single move by brute force for q_row in range(0,8): for q_col in range(0,8): if self.mboard.board[q_row][q_col] == "Q": #get the lowest cost by moving this queen for m_row in range(0,8): for m_col in range(0,8): if self.mboard.board[m_row][m_col] != "Q": #try placing the queen here and see if it's any better tryboard = copy.deepcopy(self.mboard) tryboard.board[q_row][q_col] = 0 tryboard.board[m_row][m_col] = "Q" thiscost = self.calc_cost(tryboard) if thiscost < lowcost: lowcost = thiscost lowestavailable = tryboard self.mboard = lowestavailable self.cost = lowcost if __name__ == "__main__": parser = OptionParser() parser.add_option("-q", "--quiet", dest="verbose", action="store_false", default=True, help="Don't print all the moves... wise option if using large numbers") parser.add_option("--numrun", dest="numrun", help="Number of random Boards", default=1, type="int") (options, args) = parser.parse_args() mboard = queens(verbocity=options.verbose, numruns=options.numrun) mboard.printstats()