Ramsey's theorem: Difference between revisions

Content added Content deleted

Inline

@@ Line 3: / Line 3: @@
 =={{header|C}}==
-{{incorrect|C|The task has been changed to also require demonstrating that the graph is a solution.}}
 For 17 nodes, (4,4) happens to have a special solution: arrange nodes on a circle, and connect all pairs with distances 1, 2, 4, and 8.  It's easier to prove it on paper and just show the result than let a computer find it (you can call it optimization).
 <lang c>#include <stdio.h>
+int a[17][17], idx[4];
+int find_group(int type, int min_n, int max_n, int depth)
+{
+	int i, n;
+	if (depth == 4) {
+		printf("totally %sconnected group:", type ? "" : "un");
+		for (i = 0; i < 4; i++) printf(" %d", idx[i]);
+		putchar('\n');
+		return 1;
+	}
+	for (i = min_n; i < max_n; i++) {
+		for (n = 0; n < depth; n++)
+			if (a[idx[n]][i] != type) break;
+		if (n == depth) {
+			idx[n] = i;
+			if (find_group(type, 1, max_n, depth + 1))
+				return 1;
+		}
+	}
+	return 0;
+}
 int main()
 {
-	int a[17][17] = {{0}};
 	int i, j, k;
 	const char *mark = "01-";
@@ Line 28: / Line 51: @@
 		putchar('\n');
 	}
+	// testcase breakage
+	// a[2][1] = a[1][2] = 0;
+	// it's symmetric, so only need to test groups containing node 0
+	for (i = 0; i < 17; i++) {
+		idx[0] = i;
+		if (find_group(1, i+1, 17, 1) || find_group(0, i+1, 17, 1)) {
+			puts("no good");
+			return 0;
+		}
+	}
+	puts("all good");
 	return 0;
 }</lang>
@@ Line 49: / Line 85: @@
 0 1 0 0 0 1 1 0 0 0 1 0 1 1 - 1
 1 0 1 0 0 0 1 1 0 0 0 1 0 1 1 -
+all good
 </pre>