303 lines
7.1 KiB
C
303 lines
7.1 KiB
C
/* Su Doku (Japanese meaning number place) is the name given to a popular puzzle concept. Its origin is unclear,
|
|
* but credit must be attributed to Leonhard Euler who invented a similar, and much more difficult, puzzle idea called Latin Squares.
|
|
* The objective of Su Doku puzzles, however, is to replace the blanks (or zeros) in a 9 by 9 grid in such that each row, column,
|
|
* and 3 by 3 box contains each of the digits 1 to 9. Below is an example of a typical starting puzzle grid and its solution grid.
|
|
*
|
|
* 0 0 3 0 2 0 6 0 0 4 8 3 9 2 1 6 5 7
|
|
* 9 0 0 3 0 5 0 0 1 9 6 7 3 4 5 8 2 1
|
|
* 0 0 1 8 0 6 4 0 0 2 5 1 8 7 6 4 9 3
|
|
*
|
|
* 0 0 8 1 0 2 9 0 0 5 4 8 1 3 2 9 7 6
|
|
* 7 0 0 0 0 0 0 0 8 7 2 9 5 6 4 1 3 8
|
|
* 0 0 6 7 0 8 2 0 0 1 3 6 7 9 8 2 4 5
|
|
*
|
|
* 0 0 2 6 0 9 5 0 0 3 7 2 6 8 9 5 1 4
|
|
* 8 0 0 2 0 3 0 0 9 8 1 4 2 5 3 7 6 9
|
|
* 0 0 5 0 1 0 3 0 0 6 9 5 4 1 7 3 8 2
|
|
*
|
|
* A well constructed Su Doku puzzle has a unique solution and can be solved by logic, although it may be necessary to employ
|
|
* "guess and test" methods in order to eliminate options (there is much contested opinion over this). The complexity of the search
|
|
* determines the difficulty of the puzzle; the example above is considered easy because it can be solved by straight forward direct deduction.
|
|
*
|
|
* The 6K text file, sudoku.txt, contains fifty different Su Doku puzzles ranging in difficulty, but all with unique solutions
|
|
* (the first puzzle in the file is the example above).
|
|
*
|
|
* By solving all fifty puzzles find the sum of the 3-digit numbers found in the top left corner of each solution grid;
|
|
* for example, 483 is the 3-digit number found in the top left corner of the solution grid above.*/
|
|
|
|
#define _POSIX_C_SOURCE 199309L
|
|
|
|
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <time.h>
|
|
|
|
int solve_sudoku(int grid[][9]);
|
|
int solve_recursive(int grid[][9], int step);
|
|
int check(int grid[][9], int i, int j, int n);
|
|
|
|
int main(int argc, char **argv)
|
|
{
|
|
char dummy[10], dummy_c;
|
|
int i, j, sum = 0, partial;
|
|
int grid[9][9];
|
|
double elapsed;
|
|
struct timespec start, end;
|
|
FILE *fp;
|
|
|
|
clock_gettime(CLOCK_MONOTONIC, &start);
|
|
|
|
if((fp = fopen("sudoku.txt", "r")) == NULL)
|
|
{
|
|
fprintf(stderr, "Error while opening file %s\n", "sudoku.txt");
|
|
return 1;
|
|
}
|
|
|
|
while(!feof(fp))
|
|
{
|
|
fgets(dummy, sizeof(dummy), fp);
|
|
|
|
for(i = 0; i < 9; i++)
|
|
{
|
|
for(j = 0; j < 9; j++)
|
|
{
|
|
fscanf(fp, "%c", &dummy_c);
|
|
grid[i][j] = (int)dummy_c - '0';
|
|
}
|
|
|
|
fscanf(fp, "%c", &dummy_c);
|
|
}
|
|
|
|
/* For each sudoku in the file, solve it and sum the number in the
|
|
* top left corner to the total.*/
|
|
if(!solve_sudoku(grid))
|
|
{
|
|
printf("Bad sudoku grid\n");
|
|
return 1;
|
|
}
|
|
|
|
partial = grid[0][0] * 100 + grid[0][1] * 10 + grid[0][2];
|
|
sum += partial;
|
|
}
|
|
|
|
fclose(fp);
|
|
|
|
clock_gettime(CLOCK_MONOTONIC, &end);
|
|
|
|
elapsed = (end.tv_sec - start.tv_sec) + (double)(end.tv_nsec - start.tv_nsec) / 1000000000;
|
|
|
|
printf("Project Euler, Problem 96\n");
|
|
printf("Answer: %d\n", sum);
|
|
|
|
printf("Elapsed time: %.9lf seconds\n", elapsed);
|
|
|
|
return 0;
|
|
}
|
|
|
|
int check(int grid[][9], int i, int j, int n)
|
|
{
|
|
int k, w, ii, jj;
|
|
|
|
for(k = 0; k < 9; k++)
|
|
{
|
|
if(k != j && grid[i][k] == n)
|
|
{
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
for(k = 0; k < 9; k++)
|
|
{
|
|
if(k != i && grid[k][j] == n)
|
|
{
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
ii = 3 * (i / 3);
|
|
jj = 3 * (j / 3);
|
|
|
|
for(k = 0; k < 3; k++)
|
|
{
|
|
for(w = 0; w < 3; w++)
|
|
{
|
|
if(ii + k != i && jj + w != j && grid[ii+k][jj+w] == n)
|
|
{
|
|
return 0;
|
|
}
|
|
}
|
|
}
|
|
|
|
return 1;
|
|
}
|
|
|
|
int solve_recursive(int grid[][9], int step)
|
|
{
|
|
int i, j, k;
|
|
|
|
if(step == 81)
|
|
{
|
|
return 1;
|
|
}
|
|
|
|
i = step / 9;
|
|
j = step % 9;
|
|
|
|
if(grid[i][j] != 0)
|
|
{
|
|
if(solve_recursive(grid, step+1))
|
|
{
|
|
return 1;
|
|
}
|
|
}
|
|
else
|
|
{
|
|
for(k = 1; k <= 9; k++)
|
|
{
|
|
grid[i][j] = k;
|
|
|
|
if(check(grid, i, j, k))
|
|
{
|
|
if(solve_recursive(grid, step+1))
|
|
{
|
|
return 1;
|
|
}
|
|
|
|
grid[i][j] = 0;
|
|
}
|
|
}
|
|
|
|
grid[i][j] = 0;
|
|
}
|
|
|
|
return 0;
|
|
}
|
|
|
|
int line_complete(int grid[][9], int i)
|
|
{
|
|
int n;
|
|
|
|
for(n = 0; n < 9; n++)
|
|
{
|
|
if(grid[i][n] == 0)
|
|
{
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
return 1;
|
|
}
|
|
|
|
int column_complete(int grid[][9], int j)
|
|
{
|
|
int n;
|
|
|
|
for(n = 0; n < 9; n++)
|
|
{
|
|
if(grid[n][j] == 0)
|
|
{
|
|
return 0;
|
|
}
|
|
}
|
|
|
|
return 1;
|
|
}
|
|
|
|
int solve_sudoku(int grid[][9])
|
|
{
|
|
int i, j, k, w, count, val;
|
|
|
|
for(w = 0; w < 4; w++)
|
|
{
|
|
for(i = 0; i < 9; i++)
|
|
{
|
|
for(j = 0; j < 9; j++)
|
|
{
|
|
if(grid[i][j] == 0)
|
|
{
|
|
count = 0;
|
|
|
|
for(k = 1; k <= 9 && count < 2; k++)
|
|
{
|
|
grid[i][j] = k;
|
|
|
|
if(check(grid, i, j, k) == 1)
|
|
{
|
|
count++;
|
|
val = k;
|
|
}
|
|
}
|
|
|
|
if(count == 1)
|
|
{
|
|
grid[i][j] = val;
|
|
}
|
|
else
|
|
{
|
|
grid[i][j] = 0;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
for(i = 0; i < 9; i++)
|
|
{
|
|
for(k = 1; k <= 9 && !line_complete(grid, i); k++)
|
|
{
|
|
count = 0;
|
|
|
|
for(j = 0; j < 9 && count < 2; j++)
|
|
{
|
|
if(grid[i][j] == 0)
|
|
{
|
|
grid[i][j] = k;
|
|
|
|
if(check(grid, i, j, k))
|
|
{
|
|
count++;
|
|
val = j;
|
|
}
|
|
|
|
grid[i][j] = 0;
|
|
}
|
|
}
|
|
|
|
if(count == 1)
|
|
{
|
|
grid[i][val] = k;
|
|
}
|
|
}
|
|
}
|
|
|
|
for(j = 0; j < 9; j++)
|
|
{
|
|
for(k = 1; k <= 9 && !column_complete(grid, j); k++)
|
|
{
|
|
count = 0;
|
|
|
|
for(i = 0; i < 9 && count < 2; i++)
|
|
{
|
|
if(grid[i][j] == 0)
|
|
{
|
|
grid[i][j] = k;
|
|
|
|
if(check(grid, i, j, k))
|
|
{
|
|
count++;
|
|
val = i;
|
|
}
|
|
|
|
grid[i][j] = 0;
|
|
}
|
|
}
|
|
|
|
if(count == 1)
|
|
{
|
|
grid[val][j] = k;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
|
|
return solve_recursive(grid, 0);
|
|
}
|