joshuaguerin / answer-set-programming-algorithms Goto Github PK

It feels a bit obvious, but I think that is the curse of knowledge. Queens is so common because it is a great illustration. Probably going to add.

Pretty simple example, I think.

Bin Packing?

We are starting to get occasional traffic and stargazers, so let's clean things up and make them presentable.

Going to pull partial/non-working solutions into their own branches to keep the main page clean.

Max Flow is likely worthy of a formal treatment.

Algorithm is highly inefficient and likely broken. Need to circle back to examine overall representation/strategy and correctness.

Current grid constraint is ugly and not terribly elegant. I think a solution is to be had that involves div or mod that greatly reduces the complexity of the final 2 constraints.

At the start I've avoided puzzles, but they are likely to carry useful lessons for the reader. Sudoku is one of the standard examples.

Do it.

Current problem list:

• Bin Packing
• Clique
• Clustering
• Dominating Set
• Equal Sum Partition
• Graph Coloring
• Independent Set
• Knapsack
• Max Flow
• N Queens
• Numerical 3-Dimensional Matching
• Perfect Numbers
• Prime Sieve
• Subset Sum
• Sudoku
• Travelling Salesman
• Vertex Cover
• Wolf, Goat, and Cabbage

Create a shared scripting directory that includes (minimally) more generalized parsing functionality. This is shared among all instances, so this will go a long way to clean up individual code files and improve the ease of writing new Python source.

Primes was pretty trivial. Perfect numbers would likely be another good example.

A couple of the algorithms have pretty-printers in the validate directory. Should look into doing so for more algorithms.

Current problem list:

• Bin Packing
• Clique
• Clustering
• Dominating Set
• Equal Sum Partition
• Graph Coloring
• Independent Set
• Knapsack
• Max Flow
• N Queens
• Numerical 3-Dimensional Matching
• Perfect Numbers
• Prime Sieve
• Subset Sum
• Sudoku
• Travelling Salesman
• Vertex Cover
• Wolf, Goat, and Cabbage

Is it correct?
Can I make it better looking?

Not 100% certain on that last one. Two thoughts:

1. I think two constraints are needed.
2. The same arithmetic has to be expressed somehow.

I think we may be closing rapidly in on minimizing the ugly here.

Initial solution for W-G-C problem printer had crashing upon unsat. Need to locate any similarly misbehaving scripts and fix for user friendliness.