diff --git a/0001-solver-Free-favorq-when-running-solver_solve.patch b/0001-solver-Free-favorq-when-running-solver_solve.patch
new file mode 100644
index 0000000..0c474ce
--- /dev/null
+++ b/0001-solver-Free-favorq-when-running-solver_solve.patch
@@ -0,0 +1,29 @@
+From 6c9ffb5938ed81c35df04f1c7ab4082a65e39173 Mon Sep 17 00:00:00 2001
+From: Igor Gnatenko <i.gnatenko.brain@gmail.com>
+Date: Tue, 2 Apr 2019 14:22:08 +0200
+Subject: [PATCH] solver: Free favorq when running solver_solve()
+
+Otherwise, favorq leaks from previous executions.
+
+Fixes: https://github.com/openSUSE/libsolv/issues/312
+Fixes: 2645bc64b322460ac77d0d051de63434d4a90a0a
+Signed-off-by: Igor Gnatenko <i.gnatenko.brain@gmail.com>
+---
+ src/solver.c | 1 +
+ 1 file changed, 1 insertion(+)
+
+diff --git a/src/solver.c b/src/solver.c
+index b335e6af..7957373e 100644
+--- a/src/solver.c
++++ b/src/solver.c
+@@ -3389,6 +3389,7 @@ solver_solve(Solver *solv, Queue *job)
+   map_zerosize(&solv->cleandepsmap);
+   map_zerosize(&solv->weakrulemap);
+   solv->favormap = solv_free(solv->favormap);
++  queuep_free(&solv->favorq);
+   queue_empty(&solv->weakruleq);
+   solv->watches = solv_free(solv->watches);
+   queue_empty(&solv->ruletojob);
+-- 
+2.21.0
+
diff --git a/libsolv.spec b/libsolv.spec
index 01a812b..bc102d3 100644
--- a/libsolv.spec
+++ b/libsolv.spec
@@ -42,13 +42,18 @@
 
 Name:           lib%{libname}
 Version:        0.7.4
-Release:        1%{?dist}
+Release:        2%{?dist}
 Summary:        Package dependency solver
 
 License:        BSD
 URL:            https://github.com/openSUSE/libsolv
 Source:         %{url}/archive/%{version}/%{name}-%{version}.tar.gz
 
+# https://github.com/openSUSE/libsolv/issues/312
+# https://github.com/openSUSE/libsolv/pull/313
+# https://bugzilla.redhat.com/show_bug.cgi?id=1695069
+Patch0001:      0001-solver-Free-favorq-when-running-solver_solve.patch
+
 BuildRequires:  cmake
 BuildRequires:  gcc-c++
 BuildRequires:  ninja-build
@@ -297,6 +302,9 @@ Python 3 version.
 %endif
 
 %changelog
+* Tue Apr 02 14:45:22 CEST 2019 Igor Gnatenko <ignatenkobrain@fedoraproject.org> - 0.7.4-2
+- Backport patch to fix solver_solve() running multiple times with SOLVER_FAVOR
+
 * Fri Mar 29 16:13:00 CET 2019 Igor Gnatenko <ignatenkobrain@fedoraproject.org> - 0.7.4-1
 - Update to 0.7.4