Solve this Latino puzzle: fill a 6x6 grid with the numbers 1 to 6 so that each row and column contains one...
logic/latino New
New entry, edited from material collected for the archive and not yet in a released version.
Problem
Solve this Latino puzzle: fill a 6x6 grid with the numbers 1 to 6 so
that each row and column contains one of each number, given these sums.
In a Latino puzzle, you are to fill a 6x6 grid with numbers from 1 to 6
so that each row and column contains one of each number (i.e., no
repetitions in a row or in a column). The clues give you the sum of
some two or three in a row. Use labels A-F across the bottom, 1-6 up
the side. For example, if ABC3 = 9 were a clue, that would mean that
A3 + B3 + C3 adds up to 9.
Puzzle 2:
Clues: A12 = 6 A56 = 7 AB4 = 6 BC1 = 6 B23 = 9
BCD5 = 8 D12 = 7 DEF6 = 7 E123 = 11 F45 = 8
[An NxN square in which each row and each column contains the same N
distinct symbols is called a "Latin Square"]
-- Stitch <SWILSON@nauvax.nau.ucc.edu>, October 1994
Show solution
6| 3 5 6 2 1 4
5| 4 1 2 5 6 3
4| 2 4 1 6 3 5
3| 6 3 5 1 4 2
2| 5 6 3 4 2 1
1| 1 2 4 3 5 6
------------
A B C D E F
-- David M. Tuller <tulled@rpi.edu>, October 1994
[ Editor: a Latino solver mailed to Chris Cole by Jim Gillogly in
October 1994, with his covering note, copied in full. ]
I append my Latino solver, which I've cleaned up a bit. It appears to
work for 6x6 and 7x7. Smaller sizes would be a trivial mod, and larger
ones would depend on available memory, since I use arrays up to N!. It
works on both a Sun Sparc II and my PC running Linux, using gcc. Oddly
enough, the PC (a 486 DX2/40 laptop) runs faster on this problem than
the Sparc II by about 30%, even though it theoretically has only half
the horsepower.
Have you seen Matthew Day's permutation algorithm before? Cute hack!
If this were an ACA cipher type I'd hesitate to make it generally
available, since in some sense solving is a competition and people
resent competing with others running a tool to solve a cipher they
don't even understand. I gather from what Dave said that this is a
puzzle used in the NPL; if solving there is structured as a
competition, you might want to take advice on whether it would be spoil
the fun for people if it were in the archive.
_____________________________snip_________________________________________
/* Solve a Latino puzzle.
*
* Usage: latino [-7] < cluefile
* Clues are one per line, looking like
* ABC3 = 8
*
* It deals with 6x6 squares by default, 7x7 by flag. Other sizes require
* minor code changes.
*
* SCRYER, Oct 94
*/
#include <stdio.h>
#include <ctype.h>
#define MAXCLUES 100 /* How many clues can we have? */
#define BUFLEN 100 /* Clues may be 10 bytes or so */
typedef unsigned char uchar;
int nclues; /* How many clues were there really? */
#define MAXSQUARE 7 /* How big is the square? (6 or 7 supported) */
#define MAXPERMS 5040 /* 720 used for a 6x6 square */
uchar perm[MAXPERMS][MAXSQUARE+1]; /* ascii from 1 to '6'/'7' */
int nperms = 0; /* Will end up 720 or 5040 */
int square = 6; /* Default size; overridden with a flag */
int rows[MAXSQUARE][MAXPERMS], cols[MAXSQUARE][MAXPERMS];
int nrows[MAXSQUARE], ncols[MAXSQUARE]; /* How many perms still possible? */
#define ROW 0
#define COL 1
#define YES 1
#define NO 0
struct cluestruct
{
uchar rc; /* ROW if row, COL if col */
uchar index; /* 0-5/6 for row or column 1-6/7 */
uchar elements[MAXSQUARE]; /* Up to 6/7 in the sum, each 0-5/6 */
uchar nelements; /* Typically 2-4 */
uchar target; /* What sum are we looking for? */
} clues[MAXCLUES];
int nclues = 0; /* How many clues are there? */
void readclues();
void permute();
void validity_check(), row_select();
main(int argc, char **argv)
{
int i, j, x, y;
uchar *s;
char buff[BUFLEN];
int restriction;
if (argc > 1)
{
if (strcmp(argv[1], "-7") != 0)
{
fprintf(stderr, "Usage: latino [-7] < cluefile\n");
return 1;
}
square = 7;
permute("1234567", 0);
}
else permute("123456", 0);
printf("%d permutations\n", nperms);
for (i = 0; i < square; i++)
{
nrows[i] = ncols[i] = nperms; /* All things are possible */
for (j = 0; j < nperms; j++)
rows[i][j] = cols[i][j] = j;
}
while (fgets(buff, BUFLEN, stdin) != NULL) /* Parse the clues */
{
struct cluestruct *p = &clues[nclues++];
char *s;
if (isdigit(buff[1])) /* Only one letter */
{
p->rc = COL;
p->index = buff[0] - 'A';
for (p->nelements = 0, s = &buff[1]; isdigit(*s); s++)
p->elements[p->nelements++] = *s - '1';
while (!isdigit(*s)) s++; /* Scan to target */
p->target = atoi(s);
}
else
{
p->rc = ROW;
for (p->nelements = 0, s = &buff[0]; isupper(*s); s++)
p->elements[p->nelements++] = *s - 'A';
p->index = *s++ - '1';
while (!isdigit(*s)) s++; /* Scan to target */
p->target = atoi(s);
}
}
printf("%d clues.\n", nclues);
/* Do some restrictions based on the cribs */
for (i = 0; i < nclues; i++)
{
struct cluestruct *p = &clues[i];
int *permp;
int *permn;
if (p->rc == ROW)
{
permp = &(rows[p->index][0]);
permn = &nrows[p->index];
}
else
{
permp = &(cols[p->index][0]);
permn = &ncols[p->index];
}
j = 0;
for (j = 0; j < *permn; )
{
if (vcheck(perm[permp[j]], p) == NO)
permp[j] = permp[--(*permn)];
else j++;
}
}
do
{
/* Repeat this next block until no further restriction */
restriction = NO;
for (x = 0; x < square; x++)
for (y = 0; y < square; y++)
{
int k, used[128];
for (k = '1'; k <= square + '0'; k++) used[k] = NO;
for (k = 0; k < nrows[y]; k++)
used[perm[rows[y][k]][x]] = YES;
/* Eliminate any column that uses a bad row character */
for (k = 0; k < ncols[x]; )
{
if (! used[perm[cols[x][k]][y]])
{
cols[x][k] = cols[x][--ncols[x]];
restriction = YES; /* Eliminated one */
}
else k++;
}
for (k = '1'; k <= square + '0'; k++) used[k] = NO;
for (k = 0; k < ncols[x]; k++)
used[perm[cols[x][k]][y]] = YES;
for (k = 0; k < nrows[y]; )
{
if (! used[perm[rows[y][k]][x]])
{
rows[y][k] = rows[y][--nrows[y]];
restriction = YES; /* Eliminated one */
}
else k++;
}
}
} while (restriction);
#ifdef VERBOSE
for (i = square - 1; i >= 0; i--)
for (j = 0; j < nrows[i]; j++)
printf("%d: %s\n", i + 1, perm[rows[i][j]]);
#endif
/* So now we might find out how many possibilities there <really> are. */
row_select(0); /* Assign everything for row 0 recursively */
}
uchar sq[MAXSQUARE][MAXSQUARE+1]; /* Workspace */
void row_select(int index)
{
/* Save the current state of all rows and columns so we can back up
* to here when we return.
*/
int trows[MAXSQUARE][MAXPERMS], tcols[MAXSQUARE][MAXPERMS]; /* Possible perms for each r/c */
int tnrows[MAXSQUARE], tncols[MAXSQUARE]; /* How many perms still possible? */
int i, j, k;
for (i = 0; i < square; i++)
{
tnrows[i] = nrows[i];
tncols[i] = ncols[i];
for (j = 0; j < nrows[i]; j++)
trows[i][j] = rows[i][j];
for (j = 0; j < ncols[i]; j++)
tcols[i][j] = cols[i][j];
}
/* processing row "index", and assigning everything from here up */
for (k = 0; k < nrows[index]; k++) /* The possibly-modified nrows */
{
strcpy(&sq[index][0], perm[rows[index][k]]); /* Try this one here */
while (pruning(index)); /* Prune rows/cols against square */
if (index == square - 1) validity_check(); /* Print if all OK */
else row_select(index + 1);
/* Now put the squares back where they were */
for (i = 0; i < square; i++)
{
nrows[i] = tnrows[i];
ncols[i] = tncols[i];
for (j = 0; j < tnrows[i]; j++)
rows[i][j] = trows[i][j];
for (j = 0; j < tncols[i]; j++)
cols[i][j] = tcols[i][j];
}
}
}
/* Code bloat: lots of overlap with initial clue-restriction code. Sue me. */
int pruning(int index) /* Prune columns and some rows against each other */
{ /* row "index" has been filled */
int i, x, y, pruned;
pruned = NO;
/* The new row "index" has been added to restrict columns and
* subsequent rows.
*/
for (x = 0; x < square; x++)
{
uchar fixed = sq[index][x]; /* This sucker is known */
int k;
/* Eliminate all columns that don't fit this element */
for (k = 0; k < ncols[x]; k++)
if (perm[cols[x][k]][index] != fixed)
{
cols[x][k] = cols[x][--ncols[x]];
pruned = YES;
}
}
/* Now go through all subsequent rows and columns to make them match */
for (x = 0; x < square; x++)
for (y = 0; y < square; y++) /* Not all rows may be used */
{
int k, used[128];
for (k = '1'; k <= square + '0'; k++) used[k] = NO;
for (k = 0; k < nrows[y]; k++)
used[perm[rows[y][k]][x]] = YES;
/* Eliminate any column that uses a bad row character */
for (k = 0; k < ncols[x]; )
{
if (! used[perm[cols[x][k]][y]])
{
cols[x][k] = cols[x][--ncols[x]];
pruned = YES; /* Eliminated one */
}
else k++;
}
for (k = '1'; k <= square + '0'; k++) used[k] = NO;
for (k = 0; k < ncols[x]; k++)
used[perm[cols[x][k]][y]] = YES;
for (k = 0; k < nrows[y]; )
{
if (! used[perm[rows[y][k]][x]])
{
rows[y][k] = rows[y][--nrows[y]];
pruned = YES; /* Eliminated one */
}
else k++;
}
}
return pruned; /* Did we get one this time? */
}
void validity_check() /* See if "square" is OK, and print if it is */
{
int i, j; /* We know the rows are OK; just check columns */
int used[128];
for (i = 0; i < square; i++)
{
for (j = '1'; j <= square + '0'; j++) /* should be general */
used[j] = NO;
for (j = 0; j < square; j++)
if (used[sq[j][i]]++) return; /* Doubled it */
}
/* Still here? We're OK. */
printf("Winner:\n");
for (j = square - 1; j >= 0; j--)
printf("%d: %s\n", j + 1, sq[j]);
}
vcheck(uchar *perm, struct cluestruct *p) /* Check a clue */
{
int i, sum;
for (i = sum = 0; i < p->nelements; i++)
sum += perm[p->elements[i]] - '0';
return sum == p->target;
}
#define swap(a, b) tmp = (a), (a) = (b), (b) = tmp
void permute(string, index) /* Matthew T. Day's algorithm */
register uchar *string;
register int index;
{
register int level = index, printing = !string[index + 1];
register uchar tmp;
uchar copy[square + 1];
(void) strcpy(copy, string);
do
{
if (printing) (void) strcpy(perm[nperms++], copy);
else permute(copy, level + 1);
if (index) swap(copy[index], copy[index - 1]);
} while (index--);
}
_____________________________snip_________________________________________
-- Jim Gillogly <jim@rand.org>, October 1994