I was writing a computer program version of an old South Indian mathematical strategy game known as *Pallankuzhi* and it was then that I faced the problem of how to create a computer player that would play the game. While I have not made much headway into that yet (have to read more about graphs and linking boards with similar configurations), I decided to revisit Tic Tac Toe.

While I have written a program in the past (with a computer vs. human and computer vs. computer option), I had not paid much attention to the theory of using brute force. A question like how many (legal and illegal) games are there and how to enumerate them did not cross my mind then. I don’t think such a question ever comes up in normal software programming. I thought over the problem for a couple of days and finally came up with something. While it is not the most efficient implementation, it does the job.

The code is more or less self explanatory. But let me explain the logic behind it anyway. Consider a string ‘abcd’. Since there are four elements, there are 4! (read four factorial) different permutations = 4*3*2*1 = 24. I use i, j, k and l as indices into the string and the permutations are as follows.

abcd (i = 0, j = 1, k = 2, l = 3)

abdc (i = 0, j = 1, k = 3, l = 2)

acdb (i = 0, j = 2, k = 3, l = 1)

acbd (i = 0, j = 2, k = 1, l = 3)

adbc (i = 0, j = 3, k = 1, l = 2)

adcb (i = 0, j = 3, k = 2, l = 1)

bcda (i = 1, j = 2, k = 3, l = 0)

bcad (i = 1, j = 2, k = 0, l = 3)

bdac (i = 1, j = 3, k = 0, l = 2)

bdca (i = 1, j = 3, k = 2, l = 0)

bacd (i = 1, j = 0, k = 2, l = 3)

badc (i = 1, j = 0, k = 3, l = 2)

cdab (i = 2, j = 3, k = 0, l = 1)

cdba (i = 2, j = 3, k = 1, l = 0)

cabd (i = 2, j = 0, k = 1, l = 3)

cadb (i = 2, j = 0, k = 3, l = 1)

cbda (i = 2, j = 1, k = 3, l = 0)

cbad (i = 2, j = 1, k = 0, l = 3)

dabc (i = 3, j = 0, k = 1, l = 2)

dacb (i = 3, j = 0, k = 2, l = 1)

dbca (i = 3, j = 1, k = 2, l = 0)

dbac (i = 3, j = 1, k = 0, l = 2)

dcab (i = 3, j = 2, k = 0, l = 1)

dcba (i = 3, j = 2, k = 1, l = 0)

As expected, a pattern emerges (note that I am using positive modular arithmetic where 0 – 1 = 3 in this case as the figures are mod 4).

- i goes from 0 to 3.
- Within each section of size 6 where i remains constant, j goes from i + 1 to i – 1.
- Within each section of size 2 where j remains constant, k goes from j + 1 to the first ‘non i’ j – 1.
- And, finally, within each section of size 1 where k remains constant, l will be the first ‘non i’, ‘non j’ k + 1 or k – 1 which are the same.

Put this information into a recursive function and you have your algorithm.

Some good links which discuss permutations in depth and also provide better algorithms –

Bear Cave: Calculating Permutations

Permutation Algorithms Using Iteration and the Base-N-Odometer Model (Without Recursion)

Also, an analysis of Tic Tac Toe.

## Comments

sir, kindly gimme t c progarm for Pallankuzhi permutation………………….