Software 1 - permut, queen (6)

administrivia

Web Page - http://www.cs.tau.ac.il/~efif/courses/Software1_Spring_03

permut

/*
 * permut.C -
 * Compute & print all the valid permutations of n numbers.
 */

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

int isDigitUsed(int nums[], int  size, int  digit);

int permut(int nums[], int curr, int n)
{
  int ind, digit, count;

  assert(0 <= curr && curr <= n);

  if (curr == n) {
    for (ind = 0; ind < n; ind++) 
      printf("%d", nums[ind]);
    printf("\n");
    return 1;
  }

  count = 0;
  for (digit = 1; digit <= n; digit++) {
    if (isDigitUsed(nums, curr, digit))
      continue;

    nums[ curr ] = digit;
    count += permut( nums, curr + 1, n );
  }
  return  count;
}

int isDigitUsed(int nums[], int size, int digit)
{
  int ind;

  for (ind = 0; ind < size; ind++)
    if (nums[ind] == digit)
      return 1;

  return  0;
}

int main()
{
  int num, count, nums[40];

  num = 3;
  count = permut(nums, 0, num);

  printf("Computed all the permutations of %d numbers.\n"
         "There are %d such permutations.\n", num, count);

  return  0;
}

queen

/*
 * queen.C -
 *     Print all the solutions to the 8-queens problem.
 */

#include <stdlib.h>
#include <stdio.h>
#include <assert.h>

void printBoard(int nums[], int size);
int isInvalidPlacement(int nums[], int curr_row, int new_pos);

int queen(int nums[], int curr_row, int n)
{
  int  new_pos, count;

  assert(0 <= curr_row && curr_row <= n);

  if (curr_row == n) {
    printBoard(nums, n);
    return  1;
  }

  count = 0;
  for (new_pos = 1; new_pos <= n; new_pos++) {
    if (isInvalidPlacement(nums, curr_row, new_pos))
      continue;

    nums[curr_row] = new_pos;
    count += queen( nums, curr_row + 1, n );
  }
  return  count;
}

int isInvalidPlacement(int nums[], int curr_row, int new_pos)
{
  int ind;

  for (ind = 0; ind < curr_row; ind++) {
    if (nums[ind] == new_pos)
      return 1;
    if (abs(nums[ind] - new_pos) == (curr_row - ind)) 
      return 1;
  }

  return 0;
}

void printBoard(int nums[], int size)
{
  int  ind, jnd;

  for (ind = 0; ind < size; ind++) {
    for (jnd = 1; jnd <= size; jnd++)
      printf("%c", (jnd == nums[ind]) ? '1' : '0');
    printf("\n");
  }

  printf("\n");
}

int main()
{
  int num, count, nums[40];

  num = 8;
  count = queen(nums, 0, num);

  printf("Computed all the valid placements of queens on"
         " boards of size %dx%d.\n"
         "There are %d such solutions.\n", num, num, count);

  return  0;
}

Maintained by Efi Fogel. Last modified: March 20 2003.