eightqueens_0.5.py

eightqueens_0.5.py

# The eight queens puzzle game
import ui, sound, speech
from collections import deque

nqueens = 10
v = ui.View(background_color=(0.40, 0.80, 1.00))
board = ui.View()
v.add_subview(board)
v.present('full_screen', hide_title_bar=False , orientations=['landscape'])
#steps_label = ui.Label()
#steps_label.frame = (30, 30, 250, 70)
#steps_label.background_color = (1.00, 0.00, 0.50)
#steps_label.font =  ('Futura-CondensedExtraBold', 40)
#steps_label.text = ' Steps: 0'
#v.add_subview(steps_label)
board.frame = (v.width-v.height, 0, v.height, v.height)
board.border_width = 3
board.border_color = (0,0,0)
board.background_color = (1,1,1)

buttons = []

game_state= []
for i in range(nqueens):
  game_state.append(-1)
  

def goal_test(game_state):
  if -1 in game_state:
    return False 
    
  game_state_length = len(game_state)
  
  for i in range(game_state_length):
    for j in range(game_state_length):
      if i != j:
        r1 = game_state[i]
        r2 = game_state[j]
        c1 = i
        c2 = j
        if r1 == r2:
          return False 
        elif abs(r1-r2) == abs(c1-c2):
          return False 
      
  return True       
  
  
  
def button_pressed(sender):
  x = sender.x
  y = sender.y
  r = int(round(sender.y/sender.width))
  c = int(round(sender.x/sender.width))
    
  if sender.background_image == None:
    if sender.background_color != (1,0,0, 1):
      sender.background_image = ui.Image.named('Crown')
      game_state[c] = r
      sound.play_effect('Click_1')
      for b in buttons:
        if b['button'].y == y or b['button'].x == x or abs(abs(b['button'].x -x) -abs(b['button'].y - y)) < 0.01:
          old_color = b['original_color']
          b['button'].background_color = (1,0,0)
          b['being_eaten_by_number_of_queens'] += 1
    else: 
      speech.say('not a good idea') 
  else:
    sender.background_image = None
    game_state[c] = -1
    sound.play_effect('Woosh_1')
    for b in buttons:
      if b['button'].y == y or b['button'].x == x or abs(abs(b['button'].x -x) -abs(b['button'].y - y)) < 0.01:
        b['being_eaten_by_number_of_queens'] -= 1
        if b['being_eaten_by_number_of_queens'] == 0:
          b['button'].background_color = b['original_color']
  
  if goal_test(game_state):
    speech.say('you win')
    
  return
  
def attacked(new_queen, existing_queen):
  if new_queen[0] == existing_queen[0] or new_queen[1] == existing_queen[1] or abs(new_queen[0]-existing_queen[0]) == abs(new_queen[1] - existing_queen[1]):
    return True 
  else:
    return False 
  
def next_actions(current_state):
#  return a list of possible positions to place the next queen
# we use (row_number, column_number) to reprsent the positin of a queen
# for example [(0, 0), (0, 1) .....]
  possible_places = []
  attacked_places = set([])
  if -1 in current_state:
    next_queen_column = current_state.index(-1)
    for r in range(nqueens):
      for i in range(nqueens):
        queen_column = i
        queen_row = current_state[i]
        if queen_row != -1 and attacked((r,next_queen_column), (queen_row, queen_column)):
          attacked_places.add((r,next_queen_column))
  
    for r in range(nqueens):
      if (r, next_queen_column) not in attacked_places:
        possible_places.append((r,next_queen_column))
           
  return possible_places
   
  
def smarter_next_actions(current_state):
  possible_places = []
  if -1 in current_state:
    next_queen_column = current_state.index(-1)

    for r in range(nqueens):
      possible_places.append((r,next_queen_column))
      
  return possible_places  

def dfs_nqueens(initial_state):
  frontier = deque([initial_state])
  explored = set([])
  
  while (frontier):
    current_node = frontier.pop()
    current_state = current_node
#    print current_state

    if goal_test(current_state):
      print 'solution found:'
      print current_state
      return current_state
      
    explored.add(tuple(current_state))
    for action in smarter_next_actions(current_state):
      r = action[0]
      c = action[1]    
      child_state = list(current_state)
      child_state[c] = r
      
      if tuple(child_state) not in explored: 
        frontier.append(child_state)
  
  print 'solution not found'
  return

def dfs_tree_search_nqueens(initial_state):
  frontier = deque([initial_state])
  while (frontier):
    current_node = frontier.pop()
    current_state = current_node
#    print current_state

    if goal_test(current_state):
      print 'solution found:'
      print current_state
      return current_state
      
    for action in next_actions(current_state):
      r = action[0]
      c = action[1]    
      child_state = list(current_state)
      child_state[c] = r
      frontier.append(child_state)
  
  print 'solution not found'
  return None 
  
# dfs_tree_search_nqueens(game_state)

for r in range(nqueens):
  for c in range(nqueens):
    button = ui.Button(title='')
    if c % 2 != r % 2:
      button.background_color = (0.50, 0.25, 0.00)
    else: 
      button.background_color = (1.00, 0.90, 0.70)
    
    button.width = v.height/nqueens
    button.height = button.width
    button.border_color = (0,0,0)
    button.border_width = 1
    button.x = button.width*c
    button.y = button.height*r
    button.action = button_pressed
    
    board.add_subview(button)
    buttons.append({'button': button, 'original_color': button.background_color, 'being_eaten_by_number_of_queens': 0, 'row': r, 'col': c})    

def auto_solve(sender):
  solution = dfs_tree_search_nqueens(game_state)
  if solution != None:
    for col in range(len(solution)):
      row = solution[col]
      for b in buttons:
        if b['col'] == col and b['row'] == row:
          button = b['button']
          button.background_image = ui.Image.named('Crown')

      
  
autosolve_button = ui.Button(title='Auto Solve')
autosolve_button.background_color = (1,1,1)
autosolve_button.frame = (30, 350, 250, 70)
autosolve_button.corner_radius = 5
autosolve_button.font = ('Futura-CondensedExtraBold', 40)
autosolve_button.border_color = (0,0,0)
autosolve_button.border_width = 1
autosolve_button.action = auto_solve
v.add_subview(autosolve_button)