 All about flooble | fun stuff | Get a free chatterbox | Free JavaScript | Avatars  perplexus dot info  Battleships (Posted on 2013-04-24) No Solution Yet Submitted by brianjn No Rating Comments: ( Back to comment list | You must be logged in to post comments.) computer solutions | Comment 3 of 6 | DECLARE SUB place (n!)
CLEAR , , 25000
CLS
DIM SHARED grid\$(9, 9), src\$, rowlim(8), collim(8), rowct(8), colct(8)
grid\$(8, 8) = "1"
grid\$(7, 8) = "-"
grid\$(8, 7) = "-"
grid\$(7, 7) = "-"
DATA 5,1,3,1,3,1,2,4
DATA 4,1,2,4,3,2,3,1
FOR i = 1 TO 8: READ rowlim(i): NEXT
FOR i = 1 TO 8: READ collim(i): NEXT
rowct(8) = 1
colct(8) = 1
src\$ = "433222111"

OPEN "btlshps.txt" FOR OUTPUT AS #2

place 1

SUB place (n)
sz = VAL(MID\$(src\$, n, 1))
FOR row = 1 TO 8
IF rowct(row) + sz <= rowlim(row) THEN
FOR stcol = 1 TO 9 - sz
REDIM h\$(row - 1 TO row + 1, stcol - 1 TO stcol + sz)
good = 1
FOR c = stcol TO stcol + sz - 1
IF grid\$(row, c) > "" THEN good = 0: EXIT FOR
IF colct(c) + 1 > collim(c) THEN good = 0: EXIT FOR
NEXT
IF good THEN
FOR c = stcol - 1 TO stcol + sz
h\$(row - 1, c) = grid\$(row - 1, c): grid\$(row - 1, c) = "-"
h\$(row, c) = grid\$(row, c): grid\$(row, c) = "-"
h\$(row + 1, c) = grid\$(row + 1, c): grid\$(row + 1, c) = "-"
IF c >= stcol AND c < stcol + sz THEN colct(c) = colct(c) + 1
NEXT
rowct(row) = rowct(row) + sz

FOR c = stcol TO stcol + sz - 1
grid\$(row, c) = MID\$(src\$, n, 1)
NEXT

IF n = 9 THEN
FOR r = 1 TO 8
FOR c = 1 TO 8
PRINT LEFT\$(grid\$(r, c) + " ", 1);
PRINT #2, LEFT\$(grid\$(r, c) + "  ", 2);
NEXT: PRINT : 'PRINT #2,
NEXT: PRINT : PRINT #2,
ELSE
place n + 1
END IF

rowct(row) = rowct(row) - sz

FOR c = stcol - 1 TO stcol + sz
IF c >= stcol AND c < stcol + sz THEN colct(c) = colct(c) - 1
grid\$(row - 1, c) = h\$(row - 1, c)
grid\$(row, c) = h\$(row, c)
grid\$(row + 1, c) = h\$(row + 1, c)
NEXT
END IF
NEXT stcol
END IF
NEXT row

FOR col = 1 TO 8
IF colct(col) + sz <= collim(col) THEN
FOR strow = 1 TO 9 - sz
REDIM h\$(strow - 1 TO strow + sz, col - 1 TO col + 1)
good = 1
FOR r = strow TO strow + sz - 1
IF grid\$(r, col) > "" THEN good = 0: EXIT FOR
IF rowct(r) + 1 > rowlim(r) THEN good = 0: EXIT FOR
NEXT
IF good THEN
FOR r = strow - 1 TO strow + sz
h\$(r, col - 1) = grid\$(r, col - 1): grid\$(r, col - 1) = "-"
h\$(r, col) = grid\$(r, col): grid\$(r, col) = "-"
h\$(r, col + 1) = grid\$(r, col + 1): grid\$(r, col + 1) = "-"
IF r >= strow AND r < strow + sz THEN rowct(r) = rowct(r) + 1
NEXT
colct(col) = colct(col) + sz

FOR r = strow TO strow + sz - 1
grid\$(r, col) = MID\$(src\$, n, 1)
NEXT

IF n = 9 THEN
FOR r = 1 TO 8
FOR c = 1 TO 8
PRINT LEFT\$(grid\$(r, c) + " ", 1);
PRINT #2, LEFT\$(grid\$(r, c) + "  ", 2);
NEXT: PRINT : 'PRINT #2,
NEXT: PRINT : PRINT #2,
ELSE
place n + 1
END IF

colct(col) = colct(col) - sz

FOR r = strow - 1 TO strow + sz
IF r >= strow AND r < strow + sz THEN rowct(r) = rowct(r) - 1
grid\$(r, col - 1) = h\$(r, col - 1)
grid\$(r, col) = h\$(r, col)
grid\$(r, col + 1) = h\$(r, col + 1)
NEXT
END IF
NEXT strow
END IF
NEXT col

END SUB

The output was designed so that each solution would be on a single line in order that the output be sorted with duplicates eliminated. So a subsequent program had to format the output into the familiar grid and lay them out in a larger grid.

I had expected each solution to appear 72 times, as the order of each of the two battleships would not matter, nor the order of the three cruisers nor the order of the three added destroyers, and 2 * 3! * 3! = 72. Instead I got 576 repetitions of each solution, and I don't understand why; 576 is 2^6 * 3^2, or eight times what was expected.  This is a mystery.

The 12 solutions (digits used as markers representing the size of each ship):

`- 4 4 4 4 - 2 -   - 4 4 4 4 - 2 -   - 4 4 4 4 - 2 -   - 4 4 4 4 - 3 -- - - - - - 2 -   - - - - - - 2 -   - - - - - - 2 -   - - - - - - 3 -- - 3 3 3 - - -   - - 3 3 3 - - -   1 - - 2 2 - - -   - - - 2 2 - 3 -1 - - - - - - -   3 - - - - - - -   - - - - - - 1 -   1 - - - - - - -- - - 2 2 - 1 -   3 -   - 1 - 1 -   - - 3 3 3 - - -   - - 1 - 2 2 -3 - - - - - - -   3 - - - - - - -   3 - - - - - -     3 - - - - - -3 - - - - 2 - -   - - - 2 - 2 - -   3 - - - - 2 - -   3 - - 2 - - - -3 - - 1 - 2 - 1   1 - - 2 - 2 - 1   3 - - 1 - 2 - 1   3 - - 2 - 1 - 1`
`- 4 4 4 4 - 3 -   - 4 4 4 4 - 3 -   - 4 4 4 4 - 3 -   2 - - 4 4 4 4 -- - - - - - 3 -   - - - - - - 3 -   - - - - - - 3 -   2 - - - - - - -- - - 2 2 - 3 -   - - 1 - 1 - 3 -   2 -   - 1 - 3 -   - - 2 2 - - 1 -3 - - - - - - -   3 - - - - - - -   2 - - - - - - -   1 - - - - - - -3 - 1 - 1 -       3 - - 2 2 -       - - 3 3 3 -       - - 3 3 3 - - -3 - - - - - -     3 - - - - - -     1 - - - - - -     - - - - - - 1 -- - - 2 - 2 - -   - - - 2 - 2 - -   - - - 2 - 2 - -   2 2 - - - - - -1 - - 2 - 2 - 1   1 - - 2 - 2 - 1   1 - - 2 - 2 - 1   - - - 3 3 3 - 1`
`2 - - 4 4 4 4 -   2 - 4 4 4 4 -     2 - 4 4 4 4 -     3 - - 4 4 4 4 -2 - - - - - - -   2 - - - - - -     2 - - - - - - -   3 - - - - - - -- - 3 3 3 - - -   - - 3 3 3 - - -   - - 1 - 1 - 3 -   3 - - 3 - 1 -- - - - - - 1 -   - - - - - - 3 -   - - - - - - 3 -   - - - 3 - - - -1 - 2 2 - - - -   - 1 - - 1 - 3 -   1 - - 2 - - 3 -   - 1 - 3 - - 2 -- - - - - - 1 -   - - - - - - 3 -   - - - 2 - - - -   - - - - - - 2 -2 2 - - - - - -   2 - - 2 - - - -   2 2 - - - - - -   - - 2 - 2 - - -- - - 3 3 3 - 1   2 - - 2 - 1 - 1   - - - 3 3 3 - 1   1 - 2 - 2 - - 1`

Several of these solutions have a blank space or two or three, where another destroyer or cruiser would fit (each set of 3 is not arranged in a straight line, so a battleship couldn't be placed in the hole).

 Posted by Charlie on 2013-04-24 19:35:21 Please log in:

 Search: Search body:
Forums (0)