/*
Sudokusc v. 1.0.0
Copyright (C) 2005 AMARILLI Antoine
Sudokusc is the light and fast text-based Sudoku solver.
This program is free software; you can redistribute it and/or modify
it under the terms of the GNU General Public License as published by
the Free Software Foundation; either version 2 of the License, or
(at your option) any later version.
This program is distributed in the hope that it will be useful, but
WITHOUT ANY WARRANTY; without even the implied warranty of
MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the GNU
General Public License for more details.
You should have received a copy of the GNU General Public License
along with this program; if not, write to the Free Software
Foundation, Inc., 51 Franklin Street, Fifth Floor, Boston, MA
02110-1301, USA.
Todo list :
- Nicer frontend.
- n-dimension grid processing, with the ability to change n without
recompiling.
- Progress indicator.
- Command-line options.
- Linux intergration.
- Performance improvments.
Version history :
- 0.1.0
- More comments.
- 0.1.1
- Major optimisations.
- Start of migration towards a preprocessor-based constant to
indicate dimension.
- 0.1.2
- Minor adjustments to improve code clarity.
- 0.1.3
- Removed register optimisations, that should be applied by the
compiler.
- 0.1.4
- Moved main() to the file's beginning.
- Changed formatting (tabs are now replaced by two spaces).
- Turned grid into a global.
- Changed logical approach : firstempyty now scans for empty
squares and store their positions and number into the "empty"
array, to avoid searching for them at each iteration.
- Using DIM constant ; the program is able to process grids
of various dimensions after recompiling.
- 1.0.0
- GNU GPL licensing.
- Removed globals, creating them in main() and passing pointers
to functions which require access to them.
- Debug : the program can now handle full grids without segfault.
*/
#include
#include
#include
#include
#include
/*
The grid's dimension (width of a square).
Warning : DIM^4 should fit in an int. If not, errors may
appear. To avoid this, please change the appropriate types if
required.
*/
#define DIM 3
/* Function initialisation */
int fill(int grid[DIM*DIM][DIM*DIM], int[2], int[DIM*DIM+1]);
int firstempty(int[DIM*DIM][DIM*DIM], int[DIM*DIM*DIM*DIM][2], int *);
int solve(int[DIM*DIM][DIM*DIM], int[DIM*DIM*DIM*DIM][2], int);
int solution(int[DIM*DIM][DIM*DIM]);
int main(int argc, char *argv[])
{
/*
The grid to solve. Each cell of the grid's value is stored in the
grid[x][y] int (the appropriate number, 0 if the cell is empty),
with x and y the position of the cell (from the top left corner).
*/
int grid[DIM*DIM][DIM*DIM];
/*
The positions of the empty squares to be filled by the
program. The array's size is not optimal but will always be large
enough.
The array's first dimension is the empty cell's number, the second
dimensions used to store both the X (index 0) and Y (index 1)
positions.
*/
int empty[DIM*DIM*DIM*DIM][2];
/*
The number of empty squares (number of elements in the "empty"
array.
*/
int empties = 0;
printf("Please enter the grid you wish to solve \n");
printf("Separate each digit by enter \n");
printf("Enter 0 for empty squares \n");
/*
Grid input
*/
int i, j, ret;
for(i=0;i=0;i--)
{
for(j=(DIM*DIM)-1;j>=0;j--)
{
/* Goes through the grid */
if (!grid[i][j])
{
/* If the square is empty, store its position */
empty[*empties][0] = i;
empty[*empties][1] = j;
(*empties)++;
}
}
}
return 0;
}
int solve(int grid[DIM*DIM][DIM*DIM], int empty[DIM*DIM*DIM*DIM][2], int empties)
{
/*
Sudoku solving function.
Looks at the empty square of index "depht" in "empty".
Fills it with each of the possible values given by the fill()
function.
Calls herself for each possible completition.
Calls solution() if all squares are filled ("empties", which
indicates the number of cells remaining, will be at 0).
*/
int i, ret;
int fills[DIM*DIM+1];
/*
Decrement the "empties" to avoid using the first available index
as an actual position
*/
empties--;
/* Search for possible matches */
fill(grid, (int *) empty[empties], (int *) &fills);
/* For each number */
for(i=1;i