sudoku.c
author Markus Bröker <mbroeker@largo.dyndns.tv>
Fri, 05 Mar 2010 22:03:25 +0100
changeset 113 397270b5d21a
parent 85 9568a180fc43
child 133 f46f9606dbfb
permissions -rw-r--r--
sys/wait.h is the proper header, not wait.h committer: Markus Bröker <mbroeker@largo.homelinux.org>
Ignore whitespace changes - Everywhere: Within whitespace: At end of lines:
9
c3fecc82ade6 standard tags for git projects
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 0
diff changeset
     1
/**
77
49e0babccb23 HEADER TAGS
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 29
diff changeset
     2
 * sudoku.c
9
c3fecc82ade6 standard tags for git projects
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 0
diff changeset
     3
 * Copyright (C) 2008 Markus Broeker
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     4
 *
9
c3fecc82ade6 standard tags for git projects
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 0
diff changeset
     5
 * Sudoku - The Game
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     6
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     7
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     8
#include <stdio.h>
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
     9
#include <stdlib.h>
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    10
#include <getopt.h>
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    11
#include <string.h>
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    12
#include <errno.h>
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    13
#include <limits.h>
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    14
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    15
#ifndef DIM
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    16
#define DIM 9
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    17
#endif
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    18
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    19
#define COLORED "\e[31m"
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    20
#define FGCOLOR "\e[37m"
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    21
#define BGCOLOR "\e[40m\e[2J"
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    22
#define   RESET "\e[0m"
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    23
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    24
#define TRUE   1
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    25
#define FALSE  0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    26
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    27
#ifndef u_int
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    28
typedef unsigned int u_int;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    29
#endif
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    30
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    31
#ifndef MAX_ITERATIONS
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    32
#define MAX_ITERATIONS 10000000
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    33
#endif
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    34
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    35
struct Field {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    36
    u_int value;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    37
    int isConst;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    38
};
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    39
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    40
/* the easiest way to get statistics */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    41
static unsigned long iterations = 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    42
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    43
typedef struct Field Field;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
    44
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    45
typedef Field **Board;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    46
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    47
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    48
 * read nxn fields from commandline and store it in the Board variable
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    49
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    50
int readBoard (Board board)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    51
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    52
    int i, j;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    53
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    54
    u_int c;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    55
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    56
    for (i = 0; i < DIM; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    57
        for (j = 0; j < DIM; j++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    58
            if (scanf ("%u", &c) < 1) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    59
                fprintf (stderr, "readBoard: Not enough elements\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    60
                fprintf (stderr, "readBoard: Got %d, needed %d\n", i * DIM + j, (DIM) * (DIM));
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    61
                return FALSE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    62
            }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    63
            board[i][j].value = c;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    64
            board[i][j].isConst = (c == 0) ? 0 : 1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    65
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    66
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    67
    return TRUE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    68
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    69
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    70
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    71
 * Show the content of the Board in a human readable manner
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    72
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    73
void showBoard (Board board, int colored)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    74
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    75
    int i, j;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    76
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    77
    for (i = 0; i < DIM; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    78
        if ((i % 3) == 0)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    79
            printf ("\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    80
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    81
        for (j = 0; j < DIM; j++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    82
            if ((board[i][j].isConst && colored))
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    83
                printf ("%s%2u%s ", COLORED, board[i][j].value, FGCOLOR);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    84
            else
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    85
                printf ("%2u ", board[i][j].value);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    86
            if (((j + 1) % 3) == 0)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    87
                printf ("  ");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    88
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    89
        printf ("\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    90
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    91
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    92
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    93
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    94
 * checks for the possibility of value at board[row][col]
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    95
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    96
int check (Board board, int row, int col, u_int value)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    97
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    98
    int i, j;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
    99
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   100
    if (board[row][col].value > 0)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   101
        return FALSE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   102
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   103
    for (i = 0; i < DIM; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   104
        /*
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   105
         * check vertically
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   106
         */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   107
        if (board[row][i].value == value)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   108
            return FALSE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   109
        /*
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   110
         * check horizontally
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   111
         */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   112
        if (board[i][col].value == value)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   113
            return FALSE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   114
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   115
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   116
    /*
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   117
     * check block for unique values
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   118
     */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   119
    for (i = row - (row % 3); i < row - (row % 3) + 3; i++)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   120
        for (j = col - (col % 3); j < col - (col % 3) + 3; j++)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   121
            if (board[i][j].value == value)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   122
                return FALSE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   123
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   124
    return TRUE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   125
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   126
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   127
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   128
 * go recursive from k to DIM^2 and try to solve the puzzle
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   129
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   130
int solveBoard (Board board, int k)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   131
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   132
    u_int i;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   133
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   134
    int q;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   135
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   136
    if ((++iterations > MAX_ITERATIONS))
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   137
        return FALSE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   138
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   139
    while (k < (DIM) * (DIM) && (board[k / DIM][k % DIM].value != 0))
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   140
        k++;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   141
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   142
    if (k == (DIM) * (DIM))
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   143
        return TRUE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   144
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   145
    for (q = FALSE, i = 1; q == FALSE && i <= 9; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   146
        if (check (board, k / DIM, k % DIM, i) == TRUE) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   147
            board[k / DIM][k % DIM].value = i;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   148
            if (((DIM) * (DIM) - 1) == k)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   149
                q = TRUE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   150
            else if ((q = solveBoard (board, k + 1)) == FALSE) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   151
                board[k / DIM][k % DIM].value = 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   152
            }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   153
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   154
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   155
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   156
    return q;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   157
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   158
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   159
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   160
 * Deletes every Field of the Board (CLEANUP)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   161
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   162
void freeBoard (const Board board)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   163
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   164
    int i;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   165
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   166
    for (i = 0; i < DIM; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   167
        if (board[i] != NULL)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   168
            free (board[i]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   169
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   170
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   171
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   172
/**
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   173
 * Show plain usage screen
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   174
 */
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   175
void usage (char *name)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   176
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   177
    printf ("Usage: %s [-c] [-h]\n\n", name);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   178
    printf ("-c\t\tcolored output\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   179
    printf ("-h\t\tshows this help\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   180
    printf ("Report bugs to mbroeker@largo.homelinux.org\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   181
}
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   182
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   183
int main (int argc, char **argv)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   184
{
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   185
    Board b;
27
81a574d60c15 typo in min2time format string
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 9
diff changeset
   186
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   187
    int i;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   188
    int ret;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   189
    int colored = 0;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   190
85
9568a180fc43 [getopt]: support for long options
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 77
diff changeset
   191
    struct option options[] = {
9568a180fc43 [getopt]: support for long options
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 77
diff changeset
   192
        {"colored", 0, 0, 'c'},
9568a180fc43 [getopt]: support for long options
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 77
diff changeset
   193
        {"help", 0, 0, 'h'},
9568a180fc43 [getopt]: support for long options
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 77
diff changeset
   194
    };
9568a180fc43 [getopt]: support for long options
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 77
diff changeset
   195
9568a180fc43 [getopt]: support for long options
Markus Bröker <mbroeker@largo.dyndns.tv>
parents: 77
diff changeset
   196
    while ((i = getopt_long_only (argc, argv, "ch", options, NULL)) != -1) {
0
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   197
        switch (i) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   198
        case 'h':
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   199
            usage (argv[0]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   200
            return EXIT_SUCCESS;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   201
        case 'c':
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   202
            printf ("%s%s", BGCOLOR, FGCOLOR);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   203
            colored = 1;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   204
            break;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   205
        default:
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   206
            usage (argv[0]);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   207
            return EXIT_FAILURE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   208
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   209
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   210
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   211
    if ((DIM % 3) != 0) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   212
        fprintf (stderr, "DIM must be a multiple of 3\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   213
        fprintf (stderr, "RECOMPILE WITH -DDIM=9\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   214
        return EXIT_FAILURE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   215
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   216
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   217
    if ((b = calloc (DIM, sizeof (Field *))) == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   218
        perror ("calloc");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   219
        return EXIT_FAILURE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   220
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   221
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   222
    for (i = 0; i < DIM; i++) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   223
        if ((b[i] = malloc ((DIM * sizeof (Field)) + 1)) == NULL) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   224
            perror ("malloc");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   225
            return EXIT_FAILURE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   226
        }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   227
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   228
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   229
    printf ("Sudoku - Enter a %dx%d Matrix\n", DIM, DIM);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   230
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   231
    if (readBoard (b) == FALSE) {
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   232
        fprintf (stderr, "Input Error: Aborting\n");
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   233
        return EXIT_FAILURE;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   234
    }
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   235
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   236
    showBoard (b, colored);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   237
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   238
    if ((ret = solveBoard (b, 0)) == TRUE)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   239
        printf ("\nPuzzle solved after %lu recursions\n", iterations);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   240
    else
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   241
        printf ("\nCannot solve your puzzle after %lu recursions\n", iterations);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   242
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   243
    showBoard (b, colored);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   244
    freeBoard (b);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   245
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   246
    if (b != NULL)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   247
        free (b);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   248
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   249
    if (colored)
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   250
        printf ("%s", RESET);
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   251
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   252
    return EXIT_SUCCESS;
af501b0c1716 demos cvs copy
Markus Bröker <mbroeker@largo.dyndns.tv>
parents:
diff changeset
   253
}