/*
  This file is hereby released to the public domain.
  ~aaaaaa123456789, 2015-01-21
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#include "common.h"

int fill_numbers(unsigned short *, unsigned, char **);
unsigned short validate_row(const unsigned short *, unsigned short);
unsigned short validate_column(const unsigned short *, unsigned short, unsigned short);
void assign(const unsigned short *, unsigned short);
void try_assign(const unsigned short *, unsigned short, unsigned short, unsigned short *, unsigned char *);
void output(const unsigned short *, unsigned short);

#define create_map(x) calloc(1, ((x) + 7) >> 3)
#define set_map(map, x) (((x) >> 3)[(char *) (map)] |= 1 << ((x) & 7))
#define clear_map(map, x) (((x) >> 3)[(char *) (map)] &= ~(1 << ((x) & 7)))
#define test_map(map, x) ((((x) >> 3)[(char *) (map)]) & (1 << ((x) & 7)))

int main (void) {
  // note: this function doesn't release memory before returning -- terminating handles that
  fputs("Enter data (one row per line, numbers separated by spaces, numbers", stderr);
  fputs("range from 1 to n), end with a blank line or EOF:\n", stderr);
  char ** lines = get_lines(0, "", 0, NULL);
  unsigned count = count_lines(lines);
  if (!count) return 0; // nothing to do here
  if (count > 65534) {
    fputs("Too much data.\n", stderr);
    return 1;
  }
  unsigned short * numbers = malloc(count * count * sizeof(unsigned short));
  if (!numbers) {
    fputs("Out of memory.\n", stderr);
    return 1;
  }
  if (!fill_numbers(numbers, count, lines)) return 1;
  free(lines);
  assign(numbers, count);
  return 0;
}

int fill_numbers (unsigned short * numbers, unsigned count, char ** lines) {
  char * errp;
  char ** tokens;
  unsigned long rv;
  unsigned linenumber, colnumber;
  for (linenumber = 0; linenumber < count; lines ++, linenumber ++) {
    tokens = tokenize_string(*lines, " ", 1);
    free(*lines);
    if (count_lines(tokens) != count) {
      fprintf(stderr, "ERROR: line %u does not contain %u numbers\n", linenumber + 1, count);
      return 0;
    }
    for (colnumber = 0; colnumber < count; colnumber ++) {
      rv = strtoul(tokens[colnumber], &errp, 10);
      if (*errp) {
        fprintf(stderr, "ERROR: value at (%u, %u) is not a number\n", linenumber + 1, colnumber + 1);
        return 0;
      } else if ((!rv) || (rv > count)) {
        fprintf(stderr, "ERROR: value at (%u, %u) is out of range (expected: 1..%u, got: %lu)\n", linenumber + 1, colnumber + 1, count, rv);
        return 0;
      }
      numbers[linenumber * count + colnumber] = rv;
    }
    free(tokens);
    if (rv = validate_row(numbers + linenumber * count, count)) {
      fprintf(stderr, "ERROR: row %u repeats value %lu\n", linenumber + 1, rv);
      return 0;
    }
  }
  for (colnumber = 0; colnumber < count; colnumber ++)
    if (rv = validate_column(numbers, count, colnumber)) {
      fprintf(stderr, "ERROR: column %u repeats value %lu\n", colnumber + 1, rv);
      return 0;
    }
  return count;
}

void assign (const unsigned short * numbers, unsigned short count) {
  unsigned short * assigned = malloc(sizeof(unsigned short) * count);
  memset(assigned, 0, sizeof(unsigned short) * count);
  unsigned char * available = create_map(count);
  try_assign(numbers, count, 0, assigned, available);
}

unsigned short validate_row (const unsigned short * row, unsigned short length) {
  char * values = create_map(length);
  while (length --) {
    if (test_map(values, *row - 1)) {
      free(values);
      return *row;
    }
    set_map(values, *row - 1);
    row ++;
  }
  free(values);
  return 0;
}

unsigned short validate_column (const unsigned short * numbers, unsigned short count, unsigned short column) {
  if (column >= count) return 0;
  char * values = create_map(count);
  unsigned short p;
  numbers += column;
  for (p = 0; p < count; p ++, numbers += count) {
    if (test_map(values, *numbers - 1)) {
      free(values);
      return *numbers;
    }
    set_map(values, *numbers - 1);
  }
  free(values);
  return 0;
}

void try_assign (const unsigned short * numbers, unsigned short count, unsigned short current, unsigned short * assigned, unsigned char * available) {
  if (current >= count) {
    output(assigned, count);
    return;
  }
  unsigned short attempt;
  const unsigned short * p = numbers + count * current;
  for (attempt = 0; attempt < count; attempt ++, p ++) {
    if (assigned[attempt]) continue;
    if (test_map(available, *p - 1)) continue;
    assigned[attempt] = *p;
    set_map(available, *p - 1);
    try_assign(numbers, count, current + 1, assigned, available);
    clear_map(available, *p - 1);
    assigned[attempt] = 0;
  }
}

void output (const unsigned short * assigned, unsigned short count) {
  while (-- count) printf("%hu ", *(assigned ++));
  printf("%hu\n", *assigned);
}