/*
 * sudoku.c - Generate random Suduko puzzles
 *
 * This code will create random Sudoku puzzles.
 * The algorithms used in this code heavily favor simplicity over
 * speed.  There are many obvious ways the performance of this code
 * can be improved, some fairly trivial.
 * 
 * Copyright (c) 2006 Nathan Kennedy
 *
 * Redistribution and use in source and binary forms, with or without
 * modification, are permitted provided that the following conditions
 * are met:
 * 1. Redistributions of source code must retain the above copyright
 *    notice and this list of conditions.
 * 2. Redistributions in binary form must reproduce the above copyright
 *    notice and this list of conditions in the documentation and/or
 *    materials provided with the distribution.
 */

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

/* Assigns shuffled integers from 1-9 to beginning of array p */
void
rand9(int *p)
{
  int i, j, t;
  for (i=1;i<10;i++)  /* initialize array 1-9 */
    p[i-1] = i;
  for (i=0;i<9;i++)  /* swap each element with another random element */
    {
      j=random()%9;
      t = p[i];
      p[i] = p[j];
      p[j] = t;
    }
}

/* same procedure for integers 0-80 */
void
rand81(int *p)
{
  int i, j, t;
  for (i=0;i<81;i++)
    p[i] = i;
  for (i=0;i<81;i++)
    {
      j=random()%81;
      t = p[i];
      p[i] = p[j];
      p[j] = t;
    }
}

/* check if number c is a valid addition to sudoku grid at positio n */
int
valid(int *grid, int n, int c)
{
  int i, j;

  /* check for doubles in column */
  for (i=0;i<9;i++)
    if (i != n/9)
      if (grid[i*9 + n%9] == c)
	return 0;

  /* check for doubles in row */
  for (i=0;i<9;i++)
    if (i != n%9)
      if (grid[n - (n%9) + i] == c)
	return 0;

  /* check for doubles in small square */
  for (i=0;i<3;i++)
    for (j=0;j<3;j++)
      if (n/9/3*3*9 + n%9/3*3 + i*9 + j != n)
	if (grid[n/9/3*3*9 + n%9/3*3 + i*9 + j] == c)
	  return 0;

  return 1;
}

/* recursive function to fill in a square */
int
*assign(int *grid, int n)
{
  int candidate[9];
  int *newgrid;
  int *candgrid;
  int i;

  /* get random list of integers 1-9 */
  rand9(candidate);

  i=0;
  /* if this is the last square ... */
  if (n == 80)
    {
      /* try candidates until one works */
      while (!valid(grid, n, candidate[i]) && i<9)
	i++;
      /* if none work, return 0--bad grid */
      if (i==9)
	return 0;
      /* otherwise fill it in */
      grid[80] = candidate[i];
      return grid;
    }

  while (i<9)
    {
      /* for each candidate, check if it is a valid addition */
      if (valid(grid, n, candidate[i]))
	{
	  /* create new grid with candidate filled in */
	  newgrid = (int *)malloc(sizeof(int)*81);
	  if (newgrid == 0)
	    {
	      printf ("out of mem\n");
	      exit(1);
	    }
	  memcpy(newgrid, grid, sizeof(int)*81);
	  newgrid[n] = candidate[i];
	  /* run recursive function on grid with candidate added */
	  candgrid = assign(newgrid, n+1);
	  /* if it worked, return this grid */
	  if (candgrid != 0)
	    return candgrid;
	  free(newgrid);
	}
      i++;
    }

  /* this shouldn't happen--no grid could be created */
  return 0;
}

/* recursive function tries to solve an incomplete grid, returns 0
 * if no solution, (unsolvable grid), 1 if exactly one solution,
 * (good sudoku grid), 2 if more than one solution (ambiguous grid) */
int
solvegrid(int *grid)
{
  int *newgrid;
  int i, j, k;

  /* find first blank square */
  i=0;
  while (i<81 && grid[i])
    i++;
  if (i==81)  /* if no blank squares, grid is solved */
    return 1;

  /* allocate a new grid */
  newgrid = malloc(sizeof(int)*81);
  if (newgrid == 0)
    {
      printf ("out of mem\n");
      exit(1);
    }
  memcpy(newgrid,grid,sizeof(int)*81);
  k = 0;
  /* loop through numbers 1 to 9 */
  for (j=1;j<10;j++)
    {
      /* check if number fits on grid according to rules */
      if (valid(grid, i, j))
	{
	  /* if so, add to grid */
	  newgrid[i] = j;
	  k += solvegrid(newgrid);  /* get number of solutions of new grid */
	  if (k == 2)
	    {
	      free(newgrid);  /* grid is ambiguous, bail out */
	      return 2;
	    }
	}
    }
  free(newgrid);
  return k;      /* return number of solutions, 0 or 1--should never be 0 */
}

/* make a puzzle out of a solution grid, by removing squares in
 * random order, until no further squares can be removed without
 * making puzzle ambiguous */
void
makepuzzle(int *grid, int *puzgrid)
{
  int cand[81];
  int i, t;

  rand81(cand); /* get random ordering of squares to blot out */
  memcpy(puzgrid, grid, sizeof(int)*81); /* copy grid */
  puzgrid[cand[0]] = 0;  /* block out first square--can always do this */
  /* loop through the rest of the squares */
  for (i=1;i<81;i++)
    {
      t = puzgrid[cand[i]];  /* blot out square */
      puzgrid[cand[i]] = 0;
      if (solvegrid(puzgrid) != 1) /* replace square if now ambiguous */
	puzgrid[cand[i]] = t;
    }
}

/* print a grid */
void
printgrid(int *grid)
{
  int i;

  for (i=1;i<82;i++)
    {
      if (grid[i-1])
	printf("%d ",grid[i-1]);
      else
	printf("_ ");
      if (i%9==0)
	printf("\n");
    }
}

int
main()
{
  int grid[81];
  int puzgrid[81];
  int *newgrid;
  int i;

  printf("Setting up solution grid...\n");
  srandom(time(0));

  for (i=0;i<81;i++)
    grid[i] = 0;

  rand9(grid);

  newgrid = assign(grid, 9);

  printf("Solution grid:\n");
  printgrid(newgrid);
  printf("Creating puzzle from solution grid...\n");
  makepuzzle(newgrid, puzgrid);
  printf("Puzzle:\n");
  printgrid(puzgrid);

  return 0;
}