Computer Chess Club Archives

Search

Messages

Subject: Re: Read Knuth's Dancing links.

Author: Dann Corbit

Date: 00:21:22 01/21/03

Go up one level in this thread

On January 18, 2003 at 04:15:49, Dan Andersson wrote:

>Knuth briefly discusses the Queens problem. And provides a reference. The point
>is that no searching is needed to find an empty coulumn.
/*
Knuth's N-queens solution:
*/
#include <stdio.h>
#include <stdlib.h>

static unsigned param;

static char     encode(unsigned x)
{
    if (x < 10)
        return '0' + x;
    return 'a' - 10 + x;
}


int             main(int argc, char *argv[])
{
    unsigned
                    j,
                    k,
                    n,
                    nn,
                    t;

    if (argc != 2 || sscanf(argv[1], "%u", &param) != 1) {
        fprintf(stderr, "Usage: %s n\n", argv[0]);
        exit(EXIT_FAILURE);
    }
    n = param;
    nn = n + n - 2;

    for (j = 0; j < n; j++) {
        t = (j & 1 ? n - 1 - j : n + j) >> 1;
        printf("r%c c%c ", encode(t), encode(t));
    }
    printf("|");
    for (j = 1; j < nn; j++)
        printf(" a%c b%c", encode(j), encode(j));
    printf("\n");

    for (j = 0; j < n; j++)
        for (k = 0; k < n; k++) {
            printf("r%c c%c", encode(j), encode(k));
            t = j + k;
            if (t && (t < nn))
                printf(" a%c", encode(t));
            t = n - 1 - j + k;
            if (t && (t < nn))
                printf(" b%c", encode(t));
            printf("\n");
        }
    return 0;
}

This page took 0 seconds to execute

Last modified: Thu, 15 Apr 21 08:11:13 -0700

Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.