Question
C programming - Sodoku Solution using Backtracking --------------------------------------------------- write a program that receives from the user sodoku board dimenstion(N) (can be any number for example:
C programming - Sodoku Solution using Backtracking
---------------------------------------------------
write a program that receives from the user sodoku board dimenstion(N) (can be any number for example: 3,4,5...) [not constant we must recieve it for the user]
and after that the sodoku board (we can fill elemnt a[i][j] with numbers from 1 to N and if it doesn't flled with a number then it is 0). [recieve from the user] after this the program must check if the board has solution then to print it, if not to print (NO solution!).
the rules: 1) to fill the board with numbers from 1 to N [we can assume that the user insert correct numbers no need to check it he inserts a number more than N] 2) two identical numbers must not appear on the same row
3) two identical numbers must not appear on the same colum
4) for this solution there is no limit for two identical numbers appearing in the same sub matrix(block) (for example: id it is 9x9 sodoku then number 1 for example can appear more than once in the sub matrix 3*3) [I provided an example]
5)the programm must be effective to finish in few seconds
6) must use backtracking *please run the program before giving me the solution.
I have a code that works really good in every board , the problem is when i put 9x9 board with no solution it doesn't work(I would like from you to make it more effective)
#include
int n;
// function to print matrix void print(int a[n][n]) { printf(" Your sodoku solution is: "); int i, j; for(i=0; i // function to check if a number x can be placed at a given cell int isValid(int x, int i, int j, int a[n][n]) { int k; for(k=0; k // recursive function to solve sudoku board using backtracking int backtrack(int a[n][n], int i, int j) { // base case if(i >= n) return 1; int k, ans; // skip if the cell is filled if(a[i][j] != 0) { // move to next cell // check end of row if((j+1) >= n) ans = backtrack(a, i+1, 0); else ans = backtrack(a, i, j+1); if(ans == 1) return 1; return 0; } // try to fill the cell of a number from 1 to n for(k=1; k= n) ans = backtrack(a, i+1, 0); else ans = backtrack(a, i, j+1); if(ans == 1) return 1; // backtrack if unsuccessful a[i][j] = 0; } } // no solution found return 0 return 0; } int main() { // loop variables int i, j; // input n printf("Please enter your sodoku size:"); scanf("%d", &n); // input matrix int a[n][n]; // input the n*n matrix printf(" Please insert your sodoku board: "); for(i=0; i // call the backtracking function if(backtrack(a, 0, 0) == 1) // print solution print(a); else printf("No solution "); return 0; }
Step by Step Solution
There are 3 Steps involved in it
Step: 1
Get Instant Access to Expert-Tailored Solutions
See step-by-step solutions with expert insights and AI powered tools for academic success
Step: 2
Step: 3
Ace Your Homework with AI
Get the answers you need in no time with our AI-driven, step-by-step assistance
Get Started