Solve Sudoku on the basis of the given irregular regions | C ++ program for the above approach ; Grid dimension ; Function to check if the number to be present in the current cell is safe or not ; Check if the number is present in i - th row or j - th column or not ; Check if the number to be filled is safe in current region or not ; Initialize the queue for the BFS ; Insert the current cell into queue ; Check if the neighbours cell is visited or not ; Initialize visited to 0 ; Mark current cell is visited ; Performing the BFS technique Checking for 4 neighbours at a time ; Stores front element of the queue ; Pop top element of the queue ; Check for neighbours cell ; If already contains the same number ; Mark as neighbour cell as visited ; Checking for 2 nd neighbours ; If neighbours contains the same number ; Insert neighbour cell into queue ; Mark neighbour cell as visited ; Checking for 3 rd neighbours ; If neighbours contains the same number ; Insert neighbour cell into queue ; Mark neighbour cell as visited ; Checking for 4 th neighbours ; If neighbours contains the same number ; Insert neighbour cell into queue ; Mark neighbour cell as visited ; Recursive function to solve the sudoku ; If the given sudoku already solved ; Print the solution of sudoku ; If the numbers in the current row already filled ; If current cell is not empty ; Iterate over all possible value of numbers ; If placing the current number is safe in the current cell ; Update sudoku [ i ] [ j ] ; Fill the ramining cells of the sudoku ; If remaining cells has been filled ; Otherwise No Solution ; Driver Code ; Given sudoku array ; Given region array ; Function call ; No answer exist
#include <bits/stdc++.h> NEW_LINE using namespace std ; const int N = 2 ; bool issafe ( int sudoku [ N ] [ N ] , int i , int j , int n , int number , char region [ N ] [ N ] ) { for ( int x = 0 ; x < n ; x ++ ) { if ( sudoku [ x ] [ j ] == number sudoku [ i ] [ x ] == number ) { return false ; } } char r = region [ i ] [ j ] ; queue < pair < int , int > > q ; q . push ( make_pair ( i , j ) ) ; int visited [ N ] [ N ] ; memset ( visited , 0 , sizeof visited ) ; visited [ i ] [ j ] = 1 ; while ( ! q . empty ( ) ) { pair < int , int > front = q . front ( ) ; q . pop ( ) ; if ( front . first + 1 < N && region [ front . first + 1 ] [ front . second ] == r && ! visited [ front . first + 1 ] [ front . second ] ) { if ( sudoku [ front . first + 1 ] [ front . second ] == number ) { return false ; } q . push ( make_pair ( front . first + 1 , front . second ) ) ; visited [ front . first + 1 ] [ front . second ] = 1 ; } if ( front . first - 1 >= 0 && region [ front . first - 1 ] [ front . second ] == r && ! visited [ front . first - 1 ] [ front . second ] ) { if ( sudoku [ front . first - 1 ] [ front . second ] == number ) { return false ; } q . push ( make_pair ( front . first - 1 , front . second ) ) ; visited [ front . first - 1 ] [ front . second ] = 1 ; } if ( front . second + 1 < N && region [ front . first ] [ front . second + 1 ] == r && ! visited [ front . first ] [ front . second + 1 ] ) { if ( sudoku [ front . first ] [ front . second + 1 ] == number ) { return false ; } q . push ( make_pair ( front . first , front . second + 1 ) ) ; visited [ front . first ] [ front . second + 1 ] = 1 ; } if ( front . second - 1 >= 0 && region [ front . first ] [ front . second - 1 ] == r && ! visited [ front . first ] [ front . second - 1 ] ) { if ( sudoku [ front . first ] [ front . second - 1 ] == number ) { return false ; } q . push ( make_pair ( front . first , front . second - 1 ) ) ; visited [ front . first ] [ front . second - 1 ] = 1 ; } } return true ; } bool solveSudoku ( int sudoku [ N ] [ N ] , int i , int j , int n , char region [ N ] [ N ] ) { if ( i == n ) { for ( int a = 0 ; a < n ; a ++ ) { for ( int b = 0 ; b < n ; b ++ ) { cout << sudoku [ a ] [ b ] << " ▁ " ; } cout << endl ; } return true ; } if ( j == n ) { return solveSudoku ( sudoku , i + 1 , 0 , n , region ) ; } if ( sudoku [ i ] [ j ] != 0 ) { return solveSudoku ( sudoku , i , j + 1 , n , region ) ; } else { for ( int number = 1 ; number <= n ; number ++ ) { if ( issafe ( sudoku , i , j , n , number , region ) ) { sudoku [ i ] [ j ] = number ; bool rest = solveSudoku ( sudoku , i , j + 1 , n , region ) ; if ( rest == true ) { return true ; } } } sudoku [ i ] [ j ] = 0 ; return false ; } } int main ( ) { int sudoku [ N ] [ N ] = { { 0 , 1 } , { 0 , 0 } } ; char region [ N ] [ N ] = { { ' r ' , ' r ' } , { ' b ' , ' b ' } } ; int ans = solveSudoku ( sudoku , 0 , 0 , N , region ) ; if ( ans == 0 ) { cout << " - 1" ; } return 0 ; }