Software 1 - permut, queen (5)

administrivia

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

permut

Compute & print all the valid permutations of n numbers

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

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

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

  return  0;
}

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 (is_digit_used(nums, curr, digit))
      continue;

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

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;
}

permut.c

queen

Print all the solutions to the 8-queens problem

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

void print_board(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 is_invalid_placement(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;
}

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

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

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

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

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

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;
}

queen.c

Maintained by Efi Fogel. Last modified: March 26 2004.