|
|||||||
|
|
|
|||||
|
|
|||||||
|
xor eax,eax Home Fireworks SparcZ Win32 asm Kunthrandum Linkz page Guestbook Misc... About me XXXXXXXX 7736 |
Eight Queens Problem - ronybc'z solution :) Another program from the DOS era... Eight Queens problem is famous puzzle to arrange 8 Queens on a chessboard without attacking each other. Trying it manually is somewhat difficult. There are many other algorithms to do so. The concept of this program is to randomly place all the queens over the board and let them find their places THEMSELVES. And this code is to make them alive, intelligent and moving..! It isn't the ISO9001 way to solve the problem :) but it works... as follows. Each Queen is assigned with a priority such that each Queen watches the Queens in front(more prior) of her and adjusts the position accordingly, only with vertical movements, And passes control to the Queen behind. If there is no safe positions; she asks the next Queen in front (left) to change her position once again. This process happens with all 8 Queens recursively. Thus all Queens attain zero attacking positions with a minimum number of moves, by their co-operation :) Let's play with four nice queens; A,B,C,D. And watch what Queen-C does. Somewhere in the middle of the Fight, C gets the 'control' (active queen) from B. Now.. C has to:
Queen-C has to remember which rows are visited by her until returning control to B. And It WORKS!!! looks like a bi-directional recursion..? The Queens are initially placed one Queen per column (random row). The positions are imitated in a 8 by 8 array representing the chessboard. Random initial row positioning of Queens is used for getting different results at each execution of the program. I've found more than 50 different board arrangements with this program. Amazingly.. the program also includes routines for storing the output to a text file..! It is a good example for recursion. Good one for educational purposes, I also attended it for the same but for one of my friends. Well.. He paid me a beer; Mmm.. I hope you will also sponsor one to me :) MSDOS version: Queen8.zip (10kB, code + exe) Included C source code works with Borland Turbo-C Linux version: The download files of this site are stored at anglfire.com They do not allow downloading of files with extensions .gz or .bz2 So...
Copy following code into a text file; queen8.c
compile it:
gcc -o queen8 queen8.c -lncurses
then:
./queen8 -c
and thats it..!
------------------------------------------------------------
// Queen8 - Solution for Eight Queens' Problem
// Copyright (c) 1999-2007 Rony B Chandran
//
// url: http://www.ronybc.8k.com
#include <curses.h>
#include <stdlib.h>
#define QUEEN 1
#define EMPTY 0
#define SAFE 0
int moves=0;
int q[8]; // vertical position of queens
int b[8][8]; // chessboard
int rnd(int x) { return(random()%x); }
void direct_draw_board(){
int n1,n2;
for (n1=0;n1<8;n1++) {
printf("\n");
for (n2=0;n2<8;n2++) {
if(b[n2][n1]==EMPTY) printf(" -");
else printf(" %d",n2+1); }}
printf(" moves=%d ",moves);
for (n1=0;n1<8;n1++) printf("%d ",check_front(n1));
printf("\n \n");}
void show_board(){
int n1,n2;
for (n1=0;n1<8;n1++) {
printw("\n");
for (n2=0;n2<8;n2++) {
if(b[n2][n1]==EMPTY) printw(" -");
else printw(" %d",n2+1); }}
printw("\n");
printw("\n number of moves = %d ",moves);
printw("\n conflicts = ");
for (n1=0;n1<8;n1++) printw("%d ",check_front(n1));
printw("\n\n\n");}
int check_front(int n){
int n1,n2,kicks=0;
for(n1=0;n1<n;n1++) kicks+=b[n1][q[n]];
n1=n; n2=q[n];
while((n1>0)&&(n2<7)){
n1--; n2++; kicks+=b[n1][n2];}
n1=n; n2=q[n];
while((n1>0)&&(n2>0)){
n1--; n2--; kicks+=b[n1][n2];}
return(kicks); }
void vertical_move(int n){
b[n][q[n]]=EMPTY;
if(q[n]==7) q[n]=0; else q[n]++;
b[n][q[n]]=QUEEN;}
int queen(int n){
int n1=0;
if(n>7) return(SAFE);
do
{
if(check_front(n)==SAFE && queen(n+1)==SAFE)
return(SAFE); // recursion
vertical_move(n);
moves++; n1++;
clear();
show_board();
refresh();
usleep(50000);
} while(n1<8);
return(1); }
int main(int argc, char **argv){
int n1,n2;
initscr(); clear();
srandom(time(0));
for (n1=0;n1<64;n1++) b[n1/8][n1&7]=EMPTY;
for (n1=0;n1<8;n1++){
n2=rnd(7);
q[n1]=n2;
b[n1][n2]=QUEEN; }
show_board();
printw("Hit any key to start... \n");
refresh(); getch();
if(queen(0) == SAFE) // recurse queens!
printw("Finished..! \n");
else printw("Arrange Queens' funeral and Execute the programmer..!");
refresh();
getch();
endwin();
for(n1=1;n1<argc;n1++)
if(strcmp(argv[n1],"-c")==0) direct_draw_board();
return(SAFE);
}
 Click Here to Sponsor a Beer to the Author..! |