Optimized Java library for graph-coloring problem variants

Engines, Libraries and Tools
#1

Hi! This is my first post on the JGO forum (although I’ve been a silent and enthusiast reader for a while) and I’m no native English speaker, so please bear with me if I chose the wrong section to post this question or misspell a word or two. I’ll try to be as concise as possible.
In the videogame I’m writing I need an AI to solve this problem (roughly sketched) in several different stages of the gameplay:

R is an M x N matrix.
Some cells of R must be filled with a color (to choose among a predefined finite set).
These cells should be randomly chosen, but the resulting set of <cell, color> tuples has to satisfy the following constraints:

  1. A cell can be colored with only one color or left blank.
  2. If a, b, c are three cells of the same row so that a is adjacent to b and b is adjacent to c, then a, b and c cannot be filled with the same color (two cells are adjacent if they share and edge).
  3. Same as above, but applied to columns.

It’s a variant of the graph-coloring problem, which I would normally approach with Answer Set Programming, but unfortunately there’s no free/opensource solver with a Java binding to embed in my code. So, is there any free tool or library written in Java that lets me model and solve this problem in a convenient way?

Thanks for your attention. :slight_smile:

#2

to me it sounds like classic propositional logic. might be a starting point to look around for you.

which is based on

and leads to

from my trips into these fields, java never seemed to be “convenient”, rather bold.


and java is a bit awkward.

somehow i always end up with erlang.

anyway, these things are great tools for games. sorry i cannot suggest any java-frameworks tho’.

o/

#3

Yes, it could be easily modeled with a modern approach to logic deriving from the classical propositional logic, called Disjunctive Logic Programming (DLP), which is my basic approach for stand-alone non-Java projects or where real time performance isn’t paramount. But however, thank you for making me discover Erlang, it may be unrelated but looks like a nice language to investigate about :slight_smile:

#4

now that you made me look around; did you look into http://tweetyproject.org yet ?

i’m having a blast on that code. very interesting. not too speedy but complete and mature.

#5

Omg :o
This seems to be EXACTLY what I was looking for, and bridges to ASP solvers as well!
I’ll have my hands on it as soon as possible.

Really thanks a lot man