All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars    
perplexus dot info

Home > General
Unfilled grid (Posted on 2006-05-23) Difficulty: 3 of 5
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.)
re: Possible solution. | Comment 4 of 5 |
(In reply to Possible solution. by Dej Mar)

Indeed, the last few found by the corrected program are:

 4
adefcB
bAcdef
cefbad
dbaefc
eFdcba
fcbadE
 4
adbfcE
bAcdef
cefbad
dbaefc
eFdcba
fceadB
 4
acebfD
bfacde
cedFba
dbcAef
eafdcb
fdbeaC
 4
acebfD
bfacde
cedAbf
dbcFea
eafdcb
fdbeaC
 4
acebfD
bdfcae
ceAdbf
dbcfea
eFdacb
fabedC
 4
acebfD
bAfcde
cedabf
dbcfea
eFadcb
fdbeaC

The corrected portions of the program involve switching rows and columns:

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 c = 1 TO col - 1
     r = row - (col - c)
     IF r > 0 THEN IF g$(r, c) = lt$ THEN conflict = 1: EXIT FOR
     r = row + (col - c)
     IF r < 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
        leastCt = badCt
        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
      r = row + 1: c = col
      IF r > 6 THEN r = 1: c = c + 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 23:57:51
Please log in:
Login:
Password:
Remember me:
Sign up! | Forgot password


Search:
Search body:
Forums (0)
Newest Problems
Random Problem
FAQ | About This Site
Site Statistics
New Comments (2)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

Chatterbox:
Copyright © 2002 - 2017 by Animus Pactum Consulting. All rights reserved. Privacy Information