Auto-generating XML documents from Schematron (was: N-Queens problem)

["Costello, Roger L." <costello@mitre.org>]

Hi Folks,

As you know, Schematron can be used to express powerful data relationships. We saw an example of this with the N-Queens problem.

The Schematron document for the N-Queens problem can be used to validate XML instance documents, to check that they contain a valid solution to the N-Queens problem.

Great!

But, but, but, …

Finding a valid solution to the N-Queens problem can be difficult, particularly for large chessboards.

It would be useful if we could auto-generate valid solutions directly from the Schematron document.

I am not aware of any tool that can auto-generate XML instances from Schematron.

With Alloy, you can express the same powerful data relationships that you can express with Schematron. Plus, the Alloy Analyzer can auto-generate solutions. In fact, the Analyzer can auto-generate a comprehensive set of solutions.

For example, at the bottom of this message is an Alloy model of the N-Queens problem. I instructed the Alloy Analyzer to generate solutions for a 5 x 5 chessboard. The Analyzer generated a complete set of solutions. Here are two of the solutions that it auto-generated:

Fantastic!

/Roger

Alloy Model (thanks Loïc Gammaitoni)

sig Queen {
    column: Column,
    row: Row
}

fact Queens_Not_On_Same_Row_Or_Column {
    no disj q, q': Queen | q.column = q'.column
    no disj q, q': Queen | q.row = q'.row
}

fact Queens_Not_On_Diagonal {
    no disj q, q': Queen |
        some a,b: Int {
            add[q.column.id, a] = q'.column.id
            add[q.row.id, b] = q'.row.id
            a=b or a=sub[0,b]
        }
}

…