How could I remove backtracking from this code?

Question

The goal is to select shapes that don't touch each other using constraints (clpfd). Calling start(Pairs,4) would return Pairs = [1,3,5,7].

One problem I noticed is that if I print Final before labeling, it prints [1,3,5,7]. Which means labeling isn't doing anything.

What could I change/add to this code in order to fix that and also remove possible backtracking?

:-use_module(library(clpfd)).
:-use_module(library(lists)).


% init initialises Pairs and Max
% Pairs - The elements inside the Nth list in Pairs, 
% represent the index of the shapes that shape N can touch 

init([[3,5,6,7],[4,5,7],[1,4,5,7],[2,3,7],[1,2,3,7],[1],[1,2,3,4,5]],7).

start(Final, N):-
  init(Pairs, Max),

  length(Final, N),
  domain(Final, 1, Max),

  ascending(Final),
  all_different(Final),
  rules(Pairs,Final),

  labeling([],Final).

rules(_,[]).
rules(Pairs,[H|T]):-
  nth1(H,Pairs,PairH),
  secondrule(PairH,T),
  rules(Pairs,T).

secondrule(_, []).
secondrule(PairH, [H|T]):-
  element(_,PairH,H),
  secondrule(PairH, T).

ascending([_|[]]).
ascending([H|[T1|T2]]):-
  H #< T1,
  ascending([T1|T2]).

Answer 1

This is an Independent Set problem, which is an NP-hard problem. Therefore, it is unlikely that anybody will ever find a way to do it without search (backtracking) for general instances.

Regarding your code, labeling/2 does nothing, because your rules/2 is in fact a search procedure that returns the solution it it can find it. all_different/1 is useless too, because it is implied by ascending/1.

Presumably, your goal is a program that sets up constraints (without any search) and then searches for a solution with labeling/2. For that, you need to rethink your constraint model. Read up a bit on independent sets.