A. First Edition

This is only a trivial test for assignment1 of comp6661--combinatorial algorithms.

B.The problem

Can the following partial filled latin square be completed into a latin square?
If yes, give one of the possible completions. If no, give an explanation.

1 2 3 4 5 6
2         3
3   4
4     5
5 6
6       2
　

　

C.The idea of program

　

I cannot think any better way except a brutal force search. 

In class, professor gave another way to solve it. It is an application of finding clique in a graph. 

For an example of latin square of size of three, there are six vectors like following:

(1,2,3), (1,3,2), (2,1,3),(2,3,1),(3,1,2)(3,2,1)

Some of them can be compatible in the sense that they can co-exist in a square. Some cannot. So, this kind of binary relation among six vectors

creates a graph and we are actually looking for a clique of size of three in this graph.

However, this is rather used as an example to illustrate the usage of clique than a practical way of finding latin square. (At least this is 

what I think.) Because the overhead of establishing the compatible relation of all permutations takes too long. Maybe the simple direct backtracking

search is more practical.

Of course this search for size of 6 is rather trivial.

D.The major functions

And the more interesting thing is that I am experimenting some idea I had in my mind. 

1. I am fed up with matrix type and try to use an array type to represent a matrix. However, I cannot initialize it.

i.e. 

typedef Vector size_t[6];

typedef Square Vector[6];

v1={1,2,3,4,5,6};

v2=...

...

v6={6,5,4,3,2,1};

Square square={v1,v2,v3,v4,v5,v6}; //here I got the compilation error that I cannot initialize it.

2. Another interesting thing is like this. Suppose you have a vector of size N and you know each tuple is filled with a number

between 1 to N and you want to make sure that there is no repeating tuples. i.e. the vector is a permutation number of 1 to N.

Is there any better way than using a bool array of size of N to check if each is flipped exactly once?

My idea is to use a mapping table to map number 1,2,3...N to the first N prime numbers so that I just check the product of 

all tuples in this vector. i.e.

2,3,5,7,11,13 are first six primes and their product is unique in the sense that the product of any six number of them is 

unique. Please note here I mean the combination of six number among these six number. i.e. 2,2,2,3,5,11 is one combination.

However, I didn't use this idea in this testing program.

I found this particular requirement in a couple of places like the "zebra puzzle" where all permutation of nationality, 

pets, drink etc need to be checked again and again.

3. At some point, I also want to change the recursion into an iteration. However, it is not so obvious to me. Now, I see

the way. I need the same number of space of recursive call to maintain the data in that space instead of using a function

call stack to bookkeeping data. i.e. I have to mimic the stack of function call.

E.Further improvement

F.File listing

1. main.cpp (main)

file name: main.cpp

#include <iostream>

using namespace std;

const size_t SquareSize=6;

typedef size_t Vector[SquareSize];

typedef Vector Square[SquareSize];

size_t primeMap[SquareSize]={2,3,5,7,11,13};

const size_t Checker=2*3*5*7*11*13;

Vector row0={1,2,3,4,5,6};
Vector row1={2,0,0,0,0,3};
Vector row2={3,0,4,0,0,0};
Vector row3={4,0,0,5,0,0};
Vector row4={5,6,0,0,0,0};
Vector row5={6,0,0,0,2,0};

//Square square={row0, row1, row2, row3, row4, row5};
Square square;
void copyVector(Vector& source, Vector& dest);

bool doFilling(size_t row, size_t col);
bool checkSquare();
bool checkRowCol(size_t index);

int main()
{
	size_t row=1, col=1;

	copyVector(row0, square[0]);
	copyVector(row1, square[1]);
	copyVector(row2, square[2]);
	copyVector(row3, square[3]);
	copyVector(row4, square[4]);
	copyVector(row5, square[5]);



	if (doFilling(row, col))
	{
		cout<<"print square\n";
		for (row=0; row<SquareSize; row++)
		{
			
			for (col=0; col<SquareSize; col++)
			{
				cout<<square[row][col]<<",";
			}
			cout<<"\n";
		}
	}


	return 0;
}

bool doFilling(size_t row, size_t col)
{
	size_t oldValue;
	
	if (row==SquareSize)
	{
		return true;
	}

	oldValue= square[row][col];

	for (size_t choice=1; choice<=SquareSize; choice++)
	{
		square[row][col]=choice;
		if (checkSquare())
		{
			if (col<SquareSize-1)
			{
				if (doFilling(row, col+1))
				{
					return true;
				}
			}
			else
			{
				if (doFilling(row+1, 1))
				{
					return true;
				}
			}
		}
	}
	//restore
	square[row][col]=oldValue;
	return false;
}

bool checkRowCol(size_t index)
{
	bool rowFlag[SquareSize], colFlag[SquareSize];
	size_t i;
	for (i=0; i<SquareSize; i++)
	{
		rowFlag[i]=true;
		colFlag[i]=true;
	}
	for (i=0; i<SquareSize; i++)
	{
		//no repeat number
		if (square[index][i]!=0)
		{
			if (rowFlag[square[index][i]-1])
			{
				rowFlag[square[index][i]-1]=false;
			}
			else
			{
				return false;
			}
		}
		if (square[i][index]!=0)
		{
			if (colFlag[square[i][index]-1])
			{
				colFlag[square[i][index]-1]=false;
			}
			else
			{
				return false;
			}
		}
	}
	/*
	for (i=0; i<SquareSize; i++)
	{
		if (rowFlag[i]||colFlag[i])
		{
			return false;
		}
	}
	*/
	return true;
}

void copyVector(Vector& source, Vector& dest)
{
	for (size_t i=0; i<SquareSize; i++)
	{
		dest[i]=source[i];
	}
}
		

bool checkSquare()
{
	if (square[1][5]!=3||square[2][2]!=4
		||square[3][3]!=5||square[4][1]!=6||square[5][4]!=2)
	{
		return false;
	}
	for (size_t index=0; index<SquareSize; index++)
	{
		if (!checkRowCol(index))
		{
			return false;
		}
	}
	return true;
}




			

	

The result is like following:

print square
1,2,3,4,5,6,
2,1,5,6,4,3,
3,5,4,2,6,1,
4,3,6,5,1,2,
5,6,2,1,3,4,
6,4,1,3,2,5,
Press any key to continue