Python实现八皇后问题：递归与非递归算法详解

def check(board,pos):
 # check函数暂时先不实现
 pass

def EightQueen(board,row):
 blen = len(board)
 if row == blen: # 来到不存在的第九行了
  print board
  return True # 一定要return一个True，理由在下面
 for possibleY in range(blen):
  if check(board,(row,possibleY)):
   board[row][possibleY] = 1 # 放置一个Queen
   if not EightQueen(board,row+1): # 这里其实是本行下面所有行放置皇后的递归入口。但是如果最终这条路没有找到一个解，那么
    # 此时应该将刚才放置的皇后收回，再去寻找下一个可能的解
    board[row][possibleY] = 0
   else:
    return True
 return False

def check(board,pos):
 x,y = pos
 blen = len(board)
 for i in range(x):
  for j in range(blen):
   if board[i][j] == 1:
    if j == y or abs(j-y) == abs(i-x):
     return False
 return True

def check(board,row,col):
 i = 0
 while i < row:
  if abs(col-board[i]) in (0,abs(row-i)):
   return False
  i += 1
 return True

def EightQueen(board,row):
 blen = len(board)
 if row == blen: # 来到不存在的第九行了
  print board
  return True
 col = 0
 while col < blen:
  if check(board,row,col):
   board[row] = col
   if EightQueen(board,row+1):
    return True
  col += 1
 return False

def printBoard(board):
 '''为了更友好地展示结果 方便观察'''
 import sys
 for i,col in enumerate(board):
  sys.stdout.write('□ ' * col + '■ ' + '□ ' * (len(board) - 1 - col))
  print ''

def EightQueen(board,row):
 blen = len(board)
 if row == blen: # 来到不存在的第九行了
  print board
  return True
 col = 0
 while col < blen:
  if check(board,row,col):
   board[row] = col
   if EightQueen(board,row+1):
    # return True 去掉这里即可，或者直接删除掉整个判断，只留下单一个EightQueen(board,row+1)
    pass
  col += 1
 return False

def EightQueen(board):
 blen = len(board)
 stack = Queue.LifoQueue()
 stack.put((0,0)) # 为了自洽的初始化
 while not stack.empty():
  i,j = stack.get()
  if check(board,i,j): # 当检查通过
   board[i] = j # 别忘了放Queen
   if i >= blen - 1:
    print board # i到达最后一行表明已经有了结果
    break
   else:
    if j < blen - 1: # 虽然说要把本位置右边一格入栈，但是如果本位置已经是行末尾，那就没必要了
     stack.put((i,j+1))
    stack.put((i+1,0)) # 下一行第一个位置入栈，准备开始下一行的扫描
  elif j < blen - 1:
   stack.put((i,j+1)) # 对于未通过检验的情况，自然右移一格即可

#include <stdio.h>

static int board[8] = {};
int board_size = sizeof(board)/sizeof(int);

int check(int *board,int row){
 int i = 0;
 while(i < row){
  if(board[i] == board[row] || row - i == board[row] - board[i] || row - i == board[i] - board[row]){
   return 0;
  }
  i++;
 }
 // printf("board[%d]: %d\n",row,board[row]);
 return 1;
}

void print_board(int *board){
 int i;
 int size = board_size;
 for(i=0;i<size;i++){
  printf("%d,",board[i]);
 }
 printf("\n");
 i = 0;
 while (i < size){
  int j;
  for (j=0;j<size;j++){
   if(j == board[i]){
    printf("%s ","■ ");
   }
   else{
    printf("%s ","□ ");
   }
  }
  printf("\n");
  i++;
 }
}

int eight_queen(int *board,int row){
 if (row == 8){
  print_board(board);
  return 1;
 }
 board[row] = 0;
 while (1){
  if (check(board,row) && eight_queen(board,row+1)){
    return 1;
  }
  else{
   if(++board[row] >= 8){
    break;
   }
  }
 }

 return 0; 
}

int main(){
 eight_queen(board,0);
 // print_board(board);
 return 0;
}