4 Queens Use a 4 x 4 chess board. Show the complete hand execution diagrams for the main and build functions. Show the calls to cellok as boxes, but you can omit the code details inside cellok, instead, just use your brain and the rules of chess to manually determing the return value from cellok. Execute the algorithm completely for a 4x4 chess board so that it finds all possible solutions.

int sol[5]; // global solution stack. ignore cell 0

void printsolution(void)

{

for (int i = 1; i < 5; i++)

printf("%d ,", sol[i]);

printf(" ");

}

bool cellok(int n)

{

int i;

// check for queens on other rows

for (i = 1; i < n; i++)

if (sol[i] == sol[n])

return false;

// check for queens on diagonals

for (i = 1; i < n; i++)

if ((sol[i] == (sol[n] - (n - i))) || (sol[i] == (sol[n] + (n - i))))

return false;

return true;

}

void build(int n)

{

int p = 1;

// loop while there are more possible moves

while (p <= 4) {

// Store this move

sol[n] = p;

// Check if cell is okay

if (cellok(n))

// is this the last column?

if (n == 4)

printsolution();

else

build(n + 1); // get the next move

p++;

}

}

void main(void)

{

build(1);

}