Without using multicol, and instead fitting the listing in a tikz node, you can get the following result :
Code
This code is pretty dirty, because it contains a lot of hard-coded lengths. In order to fully automate these measures, one would need to know precisely the height of the listing node. This is doable with the help of this question, but for some reason the listing alters the way the node is typeset, and causes the measured height to be excessive. So until I find better, I'll leave here a dirty but working code.
\documentclass[11pt]{article}
\usepackage{tikz}
% \usepackage{multicol} % no longer necessary
\usepackage{listings}
\usepackage{lipsum}
\lstset{ %
language=Prolog, % the language of the code
basicstyle=\scriptsize\ttfamily, % the size of the fonts that are used for the code
numbers=left, % where to put the line-numbers
numberstyle=\tiny\color{gray}, % the style that is used for the line-numbers
stepnumber=1, % the step between two line-numbers. If it's 1, each line will be numbered
numbersep=5pt, % how far the line-numbers are from the code
backgroundcolor=\color{white}, % choose the background color. You must add \usepackage{color}
showspaces=false, % show spaces adding particular underscores
showstringspaces=false, % underline spaces within strings
showtabs=false, % show tabs within strings adding particular underscores
frame=single, % adds a frame around the code
rulecolor=\color{black}, % if not set, the frame-color may be changed on line-breaks within not-black text
tabsize=4, % sets default tabsize to 4 spaces
captionpos=b, % sets the caption-position to bottom
breaklines=true, % sets automatic line breaking
breakatwhitespace=false, % sets if automatic breaks should only happen at whitespace
title=\lstname, % show the filename of files included with \lstinputlisting;
% also try caption instead of title
keywordstyle=\color{blue}, % keyword style
commentstyle=\color{dkgreen}, % comment style
stringstyle=\color{mauve}, % string literal style
escapeinside={\%*}{*)}, % if you want to add LaTeX within your code
}
\begin{document}
\tikzstyle{block} = [rectangle, draw, minimum height=1cm, minimum width=1cm]
\tikzstyle{table} = [rectangle, draw, minimum width=5cm, minimum height=0.5cm, fill=gray!50]
\tikzstyle{b1} = [fill=orange!50]
\tikzstyle{b2} = [fill=green!50]
\tikzstyle{b3} = [fill=cyan!50]
\tikzstyle{b4} = [fill=red!50]
\lipsum[1]
%\begin{multicols}{2}
\begin{tikzpicture}
\node at (-5,0) {
\begin{lstlisting}[language=Prolog,linewidth=5cm]
[
block(block1),
block(block2),
block(block3),
block(block4),
on(table,block2),
on(table,block3),
on(block2,block1),
on(table,block4),
clear(block1),
clear(block3),
clear(block4),
handempty
]
\end{lstlisting}
};
\draw(-1.5,-2.05) rectangle (4.5,2.8);
\node[block, b3] at (1.5,0) {3};
\node[block, b2] at (0,0) {2};
\node[block, b1] at (0,1) {1};
\node[block, b4] at (3,0) {4};
\node[table] at (1.5,-0.75) {Table};
\end{tikzpicture}
%\end{multicols}
\lipsum[2]
\end{document}
Edit (after OP's remarks)
The following code does, to some extent, the height computation needed for the alignment.
\documentclass[11pt]{article}
\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage{multicol}
\usepackage{listings}
\usepackage{lipsum}
\lstset{ %
language=Prolog, % the language of the code
basicstyle=\scriptsize\ttfamily, % the size of the fonts that are used for the code
numbers=left, % where to put the line-numbers
numberstyle=\tiny\color{gray}, % the style that is used for the line-numbers
stepnumber=1, % the step between two line-numbers. If it's 1, each line will be numbered
numbersep=5pt, % how far the line-numbers are from the code
% backgroundcolor=\color{white}, % choose the background color. You must add \usepackage{color}
showspaces=false, % show spaces adding particular underscores
showstringspaces=false, % underline spaces within strings
showtabs=false, % show tabs within strings adding particular underscores
% frame=single, % adds a frame around the code
% rulecolor=\color{black}, % if not set, the frame-color may be changed on line-breaks within not-black text
tabsize=4, % sets default tabsize to 4 spaces
captionpos=b, %
breaklines=true, % sets automatic line breaking
breakatwhitespace=false, % sets if automatic breaks should only happen at whitespace
% title=\lstname, % show the filename of files included with \lstinputlisting;
% also try caption instead of title
keywordstyle=\color{blue}, % keyword style
commentstyle=\color{dkgreen}, % comment style
stringstyle=\color{mauve}, % string literal style
escapeinside={\%*}{*)}, % if you want to add LaTeX within your code
}
\makeatletter
\newcommand\getheightofnode[2]{%
\pgfextracty{#1}{\pgfpointanchor{#2}{north}}%
\pgfextracty{\pgf@xa}{\pgfpointanchor{#2}{south}}% \pgf@xa is a length defined by PGF for temporary storage. No need to create a new temporary length.
\addtolength{#1}{-\pgf@xa}%
}
\makeatother
\newlength{\myheight}
\begin{document}
\tikzstyle{block} = [rectangle, draw, minimum height=1cm, minimum width=1cm]
\tikzstyle{table} = [rectangle, draw, minimum width=5cm, minimum height=0.5cm, fill=gray!50]
\tikzstyle{b1} = [fill=orange!50]
\tikzstyle{b2} = [fill=green!50]
\tikzstyle{b3} = [fill=cyan!50]
\tikzstyle{b4} = [fill=red!50]
\lipsum[1]
\begin{tikzpicture}
\node[anchor=south west,inner xsep=15pt,inner ysep=5pt,draw] (listing) at (-7,0) {%
\begin{lstlisting}[language=Prolog,aboveskip=0,belowskip=0,abovecaptionskip=0pt,belowcaptionskip=0pt]
[
block(block1),
block(block2),
block(block3),
block(block4),
on(table,block2),
on(table,block3),
on(block2,block1),
on(table,block4),
clear(block1),
clear(block3),
clear(block4),
handempty
]
\end{lstlisting}};
\getheightofnode{\myheight}{listing}
\begin{scope}[shift={($ - 0.5*(0,\myheight) + (0,2.5)$)}]
% The second term's y coordinate is 2.5 = height of the boxes + table
\draw (-1.5,0) rectangle ($(4.5,0) + (0,\myheight) $);
\begin{scope}[shift={($0.5*(0,\myheight) - (0,0.25)$)}] % Why do I need this 0.25?
\node[block, b3] at (1.5,0) {3};
\node[block, b2] at (0,0) {2};
\node[block, b1] at (0,1) {1};
\node[block, b4] at (3,0) {4};
\node[table] at (1.5,-0.75) {Table};
\end{scope}
\end{scope}
\end{tikzpicture}
\lipsum[2]
\end{document}
I commented out some options from the listings package, and let tikz do the framing, etc. The result is correct with respect to the height, however I am still not fully satisfied, because this still needs user input for the height of boxes (I don't plan on automating it, though), and there is this 0.2 "magical" value which is needed for the vertical alignment of the blocks. I guess my calculations are wrong somewhere.
Replacing this 0.2 magic by 0.4, it's not aligned anymore, but it looks more balanced in my eyes:
A (half-dirty) solution in case the right-hand picture is taller
The alignment can be more or less tweaked from there. But the syntax is a bit different for that case
\documentclass[11pt]{article}
\usepackage{tikz}
\usetikzlibrary{calc}
\usepackage{multicol}
\usepackage{listings}
\usepackage{lipsum}
\lstset{ %
language=Prolog, % the language of the code
basicstyle=\scriptsize\ttfamily, % the size of the fonts that are used for the code
numbers=left, % where to put the line-numbers
numberstyle=\tiny\color{gray}, % the style that is used for the line-numbers
stepnumber=1, % the step between two line-numbers. If it's 1, each line will be numbered
numbersep=5pt, % how far the line-numbers are from the code
% backgroundcolor=\color{white}, % choose the background color. You must add \usepackage{color}
showspaces=false, % show spaces adding particular underscores
showstringspaces=false, % underline spaces within strings
showtabs=false, % show tabs within strings adding particular underscores
% frame=single, % adds a frame around the code
% rulecolor=\color{black}, % if not set, the frame-color may be changed on line-breaks within not-black text
tabsize=4, % sets default tabsize to 4 spaces
captionpos=b, %
breaklines=true, % sets automatic line breaking
breakatwhitespace=false, % sets if automatic breaks should only happen at whitespace
% title=\lstname, % show the filename of files included with \lstinputlisting;
% also try caption instead of title
keywordstyle=\color{blue}, % keyword style
commentstyle=\color{dkgreen}, % comment style
stringstyle=\color{mauve}, % string literal style
escapeinside={\%*}{*)}, % if you want to add LaTeX within your code
}
\makeatletter
\newcommand\getheightofnode[2]{%
\pgfextracty{#1}{\pgfpointanchor{#2}{north}}%
\pgfextracty{\pgf@xa}{\pgfpointanchor{#2}{south}}% \pgf@xa is a length defined by PGF for temporary storage. No need to create a new temporary length.
\addtolength{#1}{-\pgf@xa}%
}
\makeatother
\newlength{\myheight}
\begin{document}
\tikzstyle{block} = [rectangle, draw, minimum height=1cm, minimum width=1cm]
\tikzstyle{table} = [rectangle, draw, minimum width=5cm, minimum height=0.5cm, fill=gray!50]
\tikzstyle{b1} = [fill=orange!50]
\tikzstyle{b2} = [fill=green!50]
\tikzstyle{b3} = [fill=cyan!50]
\tikzstyle{b4} = [fill=red!50]
\begin{tikzpicture}
\node[anchor=south west,inner xsep=15pt,inner ysep=5pt] (listing) at (-7,0) {%
\begin{lstlisting}[language=Prolog,aboveskip=0,belowskip=0,abovecaptionskip=0pt,belowcaptionskip=0pt]
[
block(block1),
block(block2),
block(block3),
block(block4),
on(table,block2),
on(table,block3),
on(block2,block1),
on(table,block4),
clear(block1),
clear(block3),
clear(block4),
handempty
]
\end{lstlisting}};
\def\myheight{7}
\begin{scope}[shift={($ - 0.5*(0,\myheight) + (0,2.5)$)}]
% The second term is 2.5 (height of the boxes + table)
\draw (-1.5,0) rectangle ($(4.5,0) + (0,\myheight) $);
\begin{scope}[shift={($(0,1.5)$)}] % Why do I need this 0.25?
\node[block, b3] at (1.5,0) {3};
\node[block, b2] at (0,0) {2};
\node[block, b1] at (0,1) {1};
\node[block, b4] at (3,0) {4};
\node[block, b2] at (0,2) {5};
\node[block, b3] at (0,3) {6};
\node[block, b4] at (0,4) {7};
\node[table] at (1.5,-0.75) {Table};
\end{scope}
\end{scope}
\draw ($(listing) - 0.5*(5,\myheight)$) rectangle ($(listing) + 0.5*(5,\myheight)$);
\end{tikzpicture}
\end{document}