Coding Games and Programming Challenges to Code Better
Send your feedback or ask for help here!
Created by @David_Augusto_Villa,validated by @About,@Timinator and @Drugon.
If you have any issues, feel free to ping them.
Strangely enough for me this was “tile” placement challenge.
Thanks to @5DN1L for puzzle and @Timinator for handy tutorial
I’ve seen the tutorial, it looks great, and I can’t wait to tackle some of the other puzzles myself!
Hi all, I’m trying to solve the puzzle but I got really confused by the description.
In the description it says:
“The first set of evidence thus indicates that either Madame Turquoise or Reverend Crimson is guilty. Sets 2 and 3 in this illustration state possibilities for the weapon and the location.”
But in reality, the test “Example shuffled” (n 2), it is returning the weapon and location as the last lines.
I know they are all evidences, but the description makes it clear that they stays ad line 2 and 3. Can we change the description accordingly?
Weapon and location apply only to that illustration. Many of the other test cases also deviate from this. In general only the first line is special in any way. I will try to make that clearer.
The text doesn’t tell how many time we have before giving our answer.
I’m quite confident in my algo, but I have timeout for the larger test cases, and knowing the time limit would help.
For puzzles without a viewer, time limits vary depending on the programming language and are fixed by CodinGame. Since puzzle authors have no control over these limits, they aren’t responsible for listing the limits in the statement, and it’s also weird to list them out for every puzzle.
Ok 
I mostly come here for the season challenges, it is the first time I try something without viewer so I didn’t know, thanks !
1 Like
Note: I tried to not spoil anything but there are still hints. Ignore this comment if you haven’t solved the puzzle already.
Let me preface this by saying that I already solved the puzzle a long time ago, around when Timinator’s playground appeared. But I didn’t stop there, I got baited by the Satisfiability tag, I wrote a simple SAT solver in python following some paper, and tried intermittently for a couple weeks to not timeout on the last 4 test pairs to no avail.
The pysat library has wrappers of award-winning SAT solvers that will manage to complete the test suite with no issues, but even moderately optimized python solvers (which only fulfill a pedagogical space, since the language itself is definitely not fast enough for the matter), will timeout on the last 4 test pairs. An example of this is the sympy implementation of dpll.
So today I just gave up, submitted the certainly easier DLX solution, and was much surprised at looking at the intended solution. It seemed clearly biaised to a certain strategy and hackable within the given constraints.
That was the theory, so I went and wrote some generator to prove it. Now, the constraints of the puzzle are honestly lackluster. There is no mention of the number of different clues, or the maximum number of clues in a test (and other relevant metrics that I won’t discuss). I’m saying this, because it is very easy to make a test within the stated constraints that timeouts the intended solution, but a lot harder to make it timeout when those metrics are bounded by similar values to those used in the test suite.
There is even this line:
assert min(counts.values()) > 1 or max(counts.values()) == 1
that is deceptively constraining, even though I assume its intended purpose was completely different.
The proof.
The last 4 tests have all:
L = 250
N = 3
number_of_different_clues = 1236
minmax_number_of_clues = (2, 6)
This is the simplest test (as in, simpler or equal in every possible metric) that timeouts the intended solution (and my SAT solver too, snif), but that the DLX happily pass.
L = 200
N = 2
number_of_different_clues = 693
minmax_number_of_clues = (2, 6)
200 2
Yx, az
ME, fz, ph, rw
BL, Hf, QM, RS, ep
GL, if, tM
RH, RY, Sc, zh
Zw, kY, le, nB
Fa, lD, n
Vx, dN, jX
Ei, KT, Vk
Bz, If, Lk
AS, dp, nW, tW
JN, iF, tj
Ei, HU, Kp, rV
hY, rP, sJ
bq, gx, nW, vB
Sb, dp, rp
GK, Zv, xB
BD, az, tj
Ru, ec, jX
FH, Ru, kE, kn, zU
Bu, Sc, ew
NU, Yd, mr
hS, kn, yl
Ra, ec, lI, vn
Fv, aK, qU, rw
Db, OK, sA
RY, Vc, nW
hF, id, vB
IL, YF, zU
Dx, Ju, zr
IL, Kp, n, sJ, zU
Qy, Rw, Zh, vT
TN, rP, tW
Sb, dH, eU, iq
Pz, ZD, rw
C, Zm, qg
NC, dq, iz, kf
OV, hT, hf
Dx, pz, sP
OK, Pz, wn
aH, sA, vn, zs
cA, dn, lj
by, eZ, rP
NU, PY, ov
Gk, MY, RH, sh, vS
Ac, PC, lU
Qj, Sc, kf
AM, Kz, YF, iF
NC, ZD, hg, rb
HU, Zh, ay, zS
Ba, Sj, UI
BL, kC, nB
dn, sD, tP
C, GL, sJ
nB, oR, ua
Jl, Sc, pz
NK, nB, oW, wn
RS, Yx, sE, yY
PC, bm, kE
VL, fK, pM, ua
Ac, QX, hS
PB, mr, oB, wM
PC, Ra, jQ, lD
Gh, ij, sE
BE, CC, lB
Ky, pM, qg, wr
Vx, ZW, eo, tg
Hw, IJ, Uw, rw
oI, oW, yI
NK, Vx, yL
Bu, Uw, dn
BD, jP, rp, zT
AA, Fl, NK
Db, Ju, Yd, fK, jP
DD, hS, lj, sD
Bm, CC, HZ, If, QX, YQ
EA, Nm, eo, lI
dF, gD, rw
Zu, cA, dr, fS
Pz, Yd, oW, wr, zT
FH, VJ, dn
rp, ye, zS
Vk, Vx, yY
Zh, Zw, ol
EA, dH, mN, yl
HZ, TN, wM
AA, Vx, Yx
Cp, Dq, Hs, oB, sD
Bm, Xh, sE
Ig, hH, nW, vY
QG, UI, qB
GL, QG, ya
AM, FI, hF
OK, ZD, tg
Fu, kn, rb, ye, zs
Bz, Hs, aH, ry, sA
Oo, YQ, tj, vS
BQ, CT, hI
Fa, Kp, wk
As, Fl, Hw
AS, Rw, az, if
Fu, Xz, xB
Oo, Ts, wk
Fa, ol, sh
Gk, Ib, dq, eo
Ig, Ij, Tx, yI
Dq, Sj, ya, zS
CX, Vc, jQ, oj
Dq, OV, dr
Ja, hH, zR
GK, VJ, dH, gF
PC, ph, wb
RY, ZC, mj, sE
BQ, Fv, Jl, Uw
Ba, Bz, Qj
Bz, Ts, mj, vY
Ij, ij, nB
Fu, Pa, yG
IJ, Zh, v
AD, GX, cA
iQ, lz, oI, sE
CC, DD, Mf, bm
Fu, Xb, ZW
an, gD, wr
Fu, Hw, KB
Ru, aV, ov, ya
Aq, BQ, Ig, vB
EA, hf, kS
GL, Ky, Sj
PC, qU, zR
Fl, ew, qB, ry
fS, hH, kk
Dq, aH, by, hI
Aq, IL, Ts, dN, rV
Xb, fS, zT
JN, lB, nB
GK, VJ, lj
TN, mN, v, wM
ME, Ru, gF, xy
Vx, ZW, kS
Dq, Ju, an
CX, Zv, oI
Bm, fK, ob
EA, Tx, gx
Hn, Oo, oN
Bz, Kz, hY
Dq, Pa, mr
Cp, HU, tc
Xb, az, qB, wx
Oo, aV, eZ
AD, oN, vT
AD, Mf, ph
gD, sP, wM, zs
BD, CC, GX, YQ
CC, DV, Ib, NE, Pa, iQ, kS
qg, ua, wM
AM, Qy, id
Zh, dN, le, oj
Zm, oR, tW
BE, fS, sh
AD, ew, iz, kY
Dx, iq, qU
QG, Ru, pM, wW, wb
jQ, vY, vn
Hf, QX, yI
DV, rP, yG
PY, Qy, eZ, wr, wx
GK, VL, lz
KB, Sb, dF, eU, lU
IL, ZC, xy
KT, az, tP
As, CX, Rw
EA, QZ, ZC, lI
QM, fz, ob
NU, RS, wW
DV, Nm, dn
Dx, Tx, aK
Xz, bq, hS
Nm, eU, kY, kk, le
CS, Fu, ep, iQ
Ib, ay, iF, wk
Zu, hT, mN
Ba, FH, iF, oj
Gh, dF, hT
BQ, kP, vS
AS, Xh, az, if
CS, DD, NC
Hf, hg, tc, xy
FI, Ra, vT
Ja, MY, PB
Oo, RN, kC
CT, FI, QZ
JN, Zm, kP, ry
Lk, iF, tM
Dx, Hs, zh
Ja, Zw, hg
CC, yL, zr
Hn, NE, id
Fl, RN, dq
EA, rb, zh
And while there are many more, this message is already quite long so I will stop here.
I don’t think it will be of great help since it is quite messy, but this is the generator. It is intended to be run like: python3 generator.py > test, where the debug messages get printed in the terminal and actual testcase in the test file.
I wonder if someone did indeed solve it with a general SAT solver. There is another python solution that, while based on similar ideas, it is nothing but backtracking with an heuristic that seems also hackable (yet remains to be proven!).
The purpose of that assert is to make sure I didn’t make a mistake in generation.
If you think there should be a revision to the puzzle please let me know. I was trying to make sure a trivial solution didn’t pass, but I don’t have the fastest solution and I’m not familiar with the terrain. I could scale back the difficulty if you think a general SAT solver should be able to pass it.
I thought so. The min(counts.values()) > 1 part is the tricky one. The point being that you could add blocking information in the shape of trivial evidence, forcing more depth in any backtracking solution. It is not a big deal, but respecting that constraint makes the hack test larger.
Many test suites of NP puzzles run into the same problem, including this puzzle of mine. It is possible to find hack tests within the stated constraints and it becomes a matter of does if affects someone’s solution (and is such person sufficiently annoyed to keep digging!).
I’m not sure if your puzzle deserves a revision. For once, there is no such thing as a general SAT solver, but also I don’t think many people would go that way. And finally, the SAT solver is half of the story, you still have to encode the evidences (the logical propositions “exactly one is true”) to CNF, which depends on the number of clues per evidence. I only implemented the pairwise one since it is the easiest (there are 9 implemented in pysat!), but I recall the last tests seeing a couple long evidences that would have maybe benefitted from other encodings.
For a long time I thought the issue was on my naive solver being too slow, but after seeing the sympy one timeout too, I just resigned myself to the idea that the test suite was just too hard for what I was willing to invest on it.
I just found interesting that you could, roughly speaking, (at least!) half the difficulty of the test suite, and still timeout your approach. And I’m almost certain that within the stated constraints, I could even timeout the DLX approach (which takes ms for the test above).
I usually define difficulty for a puzzle solvable with DLX based on the number of iterations required, among other factors. An iteration, in this context, refers to my DLX solver moving down or up a level (i.e. the forward or backward steps in the backtracking process). In this puzzle, the number of iterations for each case is small (no big numbers). I’m able to count all the solutions using my DLX solver without breaking early or timing out.
No. of solutions No. of iterations
Test 1 1 9
Validator 1 1 9
Test 2 1 9
Validator 2 1 9
Test 3 1 5
Validator 3 1 5
Test 4 1 8
Validator 4 1 8
Test 5 2 12
Validator 5 2 12
Test 6 1 2
Validator 6 1 4
Test 7 1 13
Validator 7 2 21
Test 8 1 16
Validator 8 1 16
Test 9 1 24
Validator 9 1 24
Test 10 1 47
Validator 10 1 48
Test 11 1 57
Validator 11 1 57
Test 12 1 60
Validator 12 1 60
Test 13 1 76
Validator 13 1 94
Test 14 1 196
Validator 14 1 208
Test 15 1 77
Validator 15 1 94
Test 16 2 177
Validator 16 2 195
Test 17 1 126
Validator 17 1 126
Test 18 1 806
Validator 18 1 767
Test 19 1 1336
Validator 19 1 937
Test 20 1 916
Validator 20 1 612
Better statement of the constraints would also be a welcome revision. I should probably add number of different clues.
I can’t comment on your implementation since I don’t think you published it.
I didn’t look too deep and stopped as soon as @Timinator’s implementation timeoutted. Let me know if you pass this test, which is way more complex that the one above but still within the stated constraints (and the input size limit):
L = 250
N = 7
number_of_different_clues = 4043
minmax_number_of_clues = (7, 26)
250 7
Ek, KM, Wd, cZ, ki, lL, xb
Ah, In, ME, SJ, Wk, YB, Yw, bI, bz, kd, pD, pJ, qf
CI, JH, Ku, Pr, Uq, WS, aK, fH, lr, mL, nb, pJ, pP, qf, rc, rt, se, tq, xA, zC
Ej, Ie, Ni, TM, UR, Us, Vm, YE, Yv, ZO, ZQ, dT, fX, mT, mq, ni, qD, sV, uq, yy
Bj, Hh, Tg, Xp, cJ, jv, mN, mq, xc
Ex, IT, Jj, KN, Ku, Uw, WS, XH, cx, gE, gK, kC, mG, qS, qX, rF, sc, vd, xL, yz
IR, Lq, MK, Pu, TM, Tp, Wy, ZA, aA, dL, eS, j, jl, jr, uC, wE, ww, xL
Cm, EP, Ej, IH, Ia, Ns, SV, VH, ZB, fo, jl, kt, oH, ow, qP, th, uu, vU, vW, wJ, zN
AK, GQ, Ih, JU, Ll, MZ, PN, Sr, Vk, Wq, Yb, ZE, dE, ey, kd, lA, qY, vc, wR, yJ
Dj, Dr, ER, P, Px, Sf, TM, U, Uu, Xa, dT, hN, jl, mN, qQ, uG
Ah, Bz, CN, DP, EC, IH, Ia, Jv, RS, VH, WS, Wt, XX, eF, fH, im, ni, pM, qS, xc, yg, zW
Bv, Ek, IH, IO, ME, P, PG, Pa, XN, Zd, ce, eF, kC, lr, np, qj, ue, wr
Ad, CI, EE, GB, Ot, Pa, Qj, Tz, XN, dE, j, lM, nV, pA, qv, ra, tX, vE, vM, yP
AE, Cx, JM, No, OX, ZE, cC, cJ, gE, iN, jw, lg, nT, rk, tq, vz, wz
Cm, Fn, Gh, Jl, QP, Uq, WJ, WW, X, Xp, cC, im, ix, qv, tq, wa, xM
Cj, DX, KN, Lq, P, ce, d, dy, hv, la, pM, qQ, uD, uq
EY, GO, Go, Lx, QT, eC, ix, jO, pG, pW, vW, yP, zE
Cf, GI, Qj, Zj, aY, dZ, iK, xv, yG, yo
Bz, GB, KN, MH, Mo, Nh, OA, aY, by, jv, uH, xv
DD, Ei, In, Jj, Ll, MH, QP, UN, Ut, Wk, Yd, hN, kd, ki, ko, kr, pV, pc, tI
BX, DX, Ek, F, FR, GA, Jv, Vf, Wc, gy, oL, qg, wW, yg
Ou, Pa, SV, Vm, Wy, Yd, aZ, dp, hJ, mN, oH, qQ, qf, wR
Bb, Bw, CN, DT, Ex, JX, ME, Wq, jL, lr, oL, oy, pC, rF, uD, vb
Cf, ID, JD, La, Nh, No, TM, Us, ZQ, ki, nT, ou, qY, yg
GI, Ie, TQ, aL, by, dp, mX, pc, qg, ue, ww, xA, xU
SV, VD, Wd, av, fs, gW, gY, gz, hV, ik, mT, pL, qY, xM, xr
AD, Bo, EC, KL, Ml, OL, RI, TQ, Vp, Yw, Zd, eX, iE, iK, la, mN, sN, sn, uu, xw, yJ, yo
Ih, NS, No, RN, RO, Va, Yw, ZJ, aL, aZ, bw, dZ, gq, im, kR
GB, Kp, No, Oa, TM, UO, cC, d, dT, iZ, np, oH, of, oz, rX, zU
Cf, IS, KL, KM, Kx, Ne, Os, Vu, dT, di, kN, ko, lA, pM, xS, xc, yw
Bo, Et, KM, OX, Vp, Xg, fX, iK, lA, mq, sV, xA, xn, zC
Ca, H, Jj, OK, P, RZ, SV, UO, Vm, Wt, Xp, Zz, bz, fp, mL, mq, qf, uo, vU, wz, yc, yg, yw
DY, La, UN, Xg, ZO, hx, kt, py, sB, tq, xn, xr, yP
DK, Ex, JX, Kh, Vk, ZD, aY, hu, hx, qc, qj, xL, xh, xm, yx
FR, Hc, Hx, Jv, Km, NK, fp, lh, np, ob, xw
HU, JD, Kx, NS, Ne, QT, RI, RZ, Sy, Tj, Vp, eH, kA, nL, ou, pC, pJ, vE
ID, Ia, MK, NB, NF, Tj, Tp, eb, fX, kr, lh, np, qD, qX, vX, xj, xr, zK
AK, EL, EP, EV, Mt, OA, OC, SX, Yd, ZD, cp, lA, lM, sr, tC, yy
AD, Ah, DA, Om, Wt, XH, bn, di, eS, eX, kR, mL, mu, wp
EE, Gh, IR, JV, Ne, No, aA, cp, pB, sk, tC
In, PG, di, fo, ft, ga, ik, js, mB, mG, pM, wr
My, OA, Tj, Tz, Wh, Xs, Yc, kA, nT, tC, vc, wF, wp, ww
Bv, Ca, Hc, Jv, MZ, Vk, WS, X, YB, ai, az, cT, gK, jl, lq, mL, ob, pC, qv, sB, tX, uo, wB, wr
AK, Ad, BF, Cj, ER, Et, GV, Ih, Ml, NB, PN, RJ, Yd, bN, dL, dn, sw, vm, zN
Ah, Fk, GV, P, RI, Tx, Uy, WO, gy, jw, jy, lg, yz, zp
Jh, Pr, VH, ZF, Zd, fK, lf, mG, mL, vb, wB, xA, yc
CN, DA, KM, Ml, Qj, RO, TU, WT, af, cc, cs, fX, ki, nr, qP, sM, tC, yg
Fu, IS, JU, JX, KR, KY, QL, RS, WT, Yx, Zr, dZ, fX, gE, kR, kh, pB, pL, tb, uZ, vb, xi
Cx, Ek, Je, Ow, QC, RZ, Yd, aN, di, jg, jl, pA, rA, sr, uG, wR, xS, yc
DK, Pu, QC, QL, QO, Sf, Tz, WW, bI, cC, fo, hJ, lX, ow, vc, xq, zp
H, Ob, UN, bn, bz, jx, lm, me, rX, sn
In, U, XN, ZJ, aK, fU, jg, nT, nn, qX, rU, xM
Ih, JD, KG, aL, cC, rF, vM, vm, yc
Lx, OP, ab, cp, dG, gq, lq, mD, vU, wJ, ww, zp
If, KY, KZ, LD, Pr, Tj, aA, ab, bK, dA, fK, gz, jl, kt, pW, th, wF, xU, xf
EY, HU, Ph, QT, Sp, WJ, Wd, YH, Zd, fp, hN, hV, lM, ob, se, tb, uq
Cj, ER, Jv, Va, Vp, Wy, Xa, cp, d, fX, kA, mp, vb
Bf, EP, Jj, Ll, NS, No, Ns, Qd, aK, af, fU, j, lX, nd, nr, oI, ow, pM, rX, sN, yS
Bw, Dr, FH, Ie, LD, PN, Tg, YE, cP, eF, eH, gW, kA, kN, kh, pV, tX
Ih, JC, JH, MZ, Mo, Og, QP, UU, Wc, Wy, fU, fX, ik, qY, tV, ws
Bz, EY, Eg, Ek, Lm, NB, OP, Om, Rl, Xg, by, lA, uE, vM, vb, vc, yJ, yg
Bf, Bo, DT, DY, GF, ID, JC, Jh, Pu, SL, VB, Xu, YB, az, bz, jv, lf, ou, xn
Ej, F, Ll, Ml, PG, Ph, WS, Xp, Yd, ix, jx, lX, oh, qv, sN, ue, wW
GB, Kh, NK, Ob, SJ, UR, av, dp, mH, nL, tV, yP, zK
AK, Bs, GQ, Hh, Oa, RN, Uu, d, kh, lr, qv, vm, xS, zS
Ca, Mp, OK, UO, Wt, ce, dL, dV, jL, jw, kh, mG, nM, pk, py, xn
FD, GM, GO, JV, NK, Ne, Pa, Qd, TQ, Wf, bz, dE, fp, gE, mG, pC, qD, xj, zS, zj
AD, AK, Bf, Ie, Uw, VB, Yv, ow, rc, xL
Bv, Lf, Sr, Vp, hu, jw, kC, ko, uu, xc, xj
AZ, GO, Ia, TU, ZZ, cc, gW, vX
BF, Cj, Cx, ER, GQ, JG, KR, Wx, eX, ix, jO, lX, nM, qg, uo, uu, xn
Jl, SL, Zr, af, bB, cp, eH, jO, la, ni, se
CO, Cm, GV, Hc, JD, TM, Va, Yd, Zd, cJ, dE, fK, fN, gz, jV, kh, mB, mX, py, sr, tC, vE, vb, wz, zE, zk
Bz, JC, Tg, WJ, Yv, ga, gz, kZ, qh, vE, vT, xb
Aj, Cm, Dd, FR, Fn, Nj, P, PN, QC, XN, dn, eF, gK, mD, tb
ER, Ei, JC, JH, Jz, Mt, Pa, Sb, Wy, eS, jl, kR, pc, rt, wr
DX, Fs, GM, HU, If, Qj, Sr, Us, bI, eb, uG
DR, Fn, Fu, LD, RZ, WW, YN, cc, hu, iN, sJ, sN, sn, tX, tr, uL, vd, yg
Ej, JH, Jj, Jk, RN, Va, WS, Wc, eb, gz, hJ, wd, wp, xv
EL, JX, Kp, LD, OK, Os, Rl, SL, VN, WW, Wf, hJ, jE, kS, nj, oy, rX, rt, xn
DK, Ek, Om, XX, YH, aL, bI, ek, uE, yS
KM, MK, Os, Uq, WZ, bK, bz, cC, eH, gz, rK, sV, tr, wz, xv, zC, zN
AZ, DA, KY, Ku, Ng, Oa, QC, WW, Wc, bN, by, eH, jg, mH, nL, qP
Bf, EE, EY, HF, IS, JG, NS, Os, SJ, Va, aK, fU, iN, jr, sJ, zU, zk, zp
CI, Hx, JU, Ns, Pa, Tp, UO, XH, ZO, fN, iZ, lI, rF, rO, se, uu, wp, xZ
DA, DD, Dr, GO, HE, Ie, LC, RI, RJ, TI, YH, bB, dA, dZ, fU, im, pD, sc, wd, xc, xw
Bz, CI, Et, Px, UN, Vf, aA, iE, kR, pA, pB, uo, xU
CN, Cx, GZ, Jz, KR, LP, Se, Yd, ZQ, cZ, eS, lX, nr, oz, pM, sB, tV, vd, wB, xr
Eg, GP, Hx, MR, Ou, Pu, QJ, SV, Wc, YN, eH, fp, im, nV, pC, pL, vM, xh
Dr, EV, GF, HE, IR, LC, Lx, Vm, Wd, cD, fK, ix, ko, uC, xv
JW, Nj, OC, Og, Ot, PG, Qd, UN, Uq, Vk, XH, XN, ZJ, cJ, dT, eH, rA, sr, tb, tq, vW, vX, wa, yo
IH, Ia, Ip, Jj, Lx, NB, OK, Oi, WT, Zd, bw, er, lf, nj, np, oz, uG, yo
BS, Bs, GA, IT, KR, Np, SJ, Sf, Uu, VN, XN, cc, fs, ix, mN, oI, tV, wp, xy, zq
Cj, If, PN, Sr, TI, Wq, Xu, ZE, jV, ki, mq, qv, ra, tI, wJ, xZ, yJ
BF, EV, Ot, TQ, fU, mH, nT, np, oq, wF, yC, yx
FD, Ia, RO, TQ, UO, Xp, hJ, iZ, im, mB, np, of, qF, rC, rt, zC
DR, GO, Hh, NB, Rl, SR, Sp, Uy, aL, cD, jO, uD, uu, wJ, wa, xw
AO, Ei, JC, KY, KZ, Uy, ey, fo, iN, lM, mB, sN, sc, se, xb
EY, Fn, NF, OP, SL, Uv, Zj, cD, cs, eH, eX, lX, lr, mL, nT, qY
Aj, BF, Ej, Go, JV, KL, Ob, Sy, Us, Xs, Xu, Yv, fo, iK, ik, lf, mG, mq, oq, sk, tc, uo, wd, xm
Bw, DK, GZ, Gh, IR, KZ, ME, QC, U, Wq, Xp, cc, dE, dZ, dn, eF, kC, kZ, ue, zU
Bk, Ip, JG, Jj, MK, Np, Ou, Xg, ZO, Zr, ix, jw, kN, kS, kt, uu, wp
GB, JG, Je, Oa, QT, TI, TU, Tz, UN, Uw, dn, hV, jU, lf, pC, rK, v
AT, Bo, CO, DA, Dr, FD, In, SR, WW, dT, hx, iZ, kN, mN, pB, qh, wR, xw
IS, JM, KG, My, RJ, WJ, WS, ZA, ab, ce, fU, mL, rc, xZ
Bw, EP, Hc, ID, KL, X, YN, Zw, dE, hx, j, qh, uq, xc, xr
Ah, Cm, KZ, Ni, OK, Vm, Wh, Xu, bo, cs, kd, kr, la, pA, sN, sc
Ie, LP, Mp, UU, Xa, ZJ, iE, jg, jw, me, qQ, rt, vE, yy
Ah, BF, DX, EC, Ei, Lq, No, RJ, RZ, VO, WB, WO, dj, fo, gz, jE, qS, rF, rX, uH
AE, BX, Bz, Gh, IH, Ll, Mt, SV, Vp, Yx, dV, oq, pL, qg, rc, vd, xh, zC
BX, Bs, F, Fu, GM, Mo, QJ, Qj, Sf, WO, cp, iZ, jU, jl, jy, kS, lg, rF, xm, yJ, zS, zk
GO, Ia, Jh, Nu, Uu, Yb, ZQ, fN, gK, ik, kd, tr
GI, Ns, RN, Vp, az, dE, jy, kN, kr, lf, ly, qD, tb, wB, zE
Cx, Dr, Jv, Lx, Ob, SL, Tg, Wf, XX, Yb, Zd, bn, cs, jL, pD, uD, ut
CO, Fn, IO, Lf, Mo, WJ, ZD, gE, hu, js, mD, ob, of, tX, uG
Go, Je, Mp, NQ, RZ, X, bN, dp, jx, jy, kt, oH, qh, uE, xA, xm, xv
Eq, JH, Kx, RZ, TU, Tg, aK, fN, hN, mD, pc, qg, tb, xv, zN, zU
Bw, Dd, NS, Ne, Nh, No, RN, Sp, XH, bI, dj, id, kN, qc, qv, tb, ww, yP
Dj, Kp, SL, Sf, Vf, cD, dL, hu, kd, lh, nL, ob, pV
BS, JG, KN, KY, MZ, OX, UO, Vm, XH, XN, ce, fU, jO, nb, nr, ut, wJ, wp, xA
IS, IT, LP, U, Uq, Uu, ZF, nn, oh, pB, qf, sN, vc, wF
EL, FH, JU, Om, SV, Xs, gy, jL, jU, nr, pP, qX, vT, xq
Bo, Cf, GQ, GZ, OK, QJ, QP, Vf, bU, cZ, dZ, sV, se, uZ, yc
Bs, Cj, Hx, Jz, ME, MK, Mo, NS, Om, Pq, RI, RS, Uw, ZE, ZQ, jx, rC, rk, xA
GA, JD, JW, KZ, QJ, Wy, Ya, dy, hV, jE, kZ, mG, nn, qD, yC
Ad, JV, Jp, LD, Pa, az, kC, tc, uH, uu, vc, xA, yx
Oa, RO, Wt, Zj, hN, kZ, ob, ou, pD, q, qP, wF, wa, xc
RS, WT, ZF, av, eX, ga, lr, mL, qS, qY
AD, Ah, CO, DT, Nh, aA, bI, bw, cP, jv, jy, kr
DR, Kt, LC, NQ, QL, QP, Sp, Wk, j, qj, rt, xr
AE, AZ, Bf, HF, JD, RJ, Yv, Yx, dL, dj, fs, iZ, jv, rk, sw, vm
AZ, DA, EL, GA, Jh, OP, TU, Tg, ZQ, cJ, dL, gE, mG, tV, uZ, yw
Bw, EP, Fs, GF, Ia, KR, KZ, Us, VO, cs, eb, er, gW, jv, mB, me, oH, pC, pP, rc, xu, yG
Jp, Kh, Ml, Ne, YE, ga, iK, oz, yz
Bo, GQ, Kh, Ll, MK, OC, Px, Wq, ZO, aA, cp, lA, nb, qh, rn
JW, Ni, Np, QO, TQ, UU, VN, dE, ek, fH, gW, nZ, qD, qc, vb
Aj, FD, GB, GM, PN, RO, SR, SV, Uw, ai, dV, hx, lO, mG, qY, rc, vX
EV, Ej, GM, JV, Og, TU, Wk, cJ, er, gy, kC, lq, oL, pD, vz, wr, xZ
EE, F, Fu, GI, RJ, UN, Uw, Xg, ab, bn, cZ, fN, jV, mH, nV, v
AK, Go, LC, MZ, My, PG, Tp, jU, pV, sB, wE, zU
Bj, Fk, Ih, Kt, Lq, MZ, Mt, NK, RS, Wh, XN, cp, dE, dn, fH, wa, xZ, xh
Eg, JC, Lq, Lx, Nj, Om, Uw, dX, ow, uu, vd, wR, zN
EP, GP, LD, Nj, OX, Sy, U, WT, aK, eF, eX, fp, id, lr, mB, nV, uD, xb, zW
Dj, KZ, Mt, Ns, PN, Uy, av, ga, jx, kS, pD, qQ, tb, wE, xZ, yP, yS, yo, yy
Bj, Ex, In, Np, Tx, gY, nr, py, se, ue
BS, DD, DX, Nh, Pr, Pu, Qd, Vf, Wd, Yv, jr, mT, nj, pc, ra, uB, xf, yS, zX
Fs, Hc, LD, Ow, Xg, bw, d, ek, fs, iE, j, kC, lh, pB, tV, xM, zE, zN
AK, Fh, JH, KM, LC, NS, RO, Tg, aA, jv, pC, th, uC, vj
AK, Ou, Tj, Uv, YH, Zw, bU, jO, mG, nj, xq, yc
FD, NV, Pr, RI, VD, WT, bU, ik, pA, pB, tC, vb, xU, yx
Ex, GB, JC, Km, PG, PN, Yb, fN, lh, oq, pC, qD, qg, rC, sr, wr, xf
DR, EC, F, Fh, Kt, My, No, az, eS, jw, kS, kZ, tC, wE, zS
Gh, ID, Ih, QL, WB, Yx, Zj, ce, kd, nM, py, ra, rk, th, uo, vM, xh
CO, EL, Ex, IT, LD, Mo, RO, Sf, Xu, YH, YN, ab, bB, d, jk, ou, rF, sJ, wW
FD, Ih, KR, Oi, Qd, Tz, YH, dL, dp, oI, rA, rC, xm, xu, yz, zp
IS, JG, Jj, Kx, RZ, Yw, av, bK, cZ, kS, la, nj, qD, qS, qY, qv, sB, tV, wd, wz, xr, yS, yl, zC
F, Ml, Px, QL, Qd, SJ, Tx, UN, VA, VO, bI, fX, iZ, jg, qP, sV, sn, ue, vW, wW
Jh, ME, Os, Ou, Uw, WT, Xg, Xp, av, cP, eb, mT, vU, wa, xq, xr
Cx, DY, GO, Je, No, Wc, Wh, bz, eb, fF, ni, tc, xM
AZ, EC, HE, Kx, Lq, My, OC, Wt, YH, kA, lX, mN, qf, wr
BS, Bo, GI, GZ, Lq, P, Qd, Xs, aN, lg, mq, tj, uH, xm, zk
Cx, DT, GZ, MR, Pr, QC, RN, WO, X, Xg, dV, iE, jE, mp, oh, pA, pG, tV, tX, vc
Bz, Cm, EY, GF, ID, Mt, RN, TQ, Uv, YB, Yx, ZD, bK, ft, oy, ra, vW, vc, wa, yC
FH, Ip, MZ, Md, Pr, QL, RJ, Ut, YH, dV, lq, pD, qj, rO, yS, zC
Ex, NB, QC, SV, Tx, U, Wh, jE, oL, ou, qf, vU, wJ, wM, xu, zS
HU, My, Ou, SJ, VH, Zd, dj, hJ, id, jL, rC, sM, vU, yg, zE
GV, JD, KY, Tp, VH, Wt, jw, ko, mu, xZ, yx
AD, DD, EC, Hc, JM, OI, Oa, SJ, TM, Tx, X, XH, Yx, cs, kZ, lM, lf, nM, pA, pP, ue, xM, xn, yw
Cx, FH, Hc, Mt, NK, Qa, RS, fU, kN, mD
H, KL, KR, KY, MK, QC, TM, Wk, YB, Yw, fq, lO, mT, oL
Bj, Bs, Cf, DX, H, JW, Kb, Zj, aK, af, nn, oH, qP, tC, xu, yo
DA, EV, GM, Je, MK, Tz, Uv, Vk, bz, cJ, fK, kN, nV, pL, qJ, sw, tI, wB, wp, yP
AZ, CN, DP, EV, Ex, Gh, JG, Lf, Mo, Pu, Yv, ZO, cT, ek, gE, gq, np, nr, qD, qg, rA, zX
CN, FD, GQ, Go, If, JH, JU, LP, Mp, Nu, Tj, UN, Uu, ZE, eS, js, me, uE, uG, xU, xw, zq
Bk, EE, Ip, VH, WT, ZO, dV, hN, lr, qc, wr, xn
CI, EY, FD, Fh, Jl, Nh, P, QP, TI, VD, bI, ce, dT, lg, nj
Ah, FH, GV, QJ, VH, gK, vM, vX, vj, yy, zN
FH, Ip, Vm, Xu, aL, bN, oG, oy, tr
Fk, HU, Ih, Jh, Lx, Ob, QL, UU, YN, iN, jx, kZ, lA, mN, oq, xf, yC, zK
Jz, KL, LP, Rl, Sp, VA, VD, XH, cJ, eC, kC, ko, oq, qc, qv, sB, uG
Bf, Cm, Kp, Kx, Np, QO, Yv, bn, hu, jL, jV, kS, rX, sN, sV, vX, xS
Cx, Eg, Gh, IS, KM, LC, MZ, RN, WJ, Wq, Wt, bn, cx, dZ, dn, ey, jy, ko, lq, pc, qc
AE, AZ, DD, Ip, Nj, RN, VD, VH, XX, Xg, Ya, ZJ, fH, sc, uE, wF, wd, wr
Dj, Ia, MK, Mn, Sp, Va, bU, gy, hJ, j, se, tb, yy
Cf, EC, GB, HF, IS, Jh, Ku, Qj, RS, SJ, TQ, VD, Vp, Wq, bK, dV, j, nV, oH, xM, yJ, yx
Bv, Fh, GV, IR, PN, U, ZA, cc, ce, dj, ek, eq, hx, jr, lO, nL, rt, ue, uu, xu, xv
Bv, Ej, GA, JW, OL, RS, RZ, UU, eF, fH, gK, jr, ko, mp, ra
Ob, PN, Wf, Xp, YA, fs, lX, lf, ob, oq, qQ, tb, uB, vb
Ah, ER, Fh, GF, KL, NQ, Pa, Px, VO, az, bB, by, dZ, dn, fp, gK, mH, nL, pc, qP, ra, xf, xj
DR, GP, Jv, KM, LP, TM, Tg, Xp, Yv, ZD, ZJ, af, az, ey, fH, gz, hN, ko, nd, pc, xw, zK
Bm, FR, GQ, HU, QO, Sp, Vm, YE, hN, kA, lg, rK, wF, xL
Fn, Ip, JX, Kx, Wd, YE, nV, ou, ow, q, qX, rA, ra, th, xw, zp
Cm, DA, DP, JW, VN, Vm, XN, Yb, cT, d, fN, kS, rD, tc, yJ, zk
CI, DP, Eg, GF, WO, Wx, Xs, bN, eF, lr, rt, yP
CI, DY, Ia, RS, Sy, Tp, Tx, VO, aY, eS, kr, pL, rk, uG, ut, wR, yg, yz
AZ, Fs, Nn, SR, Tp, Xg, aN, gE, wF
Bf, LP, UN, dG, dn, uG, zq
DR, Ej, Jj, LD, Pq, dL, di, dj, eF, eH, qP, wz
Dj, EL, FD, GP, H, Kp, Og, Os, QO, TQ, WO, Yb, Yx, iE, jg, lX, oH, xS, xj, yy
HF, Oa, Os, UO, Uq, aA, bN, fp, lO, oI, rA, tI, yJ
Ad, JX, Jh, Pa, QJ, Sb, az, jV, ki, oq, pD, rC, rF, sN, xU
AK, CO, HU, Ni, Nn, Px, Xp, cT, dL, ek, jO, lh, np, rF, rO, se, uH, xq, yJ, zK
In, KL, Ml, Pq, Wf, aN, ek, kS, me, vd, xA, xb, yC, zk
Bj, DP, JM, Mn, ZD, js, lO, lg, nM, oz, qh, ra, uB, uD, xj, xw
Cm, FH, GM, JW, KN, ME, Nj, QC, WO, dp, gq, hV, id, jw, pG, sM, tC, vU, wz, xq, yx
DP, EC, Ej, Jh, Wk, hu, iE, nd, pL, qX, sc, wa, xS
BS, Cf, GA, GF, GQ, JG, JX, Px, Tx, YB, Yw, Zj, Zr, bB, ik, oy, qg, qj, sn, sr, uE, uo, xH, xc
Ei, IH, JC, Ob, Ph, Px, Wf, ZD, d, gE, pG, tI, vM, yc, zp
F, JM, MR, UU, WO, Wy, ab, dA, fU, jx, mN, pD, zK
AT, Bf, Ca, Cj, IR, Kt, Ob, Pu, YB, Yb, aL, dZ, eb, gz, lO, of, oy, oz, rX, sr, sw, vX
AE, Cf, DY, IR, Ip, JX, KM, Kx, NS, Ou, RN, Sp, U, Uy, dA, ft, gE, id, mp, ob, xi, yz
Aj, Cf, DT, JH, LY, RI, WW, Yx, bK, bn, bz, di, fH, jy, kr, oq, rX, sJ, sn, th, vb, wd, yx
AE, DR, Ei, LP, Ng, RZ, Zj, aN, dV, mq, nM, nj, xZ, xn
Ml, Mp, RI, Sy, Tx, VN, dZ, eS, gz, hV, jv, oh, rc, sB, th, uZ, xh
Fn, GV, LC, Ni, Np, Uy, WT, gY, jr, mD, qQ, uo, vX, xj, xq
ER, IS, Ip, Jz, Mx, Qd, Sf, X, bB, bK, fN, hN, qX, rC, uB, zk
CI, DA, IK, QC, Sf, Tg, XX, hV, kt, nM, nr, sB, vE, wB, yx
Ca, GP, JH, Uq, Xu, gq, ik, jL, jv, lm, pA, uH, vW
AK, Cf, FH, Fu, Jk, Jv, Kh, PG, YB, ZQ, cD, cT, fo, oz, pG, qP, rc, yJ, zq
Jv, Kh, Md, QO, RO, Wd, Wh, ZA, eb, gy, hx, js, rC, wF, yy
Hx, LC, LP, Ni, VN, ZO, ZQ, bN, fp, id, jl, lf, mB, ni, rD, sw, ue, zC
Cm, HF, Ob, RJ, Ut, Uw, Vm, bw, by, bz, gy, of, pL, qD, qQ, qv, wR, wW, xZ
AZ, Fn, GA, IT, OC, SR, TI, Vf, Wk, Xu, eC, fK, hV, nb, ow, uq, xH
Eg, Fu, Ml, SL, WW, Wh, Yx, bN, bw, cP, hJ, js, kC, mH, nM, rC, rO, th, vE, zK
JM, KY, Lq, QO, SR, Sy, WO, XN, bU, mL, rD, wr, xj, zC
Ex, FH, IR, OX, Ut, Uy, Wf, dT, eq, of, ow, pV, rO, yC, yx
Fs, Os, QP, Vf, Wf, cT, dL, dy, eC, im, sN, th, uH, v, vm
AD, Hc, JD, MH, Om, Rl, Tj, Zr, aY, dA, ey, j, oy, rA, sn, sw, uB, xM, yc
Aj, Mx, OA, Wq, Yb, er, im, jO, kS, mN, nb, qQ, vc, xM, xS, xf, yg
Dj, GB, GM, QT, Tp, XH, bB, cJ, do, eC, jV, kh, ob, oh, rA, tX, xi
DA, Hx, IR, If, JC, Ku, NK, Qa, bn, fK, iK, kZ, oL, pD, uB, uC
NB, QP, Qd, X, XU, di, lA, yS
EY, JG, KR, Oa, SV, Tp, Wx, ce, jg, kR, mH, nV, pP, qY, rK, sr
Ip, JD, OC, QL, VA, Vf, YE, az, dp, jO, jx, oL, ow, tq
Ad, CN, Kx, OX, Tz, VD, WW, cC, cP, dj, hu, iK, jU, lO, ni, wp
EP, ER, GA, Kt, Mp, OK, Tg, Uv, VH, WW, ZA, ZD, dE, fN, he, ix, lA, qQ, qX, rX, tC, uD, zK
Bs, Dr, KY, NS, RJ, bw, dT, jV, lr, mH, mT, mX, mp, pB, sV, uE, wd, xq, yy
Ca, Cj, Dd, JH, Jv, U, Vp, ZJ, bB, er, ga, jr, lg, nL, oh
DY, Fn, IT, KN, KR, Ni, RS, Wt, Xa, aL, dy, jl, mT, rk, rt, sw, xL
Aj, BX, ER, EY, IH, IT, Jz, Uv, fH, fo, ow, tc
Fn, LC, Mx, WJ, X, eF, fs, gW, kd, mL, nn, qY, sJ, tr, ww, xM, xS
EL, Ej, GI, LP, PG, SR, Sp, YE, Yv, Zr, aA, aL, by, js, ki, np, qX, vU, wL, yy, zN
DX, FR, Nu, Og, UU, Zd, Zj, aL, di, dn, kA, ki, qS, rK, th, vE, xb, yP, yo
CI, Fh, JV, NB, Nj, OP, Ou, Ph, Uq, XH, Zd, iE, kt, nT, ra, sw, vc, yS, zS, zq
Bf, Lf, QW, Sy, dy, gK, nj, oI, sr, ue, wB, yS
GZ, Jh, Kx, Lf, Ni, Va, YN, kR, uD, uZ, wp, xi, xj, zC
F, Jz, Om, SL, aN, eb, jy, mD, nV, ob, sw, xL, xS, xn, xu, yN, zK, zq
CQ, FD, IH, Je, QJ, Sp, YB, eH, fN, jv, mq, ou, oy, yw
Ad, GM, ID, KY, Ut, YH, Yb, Zr, by, fX, jx, oz, pk, qX, qc, uC, uo, xi, zE
AD, AE, GI, JG, JV, Je, OA, Om, SL, Sf, Va, WS, WT, dX, di, mD, pG, pL, vM, vm, yo
The solution is lL
Locally:
> python3 gen_dunnit.py > log
tsize = 4043
7 26
====================
pJ UR Hh cx wE ZB Sr Xa zW IO Ot vz Jl hv pW yG MH BX aZ Bb La mX gY OL Kp Vu Et Zz DK Km NF SX mu sk ft Yc ai Fk ZF sM uZ Ow lm rU KG dG Ph nd cP ws Lm VB pk zj ZZ Wx vT Dd Sb uL Jk WZ Ng HF lI HE Se MR lL Oi xy qF AO Bk v AT Zw bo WB Nu ly ut NQ Eq Pq Ya Jp q rn nZ dX zX vj NV jk yl VA fF tj Md wM OI Qa fq Kb qJ oG Mn eq YA Bm rD Nn xH LY Mx IK do XU he wL QW yN CQ
len(solution_dunnit) = 124
====================
culprit: lL
# This is @Timinator's code, ran for validation
> cat log | python3 s.py
lL
11476.61 ms
Note that I forgot to change his code to not stop early. I ran it again to verify that the solution was unique since the generator does not guarantee that and, it is indeed unique, but the timing skyrockets:
> cat log | python3 s.py
lL
30389.72 ms
And those are local timings. They should be even higher in the codingame workspace.
Trivia: pysat wins this one (and I’m sure most of the time is spent by my part of the code that does the encoding as opposed to the solving part that uses their SAT solver):
> time cat log | python3 solver/etc/xor2.py
lL
________________________________________________________
Executed in 13.90 secs fish external
usr time 13.87 secs 332.00 micros 13.87 secs
sys time 0.03 secs 261.00 micros 0.03 secs
My code couldn’t find a solution even after 11 minutes! 
The DLX setup took just 1.4 second, so the vast majority of the time was spent “dancing”.
This brings me back to my original point: Dancing Links is essentially a way of backtracking. Say there are always multiple choices at each level. If somehow every first valid choice at each level happened to lead to a correct exact cover solution, performance would be amazing even with many items and branches as input parameters. But, of course, that’s unlikely when choices are randomised. So, I’m not surprised by your finding that “impossible” cases can be created given the current puzzle constraints.