1
$\begingroup$

I was solving the 8 queen problem and tried to look through the internet for comparison solutions to see how my solutions compared to others. I found one very small bruteforce solution that confused me. And i was wondering if anyone care to explain how the diagonal comparison actually works?

void solve(int n, int col, int *hist)
{
    int i;
    int j;

    if (col == n)
    {
        print_solution(n, hist);
    }
    i = 0;
    while (i < n)
    {
        j = 0;
        while (j < col && !(hist[j] == i || abs(hist[j] - i) == col - j))
            j++;
        if (j < col)
        {
            i++;
            continue;
        }
        hist[col] = i;
        solve(n, col + 1, hist);
        i++;
    }
}

void main(void)
{
    int hist[8];

    solve(8, 0, hist);
}

the code in particular im having problem visualizing is

abs(hist[j] - i) == col - j)

from what i understand it checks the diagonals but i dont see it.

$\endgroup$
  • 5
    $\begingroup$ The strict programming questions are off-topic here. It might be on-topic at Stack Overflow. By skimming the code, I do not understand what abs with two parameters does, it might be good to explain it. Commonly used abs takes one parameter. $\endgroup$ – Evil Jul 17 '17 at 21:12
  • $\begingroup$ sorry i misstyped, was supposed to be a subtraction there. maybe your right, i thought this was the right spot as its more of a algorithm question. $\endgroup$ – Frank Zapper Jul 17 '17 at 21:41
  • 1
    $\begingroup$ I did not check the algorithm, but maybe this exploits the fact that col - row gives the same result in (southeast-oriented) diagonals: you can see that because moving SE means incrementing both col and row. Indeed, to see if two cells fall in the same SE-diagonal, it suffices to compute that for both cells. $\endgroup$ – chi Jul 18 '17 at 14:10
  • $\begingroup$ @chi yes, i finally got it. its |x1−x2|=|y1−y2| $\endgroup$ – Frank Zapper Jul 18 '17 at 15:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.