/*------------------------------------------------------------------------------
 * problem013.c: Sudoku solver
**----------------------------------------------------------------------------*/

/* Copyright (c) 2009 Peter Bui. All Rights Reserved.
 *
 * Peter Bui <pbui@cse.nd.edu>
 *
**------------------------------------------------------------------------------
 * Includes
**----------------------------------------------------------------------------*/

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

/*------------------------------------------------------------------------------
 * Constants
**----------------------------------------------------------------------------*/

#define TRUE	    1
#define FALSE	    0

#define NDIGITS	    9
#define BLK_ROWS    3
#define	BLK_COLS    3

/*------------------------------------------------------------------------------
 * Data Structures
**----------------------------------------------------------------------------*/

typedef int Board[NDIGITS][NDIGITS];

/*------------------------------------------------------------------------------
 * Functions
**----------------------------------------------------------------------------*/

static int
read_board(Board b)
{
    int r, c, digit;

    memset(b, 0, sizeof(int) * NDIGITS * NDIGITS);

    for (r = 0; r < NDIGITS; r++) {
	for (c = 0; c < NDIGITS; c++) {
	    if (scanf("%d", &digit) == EOF)
		return (FALSE);
	    b[r][c] = digit;
	}
    }

    return (TRUE);
}

/*----------------------------------------------------------------------------*/

static int
check_digit(Board b, int r, int c, int d)
{
    int rr, cc, rb, cb;
   
    for (cc = 0; cc < NDIGITS; cc++)
	if (b[r][cc] == d) 
	    return (FALSE);

    for (rr = 0; rr < NDIGITS; rr++)
	if (b[rr][c] == d) 
	    return (FALSE);

    rb = (r / BLK_ROWS)*BLK_ROWS;
    cb = (c / BLK_COLS)*BLK_COLS;
    for (rr = 0; rr < BLK_ROWS; rr++)
	for (cc = 0; cc < BLK_COLS; cc++)
	    if (b[rb + rr][cb + cc] == d)
		return (FALSE);
    
    b[r][c] = d;
    return (TRUE);
}

/*----------------------------------------------------------------------------*/

static int
place_digit(Board b, int i)
{
    int d, r, c;

    if (i == (NDIGITS * NDIGITS))
	return (TRUE);

    r = i / NDIGITS;
    c = i % NDIGITS;

    if (b[r][c] == 0) {
	for (d = 1; d <= NDIGITS; d++) 
	    if (check_digit(b, r, c, d) && place_digit(b, i + 1))
		return (TRUE);

	b[r][c] = 0;
	return (FALSE);
    }

    return (place_digit(b, i + 1));
}

/*----------------------------------------------------------------------------*/

static void
solve_board(Board b)
{
    place_digit(b, 0);
}

/*----------------------------------------------------------------------------*/

static void
print_board(Board b)
{
    int r, c;

    for (r = 0; r < NDIGITS; r++) {
	printf("%d", b[r][0]);
	for (c = 1; c < NDIGITS; c++) 
	    printf(" %d", b[r][c]);
	putchar('\n');
    }
}

/*------------------------------------------------------------------------------
 * Main Execution
**----------------------------------------------------------------------------*/

int
main(int argc, char* argv[]) 
{
    Board b;
    int first_pass = TRUE;

    while (read_board(b)) {
	if (!first_pass) putchar('\n');

	solve_board(b);
	print_board(b);

	first_pass = FALSE;
    }

    return (EXIT_SUCCESS);
}

/*------------------------------------------------------------------------------
 * vim: sts=4 sw=4 ts=8 ft=cpp
**----------------------------------------------------------------------------*/