NCURSES程序设计之皇后问题

该程序是用NCURSES库实现的皇后问题，可以将算法结果以图形方式显示，并可遍历所有结果

编译时需要加上NCURSES链接库， gcc -o <> -lncurses

源代码如下，可在linux系统中编译后直接运行

#include <stdio.h>
 #include <curses.h>


 #define QUEEN_CHAR '*'


 int *nqueens(int num);
 int place(int current, int *position);
 int print(int *positions, int num_queens);
 void board(WINDOW *win, int starty, int startx, int lines, int cols, 
  int tile_width, int tile_height);


 int main(int argc, char *argv[])
 {
int num_queens, *positions, count;

if(argc != 2)
{ printf("Usage: %s <number of queens (chess board order)>\n", argv[0]);
exit(1);
}


num_queens = atoi(argv[1]);
initscr();
cbreak();
keypad(stdscr, TRUE);
positions = nqueens(num_queens);
free(positions);
endwin();
return 0;
 }


 int *nqueens(int num)
 {
int current, *position, num_solutions = 0;

position = (int *) calloc(num + 1, sizeof(int));


position[1] = 0; 
current = 1;  /* current queen is being checked */
/* position[current] is the coloumn*/
while(current > 0){
position[current] += 1;
while(position[current] <= num && !place(current, position) )
position[current] += 1;
if(position[current] <= num){
if(current == num) {
++num_solutions;
print(position, num);
} 
else {
current += 1;
position[current] = 0;
}
}
else current -= 1; /* backtrack */
}
printf("Total Number of Solutions : %d\n", num_solutions);
return(position);
 }


 int place(int current, int *position)
 {
int i;
if(current == 1) return(1);
for(i = 1; i < current; ++i)
if(position[i] == position[current]) return(0);
else if(abs(position[i] - position[current]) ==
abs(i - current))
return(0);

return(1);
 }

 int print(int *positions, int num_queens)
 { int count;
int y = 2, x = 2, w = 4, h = 2;
static int solution = 1;


mvprintw(0, 0, "Solution No: %d", solution++);
board(stdscr, y, x, num_queens, num_queens, w, h);
for(count = 1; count <= num_queens; ++count)
{ int tempy = y + (count - 1) * h + h / 2;
int tempx = x + (positions[count] - 1) * w + w / 2;
mvaddch(tempy, tempx, QUEEN_CHAR);
}
refresh();
mvprintw(LINES - 2, 0, "Press Any Key to See next solution (F1 to Exit)");
if(getch() == KEY_F(1))
{ endwin();
exit(0);
}
clear();
 }


 void board(WINDOW *win, int starty, int startx, int lines, int cols, 
  int tile_width, int tile_height)
 { int endy, endx, i, j;

endy = starty + lines * tile_height;
endx = startx + cols  * tile_width;

for(j = starty; j <= endy; j += tile_height)
for(i = startx; i <= endx; ++i)
mvwaddch(win, j, i, ACS_HLINE);
for(i = startx; i <= endx; i += tile_width)
for(j = starty; j <= endy; ++j)
mvwaddch(win, j, i, ACS_VLINE);
mvwaddch(win, starty, startx, ACS_ULCORNER);
mvwaddch(win, endy, startx, ACS_LLCORNER);
mvwaddch(win, starty, endx, ACS_URCORNER);
mvwaddch(win,  endy, endx, ACS_LRCORNER);
for(j = starty + tile_height; j <= endy - tile_height; j += tile_height)
{ mvwaddch(win, j, startx, ACS_LTEE);
mvwaddch(win, j, endx, ACS_RTEE); 
for(i = startx + tile_width; i <= endx - tile_width; i += tile_width)
mvwaddch(win, j, i, ACS_PLUS);
}
for(i = startx + tile_width; i <= endx - tile_width; i += tile_width)
{ mvwaddch(win, starty, i, ACS_TTEE);
mvwaddch(win, endy, i, ACS_BTEE);
}
wrefresh(win);
 }