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

Home > Logic
Battleships (Posted on 2013-04-24) Difficulty: 4 of 5

No Solution Yet Submitted by brianjn    
No Rating

Comments: ( Back to comment list | You must be logged in to post comments.)
Solution 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:
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 (14)
Unsolved Problems
Top Rated Problems
This month's top
Most Commented On

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