#include <stdio.h>
#include <stdlib.h>
void eightQueen(int** board, int n, int m);
/*if valid, return 1*/
int isValid(int** board,int n, int m, int i, int j);
int main()
{
int **board = (int **)malloc(sizeof(int *)*4);
int i = 0, j=0;
for(;i<4; i++)
{
board[i] = (int *) malloc(sizeof(int) * 4);
}
i = 0;
j = 0;
for(;i<4; i++)
for(; j < 4; j++)
{
board[i][j] = 0;
}
eightQueen(board, 4,4);
i = 0, j = 0;
for(; i<4; i++)
{
for(; j < 4; j++)
{
printf("%d(%d) ",board[i][j], i);
}
}
return 0;
}
void eightQueen(int** board, int n, int m)
{ int ii = 0;
int jj =0;
int k = 0;
while(ii < n && ii >= 0)
{
jj = 0;
while( jj<m)
{
if(board[ii][jj] == 1 && jj+1 < m)
{
board[ii][jj] = 0;
board[ii][++jj] = 1;
}
else
board[ii][jj] = 1;
if(isValid(board, n,m,ii,jj))
{
if(ii == n-1) return;
}
else
{
ii++;
break;
}
jj++;
}
if(jj>=m)
{
board[ii][jj-1] = 0;
ii--;
}
}
}
int isValid(int** board,int n, int m, int i, int j)
{
//判斷是否同列
int temp = 0;
for(; temp < n; temp++)
{
if(temp != i)
{
if(board[temp][j] != 0)
return 0;
}
}
//判斷是否右上角
int ii, jj;
for(ii =i-1, jj=j+1; ii >=0&&jj <= m; ii--,jj++)//注意中間判斷條件的&&
{
if(board[ii][jj] != 0)
return 0;
}
//判斷是否左上角
for(ii =i- 1,jj=j-1; ii >=0&&jj >=0;ii--,jj--)
{
if(board[ii][jj] != 0)
return 0;
}
return 1;
}
posted on 2008-04-12 23:39
fullfocus 閱讀(191)
評論(0) 編輯 收藏 所屬分類:
算法