ISourceCode

Make the frequent cases fast and the rare case correct

Monthly Archives: January 2011

N-Queens Problem

Problem statement : Need to place n queens on a nxn chessboard in such a way that no queen is attacked by another.

Good example of recursion and backtracking

Algorithm:

InsertQueen(row)
    for every position col on the same row
       if position col is available
       place the next queen in position col;
       if (row < n)
          InsertQueen (row+1);
       else success;
       remove the queen from position col;

Implementation : C for 4×4 replace dimension with any number.

#include "stdio.h"

#define available 1
#define dimension 4 // 4-queen problem
#define norm dimension-1

int Column[dimension], PositionInRow[dimension], count = 0;
int LeftDiagonal[dimension*2 - 1]; //contains 6 elements for 4x4 board below the diagonal
int RightDiagonal[dimension*2 - 1];//contains 6 elements for 4x4 board above the diagonal

void PrintBoard()
{   int col, row;

    for (row = 0; row < dimension; row++) {
	for (col = 0; col < PositionInRow[row]; col++)
	    putchar('.');
	putchar('$');
	for (col = PositionInRow[row] + 1; col < dimension; col++)
	    putchar('.');
	putchar('\n');
    }
    putchar('\n');
    count++;
}

void InsertQueen(int row)
{   int col;

    for (col = 0; col < dimension; col++)
	if (Column[col] == available && LeftDiagonal[row+col] == available && RightDiagonal[row-col+norm] == available)
	{
	    PositionInRow[row] = col;
	    Column[col] = !available;
	    LeftDiagonal[row+col] = !available;
	    RightDiagonal[row-col+norm] = !available;
	    if (row < dimension-1)
		 InsertQueen(row+1);
	    else PrintBoard();
	    Column[col] = available;
	    LeftDiagonal[row+col] = available;
	    RightDiagonal[row-col+norm] = available;
	}
}

int main()
{
    int i;

    for (i = 0; i < dimension; i++)
	PositionInRow[i] = -1;
    for (i = 0; i < dimension; i++)
	Column[i] = available;
    for (i = 0; i < dimension*2 - 1; i++)
	LeftDiagonal[i] = RightDiagonal[i] = available;
    InsertQueen(0);
    printf("%d solutions found\n",count);
    return 0;
}

OUTPUT:

laptop:~$ ./a.out
.$..
…$
$…
..$.

..$.
$…
…$
.$..

2 solutions found

The board is considered in this manner:
4×4 board

(0,0)| (0,1) | (0,2) | (0,3)
———————————-
(1,0)| (1,1) | (1,2) | (1,3)
———————————
(2,0)| (2,1) | (2,2) | (2,3)
———————————
(3,0)| (3,1) | (3,2) | (3,3)

First successful Board

(Moveno) | Queen | row | col
————————————–
(1) 0 0 0
(2) 2 1 2 — fail
(3) 2 1 3
(4) 3 2 1 — fail
(5) 1 0 1
(6) 2 1 3
(7) 3 2 0
(8) 4 3 2

Below is a Image of 8- queen problem – courtesy wikipedia
Click on image to see a simulation.

classic computer science problem with complete description available on Wikipedia . Also there are numerous articles and implementations on the Internet.

The no of solutions for a 8×8 board is 92.

This one had to be in a algorithms blog.

Thanks for Reading !

Ferrers Partitions which are Palindromes

Firstly, Information about Ferrers diagram can be found in this previous article

A recursively palindromic (RP) word is one that is a palindrome and whose left
half-word and right half-word are each RP. Thus ABACABA is, and MADAM is not,
an RP word. – quoted from this Paper .

The objective of this puzzle is to find the total number of RP that can be formed from the integer partitions of a number
For example:
for number = 4
Ferrers Diagram

4 = 1+1+1+1
4 = 2+1+1
4 = 2+2
4 = 3+1
4 = 4

The total no of the RP partitions are 4
4
1+1+1+1
2+2
1+2+1

Note: every integer > 1 has at least two recursively palindromic partitions one consisting of all ones and a second consisting of the integer itself

Algorithm 1:

1 . Construct the Ferrer Diagram using the algorithm used in this article

2. For all Ferrers Partitions

3. Send every partition values to a function called PossiblePalindrome described in this article.

4. If successful, increment a counter

Algorithm 2:

1. F(N) is the no of RP’s of N

2. if N is even, put any even number K <= N in the center and then a RP partition of (N-K)/2 on either side so

F(N) = 1 + F(2) + … + F(N/2) = F(N-2) + F(N/2) (1 is the case where K = N)

3.if N is odd, put any odd number K <= N in the center and then RP partition of (N-K)/2 on either side so

F(N) = 1 + F(2) + … + F((N-1)/2) = F(N-1) (1 is the case where K = N)

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

int array[100];
int max;

int PalindromePartition(int val)
{
	int i;
	if(val <= max)
	{
		return array[val];
	}
	for(i = max+1; i <= val; i++)
	{
		if((i & 1) != 0)
		{
			array[i] = array[i-1];
		}
		else
		{
			array[i] = array[i-2] + array[i/2];
		}
	}
	max = val;
	return array[val];
}
int main()
{
	int num;
	printf("Enter the Number:\n");
	scanf("%d",&num);
	array[0] = array[1] = 1;
	max = 1;
	PalindromePartition(10);//compute for until 10 or any number
	printf("The total number of possible Palindrome partitions are %d\n",array[num]);
	return 0;
}

OUTPUT:

laptop:~/code$ ./a.out
Enter the Number:
7
The total number of possible Palindrome partitions are 6

Look at ferrers table for 7

7 = 1+1+1+1+1+1+1
7 = 2+1+1+1+1+1
7 = 2+2+1+1+1
7 = 2+2+2+1
7 = 3+1+1+1+1
7 = 3+2+1+1
7 = 3+2+2
7 = 3+3+1
7 = 4+1+1+1
7 = 4+2+1
7 = 4+3
7 = 5+1+1
7 = 5+2
7 = 6+1
7 = 7

It is evident visually that from these 15 partitions only 6 are RP.

7, 1+5+1, 2+3+2, 1+1+3+1+1, 3+1+3, 1+1+1+1+1+1+1

It would be interesting to implement a function to print the RP in a formatted manner.

Thanks for Reading !

Integer Partition and Ferrers Diagram

This article is intended to give introduction to integer partitioning problem, with numerous reading material, code and explanation aggregated from various Internet sources.

In number theory, a partition of a positive integer n, also called an integer partition, is a way of writing n as a sum of positive integers. Two sums that differ only in the order of their summands are considered to be the same partition; if order matters then the sum becomes a composition. A summand in a partition is also called a part. The number of partitions of n is given by the partition function p(n). – Wikipedia

Partition of number 4:

1. 4

2. 3 + 1

3. 2 + 2

4. 2 + 1 + 1

5. 1 + 1 + 1 + 1

A generating function for p(n) is given by the reciprocal of Euler’s function:

Expanding each term on the right-hand side as a geometric series, we can rewrite it as (1 + x + x^2 + x^3 + …)(1 + x^2 + x^4 + x^6 + …)(1 + x^3 + x^6 + x^9 + …) ….

The number of partitions p(n) is the coefficient of x^n in the expansion of
(1 + x + x^2 + x^3 + …)(1 + x^2 + x^4 + x^6 + …)(1 + x^3 + x^6 + x^9 + …) ….

The objective of this article is to look into the implementation of generating this ferrer’s diagram

Some more Additional Reading:
1 . From Numericana
2 . About Ferrers Diagram
3. An interesting paper that talks about fast algorithms for generating integer partitions.

Thus with these concepts code below displays a Ferrer’s diagram for a given input number and also generate the table using the generate function

#include<stdio.h>
#include<stdlib.h>
#define false 0;
#define true 1;
#define Min(x,y) ((x<y)?x:y)
typedef struct partitionnode
{
 int m;
 int numparts;
 int parts[101];
} partition;

int Pn[40][40];
int P[50];

void output(partition a)
/*print out the partition a*/
{
 int i,j;
 printf("%d = ",a.m);
 for(i=1;i<=a.numparts;i=i+1)
 {
 j = a.parts[i];
 printf("%d",j);
 if (i != a.numparts)
 printf("+");
 }
}

void RecPartition(partition a, int m, int B, int N)
/** generate all partitions with largest part of size at most B
**  recursive procedure used in other procedures
*/
{
 int i;
 if(m==0)
 {
 a.numparts = N;
 output(a); printf("\n");
 }
 else
 {
 for (i=1;i<=Min(B,m);i=i+1)
 {
 a.parts[N+1] = i;
 RecPartition(a,m-i,i,N+1);
 }
 }
}

void GenPartitions(int m)
/*generate all partitions of m*/
{
 partition a;
 a.m =  m;
 RecPartition(a,m,m,0);
}

void EnumPartitions2(int m)
/*compute the partition numbers P[i] for i <= m*/
{
 int i,j,sum,omega,omega2,sign;
 P[0] = 1;
 P[1] = 1;
 for (i=2;i<=m;i=i+1)
 {
 sign = 1;
 sum = 0;
 omega = 1;
 j = 1;
 omega2 =  omega+j;
 while(omega <= i)
 {
 if(sign==1)
 sum =  sum + P[i-omega];
 else
 sum =  sum - P[i-omega];
 if(omega2 <= i)
 {
 if(sign==1)
 sum =  sum + P[i-omega2];
 else
 sum =  sum - P[i-omega2];
 }
 omega =  omega + 3*j+1;
 j = j+1;
 omega2 =  omega+j;
 sign =  0 - sign;
 }
 P[i] =  sum;
 }
}

int main()
{
 int m,n,i,j,r,s,num;
 int flag;
 partition a;
 char junk;
 printf("Enter the Number : \n");
 scanf("%d",&m);
 printf("Ferrers Diagram with m=%d\n\n",m);
 GenPartitions(m);
 printf("\nEnd of Ferrers.  Press enter to get the table\n"); scanf("%c",&junk);

 printf("Table with all possible combinations with m=%d \n\n",m);
 EnumPartitions2(m);
 printf("  i  |"); for(i=1;i<=m;i=i+1) printf("%5d",  i ); printf("\n");
 printf("-----|"); for(i=1;i<=m;i=i+1) printf("-----"); printf("\n");
 printf("P[i] |"); for(i=1;i<=m;i=i+1) printf("%5d",P[i]); printf("\n");
 printf("\nPress Enter to Exit\n"); scanf("%c",&junk);

 return(0);
}

I have made minor modification to code already available here . The main intention here is only educational. I was unable to identify the exact author here and give author due credit.

OUTPUT:

laptop:~/code$ ./a.out
Enter the Number :
4
Ferrers Diagram with m=4

4 = 1+1+1+1
4 = 2+1+1
4 = 2+2
4 = 3+1
4 = 4

End of Ferrers. Press enter to get the table
Table with all possible combinations with m=4

i | 1 2 3 4
—–|——————–
P[i] | 1 2 3 5

Press Enter to Exit

laptop:~/code$ ./a.out
Enter the Number :
7
Ferrers Diagram with m=7

7 = 1+1+1+1+1+1+1
7 = 2+1+1+1+1+1
7 = 2+2+1+1+1
7 = 2+2+2+1
7 = 3+1+1+1+1
7 = 3+2+1+1
7 = 3+2+2
7 = 3+3+1
7 = 4+1+1+1
7 = 4+2+1
7 = 4+3
7 = 5+1+1
7 = 5+2
7 = 6+1
7 = 7

End of Ferrers. Press enter to get the table
Table with all possible combinations with m=7

i | 1 2 3 4 5 6 7
—–|———————————–
P[i] | 1 2 3 5 7 11 15

For Perl coders:
There exists a Integer::Partition module. It implements two algorithms from this paper

For Python coders:
There exists an active state discussion

I had a good learning session , hope you did. Hope this article has provided a one stop resource on this topic.

Thanks for Reading !

Algorithm to check if a number can be rearranged to form a Palindrome

This is a slight modification of the Palindrome check question.

Can a number be arranged in such a way to form a palindrome:
Algorithm:
1. Find out the occurrence of each character
2. Only one character with odd occurrence is allowed because in a palindrome maximum number of character with odd occurrence can be 1
3. All other character should occur for even number of times
4. If condition 1, 2 and 3 does not satisfy then palindrome is not possible out of the string.

This approach was used for finding if a string is anagram of another string

#include<iostream>
using namespace std;

bool PossiblePal(char *s)
{
         int array[256]={0}, Odd=0;
  
         //Refer to anagram article similar approach is used
         while(*s!='\0')
         {
           array[(int)*s]+=1;
           s++;
         }
         
         for(int i=0;i<256;i++)
         {
           //On encountering character with odd occurance
           if(array[i]%2!=0 && Odd==0)
             Odd=1;
           //If one more charcter with odd occurances
           else if(array[i]%2!=0 && Odd==1)
             return false;
         }
  
         return true;
}
 
int main()
{
         char str[100];
         cout<<"\nEnter the Number to be checked :\n";
         cin.getline(str, 100);
         if(PossiblePal(str))
           cout<<"Palindrome is possible \n";
         else
           cout<<"Palindrome is NOT possible \n";
  
         return 0;
}

OUTPUT:

laptop:~/code$ ./a.out

Enter the Number to be checked :
1144
Palindrome is possible

laptop:~/code$ ./a.out

Enter the Number to be checked :
11133
Palindrome is possible

laptop:~/code$ ./a.out

Enter the Number to be checked :
123
Palindrome is NOT possible

Algorithm to check if a number is Palindrome

This is a standard question in computer science, extended to Strings as well.

There are numerous ways to accomplish this. In this article i will show you a recursive procedure. This article will be updated in future with implementation of several approaches, for now this article is a preface to some articles that i will be writing and i felt i need to get this basic palindrome question before diving into some other concepts in number theory.

Algorithm in the code is self explanatory

#include<stdio.h>
int pal=0; 
int Palindrome(int num)
{
	if(num>0)
	{
 		pal=(pal*10)+ (num %10);
 		Palindrome(num / 10); //recursion.        
	}
	return pal;       
}
int main()
{
	int num;
	printf("Enter a number \n");
	scanf("%d",&num);
	if(num==Palindrome(num))
	printf("Number is a Palindrome\n");	
	else
	printf("Not a palindrome\n");
	return 0;   
}

OUTPUT:
laptop:~/code$ ./a.out
Enter a number
123
Not a palindrome

laptop:~/code$ ./a.out
Enter a number
11
Number is a Palindrome

Also in future i will talk about palindrome implementation with Linked Lists.

Watch this space !

Follow

Get every new post delivered to your Inbox.