The objective of Sudoku is to fill every square in the game board (see below) su
ID: 3884873 • Letter: T
Question
The objective of Sudoku is to fill every square in the game board (see below) such the final game state meets the following constraints: 1. For an n^2 times n^2 board, every cell must contain a number between 1 and n2 (inclusive). For example, in the 9 times 9 board below, every cell must contain a value between 1 and 9. 2. Every row must contain only unique values. In other words, there can only be one of each value in a row. 3. Every column must contain only unique values. 4. Every inner n times n board delineated by bold bordering must contain only unique values. 5. You must work around the starting values in the board (see below). These problem relates to a 4 times 4 Sudoku puzzle. The idea is to complete a 4 x 4 matrix, subdivided into 4 blocks of size 2 times 2 each, in such a way that meets the constraints of a Sudoku puzzle listed above. Considering this problem as a CSP with 16 variables X_i, j with 1 lessthanorequalto i, j lessthanorequalto 4, answer the following questions. Variable X_i, j will hold the value of cell (i, j) in the 4 times 4 board. So if the value of for the cell on the second row, third column is 1, we write X_2, 3 = 1. (a) What is the domain of each of the variables? (b) Write constraints representing that each number appears in the same row exactly once. You may use quantifiers in your answer. (c) Write constraints representing that each number appears in the same column exactly once. You may use quantifiers in your answer. (d) Write constraints representing that each number appears in the same block exactly once. You may use quantifiers in your answer. (e) Write constraints representing that every row has to have all the elements of {1, 2, 3, 4}. You may use quantifiers in your answer. (f) Write constraints representing that every column has to have all the elements of {1, 2, 3, 4}. You may use quantifiers in your answer. (g) Write constraints representing that every block has to have all the elements of {1, 2, 3, 4}. You may use quantifiers in your answer. (h) Are constraints (e)-(g) needed if constraints (b)-(d) are satisfied? Explain your answer.Explanation / Answer
program:
program to solve sudoku puzzle in c for solving 9x9 sudoku by backtracking. the cells which are empty should be represented with 0.
#include<stdio.h>
int a[9][9];
void sudoku(int,int);
int check(int element,int r,int c){
for(int i=0;i<9;i++)
if(a[i][c]==element)
return 0;
for(int i=0;i<9;i++)
if(a[r][i]==element)
return 0;
int r1 = r - (r%3);
int c1 = c - (c%3);
for(int i=r1;i<r1+3;i++)
for(int j=c1;j<c1+3;j++)
if(a[i][j]==element)
return 0;
return 1;
}
void navigate(int r,int c){
if(c<8)
sudoku(r,c+1);
else
sudoku(r+1,0);
}
void display(){
printf("Solved Suduko");
for(int i=0;i<9;i++){
printf(" ");
for(int j=0;j<9;j++)
printf("%d ",a[i][j]);
}
}
void sudoku(int r,int c){
if(r>8)
display();
if(a[r][c]!=0)
navigate(r,c);
else{
for(int k=1;k<=9;k++){
if(check(k,r,c)==1){
a[r][c] = k;
navigate(r,c);
}
a[r][c] = 0;
}
}
}
void main(){
printf("enter numbers in sudoku");
for(int i=0;i<9;i++)
for(int j=0;j<9;j++)
scanf("%d",&a[i][j]);
sudoku(0,0);
}
(1)
domain of the variable is given by {1,n}
(2)
for(int i=0;i<9;i++)
if(a[i][c]==element)
return 0;
this is the condition for checking if the row has same element. If the number is already present we conclude that the number cannot be placed.
(3)
for(int i=0;i<9;i++)
if(a[r][i]==element)
return 0;
this is the condition for checking if the column has same element. If the number is already present we conclude that the number cannot be placed.
(4)
int r1 = r - (r%3);
int c1 = c - (c%3);
for(int i=r1;i<r1+3;i++)
for(int j=c1;j<c1+3;j++)
if(a[i][j]==element)
return 0;
this is the condition for checking if the block has same element. If the number is already present we conclude that the number cannot be placed.
(H)
the other 3 constarints are not necessary because if the above 3 conditions are satisfied the remaining values are also satisfied.
if we consider a row as we cannot insert a number twice we have only possibility of inserting all the numbers from 1-n in n places of a row