Assignment_8 03 PUZZLE.e

note
    description: "N-queens puzzle."

class
    PUZZLE

feature -- Access

    size: INTEGER
            -- Size of the board.

    solutions: LIST [SOLUTION]
            -- All solutions found by the last call to `solve'.

    trivial_foundation: SOLUTION
            -- Holds one solution.

feature -- Basic operations

    solve (n: INTEGER)
            -- Solve the puzzle for `n' queens.
        require
            n_positive: n > 0
        local
            i: INTEGER
        do
            size := n
            create {LINKED_LIST [SOLUTION]} solutions.make

                -- Call feature complete with the trivial foundations.
            from
                i := 1
            until
                i > size
            loop
                if
                    size = 1
                then
                    create trivial_foundation.make_empty
                    trivial_foundation := trivial_foundation.extended_with (1)
                    solutions.extend (trivial_foundation)
                else
                    create trivial_foundation.make_empty
                    trivial_foundation := trivial_foundation.extended_with (i)
                    complete (trivial_foundation)
                end
                i := i + 1
            end

        ensure
            solutions_exists: solutions /= Void
            complete_solutions: across solutions as s all s.item.row_count = n end
        end

feature {NONE} -- Implementation

    complete (partial: SOLUTION)
            -- Find all complete solutions that extend the partial solution `partial'
            -- and add them to `solutions'.
        require
            partial_exists: partial /= Void
        local
            i: INTEGER
            new_partial: SOLUTION
        do
            from
                i := 1
            until
                i > size
            loop
                if
                    under_attack (partial, i) = false
                then
                    new_partial := partial.extended_with (i)
                    if
                        new_partial.row_count < size
                    then
                        complete (new_partial)
                    else
                        solutions.extend (new_partial)
                    end
                end
                i := i + 1
            end
        end

    under_attack (partial: SOLUTION; c: INTEGER): BOOLEAN
            -- Is column `c' of the current row under attack
            -- by any queen already placed in partial solution `partial'?
        require
            partial_exists: partial /= Void
        local
            current_row, row: INTEGER
        do
            current_row := partial.row_count + 1
            from
                row := 1
            until
                Result or row > partial.row_count
            loop
                Result := attack_each_other (row, partial.column_at (row), current_row, c)
                row := row + 1
            end
        end

    attack_each_other (row1, col1, row2, col2: INTEGER): BOOLEAN
            -- Do queens in positions (`row1', `col1') and (`row2', `col2') attack each other?
        local
            temp1, temp2: INTEGER
        do
            temp1 := (col2 - col1)
            temp2 := (row2 - row1)
            if
                col1 = col2
            then
                Result := true
            elseif
                temp1.abs = temp2.abs
            then
                Result := true
            else
                Result := false
            end
        end

end