您想找到对变量{p1，p2，…，pn}的赋值（其中pi是首次出现的“ i”的位置），并且每个pi都具有以下约束：
- pi在1 ..（（1 + ni）
- 如果pi = k，则所有pj，其中j！= i
- pj！= k
- pj！= k +我
- pj！= k-j
- pj！= k + i-j
您在这里需要一个明智的搜索策略。一个不错的选择是在每个选择点选择具有最小剩余可能值的pi。
干杯!
[编辑：第二增编。]
这是我最初编写的命令式版本的“大部分功能”版本（请参见下面的第一个附录）。从与搜索树中每个顶点关联的状态独立于所有其他状态的意义上说，它主要是起作用的，因此不需要此类路径或机制。但是，我已经使用命令式代码从父域集的副本中实现每个新域集的构造。
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace MostlyFunctionalLangford{ class Program { // An (effectively functional) program to compute Langford sequences. static void Main(string[] args) { var n = 7; var DInit = InitLangford(n); var DSoln = Search(DInit); if (DSoln != null) { Console.WriteLine(); Console.WriteLine("Solution for n = {0}:", n); WriteSolution(DSoln); } else { Console.WriteLine(); Console.WriteLine("No solution for n = {0}.", n); } Console.Read(); } // The largest integer in the Langford sequence we are looking for. // [I could infer N from the size of the domain array, but this is neater.] static int N; // ---- Integer domain manipulation. ---- // Find the least bit in a domain; return 0 if the domain is empty. private static long LeastBitInDomain(long d) { return d & ~(d - 1); } // Remove a bit from a domain. private static long RemoveBitFromDomain(long d, long b) { return d & ~b; } private static bool DomainIsEmpty(long d) { return d == 0; } private static bool DomainIsSingleton(long d) { return (d == LeastBitInDomain(d)); } // Return the size of a domain. private static int DomainSize(long d) { var size = 0; while (!DomainIsEmpty(d)) { d = RemoveBitFromDomain(d, LeastBitInDomain(d)); size++; } return size; } // Find the k with the smallest non-singleton domain D[k]. // Returns zero if none exists. private static int SmallestUndecidedDomainIndex(long[] D) { var bestK = 0; var bestKSize = int.MaxValue; for (var k = 1; k <= N && 2 < bestKSize; k++) { var kSize = DomainSize(D[k]); if (2 <= kSize && kSize < bestKSize) { bestK = k; bestKSize = kSize; } } return bestK; } // Obtain a copy of a domain. private static long[] CopyOfDomain(long[] D) { var DCopy = new long[N + 1]; for (var i = 1; i <= N; i++) DCopy[i] = D[i]; return DCopy; } // Destructively prune a domain by setting D[k] = {b}. // Returns false iff this exhausts some domain. private static bool Prune(long[] D, int k, long b) { for (var j = 1; j <= N; j++) { if (j == k) { D[j] = b; } else { var dj = D[j]; dj = RemoveBitFromDomain(dj, b); dj = RemoveBitFromDomain(dj, b << (k + 1)); dj = RemoveBitFromDomain(dj, b >> (j + 1)); dj = RemoveBitFromDomain(dj, (b << (k + 1)) >> (j + 1)); if (DomainIsEmpty(dj)) return false; if (dj != D[j] && DomainIsSingleton(dj) && !Prune(D, j, dj)) return false; } } return true; } // Search for a solution from a given set of domains. // Returns the solution domain on success. // Returns null on failure. private static long[] Search(long[] D) { var k = SmallestUndecidedDomainIndex(D); if (k == 0) return D; // Branch on k, trying each possible assignment. var dk = D[k]; while (!DomainIsEmpty(dk)) { var b = LeastBitInDomain(dk); dk = RemoveBitFromDomain(dk, b); var DKeqB = CopyOfDomain(D); if (Prune(DKeqB, k, b)) { var DSoln = Search(DKeqB); if (DSoln != null) return DSoln; } } // Search failed. return null; } // Set up the problem. private static long[] InitLangford(int n) { N = n; var D = new long[N + 1]; var bs = (1L << (N + N - 1)) - 1; for (var k = 1; k <= N; k++) { D[k] = bs & ~1; bs >>= 1; } return D; } // Print out a solution. private static void WriteSolution(long[] D) { var l = new int[N + N + 1]; for (var k = 1; k <= N; k++) { for (var i = 1; i <= N + N; i++) { if (D[k] == 1L << i) { l[i] = k; l[i + k + 1] = k; } } } for (var i = 1; i < l.Length; i++) { Console.Write("{0} ", l[i]); } Console.WriteLine(); } }}[编辑：第一增编。]
我决定编写一个C＃程序来解决Langford问题。它运行非常快，直到n = 16，但是此后您需要将其更改为使用long，因为它将域表示为位模式。
using System;using System.Collections.Generic;using System.Linq;using System.Text;namespace Langford{ // Compute Langford sequences. A Langford sequence L(n) is a permutation of [1, 1, 2, 2, ..., n, n] such // that the pair of 1s is separated by 1 place, the pair of 2s is separated by 2 places, and so forth. // class Program { static void Main(string[] args) { var n = 16; InitLangford(n); WriteDomains(); if (FindSolution()) { Console.WriteLine(); Console.WriteLine("Solution for n = {0}:", n); WriteDomains(); } else { Console.WriteLine(); Console.WriteLine("No solution for n = {0}.", n); } Console.Read(); } // The n in L(n). private static int N; // D[k] is the set of unexcluded possible positions in the solution of the first k for each pair of ks. // Each domain is represented as a bit pattern, where bit i is set iff i is in D[k]. private static int[] D; // The trail records domain changes to undo on backtracking. T[2k] gives the element in D to undo; // T[2k+1] gives the value to which it must be restored. private static List<int> T = new List<int> { }; // This is the index of the next unused entry in the trail. private static int TTop; // Extend the trail to restore D[k] on backtracking. private static void TrailDomainValue(int k) { if (TTop == T.Count) { T.Add(0); T.Add(0); } T[TTop++] = k; T[TTop++] = D[k]; } // Undo the trail to some earlier point. private static void UntrailTo(int checkPoint) { //Console.WriteLine("Backtracking..."); while (TTop != checkPoint) { var d = T[--TTop]; var k = T[--TTop]; D[k] = d; } } // Find the least bit in a domain; return 0 if the domain is empty. private static int LeastBitInDomain(int d) { return d & ~(d - 1); } // Remove a bit from a domain. private static int RemoveBitFromDomain(int d, int b) { return d & ~b; } private static bool DomainIsEmpty(int d) { return d == 0; } private static bool DomainIsSingleton(int d) { return (d == LeastBitInDomain(d)); } // Return the size of a domain. private static int DomainSize(int d) { var size = 0; while (!DomainIsEmpty(d)) { d = RemoveBitFromDomain(d, LeastBitInDomain(d)); size++; } return size; } // Find the k with the smallest non-singleton domain D[k]. // Returns zero if none exists. private static int SmallestUndecidedDomainIndex() { var bestK = 0; var bestKSize = int.MaxValue; for (var k = 1; k <= N && 2 < bestKSize; k++) { var kSize = DomainSize(D[k]); if (2 <= kSize && kSize < bestKSize) { bestK = k; bestKSize = kSize; } } return bestK; } // Prune the other domains when domain k is reduced to a singleton. // Return false iff this exhausts some domain. private static bool Prune(int k) { var newSingletons = new Queue<int>(); newSingletons.Enqueue(k); while (newSingletons.Count != 0) { k = newSingletons.Dequeue(); //Console.WriteLine("Pruning from domain {0}.", k); var b = D[k]; for (var j = 1; j <= N; j++) { if (j == k) continue; var dOrig = D[j]; var d = dOrig; d = RemoveBitFromDomain(d, b); d = RemoveBitFromDomain(d, b << (k + 1)); d = RemoveBitFromDomain(d, b >> (j + 1)); d = RemoveBitFromDomain(d, (b << (k + 1)) >> (j + 1)); if (DomainIsEmpty(d)) return false; if (d != dOrig) { TrailDomainValue(j); D[j] = d; if (DomainIsSingleton(d)) newSingletons.Enqueue(j); } } //WriteDomains(); } return true; } // Search for a solution. Return false iff one is not found. private static bool FindSolution() { var k = SmallestUndecidedDomainIndex(); if (k == 0) return true; // Branch on k, trying each possible assignment. var dOrig = D[k]; var d = dOrig; var checkPoint = TTop; while (!DomainIsEmpty(d)) { var b = LeastBitInDomain(d); d = RemoveBitFromDomain(d, b); D[k] = b; //Console.WriteLine(); //Console.WriteLine("Branching on domain {0}.", k); if (Prune(k) && FindSolution()) return true; UntrailTo(checkPoint); } D[k] = dOrig; return false; } // Print out a representation of the domains. private static void WriteDomains() { for (var k = 1; k <= N; k++) { Console.Write("D[{0,3}] = {{", k); for (var i = 1; i <= N + N; i++) { Console.Write("{0, 3}", ( (1 << i) & D[k]) != 0 ? i.ToString() : DomainIsSingleton(D[k]) && (1 << i) == (D[k] << (k + 1)) ? "x": ""); } Console.WriteLine(" }"); } } // Set up the problem. private static void InitLangford(int n) { N = n; D = new int[N + 1]; var bs = (1 << (N + N - 1)) - 1; for (var k = 1; k <= N; k++) { D[k] = bs & ~1; bs >>= 1; } } }}
