The Eight Queens

29Mar13

In the twelve months from March 2013 to March 2014, I programmed solutions to the problems posted on the Contest Coding blog run by Lewis Cornwall, solving 33 problems (out of 47) and achieving a position of 4th on the leaderboard (out of 23).

As that blog has now been discontinued, I’m posting here the solutions I programmed to those problems.

The Eight Queens

The Eight Queens Puzzle is as follows: position 8 queens on an 8×8 chessboard so that no two queens threaten each other (no two queens appear on the same row, column or diagonal as each other). Solve the Eight Queens Puzzle.

Solution and answer (The Eight Queens.c):

Includes: seal_bool, printDateAndTime.

/*
Solution and answer for problem "The Eight Queens" (29th March 2013) of http://ContestCoding.WordPress.com/

Fri Mar 29 09:00:00 2013

Q.......
....Q...
.......Q
.....Q..
..Q.....
......Q.
.Q......
...Q....

Fri Mar 29 09:00:05 2013

Solution programmed in C using Leonardo IDE 3.4.1; solution took ~5s to run on a 80MHz PowerPC 601.
*/

#include "seal_bool.h"
#include "printDateAndTime.h"
#include <stdio.h>

#define k_WIDTH 8
#define k_HEIGHT 8

static bool g_board[ k_WIDTH ][ k_HEIGHT ];

bool f_AnyQueenThreatensAnother( const short p_y );

bool f_Solve( const short p_y )
{
  short x = 0;
  for( ; x < k_WIDTH; x ++ )
  {
    g_board[ x ][ p_y ] = true;
    if( !f_AnyQueenThreatensAnother( p_y ))
    {
      if( p_y == k_HEIGHT - 1 )
        return true;
      if( f_Solve( p_y + 1 ))
        return true;
    }
    g_board[ x ][ p_y ] = false;
  }
  return false;
}

bool f_AnyQueenThreatensAnother( const short p_y )
{
  short x = 0, y, n, start_y, start_x;

  // Test if there are >1 Queens in a column.
  for( ; x < k_WIDTH; x ++ )
    for( y = 0, n = 0; y <= p_y; y ++ )
      if( g_board[ x ][ y ] )
        if( ++ n > 1 )
          return true;

  // Test if there are >1 Queens diagonally (down-right).
  for( start_y = 0; start_y < p_y; start_y ++ )
    for( start_x = 0; start_x < k_WIDTH - 1; start_x ++ )
      for( x = start_x, y = start_y, n = 0; (( x < k_WIDTH ) && ( y <= p_y )); x ++, y ++ )
        if( g_board[ x ][ y ] )
          if( ++ n > 1 )
            return true;

  // Test if there are >1 Queens diagonally (down-left).
  for( start_y = 0; start_y < p_y; start_y ++ )
    for( start_x = k_WIDTH - 1; start_x > 0; start_x -- )
      for( x = start_x, y = start_y, n = 0; (( x >= 0 ) && ( y <= p_y )); x --, y ++ )
        if( g_board[ x ][ y ] )
          if( ++ n > 1 )
            return true;

  return false;
}

void p_PrintBoard( void )
{
  short x, y = 0;
  for( ; y < k_HEIGHT; y ++ )
  {
    for( x = 0; x < k_WIDTH; x ++ )
      printf( "%c", (( !g_board[ x ][ y ] )?'.':'Q' ));
    printf( "\n" );
  }
}

void main( void )
{
  short x, y = 0;

  p_PrintDateAndTime();
  printf( "\n" );

  for( ; y < k_HEIGHT; y ++ )
    for( x = 0; x < k_WIDTH; x ++ )
      g_board[ x ][ y ] = false;
  if( f_Solve( 0 ))
    p_PrintBoard();

  printf( "\n" );
  p_PrintDateAndTime();
}
Advertisements


No Responses Yet to “The Eight Queens”

  1. Leave a Comment

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


%d bloggers like this: