8-queens problem hill climbing python implementation

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 Boards

mopey-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.83

mopey-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 0

Board 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 0

Board 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 0

Board 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 0

NO SOLUTION FOUND
Total Runs: 1
Total Success: 0
Success Percentage: 0.0
Average number of steps: 4.0

mopey-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 Q

Board 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 0

Board 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 0

SOLUTION 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 0

Board 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 0

Board 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 0

Board 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 0

NO 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 0

Board 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 0

Board 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 0

Board 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 0

Board 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 0

SOLUTION 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 0

Board 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 0

Board 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 0

Board 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 0

SOLUTION 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()