Is it possible to use 'set of tuple'?

[Miran]

Hi OscaR group,

I have been modelling the bishops constraint problem, stating "maximum number of bishops on a n times n board, not attacking each other" (more info at: http://mathworld.wolfram.com/BishopsProblem.html), which is also close the N Queens problem. 

Currently I have created a model using a 2 D array for creating the board, and afterwards adding the constraints. This works fine, and it finds the solutions. Also it is seems the way done in other CP models to use a 2D array.

However, I am wondering if it is possible to model in Oscar by representing the board as a 'set of tuples', e,g, {1..n}x{1..n}, and then say that the solution is a subset of the full set with constraints added?. This would allow to say fx 'solution in set board' or 'solution not in set board'.

An concrete example is described at http://mathematica.stackexchange.com/questions/134218/solving-chess-bishop-problem , that I coped in here:

"list=Tuples[Range[8],2]

I want to find the largest sublist in which the addition of the two entries for any two elements of the sublist will not be same and similarly the subtraction of the two entries for any two elements of the sublist will not be same. Ex:
sublist ={{1,3},{2,5},{7,3}}

here 1−3≠2−5≠7−31−3≠2−5≠7−3 and 1+3≠2+5≠7+31+3≠2+5≠7+3."

A motivation is the compare such a model, with the one using 2D array.

Best regards,

Miran

[Pierre Schaus]

Hi Miran,

On Thu, Feb 23, 2017 at 1:18 PM, Miran <mira...@gmail.com> wrote:

Hi OscaR group,

I have been modelling the bishops constraint problem, stating "maximum number of bishops on a n times n board, not attacking each other" (more info at: http://mathworld.wolfram.com/BishopsProblem.html), which is also close the N Queens problem. 

Currently I have created a model using a 2 D array for creating the board, and afterwards adding the constraints. This works fine, and it finds the solutions. Also it is seems the way done in other CP models to use a 2D array.

However, I am wondering if it is possible to model in Oscar by representing the board as a 'set of tuples', e,g, {1..n}x{1..n}, and then say that the solution is a subset of the full set with constraints added?. This would allow to say fx 'solution in set board' or 'solution not in set board'.

I would suggest you use table constraints (available in OscaR).

Simply enumerate every possible pairs of combinations of non attacking bishops (x1y1,x2y2) below to the table of feasible positions.

Then you can add an alldifferent on the positions to make sure that no two bishops are placed at the same location x1y1.

In this model x1y1 is one CPIntVar that represents uniquely one (x,y) position as x*n+y for instance. 

Cheers,

Pierre

 

An concrete example is described at http://mathematica.stackexchange.com/questions/134218/solving-chess-bishop-problem , that I coped in here:

"list=Tuples[Range[8],2]

I want to find the largest sublist in which the addition of the two entries for any two elements of the sublist will not be same and similarly the subtraction of the two entries for any two elements of the sublist will not be same. Ex:
sublist ={{1,3},{2,5},{7,3}}

here 1−3≠2−5≠7−31−3≠2−5≠7−3 and 1+3≠2+5≠7+31+3≠2+5≠7+3."

A motivation is the compare such a model, with the one using 2D array.

Best regards,

Miran

--

---
You received this message because you are subscribed to the Google Groups "OscaR" group.
To unsubscribe from this group and stop receiving emails from it, send an email to oscar-user+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

[Miran]

Hi Pierre,

Thanks for the suggestion.

Yes, the tabel constraint could be a good way to achieve this, before I was trying with two individual arrays which then refer to the respective indices in 2D fashion, which does not yet work.

I have been trying your approach since last week, and looking at the table constraint as described in the "getting started with Oscar" online, but I have questions if you get time:

I am a bit confused about the "In this model x1y1 is one CPIntVar that represents uniquely one (x,y) position as x*n+y for instance." modelling in Oscar/Scala. How does this correspond with the domain of a CPIntVar?. I see how the table constraint works, but the representation by using this enumeration approach I am not sure of, for example how it fits with the domain of each CPIntVar().

I think my main challenge is the actual representation of this in OscaR, e.g. how the positions and both the list and sublist are constraint modelled.

Best,

Miran

Hi Miran,

To unsubscribe from this group and stop receiving emails from it, send an email to oscar-user+...@googlegroups.com.

[Pierre Schaus]

On Mon, Mar 6, 2017 at 3:37 PM, Miran <mira...@gmail.com> wrote:

Hi Pierre,

Thanks for the suggestion.

Yes, the tabel constraint could be a good way to achieve this, before I was trying with two individual arrays which then refer to the respective indices in 2D fashion, which does not yet work.

I have been trying your approach since last week, and looking at the table constraint as described in the "getting started with Oscar" online, but I have questions if you get time:

I am a bit confused about the "In this model x1y1 is one CPIntVar that represents uniquely one (x,y) position as x*n+y for instance." modelling in Oscar/Scala. How does this correspond with the domain of a CPIntVar?.

Assume a 3x3 board. I label the cells on the board as:

0 1 2

3 4 5

6 7 8

The your table of feasible positions for any two bishops are feasibleBishops = {(0,1),(0,2),(0,5),(0,3),(0,6),(0,7),...}

Let x represent the position for one bishop, y represent the position of another one.

You must have (x,y) belongs to feasbielBishops (i.e. a table constraint).

Is it more clear?

Cheers,

Pierre

 

To unsubscribe from this group and stop receiving emails from it, send an email to oscar-user+unsubscribe@googlegroups.com.

[Miran]

Hi Pierre,

Thanks for the quick reply. 

Yes I think it a got a better idea now for beginning the modelling. I will try starting on the OscaR modelling during this week, to get a starting point.

Thanks for you help so far,

Best

Miran