solver3: Verbose error messages

Introduce a new function, LongWhyStr() that returns a longer
reason for why something is being installed (or not).

This does the same path walk as the other function does, but
it renders the clauses at each level, and one per line, so
the whole output is a lot more informative.

It is a separate function to keep the existing debug messages
use the simple single line implication graph

We remove the other special case in AddWork() for empty solutions
to mke use of the general case in Solve() instead, and then adapt
the case in Solve() to the same case as in Enqueue(). This also
happens to fix the bug that when we encountered an empty clause
we just printed the clause had no solution, but not how we got
to install the package with the clause.

Adapt the test suite for the changes which is an annoying amount
of paperwork.

28 files changed, 401 insertions, 59 deletions

diff --git a/test/integration/test-apt-get-build-dep-barbarian b/test/integration/test-apt-get-build-dep-barbarian
index 48873c59b..8763e8fc7 100755
--- a/test/integration/test-apt-get-build-dep-barbarian
+++ b/test/integration/test-apt-get-build-dep-barbarian
@@ -83,7 +83,16 @@ testsuccessequal "$(installsfoosamey 'amd64' 'i386')" apt build-dep cool-foo -s
 testsuccessequal "$(installsfoosamey 'i386' 'i386')" apt build-dep bad-amd64-foo -s -a i386
 testsuccessequal "$(installsfoosamey 'amd64' 'i386')" apt build-dep bad-armel-foo -s -a i386
 testsuccessequal "$(installsfoosamey 'i386' 'i386')" apt build-dep bad-amd64-armel-foo -s -a i386
-testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-foo:i386=1 -> builddeps:bad-amd64-i386-foo:i386 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-foo:i386 but builddeps:bad-amd64-i386-foo:i386=1 -> builddeps:bad-amd64-i386-foo:i386'  apt build-dep bad-amd64-i386-foo -s -a i386 --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:bad-amd64-i386-foo:i386=1 is selected for install
+   2. builddeps:bad-amd64-i386-foo:i386 Depends foo:i386
+      but none of the choices are installable:
+      - foo:amd64=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-foo:i386=1 is selected for install
+        2. builddeps:bad-amd64-i386-foo:i386 Conflicts foo:amd64
+      - foo:i386=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-foo:i386=1 is selected for install as above
+        2. builddeps:bad-amd64-i386-foo:i386 Conflicts foo:i386'  apt build-dep bad-amd64-i386-foo -s -a i386 --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -96,7 +105,16 @@ The following information may help to resolve the situation:
 The following packages have unmet dependencies:
  builddeps:bad-amd64-i386-foo:i386 : Depends: foo:i386
 E: Unable to correct problems, you have held broken packages.' apt build-dep bad-amd64-i386-foo -s -a i386 --solver internal
-testfailuremsg 'E: Conflict: builddeps:bad-amd64-i386-armel-foo:i386=1 -> builddeps:bad-amd64-i386-armel-foo:i386 -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-armel-foo:i386 but builddeps:bad-amd64-i386-armel-foo:i386=1 -> builddeps:bad-amd64-i386-armel-foo:i386' apt build-dep bad-amd64-i386-armel-foo -s -a i386 --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:bad-amd64-i386-armel-foo:i386=1 is selected for install
+   2. builddeps:bad-amd64-i386-armel-foo:i386 Depends foo:i386
+      but none of the choices are installable:
+      - foo:amd64=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:i386=1 is selected for install
+        2. builddeps:bad-amd64-i386-armel-foo:i386 Conflicts foo:amd64
+      - foo:i386=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:i386=1 is selected for install as above
+        2. builddeps:bad-amd64-i386-armel-foo:i386 Conflicts foo:i386' apt build-dep bad-amd64-i386-armel-foo -s -a i386 --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -115,7 +133,19 @@ testsuccessequal "$(installsfoosamey 'i386' 'armel')" apt build-dep bad-amd64-fo
 testsuccessequal "$(installsfoosamey 'amd64' 'armel')" apt build-dep bad-armel-foo -s -a armel
 testsuccessequal "$(installsfoosamey 'i386' 'armel')" apt build-dep bad-amd64-armel-foo -s -a armel
 testsuccessequal "$(installsfoosamey 'armel' 'armel')" apt build-dep bad-amd64-i386-foo -s -a armel
-FAILUREMSG="E: Conflict: builddeps:bad-amd64-i386-armel-foo:armel=1 -> builddeps:bad-amd64-i386-armel-foo:armel -> not foo:amd64=1 -> not builddeps:bad-amd64-i386-armel-foo:armel but builddeps:bad-amd64-i386-armel-foo:armel=1 -> builddeps:bad-amd64-i386-armel-foo:armel"
+FAILUREMSG="E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install
+   2. builddeps:bad-amd64-i386-armel-foo:armel Depends foo:armel
+      but none of the choices are installable:
+      - foo:amd64=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install
+        2. builddeps:bad-amd64-i386-armel-foo:armel Conflicts foo:amd64
+      - foo:i386=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install as above
+        2. builddeps:bad-amd64-i386-armel-foo:armel Conflicts foo:i386
+      - foo:armel=1 is not selected for install because:
+        1. builddeps:bad-amd64-i386-armel-foo:armel=1 is selected for install as above
+        2. builddeps:bad-amd64-i386-armel-foo:armel Conflicts foo:armel"
 FAILURE='Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-apt-get-build-dep-file b/test/integration/test-apt-get-build-dep-file
index 8147bb0a3..fd48aef47 100755
--- a/test/integration/test-apt-get-build-dep-file
+++ b/test/integration/test-apt-get-build-dep-file
@@ -160,7 +160,11 @@ cd ../..
 
 testfailureequal 'E: Must specify at least one package to check builddeps for' aptget build-dep
 testfailuremsg 'W: No architecture information available for armel. See apt.conf(5) APT::Architectures for setup
-E: Unsatisfiable dependency group builddeps:./foo-1.0:armel -> debhelper:armel' aptget build-dep --simulate ./foo-1.0 -a armel --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:./foo-1.0:armel=1 is selected for install
+   2. builddeps:./foo-1.0:armel Depends debhelper:armel (>= 7)
+      but none of the choices are installable:
+      [no choices]' aptget build-dep --simulate ./foo-1.0 -a armel --solver 3.0
 testfailureequal "Note, using directory './foo-1.0' to get the build dependencies
 Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-apt-get-install-deb b/test/integration/test-apt-get-install-deb
index 1540db272..07de975c4 100755
--- a/test/integration/test-apt-get-install-deb
+++ b/test/integration/test-apt-get-install-deb
@@ -32,7 +32,11 @@ done
 
 buildsimplenativepackage 'foo' 'i386,amd64' '1.0'
 
-testfailuremsg "E: Conflict: foo:amd64=1.0 -> foo:amd64 but foo:i386=1.0 -> not foo:amd64" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64 is not selected for install because:
+      1. foo:i386=1.0 is selected for install
+      2. foo:amd64 Conflicts foo:i386
+   2. foo:amd64=1.0 is selected for install" aptget install ./incoming/foo_1.0_i386.deb ./incoming/foo_1.0_amd64.deb -s --solver 3.0
 testfailureequal "Reading package lists...
 Building dependency tree...
 Note, selecting 'foo:i386' instead of './incoming/foo_1.0_i386.deb'
@@ -177,7 +181,11 @@ echo 'Package: /pkg-/
 Pin: release a=experimental
 Pin-Priority: 501' > rootdir/etc/apt/preferences.d/pinit
 
-testfailuremsg 'E: Unsatisfiable dependency group pkg-last-line-parse:amd64 -> pkg-as-it-should-be:amd64' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. pkg-last-line-parse:amd64=0 is selected for install
+   2. pkg-last-line-parse:amd64 PreDepends pkg-as-it-should-be
+      but none of the choices are installable:
+      [no choices]' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver 3.0
 testfailuremsg 'E: Unable to correct problems, you have held broken packages.' aptget install -q=0 ./incoming/pkg-last-line-parse_0_all.deb --solver internal
 testsuccess aptget install ./incoming/pkg-as-it-should-be_0_all.deb
 testsuccess aptget install ./incoming/pkg-last-line-parse_0_all.deb
diff --git a/test/integration/test-apt-get-satisfy b/test/integration/test-apt-get-satisfy
index 02a444dff..8e5e06843 100755
--- a/test/integration/test-apt-get-satisfy
+++ b/test/integration/test-apt-get-satisfy
@@ -80,7 +80,11 @@ testrun 'External' 'Reading package lists...
 Building dependency tree...
 Execute external solver...' --solver apt
 
-testfailuremsg "E: Unsatisfiable dependency group satisfy:command-line:i386 -> depends:i386" aptget satisfy --simulate "depends (>= 2)" "Conflicts: conflicts:i386 (>= 1) [i386], conflicts:amd64 (>= 1) [amd64]" --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. satisfy:command-line:i386=1 is selected for install
+   2. satisfy:command-line:i386 Depends depends (>= 2)
+      but none of the choices are installable:
+      [no choices]" aptget satisfy --simulate "depends (>= 2)" "Conflicts: conflicts:i386 (>= 1) [i386], conflicts:amd64 (>= 1) [amd64]" --solver 3.0
 
 testfailureequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-apt-get-source-only b/test/integration/test-apt-get-source-only
index 882f82b33..e5d246f6e 100755
--- a/test/integration/test-apt-get-source-only
+++ b/test/integration/test-apt-get-source-only
@@ -40,7 +40,11 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  builddeps:foo : Depends: foo-bd but it is not installable
-E: Unsatisfiable dependency group builddeps:foo:amd64 -> foo-bd:amd64"
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:foo:amd64=1 is selected for install
+   2. builddeps:foo:amd64 Depends foo-bd
+      but none of the choices are installable:
+      [no choices]"
 
 BUILDDEPNOTFOO="Reading package lists...
 Building dependency tree...
@@ -52,7 +56,11 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  builddeps:not-foo : Depends: not-foo-bd but it is not installable
-E: Unsatisfiable dependency group builddeps:not-foo:amd64 -> not-foo-bd:amd64"
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:not-foo:amd64=1 is selected for install
+   2. builddeps:not-foo:amd64 Depends not-foo-bd
+      but none of the choices are installable:
+      [no choices]"
 else
 BUILDDEPFOO="Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-apt-install-file-reltag b/test/integration/test-apt-install-file-reltag
index 0637c5472..053c785fd 100755
--- a/test/integration/test-apt-install-file-reltag
+++ b/test/integration/test-apt-install-file-reltag
@@ -31,7 +31,7 @@ buildsimplenativepackage 'foobar2' 'all' '1' 'unstable' 'Depends: foo (= 5), baz
 
 testunsat() {
     testfailure "$@"
-    testsuccess grep -E "^E: (Unable to correct problems,|Conflict:)" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testfailure.output"
+    testsuccess grep -E "^E: (Unable to correct problems,|Unable to satisfy dependencies. Reached two conflicting decisions)" "${TMPWORKINGDIRECTORY}/rootdir/tmp/testfailure.output"
 }
 
 ln -s "$(readlink -f ./incoming/foobar2_1_all.deb)" foobar.deb
diff --git a/test/integration/test-apt-never-markauto-sections b/test/integration/test-apt-never-markauto-sections
index 95ba47553..bf08507d0 100755
--- a/test/integration/test-apt-never-markauto-sections
+++ b/test/integration/test-apt-never-markauto-sections
@@ -49,7 +49,18 @@ Remv foreignpkg:i386 [1]
 Remv nosection [1]
 Remv texteditor [1]' aptget autoremove mydesktop -s
 
-testfailuremsg 'E: Conflict: not texteditor:amd64 -> not bad-texteditor:amd64 but mydesktop:amd64 -> mydesktop-core:amd64 -> bad-texteditor:amd64' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. bad-texteditor:amd64 is selected for install because:
+      1. mydesktop:amd64 is selected for install
+      2. mydesktop:amd64 Depends mydesktop-core
+      3. mydesktop-core:amd64 Depends bad-texteditor | texteditor
+         [selected mydesktop-core:amd64]
+      For context, additional choices that could not be installed:
+      * In mydesktop-core:amd64 Depends bad-texteditor | texteditor:
+        - texteditor:amd64 is selected for removal
+   2. bad-texteditor:amd64 Depends texteditor
+      but none of the choices are installable:
+      - texteditor:amd64 is selected for removal' aptget autoremove texteditor -s --solver 3.0 #-o Debug::pkgDepCache::AutoInstall=1 -o Debug::pkgProblemResolver=1 -o Debug::pkgDepCache::Marker=1
 testsuccessequal 'Reading package lists...
 Building dependency tree...
 Reading state information...
diff --git a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
index 6c9fb60c0..98479b5fd 100755
--- a/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
+++ b/test/integration/test-bug-598669-install-postfix-gets-exim-heavy
@@ -1,4 +1,4 @@
-#!/bin/sh
+t-bug-598669-install-postfix-gets-exim-heavy!/bin/sh
 set -e
 
 TESTDIR="$(readlink -f "$(dirname "$0")")"
@@ -7,7 +7,13 @@ setupenvironment
 configarchitecture "i386"
 setupaptarchive
 
-testfailuremsg "E: Conflict: exim4-daemon-light:i386 -> not postfix:i386=2.7.1-1 but postfix:i386=2.7.1-1" aptget install postfix --solver 3.0
+# FIXME: Should this say selected postifx?
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. postfix:i386=2.7.1-1 is selected for install
+   2. postfix:i386=2.7.1-1 is not selected for install because:
+      1. exim4-daemon-light:i386 is selected for install
+      2. exim4-daemon-light:i386 Conflicts mail-transport-agent
+         [selected exim4-daemon-light:i386]" aptget install postfix --solver 3.0
 allowremovemanual
 testfailureequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-601961-install-info b/test/integration/test-bug-601961-install-info
index 6d68372b5..be55e76a7 100755
--- a/test/integration/test-bug-601961-install-info
+++ b/test/integration/test-bug-601961-install-info
@@ -60,4 +60,8 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  findutils : Depends: essentialpkg but it is not going to be installed
-E: Conflict: findutils:i386 -> essentialpkg:i386 but not essentialpkg:i386' aptget remove essentialpkg --trivial-only --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. essentialpkg:i386 is selected for removal
+   2. essentialpkg:i386 is selected for install because:
+      1. findutils:i386 is selected for install
+      2. findutils:i386 Depends essentialpkg' aptget remove essentialpkg --trivial-only --solver 3.0
diff --git a/test/integration/test-bug-612557-garbage-upgrade b/test/integration/test-bug-612557-garbage-upgrade
index 4ef241cad..a001c4385 100755
--- a/test/integration/test-bug-612557-garbage-upgrade
+++ b/test/integration/test-bug-612557-garbage-upgrade
@@ -18,7 +18,14 @@ testsuccess aptmark markauto python-uno openoffice.org-common
 testmarkedauto python-uno openoffice.org-common
 
 # The 3.0 solver does not remove openoffice.org-emailmerge because it is manually installed.
-testfailuremsg "E: Conflict: openoffice.org-emailmerge:i386 -> openoffice.org-common:i386 -> openoffice.org-common:i386=1:3.2.1-11+squeeze2 but python-uno:i386=1:3.3.0-2 -> libreoffice-common:i386 -> not openoffice.org-common:i386=1:3.2.1-11+squeeze2" aptget --trivial-only install python-uno --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. openoffice.org-common:i386=1:3.2.1-11+squeeze2 is not selected for install because:
+      1. python-uno:i386=1:3.3.0-2 is selected as an upgrade
+      2. python-uno:i386=1:3.3.0-2 Depends libreoffice-common
+      3. libreoffice-common:i386 Conflicts openoffice.org-common
+   2. openoffice.org-common:i386 is selected for install because:
+      1. openoffice.org-emailmerge:i386 is selected for install
+      2. openoffice.org-emailmerge:i386 PreDepends openoffice.org-common" aptget --trivial-only install python-uno --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Reading state information...
diff --git a/test/integration/test-bug-618848-always-respect-user-requests b/test/integration/test-bug-618848-always-respect-user-requests
index d59491af6..b1cccef9d 100755
--- a/test/integration/test-bug-618848-always-respect-user-requests
+++ b/test/integration/test-bug-618848-always-respect-user-requests
@@ -14,7 +14,11 @@ insertpackage 'unstable' 'exim4-daemon-heavy' 'all' '1.0' 'Depends: libdb4.8'
 setupaptarchive
 
 # This does not work in 3.0 solver: We do not remove manually installed packages.
-testfailuremsg "E: Conflict: not libdb4.8:i386 -> not exim4-daemon-light:i386 but exim4-daemon-light:i386" aptget remove libdb4.8 --solver 3.0 -s
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. exim4-daemon-light:i386 is selected for install
+   2. exim4-daemon-light:i386 Depends libdb4.8
+      but none of the choices are installable:
+      - libdb4.8:i386 is selected for removal" aptget remove libdb4.8 --solver 3.0 -s
 allowremovemanual
 testsuccessequal "Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-632221-cross-dependency-satisfaction b/test/integration/test-bug-632221-cross-dependency-satisfaction
index d101bd1fa..6e39b384c 100755
--- a/test/integration/test-bug-632221-cross-dependency-satisfaction
+++ b/test/integration/test-bug-632221-cross-dependency-satisfaction
@@ -35,7 +35,11 @@ insertsource 'unstable' 'source-specific-armel' 'armel' '1' 'Build-Depends: spec
 
 setupaptarchive
 
-testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-no:armel -> amdboot:any:any" aptget build-dep forbidden-no -s -a armel --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:forbidden-no:armel=1 is selected for install
+   2. builddeps:forbidden-no:armel Depends amdboot:any
+      but none of the choices are installable:
+      [no choices]" aptget build-dep forbidden-no -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -49,7 +53,11 @@ The following packages have unmet dependencies:
  builddeps:forbidden-no:armel : Depends: amdboot:any but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-no -s -a armel --solver internal
 
-testfailuremsg "E: Unsatisfiable dependency group builddeps:forbidden-same:armel -> libc6:any:any" aptget build-dep forbidden-same -s -a armel --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:forbidden-same:armel=1 is selected for install
+   2. builddeps:forbidden-same:armel Depends libc6:any
+      but none of the choices are installable:
+      [no choices]" aptget build-dep forbidden-same -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -63,7 +71,11 @@ The following packages have unmet dependencies:
  builddeps:forbidden-same:armel : Depends: libc6:any but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget build-dep forbidden-same -s -a armel --solver internal
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:forbidden-foreign:armel -> doxygen:any:any' aptget build-dep forbidden-foreign -s -a armel --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:forbidden-foreign:armel=1 is selected for install
+   2. builddeps:forbidden-foreign:armel Depends doxygen:any
+      but none of the choices are installable:
+      [no choices]' aptget build-dep forbidden-foreign -s -a armel --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-675449-essential-are-protected b/test/integration/test-bug-675449-essential-are-protected
index 36e7b645e..c8e832d72 100755
--- a/test/integration/test-bug-675449-essential-are-protected
+++ b/test/integration/test-bug-675449-essential-are-protected
@@ -114,7 +114,7 @@ The following packages have unmet dependencies:
  foo : Depends: libfoo but it is not going to be installed
 E: Error, pkgProblemResolver::Resolve generated breaks, this may be caused by held packages.' aptget purge libfoo -s --solver internal
 
-testequal 'Reading package lists...
+testfailureequal 'Reading package lists...
 Building dependency tree...
 Solving dependencies...
 Some packages could not be installed. This may mean that you have
@@ -125,4 +125,8 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  foo : Depends: libfoo but it is not going to be installed
-E: Conflict: foo:amd64 -> libfoo:amd64 but not libfoo:amd64' aptget purge libfoo -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. libfoo:amd64 is selected for removal
+   2. libfoo:amd64 is selected for install because:
+      1. foo:amd64 is selected for install
+      2. foo:amd64 Depends libfoo' aptget purge libfoo -s --solver 3.0
diff --git a/test/integration/test-bug-683786-build-dep-on-virtual-packages b/test/integration/test-bug-683786-build-dep-on-virtual-packages
index 75f0a9626..a682a2f1a 100755
--- a/test/integration/test-bug-683786-build-dep-on-virtual-packages
+++ b/test/integration/test-bug-683786-build-dep-on-virtual-packages
@@ -41,7 +41,11 @@ The following NEW packages will be installed:
 Inst po-debconf (1 unstable [all])
 Conf po-debconf (1 unstable [all])' aptget build-dep dash -s
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:dash:armel -> po-debconf:armel' aptget build-dep -aarmel dash -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:dash:armel=1 is selected for install
+   2. builddeps:dash:armel Depends po-debconf:armel
+      but none of the choices are installable:
+      [no choices]' aptget build-dep -aarmel dash -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -55,7 +59,11 @@ The following packages have unmet dependencies:
  builddeps:dash:armel : Depends: po-debconf:armel but it is not installable
 E: Unable to correct problems, you have held broken packages.' aptget build-dep -aarmel dash -s --solver internal
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:diffutils:armel -> texi2html:armel' aptget build-dep -aarmel diffutils -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:diffutils:armel=1 is selected for install
+   2. builddeps:diffutils:armel Depends texi2html:armel
+      but none of the choices are installable:
+      [no choices]' aptget build-dep -aarmel diffutils -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
@@ -78,7 +86,11 @@ The following NEW packages will be installed:
 Inst libselinux1-dev (1 unstable [amd64])
 Conf libselinux1-dev (1 unstable [amd64])" aptget build-dep sed -s
 
-testfailuremsg 'E: Unsatisfiable dependency group builddeps:sed:armel -> libselinux-dev:armel' aptget build-dep -aarmel sed -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. builddeps:sed:armel=1 is selected for install
+   2. builddeps:sed:armel Depends libselinux-dev:armel
+      but none of the choices are installable:
+      [no choices]' aptget build-dep -aarmel sed -s --solver 3.0
 testfailureequal 'Reading package lists...
 Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-723586-any-stripped-in-single-arch b/test/integration/test-bug-723586-any-stripped-in-single-arch
index 17c3839d1..672413125 100755
--- a/test/integration/test-bug-723586-any-stripped-in-single-arch
+++ b/test/integration/test-bug-723586-any-stripped-in-single-arch
@@ -41,7 +41,11 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  python-mips : Depends: python3:mips but it is not installable
-E: Unsatisfiable dependency group python-mips:amd64 -> python3:mips:any'
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. python-mips:amd64=3 is selected for install
+   2. python-mips:amd64 Depends python3:mips
+      but none of the choices are installable:
+      [no choices]'
 else
 FAILLOG='Reading package lists...
 Building dependency tree...
diff --git a/test/integration/test-bug-735967-lib32-to-i386-unavailable b/test/integration/test-bug-735967-lib32-to-i386-unavailable
index 2eedf22ab..83992e386 100755
--- a/test/integration/test-bug-735967-lib32-to-i386-unavailable
+++ b/test/integration/test-bug-735967-lib32-to-i386-unavailable
@@ -50,7 +50,13 @@ Remv lib32nss-mdns [0.9-1]
 Inst libnss-mdns [0.9-1] (0.10-6 unstable [amd64])
 Conf libnss-mdns (0.10-6 unstable [amd64])' aptget dist-upgrade -s --solver internal
 
-testfailuremsg 'E: Unsatisfiable dependency group libfoo:amd64 -> libfoo-bin:amd64' aptget install foo -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. libfoo:amd64 is selected for install because:
+      1. foo:amd64=1 is selected for install
+      2. foo:amd64 Depends libfoo
+   2. libfoo:amd64 Depends libfoo-bin
+      but none of the choices are installable:
+      [no choices]' aptget install foo -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-bug-745046-candidate-propagation-fails b/test/integration/test-bug-745046-candidate-propagation-fails
index a8ee50124..8475a4ea1 100755
--- a/test/integration/test-bug-745046-candidate-propagation-fails
+++ b/test/integration/test-bug-745046-candidate-propagation-fails
@@ -39,7 +39,11 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  gedit : Depends: common (>= 2) but it is not installable
-E: Unsatisfiable dependency group gedit:amd64=2 -> common:amd64" aptget install gedit/experimental -sq=0 --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. gedit:amd64=2 is selected as an upgrade
+   2. gedit:amd64=2 Depends common (>= 2)
+      but none of the choices are installable:
+      [no choices]" aptget install gedit/experimental -sq=0 --solver 3.0
 
 insertinstalledpackage 'common' 'amd64' '2'
 
diff --git a/test/integration/test-bug-961266-hold-means-hold b/test/integration/test-bug-961266-hold-means-hold
index 8c18cd757..c97aa0839 100755
--- a/test/integration/test-bug-961266-hold-means-hold
+++ b/test/integration/test-bug-961266-hold-means-hold
@@ -89,7 +89,16 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Conflict: git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 -> not git-ng:amd64 but git-ng:amd64=1:2.26.2-1 -> git-ng:amd64' apt install git-ng -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. git-ng:amd64=1:2.26.2-1 is selected for install
+   2. git-ng:amd64 Depends git (> 1:2.26.2)
+      but none of the choices are installable:
+      - git:amd64=1:2.26.2-1 is not selected for install because:
+        1. git:amd64=1:2.25.1-1 is selected for install
+        2. git:amd64=1:2.25.1-1 conflicts with other versions of itself
+      - git:i386=1:2.26.2-1 is not selected for install because:
+        1. git:amd64=1:2.25.1-1 is selected for install as above
+        2. git:amd64 Conflicts git:i386' apt install git-ng -s --solver 3.0
 
 
 msgmsg 'Now mix it up by' 'holding git-cvs'
@@ -126,7 +135,20 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Conflict: git-cvs:amd64=1:2.25.1-1 -> git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 but git-ng:amd64=1:2.26.2-1 -> git-ng:amd64 -> git:amd64=1:2.26.2-1' apt install git-ng -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. git:amd64=1:2.26.2-1 is selected as an upgrade because:
+      1. git-ng:amd64=1:2.26.2-1 is selected for install
+      2. git-ng:amd64 Depends git (> 1:2.26.2)
+         [selected git-ng:amd64]
+      For context, additional choices that could not be installed:
+      * In git-ng:amd64 Depends git (> 1:2.26.2):
+        - git:i386=1:2.26.2-1 is not selected for install because:
+          1. git:amd64 is selected for install
+          2. git:amd64 Conflicts git:i386
+   2. git:amd64=1:2.26.2-1 is not selected for install because:
+      1. git-cvs:amd64=1:2.25.1-1 is selected for install
+      2. git-cvs:amd64=1:2.25.1-1 Depends git (< 1:2.25.1-.)
+      3. git:amd64=1:2.25.1-1 conflicts with other versions of itself' apt install git-ng -s --solver 3.0
 
 
 msgmsg 'Now mix it up by' 'holding both'
@@ -162,4 +184,13 @@ The following information may help to resolve the situation:
 
 The following packages have unmet dependencies:
  git-ng : Depends: git (> 1:2.26.2)
-E: Conflict: git:amd64=1:2.25.1-1 -> not git:amd64=1:2.26.2-1 -> not git-ng:amd64 but git-ng:amd64=1:2.26.2-1 -> git-ng:amd64' apt install git-ng -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. git-ng:amd64=1:2.26.2-1 is selected for install
+   2. git-ng:amd64 Depends git (> 1:2.26.2)
+      but none of the choices are installable:
+      - git:amd64=1:2.26.2-1 is not selected for install because:
+        1. git:amd64=1:2.25.1-1 is selected for install
+        2. git:amd64=1:2.25.1-1 conflicts with other versions of itself
+      - git:i386=1:2.26.2-1 is not selected for install because:
+        1. git:amd64=1:2.25.1-1 is selected for install as above
+        2. git:amd64 Conflicts git:i386' apt install git-ng -s --solver 3.0
diff --git a/test/integration/test-explore-or-groups-in-markinstall b/test/integration/test-explore-or-groups-in-markinstall
index 4c67296d7..60de59193 100755
--- a/test/integration/test-explore-or-groups-in-markinstall
+++ b/test/integration/test-explore-or-groups-in-markinstall
@@ -161,7 +161,13 @@ testfailureequal "$BADSOLVETEXT3
 The following packages have unmet dependencies:
  bad-upgrade-level1 : Depends: bad-upgrade-level0 (>= 2) but 1 is to be installed
                       Depends: unneeded2 but it is not going to be installed
-E: Unsatisfiable dependency group bad-upgrade-level0:amd64=2 -> unknown:amd64" apt install bad-upgrade-level1 -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. bad-upgrade-level0:amd64=2 is selected as an upgrade because:
+      1. bad-upgrade-level1:amd64=2 is selected as an upgrade
+      2. bad-upgrade-level1:amd64=2 Depends bad-upgrade-level0 (>= 2)
+   2. bad-upgrade-level0:amd64=2 Depends unknown
+      but none of the choices are installable:
+      [no choices]" apt install bad-upgrade-level1 -s --solver 3.0
 testfailureequal "$BADSOLVETEXT
 The following packages have unmet dependencies:
  bad-conflict-level0 : Conflicts: bad-conflict-level2 but 1 is to be installed
@@ -171,7 +177,15 @@ testfailureequal "$BADSOLVETEXT3
 The following packages have unmet dependencies:
  bad-conflict-level2 : Depends: bad-conflict-level1 but it is not going to be installed
                        Depends: unneeded2 but it is not going to be installed
-E: Conflict: bad-conflict-level2:amd64=1 -> not bad-conflict-level0:amd64 -> not bad-conflict-level1:amd64 but bad-conflict-level2:amd64=1 -> bad-conflict-level2:amd64 -> bad-conflict-level1:amd64" apt install bad-conflict-level2 -s --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. bad-conflict-level1:amd64 is selected for install because:
+      1. bad-conflict-level2:amd64=1 is selected for install
+      2. bad-conflict-level2:amd64 Depends bad-conflict-level1
+   2. bad-conflict-level1:amd64 Depends bad-conflict-level0
+      but none of the choices are installable:
+      - bad-conflict-level0:amd64 is not selected for install because:
+        1. bad-conflict-level2:amd64=1 is selected for install as above
+        2. bad-conflict-level0:amd64 Conflicts bad-conflict-level2" apt install bad-conflict-level2 -s --solver 3.0
 
 if $TEST_WITH_APTITUDE; then
 	testsuccesstailequal 6 'The following packages have been kept back:
diff --git a/test/integration/test-handling-broken-orgroups b/test/integration/test-handling-broken-orgroups
index f9c436f81..5c882b516 100755
--- a/test/integration/test-handling-broken-orgroups
+++ b/test/integration/test-handling-broken-orgroups
@@ -47,7 +47,11 @@ Inst coolstuff2 (1.0-1 unstable [all])
 Conf stuff (1.0-1 unstable [all])
 Conf coolstuff2 (1.0-1 unstable [all])' aptget install coolstuff2 -s
 
-testfailuremsg 'E: Unsatisfiable dependency group coolstuff-broken:i386 -> cool2:i386' aptget install coolstuff-broken --solver 3.0 -s
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. coolstuff-broken:i386=1.0-1 is selected for install
+   2. coolstuff-broken:i386 Depends cool2 | stuff2
+      but none of the choices are installable:
+      [no choices]' aptget install coolstuff-broken --solver 3.0 -s
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -95,7 +99,11 @@ Inst coolstuff-provided (1.0-1 unstable [all])
 Conf extrastuff (1.0-1 unstable [all])
 Conf coolstuff-provided (1.0-1 unstable [all])' aptget install coolstuff-provided -s
 
-testfailuremsg 'E: Conflict: coolstuff-provided-broken:i386=1.0-1 -> coolstuff-provided-broken:i386 -> extrastuff:i386=1.0-1 but not extrastuff:i386=1.0-1' aptget install coolstuff-provided-broken --solver 3.0 -s
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. extrastuff:i386=1.0-1 is not selected for install
+   2. extrastuff:i386=1.0-1 is selected for install because:
+      1. coolstuff-provided-broken:i386=1.0-1 is selected for install
+      2. coolstuff-provided-broken:i386 Depends cool2 | stuff-abi-2' aptget install coolstuff-provided-broken --solver 3.0 -s
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-ignore-provides-if-versioned-breaks b/test/integration/test-ignore-provides-if-versioned-breaks
index 27197e1e6..87e609bef 100755
--- a/test/integration/test-ignore-provides-if-versioned-breaks
+++ b/test/integration/test-ignore-provides-if-versioned-breaks
@@ -32,7 +32,12 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Breaks: foo-same'
 
 
 setupaptarchive
-testfailuremsg 'E: Conflict: foo-provider:i386=1.0 -> not foo-breaker-none:i386 but foo-breaker-none:i386=1.0 -> foo-breaker-none:i386' aptget install foo-provider foo-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-breaker-none:i386=1.0 is selected for install
+   2. foo-breaker-none:i386 is not selected for install because:
+      1. foo-provider:i386=1.0 is selected for install
+      2. foo-breaker-none:i386 Breaks foo
+         [selected foo-provider:i386=1.0]' aptget install foo-provider foo-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -71,7 +76,12 @@ Conf foo (4.0 unstable [i386])
 Conf foo-breaker-3 (1.0 unstable [i386])
 Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-foreign-breaker-none:i386=1.0 -> foo-foreign-breaker-none:i386 -> not foo-foreign-provider:i386=1.0 but foo-foreign-provider:i386=1.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-foreign-provider:i386=1.0 is selected for install
+   2. foo-foreign-provider:i386=1.0 is not selected for install because:
+      1. foo-foreign-breaker-none:i386=1.0 is selected for install
+      2. foo-foreign-breaker-none:i386 Breaks foo-foreign
+         [selected foo-foreign-breaker-none:i386]' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -110,7 +120,12 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64])
 Conf foo-foreign-breaker-3 (1.0 unstable [i386])
 Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-same-provider:i386=1.0 -> not foo-same-breaker-none:i386 but foo-same-breaker-none:i386=1.0 -> foo-same-breaker-none:i386' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-same-breaker-none:i386=1.0 is selected for install
+   2. foo-same-breaker-none:i386 is not selected for install because:
+      1. foo-same-provider:i386=1.0 is selected for install
+      2. foo-same-breaker-none:i386 Breaks foo-same
+         [selected foo-same-provider:i386=1.0]' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-ignore-provides-if-versioned-conflicts b/test/integration/test-ignore-provides-if-versioned-conflicts
index caff5e3b0..cdf69656e 100755
--- a/test/integration/test-ignore-provides-if-versioned-conflicts
+++ b/test/integration/test-ignore-provides-if-versioned-conflicts
@@ -33,7 +33,12 @@ insertpackage 'unstable' 'foo-same-breaker-none' 'i386' '1.0' 'Conflicts: foo-sa
 
 setupaptarchive
 
-testfailuremsg 'E: Conflict: foo-provider:i386=1.0 -> not foo-breaker-none:i386 but foo-breaker-none:i386=1.0 -> foo-breaker-none:i386' aptget install foo-provider foo-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-breaker-none:i386=1.0 is selected for install
+   2. foo-breaker-none:i386 is not selected for install because:
+      1. foo-provider:i386=1.0 is selected for install
+      2. foo-breaker-none:i386 Conflicts foo
+         [selected foo-provider:i386=1.0]' aptget install foo-provider foo-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -72,7 +77,12 @@ Conf foo (4.0 unstable [i386])
 Conf foo-breaker-3 (1.0 unstable [i386])
 Conf foo-provider (1.0 unstable [i386])' aptget install foo-provider foo-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-foreign-breaker-none:i386=1.0 -> foo-foreign-breaker-none:i386 -> not foo-foreign-provider:i386=1.0 but foo-foreign-provider:i386=1.0' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-foreign-provider:i386=1.0 is selected for install
+   2. foo-foreign-provider:i386=1.0 is not selected for install because:
+      1. foo-foreign-breaker-none:i386=1.0 is selected for install
+      2. foo-foreign-breaker-none:i386 Conflicts foo-foreign
+         [selected foo-foreign-breaker-none:i386]' aptget install foo-foreign-provider foo-foreign-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -111,7 +121,12 @@ Conf foo-foreign:amd64 (4.0 unstable [amd64])
 Conf foo-foreign-breaker-3 (1.0 unstable [i386])
 Conf foo-foreign-provider (1.0 unstable [i386])' aptget install foo-foreign-provider foo-foreign-breaker-3 -s
 
-testfailuremsg 'E: Conflict: foo-same-provider:i386=1.0 -> not foo-same-breaker-none:i386 but foo-same-breaker-none:i386=1.0 -> foo-same-breaker-none:i386' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-same-breaker-none:i386=1.0 is selected for install
+   2. foo-same-breaker-none:i386 is not selected for install because:
+      1. foo-same-provider:i386=1.0 is selected for install
+      2. foo-same-breaker-none:i386 Conflicts foo-same
+         [selected foo-same-provider:i386=1.0]' aptget install foo-same-provider foo-same-breaker-none -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
diff --git a/test/integration/test-multiarch-allowed b/test/integration/test-multiarch-allowed
index 9d8920e0f..ca13cc50d 100755
--- a/test/integration/test-multiarch-allowed
+++ b/test/integration/test-multiarch-allowed
@@ -64,18 +64,36 @@ Inst needsfoo:i386 (1 unstable [i386])
 Conf foo:i386 (1 unstable [i386])
 Conf needsfoo:i386 (1 unstable [i386])' aptget install needsfoo:i386 -s
 # FIXME: same problem, but two different unmet dependency messages depending on install order
-testfailuremsg "E: Conflict: foo:amd64=1 -> not foo:i386 -> not needsfoo:i386 but needsfoo:i386=1 -> needsfoo:i386" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoo:i386=1 is selected for install
+   2. needsfoo:i386 Depends foo:i386
+      but none of the choices are installable:
+      - foo:i386 is not selected for install because:
+        1. foo:amd64=1 is selected for install
+        2. foo:i386 Conflicts foo" aptget install needsfoo:i386 foo:amd64 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  foo : Conflicts: foo:i386 but 1 is to be installed
  foo:i386 : Conflicts: foo but 1 is to be installed
 E: Unable to correct problems, you have held broken packages." aptget install needsfoo:i386 foo:amd64 -s --solver internal
-testfailuremsg "E: Conflict: foo:amd64=1 -> not foo:i386 -> not needsfoo:i386 but needsfoo:i386=1 -> needsfoo:i386" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoo:i386=1 is selected for install
+   2. needsfoo:i386 Depends foo:i386
+      but none of the choices are installable:
+      - foo:i386 is not selected for install because:
+        1. foo:amd64=1 is selected for install
+        2. foo:i386 Conflicts foo" aptget install foo:amd64 needsfoo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needsfoo:i386 : Depends: foo:i386 but it is not installable
 E: Unable to correct problems, you have held broken packages." aptget install foo:amd64 needsfoo:i386 -s --solver internal
-testfailuremsg "E: Conflict: foo:i386=1 -> not foo:amd64 -> not needsfoo:amd64 but needsfoo:amd64=1 -> needsfoo:amd64" aptget install needsfoo foo:i386 -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoo:amd64=1 is selected for install
+   2. needsfoo:amd64 Depends foo
+      but none of the choices are installable:
+      - foo:amd64 is not selected for install because:
+        1. foo:i386=1 is selected for install
+        2. foo:amd64 Conflicts foo:i386" aptget install needsfoo foo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  foo : Conflicts: foo:i386 but 1 is to be installed
@@ -135,11 +153,19 @@ if [ "$APT_SOLVER" = "3.0" ]; then
 NEEDSFOO2NATIVE="$BADPREFIX
 The following packages have unmet dependencies:
  needsfoover2 : Depends: foo:any (>= 2)
-E: Unsatisfiable dependency group needsfoover2:amd64 -> foo:any:any"
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoover2:amd64=1 is selected for install
+   2. needsfoover2:amd64 Depends foo:any (>= 2)
+      but none of the choices are installable:
+      [no choices]"
 NEEDSFOO2FOREIGN="$BADPREFIX
 The following packages have unmet dependencies:
  needsfoover2:i386 : Depends: foo:any (>= 2)
-E: Unsatisfiable dependency group needsfoover2:i386 -> foo:any:any"
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needsfoover2:i386=1 is selected for install
+   2. needsfoover2:i386 Depends foo:any (>= 2)
+      but none of the choices are installable:
+      [no choices]"
 else
 NEEDSFOO2NATIVE="$BADPREFIX
 The following packages have unmet dependencies:
@@ -156,9 +182,31 @@ testfailureequal "$NEEDSFOO2FOREIGN" aptget install needsfoover2:i386 foo:i386 -
 testfailureequal "$NEEDSFOO2NATIVE" aptget install needsfoover2 foo:i386 -s
 
 solveableinsinglearch2() {
-	testfailuremsg 'E: Conflict: hatesfoo:amd64=1 -> hatesfoo:amd64 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfoo -s --solver 3.0
-	testfailuremsg 'E: Conflict: hatesfooany:amd64=1 -> hatesfooany:amd64 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfooany -s --solver 3.0
-	testfailuremsg 'E: Conflict: hatesfoonative:amd64=1 -> hatesfoonative:amd64 -> not foo:amd64=1 but foo:amd64=1' aptget install foo hatesfoonative -s --solver 3.0
+	testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64=1 is selected for install
+   2. foo:amd64=1 is not selected for install because:
+      1. hatesfoo:amd64=1 is selected for install
+      2. hatesfoo:amd64 Conflicts foo' aptget install foo hatesfoo -s --solver 3.0
+
+	if [ "$(getarchitectures)" = "amd64 " ]; then
+		testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64=1 is selected for install
+   2. foo:amd64=1 is not selected for install because:
+      1. hatesfooany:amd64=1 is selected for install
+      2. hatesfooany:amd64 Conflicts foo:any' aptget install foo hatesfooany -s --solver 3.0
+	else
+		testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64=1 is selected for install
+   2. foo:amd64=1 is not selected for install because:
+      1. hatesfooany:amd64=1 is selected for install
+      2. hatesfooany:amd64 Conflicts foo:any
+         [selected hatesfooany:amd64]' aptget install foo hatesfooany -s --solver 3.0
+	fi
+	testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:amd64=1 is selected for install
+   2. foo:amd64=1 is not selected for install because:
+      1. hatesfoonative:amd64=1 is selected for install
+      2. hatesfoonative:amd64 Conflicts foo:amd64' aptget install foo hatesfoonative -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfoo : Conflicts: foo but 1 is to be installed
@@ -171,12 +219,21 @@ The following packages have unmet dependencies:
 E: Unable to correct problems, you have held broken packages." aptget install foo hatesfoonative -s --solver internal
 }
 solveableinsinglearch2
-testfailuremsg "E: Conflict: hatesfoo:amd64=1 -> hatesfoo:amd64 -> not foo:i386=1 but foo:i386=1" aptget install foo:i386 hatesfoo -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:i386=1 is selected for install
+   2. foo:i386=1 is not selected for install because:
+      1. hatesfoo:amd64=1 is selected for install
+      2. hatesfoo:amd64 Conflicts foo:i386" aptget install foo:i386 hatesfoo -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfoo : Conflicts: foo:i386 but 1 is to be installed
 E: Unable to correct problems, you have held broken packages." aptget install foo:i386 hatesfoo -s --solver internal
-testfailuremsg "E: Conflict: hatesfooany:amd64=1 -> hatesfooany:amd64 -> not foo:i386=1 but foo:i386=1" aptget install foo:i386 hatesfooany -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:i386=1 is selected for install
+   2. foo:i386=1 is not selected for install because:
+      1. hatesfooany:amd64=1 is selected for install
+      2. hatesfooany:amd64 Conflicts foo:any
+         [selected hatesfooany:amd64]" aptget install foo:i386 hatesfooany -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hatesfooany : Conflicts: foo:any
@@ -191,7 +248,11 @@ Inst hatesfoonative (1 unstable [amd64])
 Conf foo:i386 (1 unstable [i386])
 Conf hatesfoonative (1 unstable [amd64])' aptget install foo:i386 hatesfoonative -s
 
-testfailuremsg "E: Unsatisfiable dependency group needscoolfoo:i386 -> coolfoo:i386" aptget install needscoolfoo:i386 -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needscoolfoo:i386=1 is selected for install
+   2. needscoolfoo:i386 Depends coolfoo:i386
+      but none of the choices are installable:
+      [no choices]" aptget install needscoolfoo:i386 -s --solver 3.0
 testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoo:i386 : Depends: coolfoo:i386 but it is not installable
@@ -264,12 +325,20 @@ Inst needscoolfoover1 (1 unstable [amd64])
 Conf coolfoo (1 unstable [amd64])
 Conf coolfoover (1 unstable [amd64])
 Conf needscoolfoover1 (1 unstable [amd64])' aptget install needscoolfoover1 -s
-	testfailuremsg "E: Unsatisfiable dependency group needscoolfoover2:amd64 -> coolfoo:any:any" aptget install needscoolfoover2 -s --solver 3.0
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needscoolfoover2:amd64=1 is selected for install
+   2. needscoolfoover2:amd64 Depends coolfoo:any (>= 2)
+      but none of the choices are installable:
+      [no choices]" aptget install needscoolfoover2 -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoover2 : Depends: coolfoo:any (>= 2)
 E: Unable to correct problems, you have held broken packages." aptget install needscoolfoover2 -s --solver internal
-	testfailuremsg "E: Unsatisfiable dependency group needscoolfoover3:amd64 -> coolfoo:any:any" aptget install needscoolfoover3 -s --solver 3.0
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. needscoolfoover3:amd64=1 is selected for install
+   2. needscoolfoover3:amd64 Depends coolfoo:any (>= 2)
+      but none of the choices are installable:
+      [no choices]" aptget install needscoolfoover3 -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  needscoolfoover3 : Depends: coolfoo:any (>= 2)
diff --git a/test/integration/test-multiarch-foreign b/test/integration/test-multiarch-foreign
index 5a7b1a3b7..a04b854a5 100755
--- a/test/integration/test-multiarch-foreign
+++ b/test/integration/test-multiarch-foreign
@@ -179,14 +179,23 @@ distribution that some required packages have not yet been created
 or been moved out of Incoming.
 The following information may help to resolve the situation:
 '
-	testfailuremsg "E: Conflict: ${1%:*}:$4=1.0 -> not hates-foo:amd64 but hates-foo:amd64=1.0 -> hates-foo:amd64"  aptget install $1 hates-foo -s --solver 3.0
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. hates-foo:amd64=1.0 is selected for install
+   2. hates-foo:amd64 is not selected for install because:
+      1. ${1%:*}:$4=1.0 is selected for install
+      2. hates-foo:amd64 Conflicts foo
+         [selected ${1%:*}:$4=1.0]"  aptget install $1 hates-foo -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  hates-foo : Conflicts: foo
              Conflicts: foo:i386
              Conflicts: foo:armel
 E: Unable to correct problems, you have held broken packages." aptget install $1 hates-foo -s --solver internal
-	testfailuremsg "E: Conflict: $2:amd64=1.0 -> $2:amd64 -> not foo:$4=1.0 but foo:$4=1.0" aptget install $1 $2 -s --solver 3.0
+	testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo:$4=1.0 is selected for install
+   2. foo:$4=1.0 is not selected for install because:
+      1. $2:amd64=1.0 is selected for install
+      2. $2:amd64 Conflicts foo:$4" aptget install $1 $2 -s --solver 3.0
 	testfailureequal "$BADPREFIX
 The following packages have unmet dependencies:
  $2 : Conflicts: foo:$4
diff --git a/test/integration/test-prefer-higher-priority-providers b/test/integration/test-prefer-higher-priority-providers
index e16e98e23..87954c5d4 100755
--- a/test/integration/test-prefer-higher-priority-providers
+++ b/test/integration/test-prefer-higher-priority-providers
@@ -91,7 +91,16 @@ Inst awesome (1 unstable [all])
 Conf baz (1 unstable [all])
 Conf awesome (1 unstable [all])" aptget install awesome foo- bar- -s
 
-testfailuremsg "E: Conflict: awesome:$native=1 -> awesome:$native -> baz:$native=1 -> baz:$native but not baz:$native" aptget install awesome foo- bar- baz- -s --solver 3.0
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. baz:$native is not selected for install
+   2. baz:$native=1 is selected for install because:
+      1. awesome:$native=1 is selected for install
+      2. awesome:$native Depends stuff
+         [selected awesome:$native]
+      For context, additional choices that could not be installed:
+      * In awesome:$native Depends stuff:
+        - foo:$native=1 is not selected for install
+        - bar:$native=1 is not selected for install" aptget install awesome foo- bar- baz- -s --solver 3.0
 testfailureequal "Reading package lists...
 Building dependency tree...
 Package 'foo' is not installed, so not removed
diff --git a/test/integration/test-release-candidate-switching b/test/integration/test-release-candidate-switching
index db7e29495..be5b3f997 100755
--- a/test/integration/test-release-candidate-switching
+++ b/test/integration/test-release-candidate-switching
@@ -449,7 +449,11 @@ The following information may help to resolve the situation:
 The following packages have unmet dependencies:
  uninstallablepkg : Depends: libmtp8 (>= 10:0.20.1) but it is not going to be installed
                     Depends: amarok-utils (= 2.3.2-2+exp) but it is not going to be installed
-E: Unsatisfiable dependency group uninstallablepkg:i386 -> libmtp8:i386" aptget install uninstallablepkg/experimental --trivial-only -V --solver 3.0
+E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. amarok-utils:i386=2.3.2-2+exp is not selected for install
+   2. amarok-utils:i386=2.3.2-2+exp is selected for install because:
+      1. uninstallablepkg:i386=1.0 is selected for install
+      2. uninstallablepkg:i386 Depends amarok-utils (= 2.3.2-2+exp)" aptget install uninstallablepkg/experimental --trivial-only -V --solver 3.0
 
 insertinstalledpackage 'libmtp8' 'i386'  '1'
 insertinstalledpackage 'amarok' 'i386' '3' 'Depends: amarok-common (= 3), libmtp8 (>= 1)'
diff --git a/test/integration/test-solver3-alternatives b/test/integration/test-solver3-alternatives
new file mode 100755
index 000000000..8a3645f82
--- /dev/null
+++ b/test/integration/test-solver3-alternatives
@@ -0,0 +1,32 @@
+#!/bin/sh
+set -e
+
+TESTDIR="$(readlink -f "$(dirname "$0")")"
+. "$TESTDIR/framework"
+setupenvironment
+configarchitecture 'amd64'
+
+insertpackage 'unstable' 'unsat' 'all' '3' 'Depends: a | b'
+insertpackage 'unstable' 'a' 'all' '3' 'Depends: aa|ab'
+insertpackage 'unstable' 'b' 'all' '3' 'Depends: ba|bb'
+insertpackage 'unstable' 'aa' 'all' '3' 'Depends: aax'
+insertpackage 'unstable' 'ab' 'all' '3' 'Depends: abx'
+insertpackage 'unstable' 'ba' 'all' '3' 'Depends: bay'
+insertpackage 'unstable' 'bb' 'all' '3' 'Depends: bby'
+setupaptarchive
+
+testfailuremsg "E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. bb:amd64 is selected for install because:
+      1. unsat:amd64=3 is selected for install
+      2. unsat:amd64 Depends a | b
+         [selected b:amd64 for install]
+      3. b:amd64 Depends ba | bb
+         [selected b:amd64]
+      For context, additional choices that could not be installed:
+      * In unsat:amd64 Depends a | b:
+        - a:amd64 is not selected for install
+      * In b:amd64 Depends ba | bb:
+        - ba:amd64 is not selected for install
+   2. bb:amd64 Depends bby
+      but none of the choices are installable:
+      [no choices]" apt install unsat --solver 3.0
diff --git a/test/integration/test-specific-architecture-dependencies b/test/integration/test-specific-architecture-dependencies
index be8ea4245..b9ce155de 100755
--- a/test/integration/test-specific-architecture-dependencies
+++ b/test/integration/test-specific-architecture-dependencies
@@ -194,7 +194,11 @@ The following NEW packages will be installed:
 Inst foo-depender (1 unstable [amd64])
 Conf foo-depender (1 unstable [amd64])' aptget install foo-depender -s
 
-testfailuremsg 'E: Unsatisfiable dependency group foo-depender:i386 -> foo:i386' aptget install foo-depender:i386 -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. foo-depender:i386=1 is selected for install
+   2. foo-depender:i386 Depends foo:i386
+      but none of the choices are installable:
+      [no choices]' aptget install foo-depender:i386 -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have
@@ -313,7 +317,11 @@ Remv libold [1]
 Inst breaker-x64 (1 unstable [amd64])
 Conf breaker-x64 (1 unstable [amd64])' aptget install breaker-x64:amd64 -s
 
-testfailuremsg 'E: Unsatisfiable dependency group depender-x32:amd64 -> libc6:i386:any' aptget install depender-x32 -s --solver 3.0
+testfailuremsg 'E: Unable to satisfy dependencies. Reached two conflicting decisions:
+   1. depender-x32:amd64=1 is selected for install
+   2. depender-x32:amd64 Depends libc6:i386
+      but none of the choices are installable:
+      [no choices]' aptget install depender-x32 -s --solver 3.0
 testfailureequal 'Reading package lists...
 Building dependency tree...
 Some packages could not be installed. This may mean that you have