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 |
computer solutions
