From 3b55074fcfdaeb2b2443d249dfac031f06e32d11 Mon Sep 17 00:00:00 2001
From: azuminha <azuminha@azuminha.com>
Date: Thu, 3 Aug 2023 13:25:14 -0300
Subject: final

---
 solve.c | 82 ++++++++++++++++++++++++++++++++++++++++++++++++++++++++++-------
 1 file changed, 74 insertions(+), 8 deletions(-)

diff --git a/solve.c b/solve.c
index d1f7114..67832ab 100644
--- a/solve.c
+++ b/solve.c
@@ -4,14 +4,17 @@
 #include <stdbool.h>
 
 int** create_sudoku();
+int** read_sudoku();
 void print_sudoku(int** sudoku);
 int calculate_square(int lin, int col);
+bool solve(int ***sudoku, int lin, int col);
 
 bool lines[9][10], columns[9][10], squares[9][10]; 
 
 int main(){
-    int** sudoku = create_sudoku();
-    print_sudoku(sudoku);
+    //int** sudoku = create_sudoku();
+    int** sudoku = read_sudoku();
+    //print_sudoku(sudoku);
 
     memset(lines, 0, sizeof(lines));
     memset(columns, 0, sizeof(columns));
@@ -27,15 +30,78 @@ int main(){
             }
         }
     }
-    
+    printf("\n\n");
+    solve(&sudoku, 0, 0);
+}
+
+int** read_sudoku(){
+    int s[9][9];
+    printf("0 for the empty spaces: \n");
+    for(int i = 0; i < 9; ++i){
+        for(int j = 0; j < 9; ++j){
+            scanf("%d", &s[i][j]);
+        }
+    }
+
+    int **r = (int**)malloc(sizeof(int*)*9);
+    for(int i = 0; i < 9; ++i){
+        r[i] = (int*)malloc(sizeof(int)*9);
+
+        for(int j = 0; j < 9; ++j){
+            r[i][j] = s[i][j];
+        }
+    }
+
+    return r;
+}
+
+bool solve(int ***sudoku, int lin, int col){
+    if(col == 9){
+        print_sudoku(*sudoku);
+        return true;
+    }
+
+    if((*sudoku)[lin][col] != 0){
+        if(lin < 8){
+            if(solve(sudoku, lin+1, col)){
+                return true;
+            }
+        }
+        else {
+            if(solve(sudoku, 0, col+1)){
+                return true;
+            }
+        }
+    }else{
+        for(int i=1; i<=9; ++i){
+            if(!lines[lin][i] && !columns[col][i] && !squares[calculate_square(lin, col)][i]){
+                lines[lin][i] = true;
+                columns[col][i] = true;
+                squares[calculate_square(lin, col)][i] = true;
+                (*sudoku)[lin][col] = i;
+                
+                if(lin < 8){
+                    if(solve(sudoku, lin+1, col)){
+                        return true;
+                    }
+                }
+                else{
+                    if(solve(sudoku, 0, col+1)){
+                        return true;
+                    }
+                }
+            
+                lines[lin][i] = false;
+                columns[col][i] = false;
+                squares[calculate_square(lin, col)][i] = false;
+                (*sudoku)[lin][col] = 0;
+            }
+        }
+    }
+    return false;
 }
 
 int calculate_square(int lin, int col){
-    /*
-    0 1 2
-    3 4 5
-    6 7 8
-    */
     return (lin/3)*3 + col/3;
 }
 
-- 
cgit v1.2.3