use strict;
use warnings;

my $filename = shift;
our $n = shift;
our @r = @ARGV;
our @s = pSums(@r);
backTrack($filename);

sub backTrack
{
	open(OUTPUT, ">>".shift);
	print OUTPUT "Begin log: n=$n, r=(@r).\n";
	for my $i (1..int(($n+1)/2))
	{
		my %used;
		my %h;
		for (1..$n) {$used{$_} = 0; $h{$_} = 0;}
		$used{$i}++;
		my @res;
		$res[0] = $i;
		my $count = 1;
		recurse(\%used,\%h,\@res,$count);
	}
	print OUTPUT "End log.\n\n";
}

sub recurse
{
	my ($used,$h,$res,$count) = @_;
	unless ($count == $n) {
		for (1..$n)
		{
			if ((($count <= $s[0]+1)or(abs(@$res[$s[0]]-@$res[0]) == abs(@$res[$s[0]+1]-@$res[$s[0]])))&&($$used{$_} == 0)&&($$h{abs(@$res[$count-1]-$_)}==0))
			{
				@$res[$count] = $_;
				$$used{$_}++;
				$$h{abs(@$res[$count-1]-$_)}++;
				recurse($used,$h,$res,$count+1);
				$$h{abs(@$res[$count-1]-$_)}--;
				$$used{$_}--;
			}
		}
	}
	elsif (newtest($res)) {
		print "(@$res) works for r=(@r)!\n";
		print OUTPUT "g=(@$res) works for r=(@r)!\n";
		unless (@$res[0] == ($n+1)/2) {
			my @temp = map($n+1-$_,@$res);
			print OUTPUT "g=(@temp) works for r=(@r)!\n";
		}
	}
}

sub newtest
{
	my $input = shift;
	return 0 unless (abs(@$input[$s[0]]-@$input[0]) == abs(@$input[$s[0]+1]-@$input[$s[0]]));
	grep(((abs(@$input[$s[$_]]-@$input[$s[$_-1]+1]) == abs(@$input[$s[$_]+1]-@$input[$s[$_]])) or (return 0)), (1..@s-1));
	return 1;
}

sub pSums
{
	my @s;
	my @input = @_;
	$s[0] = $input[0]-1;
	for (1..@input-1) { $s[$_] = $s[$_-1] + $input[$_]; }
	return @s;
}