I implemented the Sosic and Gu fast N-Queens solver first in C++ and later in C#. The five screen shots below were created by latest C# application. None of my other algorithms can compete with this method.
The Graph Coloring Problem and N-Queens Puzzle are both NP-Complete constraint satisfaction problems. There does not exist polynomial time algorithms to solve large instances of either problem. The Graph Coloring Problem is given a graph of n-vertices and m-edges find the minimum number of colors such that no two connected vertices are of the same color. The N-Queens Puzzle is given a n-by-n chessboard and n-queens place the queens such that no two queens are attacking one another. A queen in chess can move any number of squares diagonally, horizontally, or vertically.
As a Master of Software Engineering graduate student in the era 1998 to 2000, I majored in the subdiscipline of artificial intelligence known as constraint satisfaction. I developed evolutionary hill-climbing algorithms to solve constraint satisfaction problems. I specifically solved instances of the Graph Coloring Problem and the N-Queens Puzzle. I compared my algorithms with other researchers’ algorithms. One of the algorithms tested was Makato Yokoo’s Weak-Commitment Search Algorithm (WCSA). Yakoo wrote a very nice book named “Distributed Constraint Satisfaction” which has excellent flow-charts of several algorithms including the Min-Conflicts Search Algorithm (MCSA) and his WCSA. I implemented both algorithms in the C++ and Java computer languages.
I rewrote the preceding two algorithms in the C# computer language sometime in the epoch 2008 – 2009. Below are three instances of the Graph Coloring Problem with four, eight, and twelve vertices solved by the Yakoo’s WCSA.
In the early 2000s I bought a hardware SNARLING DOGS GUITAR CHORD Computer. In 2003 I decided to emulate the hardware device in Java and later in 2009 C#. I have more work to do such as adding minor, augmented, diminished, sixth, seventh, and ninth chords. I require more scales such as the seventh and ninth scales.
A few years ago, I implemented the LLL lattice reduction algorithm found in two references: “Handbook of Applied Cryptography” Edited by Alfred J. Menezes et al and “A Course in Computational Algebraic Number Theory” by Henri Cohen. My new implementation in C# uses 64-bit integers and BigIntegers. Here are some results.
27-Decimal Digit Number 123456789012345678901234567
31-Digit Decimal Number 1234567890123456789012345678901 Pollard Failed
The same factorizations by the Classical Shor-Pollard- James Pate Williams, Jr. algorithm.
// Algorithms from "A Course in Computational
// Algebraic Number Theory" by Henri Cohen
// Implemented by James Pate Williams, Jr.
// Copyright (c) 2023 All Rights Reserved
using System.Collections.Generic;
using System.Numerics;
namespace PoweringAlgorithms
{
public interface IAlgorithms
{
// Extended Euclidean Algorithm
BigInteger Algorithm_1_2_1(
BigInteger g, BigInteger n);
BigInteger Algorithm_1_2_2(
int e, BigInteger g, BigInteger n);
public BigInteger Algorithm_1_2_3(
int e, BigInteger g, BigInteger n);
void Algorithm_1_3_6(
BigInteger a, BigInteger b,
out BigInteger u, out BigInteger v,
out BigInteger d);
List<int> GetBits(BigInteger N);
BigInteger Inverse(
BigInteger a, BigInteger n);
}
}
using System.Collections.Generic;
using System.Numerics;
namespace PoweringAlgorithms
{
public class Algorithms : IAlgorithms
{
public BigInteger Algorithm_1_2_1(
BigInteger g, BigInteger n)
{
BigInteger y = 1;
if (n == 0)
return y;
BigInteger N, z;
if (n < 0)
{
N = -n;
z = Inverse(g, n);
}
else
{
N = n;
z = g;
}
while (N > 0)
{
if (N % 2 == 1)
y *= z;
N /= 2;
z *= z;
}
return y;
}
public BigInteger Algorithm_1_2_2(
int e, BigInteger g, BigInteger n)
{
BigInteger E, N, y, z;
if (n == 0)
return BigInteger.One;
if (n < 0)
{
N = -n;
z = Inverse(g, n);
}
else
{
N = n;
z = g;
}
y = z;
E = BigInteger.Pow(2, e);
N -= E;
while (E > 1)
{
E /= 2;
y *= y;
if (N >= E)
{
N -= E;
y *= z;
}
}
return y;
}
public BigInteger Algorithm_1_2_3(
int e, BigInteger g, BigInteger n)
{
BigInteger y = 1;
if (n == 0)
return y;
BigInteger N, z;
if (n < 0)
{
N = -n;
z = Inverse(g, n);
}
else
{
N = n;
z = g;
}
y = z;
int f = e;
List<int> bits = GetBits(N);
while (f > 0)
{
f--;
y *= y;
if (bits[f] == 1)
y *= z;
}
return y;
}
public void Algorithm_1_3_6(
BigInteger a, BigInteger b,
out BigInteger u, out BigInteger v,
out BigInteger d)
{
u = 1;
d = a;
if (b == 0)
{
v = 0;
return;
}
BigInteger q, t1, t3, v1 = 0, v3 = b;
while (v3 > 0)
{
q = d / v3;
t3 = d % v3;
t1 = u - q * v1;
u = v1;
d = v3;
v1 = t1;
v3 = t3;
}
v = (d - a * u) / b;
}
public List<int> GetBits(BigInteger N)
{
int b;
List<int> temp = new();
while (N > 0)
{
b = (int)(N % 2);
N /= 2;
temp.Add(b);
}
List<int> bits = new();
for (int i = temp.Count; i >= 0; i--)
bits.Add(temp[i]);
return bits;
}
public BigInteger Inverse(BigInteger a, BigInteger n)
{
BigInteger d, u, v;
Algorithm_1_3_6(
a, n, out u, out v, out d);
return u;
}
}
}
using System;
using System.Numerics;
using System.Windows.Forms;
namespace PoweringAlgorithms
{
public partial class TestForm : Form
{
public TestForm()
{
InitializeComponent();
}
private static BigInteger Horner(string text)
{
BigInteger a = text[0] - '0';
for (int i = 1; i < text.Length; i++)
a = 10 * a + text[i] - '0';
return a;
}
private void button1_Click(object sender, EventArgs e)
{
int expon = 0;
Algorithms algos = new Algorithms();
BigInteger g = Horner(textBox1.Text);
BigInteger n = Horner(textBox2.Text);
BigInteger a = algos.Algorithm_1_2_1(g, n);
BigInteger m = BigInteger.Abs(n);
while (m > 0)
{
expon++;
m /= 2;
}
BigInteger b = algos.Algorithm_1_2_2(expon - 1, g, n);
BigInteger c = algos.Algorithm_1_2_2(expon - 1, g, n);
textBox3.Text = a.ToString();
textBox4.Text = b.ToString();
textBox5.Text = c.ToString();
}
private void button2_Click(object sender, EventArgs e)
{
Close();
}
}
}
Algorithms are found in the textbook “Introduction to Algorithms” by Thomas H. Cormen, Charles E. Leiserson, Ronald L. Rivest p. 340.
using System;
using System.Collections.Generic;
using System.Windows.Forms;
namespace Huffman
{
public partial class MainForm : Form
{
private int leafNodes;
public MainForm()
{
InitializeComponent();
}
private void InorderTraversal(BinaryTreeNode<CharFreq> node)
{
if (node != null)
{
InorderTraversal(node.Left);
CharFreq cf = node.Value;
int ord = (int)cf.ch;
if (node.Left == null && node.Right == null)
{
textBox2.Text += leafNodes.ToString("F0").PadLeft(3) + '\t';
textBox2.Text += "'" + new string(cf.ch, 1) + "' " + '\t';
textBox2.Text += node.Value.freq.ToString() + "\r\n";
leafNodes++;
}
InorderTraversal(node.Right);
}
}
private void button1_Click(object sender, EventArgs e)
{
string s = textBox1.Text;
int n = s.Length;
List<CharFreq> list = new List<CharFreq>();
textBox2.Text = string.Empty;
for (int i = 0; i < n; i++)
{
bool found = false;
char c = s[i];
CharFreq cf = new CharFreq();
for (int j = 0; !found && j < list.Count; j++)
{
if (c == list[j].ch)
{
found = true;
cf.ch = c;
cf.freq = 1 + list[j].freq;
list.RemoveAt(j);
list.Add(cf);
}
}
if (!found)
{
cf.ch = c;
cf.freq = 1;
list.Add(cf);
}
}
HuffmanTree ht = new HuffmanTree();
BinaryTreeNode<CharFreq> root = ht.Build(list, list.Count);
InorderTraversal(root);
textBox2.Text += "\r\n# characters = " + n.ToString() + "\r\n";
textBox2.Text += "# leaf nodes = " + leafNodes.ToString() + "\r\n";
textBox2.Text += "% compressed = " +
(100.0 - 100.0 * ((double)leafNodes) / n).ToString("F2") + "\r\n";
}
}
}
namespace Huffman
{
public class BinaryTreeNode<T> : Node<T>
{
public BinaryTreeNode() : base() { }
public BinaryTreeNode(T data) : base(data, null) { }
public BinaryTreeNode(T data, BinaryTreeNode<T> left, BinaryTreeNode<T> right)
{
base.Value = data;
NodeList<T> children = new NodeList<T>(2)
{
[0] = left,
[1] = right
};
base.Neighbors = children;
}
public BinaryTreeNode<T> Left
{
get
{
if (base.Neighbors == null)
return null;
else
return (BinaryTreeNode<T>)base.Neighbors[0];
}
set
{
if (base.Neighbors == null)
base.Neighbors = new NodeList<T>(2);
base.Neighbors[0] = value;
}
}
public BinaryTreeNode<T> Right
{
get
{
if (base.Neighbors == null)
return null;
else
return (BinaryTreeNode<T>)base.Neighbors[1];
}
set
{
if (base.Neighbors == null)
base.Neighbors = new NodeList<T>(2);
base.Neighbors[1] = value;
}
}
}
}
using System.Collections.Generic;
namespace Huffman
{
public class HuffmanTree
{
public BinaryTreeNode<CharFreq> Build(List<CharFreq> charFreq, int n)
{
PriorityQueue Q = new PriorityQueue();
for (int i = 0; i < n; i++)
{
BinaryTreeNode<CharFreq> z = new BinaryTreeNode<CharFreq>(charFreq[i]);
Q.insert(z);
}
Q.buildHeap();
for (int i = 0; i < n - 1; i++)
{
BinaryTreeNode<CharFreq> x = Q.extractMin();
BinaryTreeNode<CharFreq> y = Q.extractMin();
CharFreq chFreq = new CharFreq();
chFreq.ch = (char)((int)x.Value.ch + (int)y.Value.ch);
chFreq.freq = x.Value.freq + y.Value.freq;
BinaryTreeNode<CharFreq> z = new BinaryTreeNode<CharFreq>(chFreq);
z.Left = x;
z.Right = y;
Q.insert(z);
}
return Q.extractMin();
}
}
}
namespace Huffman
{
public class Node<T>
{
// Private member-variables
private T data;
private NodeList<T> neighbors = null;
public Node() { }
public Node(T data) : this(data, null) { }
public Node(T data, NodeList<T> neighbors)
{
this.data = data;
this.neighbors = neighbors;
}
public T Value
{
get
{
return data;
}
set
{
data = value;
}
}
protected NodeList<T> Neighbors
{
get
{
return neighbors;
}
set
{
neighbors = value;
}
}
}
}
using System.Collections.ObjectModel;
namespace Huffman
{
public class NodeList<T> : Collection<Node<T>>
{
public NodeList() : base() { }
public NodeList(int initialSize)
{
// Add the specified number of items
for (int i = 0; i < initialSize; i++)
base.Items.Add(default(Node<T>));
}
public Node<T> FindByValue(T value)
{
// search the list for the value
foreach (Node<T> node in Items)
if (node.Value.Equals(value))
return node;
// if we reached here, we didn't find a matching node
return null;
}
}
}
using System.Collections.Generic;
namespace Huffman
{
public struct CharFreq
{
public char ch;
public int freq;
}
public class PriorityQueue
{
int heapSize;
List<BinaryTreeNode<CharFreq>> nodeList;
public List<BinaryTreeNode<CharFreq>> NodeList
{
get
{
return nodeList;
}
}
public PriorityQueue()
{
nodeList = new List<BinaryTreeNode<CharFreq>>();
}
public PriorityQueue(List<BinaryTreeNode<CharFreq>> nl)
{
heapSize = nl.Count;
nodeList = new List<BinaryTreeNode<CharFreq>>();
for (int i = 0; i < nl.Count; i++)
nodeList.Add(nl[i]);
}
public void exchange(int i, int j)
{
BinaryTreeNode<CharFreq> temp = nodeList[i];
nodeList[i] = nodeList[j];
nodeList[j] = temp;
}
public void heapify(int i)
{
int l = 2 * i + 1;
int r = 2 * i + 2;
int largest = -1;
if (l < heapSize && nodeList[l].Value.ch > nodeList[i].Value.ch)
largest = l;
else
largest = i;
if (r < heapSize && nodeList[r].Value.ch > nodeList[largest].Value.ch)
largest = r;
if (largest != i)
{
exchange(i, largest);
heapify(largest);
}
}
public void buildHeap()
{
for (int i = heapSize / 2; i >= 0; i--)
heapify(i);
}
public int size()
{
return heapSize;
}
public BinaryTreeNode<CharFreq> elementAt(int i)
{
return nodeList[i];
}
public void heapSort()
{
int temp = heapSize;
buildHeap();
for (int i = heapSize - 1; i >= 1; i--)
{
exchange(0, i);
heapSize--;
heapify(0);
}
heapSize = temp;
}
public BinaryTreeNode<CharFreq> extractMin()
{
if (heapSize < 1)
return null;
heapSort();
exchange(0, heapSize - 1);
heapSize--;
BinaryTreeNode<CharFreq> node = nodeList[heapSize];
nodeList.RemoveAt(heapSize);
heapSize = nodeList.Count;
return node;
}
public void insert(BinaryTreeNode<CharFreq> node)
{
nodeList.Add(node);
heapSize = nodeList.Count;
buildHeap();
}
}
}
We calculate the ground state energies for Helium (Z = 2), Lithium (Z = 3), Beryllium (Z = 4), Boron (Z = 5), and Carbon (Z = 6). Currently, only three of the five atoms are implemented.
See the following website for the used algorithms pages 119 to 121:
Numerical Explorations 