 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Unfilled grid (Posted on 2006-05-23) Fill as much of a 6x6 grid with the letters A, B, C, D, E, F so no two of the same letter are in the same row, column or diagonal.

It is impossible to entirely fill the grid, but what is the largest number of letters that may be placed?

 See The Solution Submitted by Jer Rating: 4.1429 (7 votes) Comments: ( Back to comment list | You must be logged in to post comments.) computer program still running, but so far... | Comment 1 of 5

The program has a lot of possibilities to try and it's still running, but so far it has found a solution with 33 letters filled in.  They are the lower-case letters in the grid below.  While there are no conflicts within a row or column, the capital letters conflict with a correctly placed letter on a diagonal, and so should not actually be placed--consider them blank:

`afebdcbdcfaeceAdbfdbfceaeCdafbfabecD`

The program was written to assume the left-hand column goes from a to f from top to bottom. Every possibility is tried for every position thereafter so long as there is no conflict within row or column. The letters for any position are tried in reverse order, to minimize initial diagonal conflicts between the first row and the first column.

DECLARE SUB place (row!, col!)
CLEAR , , 9999
DIM SHARED g\$(6, 6), bad(6, 6), badCt, l\$, leastCt
l\$ = "abcdef": leastCt = 999
FOR i = 1 TO 6
g\$(i, 1) = MID\$(l\$, i, 1)
NEXT

place 1, 2

SUB place (row, col)
FOR i = 6 TO 1 STEP -1
lt\$ = MID\$(l\$, i, 1)
good = 1
FOR c = 1 TO col - 1
IF g\$(row, c) = lt\$ THEN good = 0: EXIT FOR
NEXT
IF good THEN
FOR r = 1 TO row - 1
IF g\$(r, col) = lt\$ THEN good = 0: EXIT FOR
NEXT
END IF
IF good THEN
g\$(row, col) = lt\$
conflict = 0
FOR r = 1 TO row - 1
c = col - (row - r)
IF c > 0 THEN IF g\$(r, c) = lt\$ THEN conflict = 1: EXIT FOR
c = col + (row - r)
IF c < 7 THEN IF g\$(r, c) = lt\$ THEN conflict = 1: EXIT FOR
NEXT
bad(row, col) = conflict
IF conflict THEN badCt = badCt + 1

IF row = 6 AND col = 6 THEN
IF badCt < leastCt THEN
PRINT leastCt
FOR r = 1 TO 6
FOR c = 1 TO 6
IF bad(r, c) THEN
PRINT UCASE\$(g\$(r, c));
ELSE
PRINT g\$(r, c);
END IF
NEXT
PRINT
NEXT
PRINT
END IF
ELSE
c = col + 1: r = row
IF c > 6 THEN c = 2: r = r + 1
place r, c
END IF

IF conflict THEN bad(row, col) = 0: badCt = badCt - 1
END IF
NEXT i
END SUB

 Posted by Charlie on 2006-05-23 09:41:16 Please log in:

 Search: Search body:
Forums (0)