260 lines
6.2 KiB
C
260 lines
6.2 KiB
C
#include <stdio.h>
|
|
#include <stdlib.h>
|
|
#include <time.h>
|
|
#include <string.h>
|
|
#include <ctype.h>
|
|
#include <math.h>
|
|
typedef struct {
|
|
int * at;
|
|
size_t used;
|
|
size_t size;
|
|
} array;
|
|
void arrayinit(array *a,size_t init){
|
|
a->at = malloc(init*sizeof(int));
|
|
a->used = 0;
|
|
a->size = init;
|
|
}
|
|
void arrayins(array *a, int e){
|
|
if(a->used == a->size){
|
|
a->size *= 2;
|
|
a->at = realloc(a->at, a->size * sizeof(int));
|
|
}
|
|
a->at[a->used++] = e;
|
|
}
|
|
void arraykill(array *a){
|
|
free(a->at);
|
|
a->at = NULL;
|
|
a->used = a->size = 0;
|
|
}
|
|
typedef struct {
|
|
array* at;
|
|
size_t used;
|
|
size_t size;
|
|
int valid; //make this 0 when you wanna forgor it
|
|
} matrix;
|
|
void matrixinit(matrix *m,size_t init){
|
|
m->at = malloc(init*sizeof(array));
|
|
m->used = 0;
|
|
m->size = init;
|
|
m->valid = 0;
|
|
}
|
|
void matrixins(matrix *m,array e){
|
|
if(m->used <= m->size){
|
|
m->size *= 2;
|
|
m->at = realloc(m->at,m->size*sizeof(e));
|
|
}
|
|
m->at[m->used++]=e;
|
|
}
|
|
void matrixkill(matrix*m){
|
|
for(int i = 0;i!=m->used;i++){
|
|
arraykill(&m->at[i]);
|
|
}
|
|
free(m->at);
|
|
m->at = NULL;
|
|
m->used = m->size = 0;
|
|
}
|
|
int isvalid(array a){
|
|
for(int i = 0;i!=a.used;i++){
|
|
for(int z = 0;z!=a.used;z++){
|
|
if(a.at[i]==a.at[z]&&i!=z&&a.at[i]!=0){
|
|
return 0;
|
|
}
|
|
}
|
|
}
|
|
return 1;
|
|
}
|
|
void matrixlist(matrix m){
|
|
//printf("\n~ | 0 1 2 3 4 5 6 7 8 ...\n===============================\n");
|
|
printf("\n~ | ");
|
|
for(int i = 0; i!= m.used;i++){
|
|
printf(" %i ",i);
|
|
}
|
|
printf("\n=-|-");
|
|
for(int i = 0; i!= m.used;i++){
|
|
printf("=-=");
|
|
}
|
|
printf("\n");
|
|
for(int x = 0; x!= m.used;x++){
|
|
printf("%i | ",x);
|
|
for(int y =0; y!= m.at[x].used;y++){
|
|
printf(" %i ",m.at[x].at[y]);
|
|
}
|
|
printf("\n");
|
|
}
|
|
}
|
|
void arraylist(array a){
|
|
printf("\n~ | ");
|
|
for(int x = 0; x!=a.used;x++){
|
|
printf(" %i ", a.at[x]);
|
|
}
|
|
}
|
|
int rowtocol(matrix m,int col){
|
|
for(int i = 0; i!= m.used; i++){
|
|
for(int z = 0; z!= m.used; z++){
|
|
if(m.at[i].at[col]==m.at[z].at[col]&&i!=z&&m.at[i].at[col]!=0){
|
|
return 0;
|
|
};
|
|
}
|
|
}
|
|
return 1;
|
|
}
|
|
|
|
int getsquare(matrix q, int n){//only works with 9x9 probably
|
|
int start_x,start_y;
|
|
start_x = (n%3)*3;
|
|
start_y = floor((n*0.11)*3+0.1)*3;// round((float)(n*0.11)*3+0.1);//nearbyint((n/9)*3)*3;
|
|
//int temp = round((float)(n*0.11)*3+0.1);
|
|
//printf("\n%i | %i",n,start_y);
|
|
//printf("\n--------");
|
|
//matrixlist(q);
|
|
//printf("\n%i start y:%i, start x:%i; math:%f\n",n,start_y,start_x,floor((n*0.11)*3+0.1)*3);
|
|
for(int x_1 = 0; x_1!=3; x_1++)
|
|
for(int x_2 = 0; x_2!=3; x_2++)//{
|
|
//printf("%i",q.at[x_1+start_y].at[x_2+start_x]);
|
|
for(int y_1 = 0; y_1!=3; y_1++)
|
|
for(int y_2 = 0; y_2!=3; y_2++)
|
|
if(q.at[y_1+start_y].at[x_1+start_x]==q.at[y_2+start_y].at[x_2+start_x]&&x_1!=x_2&&y_1!=y_2&&q.at[y_1+start_y].at[x_1+start_x]!=0)
|
|
return 0;
|
|
//}
|
|
return 1;
|
|
}
|
|
int isMvalid(matrix q){
|
|
for(int x = 0; x!= q.used;x++){
|
|
if(0==getsquare(q,x)||0==rowtocol(q,x)){
|
|
return 1;
|
|
}
|
|
//arraykill(&t1);
|
|
//arraykill(&t2);
|
|
}
|
|
return 0;
|
|
}
|
|
void arrayclear(array*a){
|
|
a->used=0;
|
|
a->size=1;
|
|
a->at=malloc(sizeof(int));
|
|
}
|
|
matrix bruteforce(matrix q){
|
|
|
|
matrix temp;
|
|
matrixinit(&temp,1);
|
|
array ttt;
|
|
arrayinit(&ttt,1);
|
|
for(int x = 0;x!=q.used;x++){
|
|
for(int y = 0;y!=q.at[x].used;y++){
|
|
arrayins(&ttt,q.at[x].at[y]);
|
|
}
|
|
matrixins(&temp,ttt);
|
|
arrayclear(&ttt);
|
|
|
|
}
|
|
arraykill(&ttt);
|
|
// everything before this is just to
|
|
// initialize a matrix clone so that
|
|
// the original matrix isnt effected
|
|
// and so it can refer to it later
|
|
int backtrace = 0;
|
|
// iterate through every value of matrix
|
|
// note that the second loop does not change y
|
|
for(int x = 0; x != temp.used; x++){
|
|
for(int y = 0; y!= temp.at[x].used; y=y){
|
|
if(q.at[x].at[y]==0){
|
|
if(temp.at[x].at[y]==0){
|
|
for(int z = 1; z!=temp.at[x].used+1;z++){
|
|
temp.at[x].at[y]=z;
|
|
if(isvalid(temp.at[x])==1&&isMvalid(temp)==0){
|
|
break;
|
|
}
|
|
temp.at[x].at[y]=0;
|
|
}
|
|
} else {
|
|
//go through everything after previous value
|
|
if(temp.at[x].at[y]!=9){
|
|
for(int z = temp.at[x].at[y]+1; z!=temp.at[x].used+1;z++){
|
|
temp.at[x].at[y]=z;
|
|
if(isvalid(temp.at[x])==1&&isMvalid(temp)==0){
|
|
break;
|
|
}
|
|
temp.at[x].at[y]=0;
|
|
}
|
|
} else {
|
|
temp.at[x].at[y]=0;
|
|
}
|
|
//
|
|
}
|
|
if(temp.at[x].at[y]==0){
|
|
//oh no! there arent any more valid numbers, time to backtrace more
|
|
backtrace = 1;
|
|
} else {
|
|
//seems good, continue on
|
|
backtrace = 0;
|
|
}
|
|
}
|
|
if(backtrace==0){
|
|
y++;
|
|
} else {
|
|
if(y==0){
|
|
if(x==0){
|
|
printf("\n:( cant continue; puzzle is impossible");
|
|
return temp;
|
|
}
|
|
x--;
|
|
y=8;
|
|
} else {
|
|
y--;
|
|
}
|
|
}
|
|
}
|
|
}
|
|
return temp;
|
|
}
|
|
int main( int argc, char *argv[] ) {
|
|
matrix sudoku;
|
|
matrixinit(&sudoku,9);
|
|
FILE *fp = fopen(argv[1], "r");
|
|
if(fp == NULL||argv[1] == NULL) {
|
|
perror("Unable to open provided file\nusage:\ncdoku {path of file}\ncdoku example.sudoku\n\nsee examples at https://git.disroot.org/grantsquires/cdoku\n\n raw error");
|
|
return 1;
|
|
}
|
|
|
|
char chunk[128]={};
|
|
array trow;
|
|
arrayinit(&trow,1);
|
|
while(fgets(chunk, sizeof(chunk), fp) != NULL) {
|
|
if(chunk[0]!=';'){
|
|
for(int i = 0; i!= strlen(chunk);i++){
|
|
if(chunk[i]=='\n'||trow.used==9){
|
|
break;
|
|
}
|
|
if(isdigit(chunk[i])){
|
|
arrayins(&trow,chunk[i]-'0');
|
|
}
|
|
|
|
}
|
|
matrixins(&sudoku,trow);
|
|
arrayclear(&trow);
|
|
if(sudoku.used==9)break;
|
|
}
|
|
|
|
}
|
|
/*
|
|
*everything before this is only
|
|
*to initialize the 'matrix' object as a sudoku puzzle
|
|
*that the program can read
|
|
*/
|
|
clock_t t;
|
|
t = clock();
|
|
matrix brc = bruteforce(sudoku);
|
|
matrixlist(brc);
|
|
//for(int y = 0; y!=9;y++)
|
|
// getsquare(sudoku,y);
|
|
t = clock() - t;
|
|
double time_taken = ((double)t)/CLOCKS_PER_SEC;
|
|
printf("took %f seconds",time_taken);
|
|
matrixkill(&brc);
|
|
matrixkill(&sudoku);
|
|
arraykill(&trow);
|
|
fclose(fp);
|
|
return 0;
|
|
}
|
|
|