OpenVMS Source Code Demos
sudoku
//===========================================================================
// title : sudoku.c ( Dec 6, 2011 )
// Author : Ricardo Garcia Gonzalez. ( https://github.com/rg3/sudoku )
// purpose: A simple command-line Sudoku solver in C for educational purposes
// limit : currently limited to Sudoku 3x3 but can be enlarged (see below)
//============================================================================
// OpenVMS Instructions ( Mar 12, 2018 )
// editor : Neil Rieck, Waterloo, Ontario, Canada (verified on Itanium2)
// machine: OpenVMS-8.4 on Itanium2 (rx2800-i2)
// DCL Build $cc sudoku.c ! compile
// $link sudoku ! link
// DCL Run $yada = f$environment("default") ! find local path
// $sudoku := $'yada'sudoku ! create foreign cmd
// $sudoku sudoku99.txt ! solve puzzle-file-99
//============================================================================
// contents of file: sudoku98.txt (solvable)
/* ------
53..7....
6..195...
.98....6.
8...6...3
4..8.3..1
7...2...6
.6....28.
...419..5
....8..79
-------*/
//=============================================================================
// contents of file: sudoku99.txt (solvable)
/* ------
.4..2....
....964.2
.63...7..
.9.......
12.....89
.......2.
..7...86.
3.641....
....8..3.
-------*/
//=============================================================================
// contents of file: sudoku90.txt (solvable)
/* ------
.........
.........
.........
.........
.........
.........
.........
.........
.........
-------*/
//=============================================================================
#define __NEW_STARLET 1 // enable strict for OpenVMS 7.0 and later
#include <assert.h>
#include <ctype.h>
#include <stdio.h>
#include <stdlib.h>
#define SUBDIMENSION (3)
#define MIN_NUM (1)
#define MAX_NUM (9)
#define TOTAL_NUMS (9)
#define ARRAY_SIZE (MIN_NUM + TOTAL_NUMS)
#ifdef ASSERT
#define assert_(A) assert(A)
#else
#define assert_(A)
#endif
long tries = 0; // for hacking
/*
*
* CANDIDATES.
*
*/
/*
* A candidates array represents which values have already been used for a row,
* column or square.
*/
typedef int candidates[ARRAY_SIZE];
/*
* All candidates start as unused.
*/
void init_candidates(candidates *c)
{
int i;
for (i = MIN_NUM; i <= MAX_NUM; ++i)
(*c)[i] = 0;
}
/*
* Using a candidate number means marking it as used in the array.
*/
void use_candidate(candidates *cp, int num)
{
assert_(cp != NULL && num >= MIN_NUM && num <= MAX_NUM);
(*cp)[num] = 1;
}
/*
* Restoring a candidate means marking it as unused in the array.
*/
void restore_candidate(candidates *cp, int num)
{
assert_(cp != NULL && num >= MIN_NUM && num <= MAX_NUM);
(*cp)[num] = 0;
}
/*
*
* CELLS AND BOARDS.
*
*/
/*
* A cell has a flag to indicate if its value has been set or not, the cell
* value and three pointers to candidate arrays. One for the row it belongs to,
* one for the column it belongs to and one for the square it belongs to.
*/
struct cell {
int has_value;
int value;
candidates *row_candidates;
candidates *col_candidates;
candidates *square_candidates;
};
/*
* A board has a number of unset cells, a matrix of cells and the candidate
* arrays for each row, column and square in the board.
*/
struct board {
int unset_cells;
struct cell cells[ARRAY_SIZE][ARRAY_SIZE];
candidates rows[ARRAY_SIZE];
candidates columns[ARRAY_SIZE];
candidates squares[ARRAY_SIZE];
};
/*
* Auxiliar. Calculates the square number for the given cell. Squares are
* numberd from top to bottom, left to right.
*/
int square(int row, int col)
{
assert_(row >= MIN_NUM && row <= MAX_NUM &&
col >= MIN_NUM && col <= MAX_NUM);
return (((row - 1) / SUBDIMENSION) * SUBDIMENSION) +
((col - 1) / SUBDIMENSION) + 1;
}
/*
* Every board starts empty. Cell candidate pointers are established.
*/
void init_board(struct board *b)
{
int i;
int j;
assert_(b != NULL);
b->unset_cells = TOTAL_NUMS * TOTAL_NUMS;
for (i = MIN_NUM; i <= MAX_NUM; ++i) {
init_candidates(b->rows + i);
init_candidates(b->columns + i);
init_candidates(b->squares + i);
for (j = MIN_NUM; j <= MAX_NUM; ++j) {
b->cells[i][j].has_value = 0;
b->cells[i][j].value = 0;
b->cells[i][j].row_candidates = b->rows + i;
b->cells[i][j].col_candidates = b->columns + j;
b->cells[i][j].square_candidates = b->squares + square(i, j);
}
}
}
/*
* Finds the lowest candidate number which is free in all arrays, having a
* value greater or equal to the "atleast" argument.
*/
int find_common_free(candidates *r, candidates *c, candidates *s, int atleast)
{
assert_(r != NULL && c != NULL && s != NULL);
int i;
for (i = atleast; i <= MAX_NUM; ++i)
if ((! (*r)[i]) && (! (*c)[i]) && (! (*s)[i]))
return i;
return (-1);
}
/*
* Sets a cell value in the given board.
*/
void set_cell(struct board *b, int r, int c, int val)
{
assert_(b != NULL &&
r >= MIN_NUM && r <= MAX_NUM &&
c >= MIN_NUM && c <= MAX_NUM &&
val >= MIN_NUM && val <= MAX_NUM);
assert_((! (*(b->cells[r][c].row_candidates))[val]) &&
(! (*(b->cells[r][c].col_candidates))[val]) &&
(! (*(b->cells[r][c].square_candidates))[val]));
b->unset_cells -= 1;
b->cells[r][c].has_value = 1;
b->cells[r][c].value = val;
use_candidate(b->cells[r][c].row_candidates, val);
use_candidate(b->cells[r][c].col_candidates, val);
use_candidate(b->cells[r][c].square_candidates, val);
}
/*
* Unsets a cell value in the given board.
*/
void unset_cell(struct board *b, int r, int c, int val)
{
assert_(b != NULL &&
r >= MIN_NUM && r <= MAX_NUM &&
c >= MIN_NUM && c <= MAX_NUM &&
val >= MIN_NUM && val <= MAX_NUM);
assert_((*(b->cells[r][c].row_candidates))[val] &&
(*(b->cells[r][c].col_candidates))[val] &&
(*(b->cells[r][c].square_candidates))[val]);
b->unset_cells += 1;
b->cells[r][c].has_value = 0;
b->cells[r][c].value = 0;
restore_candidate(b->cells[r][c].row_candidates, val);
restore_candidate(b->cells[r][c].col_candidates, val);
restore_candidate(b->cells[r][c].square_candidates, val);
}
/*
* Checks if a cell value is set. Returns 1 if set, 0 otherwise.
*/
int is_set(struct board *b, int r, int c)
{
assert_(b != NULL &&
r >= MIN_NUM && r <= MAX_NUM &&
c >= MIN_NUM && c <= MAX_NUM);
return (b->cells[r][c].has_value);
}
/*
* Calculates the number following a given one circularly.
*/
int following(int num)
{
assert_(num >= MIN_NUM && num <= MAX_NUM);
return ((num - MIN_NUM + 1) % TOTAL_NUMS + MIN_NUM);
}
/*
* Calculates the cell following a given one. Advances from top to bottom and
* left to right. Returns 0 if there is no next cell, 1 otherwise and modifies
* the arguments to point to the next cell in that case.
*/
int next_cell(int *r, int *c)
{
assert_(r != NULL && c != NULL);
if ((*r) == MAX_NUM && (*c) == MAX_NUM)
return 0;
*c = following(*c);
if ((*c) == MIN_NUM)
(*r) = following(*r);
return 1;
}
/*
* Prints the given board on screen.
*/
void print_board(struct board *b)
{
int i;
int j;
assert_(b != NULL);
for (i = MIN_NUM; i <= MAX_NUM; ++i) {
for (j = MIN_NUM; j <= MAX_NUM; ++j)
printf(" %d", b->cells[i][j].value);
printf("\n");
}
}
//
// Solves a board starting with the given cell.
// Note: recursion happens here
// Return: 1=solved
// 0=unsolvable
//
int solve_board(struct board *b, int r, int c)
{
int prev;
int val;
//
tries++;
assert_(b != NULL &&
r >= MIN_NUM && r <= MAX_NUM &&
c >= MIN_NUM && c <= MAX_NUM);
/* Base case: board solved, print it. */
if (b->unset_cells == 0) {
print_board(b);
return 1;
}
/* Find the next unset cell. */
while (is_set(b, r, c) && next_cell(&r, &c))
;
/* This should never happen. */
if (is_set(b, r, c))
return 1;
/* Try every possible cell value until the board can be solved. */
prev = MIN_NUM;
while (1) {
val = find_common_free(b->cells[r][c].row_candidates,
b->cells[r][c].col_candidates,
b->cells[r][c].square_candidates,
prev);
if (val == -1)
break;
set_cell(b, r, c, val);
if (solve_board(b, r, c))
return 1;
unset_cell(b, r, c, val);
prev = val+1;
}
return 0;
}
/*
* Reads a board from the given file. Format: a digit represents a cell value,
* a dot represents an empty cell. Cells should be given from top to bottom and
* left to right. All other characters are ignored.
*
* Example:
*
* 5 3 . . 7 . . . .
* 6 . . 1 9 5 . . .
* . 9 8 . . . . 6 .
* 8 . . . 6 . . . 3
* 4 . . 8 . 3 . . 1
* 7 . . . 2 . . . 6
* . 6 . . . . 2 8 .
* . . . 4 1 9 . . 5
* . . . . 8 . . 7 9
*
*/
void read_board(FILE *f, struct board *b)
{
int row;
int col;
int c;
assert_(f != NULL && b != NULL);
row = MIN_NUM;
col = MIN_NUM;
while (! feof(f)) {
c = fgetc(f);
if ((isdigit(c) && c != '0') || c == '.') {
if (c != '.')
set_cell(b, row, col, (c - '0'));
if (! next_cell(&row, &col))
break;
}
}
}
//===========================================================================
//
// MAIN
//
//===========================================================================
int main(int argc, char *argv[]) {
FILE *in;
struct board b;
int ret;
//
printf("\n-i-pgm:%s\n",argv[0]);
//
// process command-line args
//
if (argc > 2) {
fprintf(stderr, "ERROR: too many arguments\n");
fprintf(stderr, "-i-usage: sudoku [ puzzle99.txt ]\n");
return 1;
}
if (argc == 2) {
in = fopen(argv[1], "r");
if (in == NULL) {
fprintf(stderr, "ERROR: could not open \"%s\"\n", argv[1]);
return 2;
}
} else {
fprintf(stderr, " usage: sudoku [ puzzle99.txt ]\n");
printf("-w-no filename argument provided so expecting keyboard data\n");
//
// obviously this help is only valid when we have a 3x3 board
//
printf("-i-type (or paste) 81 characters on one line\n");
printf(" or 9 rows of 9 characters like this example:\n");
printf(".4..2....\n");
printf("....964.2\n");
printf(".63...7..\n");
printf(".9.......\n");
printf("12.....89\n");
printf(".......2.\n");
printf("..7...86.\n");
printf("3.641....\n");
printf("....8..3.\n");
printf("-i-start typing now (or control-c to abort)\n");
in = stdin;
}
//
// Initialize data structures
//
init_board(&b);
//
// read data onto board
//
read_board(in, &b);
fclose(in);
//
// solve board if possible
//
printf("-i-processing...\n");
ret = solve_board(&b, MIN_NUM, MIN_NUM);
printf("-i-tries: %ld\n",tries);
if (! ret)
fprintf(stderr, "ERROR: board could not be solved\n");
//
// exit: 0 (error)
// 3 (success)
//
return (ret?0:3);
}
Back to HomeNeil Rieck
Waterloo, Ontario, Canada.