add rush01HEADmaster

1 files changed, 134 insertions, 0 deletions

diff --git a/rush01/code.c b/rush01/code.c
new file mode 100644
index 0000000..3e35616
--- /dev/null
+++ b/rush01/code.c
@@ -0,0 +1,134 @@
+
+
+#define SIZE 6
+
+//sudoku problem
+
+char col1up = 4, col2up = 3, col3up = 2, col4up = 1, col1down = 1, col2down = 2, col3down = 2, col4down = 2, row1left = 4, row2left = 3, row3left = 2, row4left = 1, row1right = 1, row2right = 2, row3right = 2, row4right = 2;
+
+char a = 0, b = 0, c = 0, d = 0, e = 0, f = 0, g = 0, h = 0, i = 0, j = 0, k = 0, l = 0, m = 0, n = 0, o = 0, p = 0;
+
+
+char matrix[6][6] = {
+    {0, col1up,col2up,col3up,col4up, 0},
+    {row1left,a,b,c,d,row1right},
+    {row2left,e,f,g,h,row2right},
+    {row3left,i,j,k,l,row3right},
+    {row4left,m,n,o,p,row4right},
+    {0, col1down,col2down,col3down,col4down, 0},
+
+
+};
+
+//function to print sudoku
+void print_sudoku()
+{
+    int i,j;
+    for(i=0;i<SIZE;i++)
+    {
+        for(j=0;j<SIZE;j++)
+        {
+            printf("%d\t",matrix[i][j]);
+        }
+        printf("\n\n");
+    }
+}
+
+//function to check if all cells are assigned or not
+//if there is any unassigned cell (cell that is set to 0)
+//then this function will change the values of
+//row and col accordingly
+int number_unassigned(int *row, int *col)
+{
+    int num_unassign = 0;
+    int i,j;
+    for(i=0;i<SIZE;i++)
+    {
+        for(j=0;j<SIZE;j++)
+        {
+            //cell is unassigned
+            if(matrix[i][j] == 0)
+            {
+                //changing the values of row and col
+                *row = i;
+                *col = j;
+                //there is one or more unassigned cells
+                num_unassign = 1;
+                return num_unassign;
+            }
+        }
+    }
+    return num_unassign;
+}
+
+//function to check if we can put a
+//value in a paticular cell or not
+int is_safe(int n, int r, int c)
+{
+    int i,j;
+    //checking in row
+    for(i=0;i<SIZE;i++)
+    {
+        //there is a cell with same value
+        if(matrix[r][i] == n)
+            return 0;
+    }
+    //checking column
+    for(i=0;i<SIZE;i++)
+    {
+        //there is a cell with the value equal to i
+        if(matrix[i][c] == n)
+            return 0;
+    }
+    //checking sub matrix
+    int row_start = (r/3)*3;
+    int col_start = (c/3)*3;
+    for(i=row_start;i<row_start+3;i++)
+    {
+        for(j=col_start;j<col_start+3;j++)
+        {
+            if(matrix[i][j]==n)
+                return 0;
+        }
+    }
+    return 1;
+}
+
+//function to solve sudoku
+//using backtracking
+int solve_sudoku()
+{
+    int row;
+    int col;
+    //if all cells are assigned then the sudoku is already solved
+    //pass by reference because number_unassigned will change the values of row and col
+    if(number_unassigned(&row, &col) == 0)
+        return 1;
+    int n,i;
+    //number between 1 to 9
+    for(i=1;i<=SIZE;i++)
+    {
+        //if we can assign i to the cell or not
+        //the cell is matrix[row][col]
+        if(is_safe(i, row, col))
+        {
+            matrix[row][col] = i;
+            //backtracking
+            if(solve_sudoku())
+                return 1;
+            //if we can't proceed with this solution
+            //reassign the cell
+            matrix[row][col]=0;
+        }
+    }
+    return 0;
+}
+
+int main()
+{
+    if (solve_sudoku())
+        print_sudoku();
+    else
+        printf("No solution\n");
+    return 0;
+}