sudoku solver Algorithm
The Sudoku Solver Algorithm is an advanced technique designed to solve Sudoku puzzles by implementing various logical strategies and computational methods. It aims to find the correct numerical sequence for each row, column, and 3x3 grid in the puzzle without violating the basic rules of Sudoku. The algorithm is capable of solving puzzles of varying difficulty levels, from simple to highly complex ones. The core idea behind this algorithm is to use a combination of logic-based techniques, such as naked singles, hidden singles, locked candidates, and more, along with backtracking, which is a form of trial-and-error, to deduce the correct values for each cell in the puzzle.
One of the most popular techniques used in the Sudoku Solver Algorithm is backtracking, which involves placing a number in a cell and then proceeding to the next cell to place another number. If the algorithm reaches a point where the current number cannot be placed without violating the puzzle's rules, it will backtrack to the previous cell and try a different number. This process continues until the solution is found or all possibilities are exhausted. Another essential aspect of the algorithm is the elimination method, which systematically narrows down the possible values for each cell by examining the numbers present in the corresponding row, column, and 3x3 grid. By combining these techniques, the Sudoku Solver Algorithm can efficiently solve even the most challenging puzzles, making it a valuable tool for both casual players and competitive Sudoku enthusiasts.
//recursion problem : Sudoku Solver
/*You are given an incomplete N*N Sudoku and asked to solve it using the following recursive algorithm:
(1) Scan the Sudoku from left to right row-wise to search for an empty cell.
(2) If there are no empty cells, print the Sudoku. Go to step 5.
(3) In the empty cell, try putting numbers 1 to N while ensuring that no two numbers in a single row, column, or box are same. Go back to step 1.
(4) Declare that the Sudoku is Invalid.
(5) Exit.*/
#include <stdio.h>
const int M=144;
int N, R, C;
int OKrow(int a[M], int x, int y, int v) {
int j;
for(j=0; j<N; j++)
if(a[x*N+j] == v)
return 0;
return 1;
}
int OKcol(int a[M], int x, int y, int v) {
int i;
for(i=0; i<N; i++)
if(a[i*N+y] == v)
return 0;
return 1;
}
int OKbox(int a[M], int x, int y, int v) {
int bi=x/R, bj=y/C, i, j;
for(i=0; i<R; i++)
for(j=0; j<C; j++)
if(a[(i + bi*R)*N + (j + bj*C)] == v)
return 0;
return 1;
}
int OK(int a[M], int x, int y, int v) {
return OKrow(a,x,y,v) && OKcol(a,x,y,v) && OKbox(a,x,y,v);
}
void print(int a[M]) {
int i, j;
for(i=0; i<N; i++)
for(j=0; j<N; j++)
printf("%d%c", a[i*N+j], (j==N-1 ? '\n':' '));
}
int solve(int a[M]) {
int i, j, v, rem=0;
for(i=0; i<N; i++) {
for(j=0; j<N; j++) {
if(a[i*N+j] == 0) {
rem = 1;
for(v=1; v<=N; v++) {
if(OK(a,i,j,v)) {
a[i*N+j] = v;
if(solve(a)) return 1;
a[i*N+j] = 0;
}
}
}
}
}
if(rem == 0) return 1;
return 0;
}
int main() {
scanf("%d%d%d", &N, &R, &C);
int a[M], i, j;
for(i=0; i<N; i++)
for(j=0; j<N; j++)
scanf("%d", &a[i*N+j]);
if(solve(a)) print(a);
else printf("Invalid\n");
return 0;
}
