NP-douce 1.2

HC solve node limit HC backtrack tries TSP beta multiplier c Search all answers

Shared settings apply across tabs. TSP uses adaptive beta with the multiplier c; for gr17 matrix/manual, try c = 1.5 with HC backtrack tries = 4.

3-SAT to Hamiltonian Cycle

Uses the classic 3-SAT to Vertex Cover triangle reduction, then the direct Hamiltonian-cycle gadget with the degree-2 forced-edge precheck. The optional third number on the first line adds forced padding nodes.

3-SAT data

Benchmark: SATLIB uf20-91, instance uf20-01.cnf, DIMACS CNF converted to app 3-literal rows, expected SAT. Set HC backtrack tries to 2 before running this example.

# SATLIB uf20-91, instance uf20-01.cnf
# Source: https://www.cs.ubc.ca/~hoos/SATLIB/benchm.html
# Copy used for exact clauses: https://github.com/mitchellh/go-sat/blob/master/testdata/satlib/sat-uniform-20-91/uf20-01.cnf
# Original format: DIMACS CNF, p cnf 20 91; conversion removes trailing 0 from each clause.
# Expected original answer: SAT
20 91
4 -18 19
3 18 -5
-5 -8 -15
-20 7 -16
10 -13 -7
-12 -9 17
17 19 5
-16 9 15
11 -5 -14
18 -10 13
-3 11 12
-6 -17 -8
-18 14 1
-19 -15 10
12 18 -19
-8 4 7
-8 -9 4
7 17 -15
12 -7 -14
-10 -11 8
2 -15 -11
9 6 1
-11 20 -17
9 -15 13
12 -7 -17
-18 -2 20
20 12 4
19 11 14
-16 18 -4
-1 -17 -19
-13 15 10
-12 -14 -13
12 -14 -7
-7 16 10
6 10 7
20 14 -16
-19 17 11
-7 1 -20
-5 12 15
-4 -9 -13
12 -11 -7
-5 19 -8
1 16 17
20 -14 -15
13 -4 10
14 7 10
-5 9 20
10 1 -19
-16 -15 -1
16 3 -11
-15 -10 4
4 -15 -3
-10 -16 11
-8 12 -5
14 -6 12
1 6 11
-13 -5 -1
-7 -2 12
1 -20 19
-2 -13 -8
15 18 4
-11 14 9
-6 -15 -2
5 -12 -15
-6 17 5
-13 5 -19
20 -1 14
9 -17 15
-5 19 -18
-12 8 -10
-18 14 -4
15 -9 13
9 -5 -1
10 -19 -14
20 9 4
-9 -2 19
-5 13 -17
2 -10 -18
-18 3 11
7 -9 17
-15 -6 -3
-2 3 -13
12 3 -2
-2 -3 17
20 -15 -16
-5 -17 -19
-20 -18 11
-9 1 -5
-19 9 17
12 -2 17
4 -16 -5

Load text file

Vertex Cover to Hamiltonian Cycle

First line is vertices k optional_padding, then one undirected edge per line. Example: 12 4 followed by edge pairs.

Vertex cover data

Benchmark: DIMACS COLOR myciel3.col graph, converted to Vertex Cover with k=6, expected YES; k=5 is NO.

Load text file

Clique to Hamiltonian Cycle

First line is vertices k optional_padding, then one undirected edge per line. Example: 50 10 followed by the clique edge pairs.

Clique data

Benchmark: complement of DIMACS COLOR myciel3.col graph, clique threshold k=5, expected YES; k=6 is NO.

Load text file

Independent Set to Hamiltonian Cycle

First line is vertices k optional_padding, then one undirected edge per line. Example: 16 6 followed by edge pairs.

Independent set data

Benchmark: DIMACS COLOR myciel3.col graph, independent-set threshold k=5, expected YES; k=6 is NO.

Load text file

Set Cover to Hamiltonian Cycle

First line is universe_size set_count k optional_padding, then one set per line using element numbers. Example: 12 6 4 followed by six sets.

Set cover data

Benchmark: Beasley-style set-covering example, converted from row/column incidence to app set rows, optimum 3, expected YES for k=3.

Load text file

X3C to Hamiltonian Cycle

First line is universe_size set_count optional_padding, then one 3-element set per line. Example: 12 6 followed by six 3-sets.

X3C data

Benchmark: canonical X3C/3-dimensional-matching teaching instance; no tiny library-format X3C file is bundled, expected YES.

Load text file

Graph Coloring to Hamiltonian Cycle

First line is vertices edges colors optional_padding, then one undirected edge per line. Example: 12 12 3 followed by a 12-cycle.

Graph coloring data

Benchmark-format DIMACS COLOR complete bipartite graph K3,3, 3 colors, expected YES; it survives the exact precheck and runs through HC witness search.

Load text file

Hamiltonian Pairs

One undirected edge per line, like u v. Listed edges get weight -1; all others are 0.

Pairs data

Benchmark: DIMACS COLOR myciel3.col interpreted as an HC graph; locally verified Hamiltonian cycle exists.

Load text file

TSP Weight Matrix

First line is n, followed by an n x n symmetric weight matrix.

Matrix data

Benchmark: TSPLIB gr17, full symmetric matrix converted from lower-diagonal format, optimum tour length 2085.

17
0 633 257 91 412 150 80 134 259 505 353 324 70 211 268 246 121
633 0 390 661 227 488 572 530 555 289 282 638 567 466 420 745 518
257 390 0 228 169 112 196 154 372 262 110 437 191 74 53 472 142
91 661 228 0 383 120 77 105 175 476 324 240 27 182 239 237 84
412 227 169 383 0 267 351 309 338 196 61 421 346 243 199 528 297
150 488 112 120 267 0 63 34 264 360 208 329 83 105 123 364 35
80 572 196 77 351 63 0 29 232 444 292 297 47 150 207 332 29
134 530 154 105 309 34 29 0 249 402 250 314 68 108 165 349 36
259 555 372 175 338 264 232 249 0 495 352 95 189 326 383 202 236
505 289 262 476 196 360 444 402 495 0 154 578 439 336 240 685 390
353 282 110 324 61 208 292 250 352 154 0 435 287 184 140 542 238
324 638 437 240 421 329 297 314 95 578 435 0 254 391 448 157 301
70 567 191 27 346 83 47 68 189 439 287 254 0 145 202 289 55
211 466 74 182 243 105 150 108 326 336 184 391 145 0 57 426 96
268 420 53 239 199 123 207 165 383 240 140 448 202 57 0 483 153
246 745 472 237 528 364 332 349 202 685 542 157 289 426 483 0 336
121 518 142 84 297 35 29 36 236 390 238 301 55 96 153 336 0

For gr17, try c = 1.5 with HC backtrack tries = 4.

Load text file

TSP Euclidean Points

First line is n, followed by x y point coordinates.

Points data

Benchmark: TSPLIB burma14 coordinates, converted to app Euclidean points; TSPLIB's official GEO optimum is not reused for Euclidean scoring.

Load text file

TSP Manual Weights

First line is n, then one upper-triangle weight per line in order: (1,2), (1,3), ....

Manual edge data

Benchmark: TSPLIB gr17, upper-triangle manual weights derived from the same instance as the matrix tab, optimum 2085.

For gr17, try c = 1.5 with HC backtrack tries = 4.

Load text file

Output

Ready.