//----------------------------------------------------------------------
// enigma1367.c (c) 2005 by Charles Petzold
//
// "Roman Ladder" by Adrian Somerfield, New Scientist, 19 November 2005
//----------------------------------------------------------------------

#include <stdio.h>
#include <string.h>

// Of course we need a function to convert Arabic numbers to Roman.
// A character string of sufficient length is required.
// The 'roman' array is filled with least-significant digit first.
// Only good for < 50.
void ArabicToRoman(int num, char roman[])
{
	int digits = num % 10;
	int tens = num / 10;
	int ones = num % 5;
	int i, index = 0;

	if (ones == 4)
	{
		roman[index++] = digits > 5 ? 'X' : 'V';			
		roman[index++] = 'I';
	}
	else
	{
		for (i = 0; i < ones; i++)
			roman[index++] = 'I';

		if (digits >= 5)
			roman[index++] = 'V';
	}
	for (i = 0; i < tens; i++)
		roman[index++] = 'X';

	roman[index] = '\0';
}

// And, for consistency checking we need to convert Roman numerals to Arabic.
// The 'roman' array is most-significant first.
int RomanToArabic(char roman[])
{
	int i, num = 0, noMoreV = 0, noMoreX = 0, subtractive = 0, noSubtractive = 0;

	for (i = 0; i < strlen(roman); i++)
	{
		if (roman[i] == 'X')
		{
			if (subtractive)
				num -= 2;

			else if (noMoreX)
				break;

			num += 10;
		}
		else if (roman[i] == 'V')
		{
			if (subtractive)
				num -= 2;

			else if (noMoreV)
				break;

			noMoreX = 1;
			noMoreV = 1;
			num += 5;
		}
		else if (roman[i] == 'I')
		{
			noMoreX = noMoreV = 1;

			if (i < strlen(roman) - 2)
				noSubtractive = 1;

			subtractive = !noSubtractive && (i == strlen(roman) - 2);
			num += 1; 
		}				
	}

	if (i != strlen(roman))
		num = -1;

	if (num > 48)
		num = -1;

	return num;
}

// This is the recursive function. The 'ladder' array is a 6 by 6 character array.
// y is the row (from 0 to 5), and haveEven is 1 if a previous row is even.
// Returns 1 if all is well, and 0 otherwise.
int Try(char ladder[][6], int y, int haveEven)
{
	char roman[10];
	int num, i, x, isEven;

	// If we now have all 6 rows, it's time to tally
	//	the number of matches between rows and columns.
	// There must be one and only one match.
	if (y == 6)
	{
		char row[7], col[7];
		int rc, matches = 0;

		for (rc = 0; rc < 6; rc++)
		{
			// Convert the ladder row to a string.
			for (i = 0; i < 6 - rc; i++)
				row[i] = ladder[rc][i];

			row[i] = '\0';

			// Ditto for the column.
			for (i = 0; i < 6 - rc; i++)
				col[i] = ladder[i][rc];

			col[i] = '\0';

			// If they're the same, increment 'matches'
			if (RomanToArabic(row) == RomanToArabic(col))
				matches++;
		}
		// Return success only if 'matches' equals 1
		return matches == 1;						
	}

	// Loop through the possible numbers.
	for (num = 1; num < 50; num++)
	{
		// Convert the number to Roman.
		ArabicToRoman(num, roman);

		// Check if the Roman numeral is the right length
		if (strlen(roman) != 6 - y)
			continue;

		// Check that there's only one even row
		isEven = 0 == (num & 1);

		if (haveEven & isEven)
		{
			continue;
		}

		// Check that all the letters appear in the row above it
		if (y > 0)
		{
			for (i = 0; i < 6 - y; i++)
			{
				for (x = 0; x < 7 - y; x++)
					if (roman[i] == ladder[y - 1][x])
						break;
				if (x == 7 - y)
					break;
			}
			if (i != 6 - y)
			{
				continue;
			}
		}

		// Transfer it to the ladder array
		for (x = 0; x < 6 - y; x++)
			ladder[y][x] = roman[5 - y - x];

		// Check if the column is a correct Roman numeral
		if (y > 0)
		{
			char column[7];
			int arabic;

			for (i = 0; i < y + 1; i++)
				column[i] = ladder[i][5 - y];

			column[i] = '\0';

			arabic = RomanToArabic(column);

			if (arabic == -1)
			{
				continue;
			}
		}

		if (Try(ladder, y + 1, haveEven | isEven))
			return 1;
	}
	return 0;
}



int main(void)
{
	char ladder[6][6];
	char roman[10];
	int num, x, y;

	// Call the recursive function
	if (Try(ladder, 0, 0))
	{
		for (y = 0; y < 6; y++)
		{
			for (x = 0; x < (6 - y); x++)
				printf("%c ", ladder[y][x]);

			printf("\n");
		}
	}
	return 0;
}