Dev C%2b%2b Sudoku Code

1. Dev C 2b 2b Sudoku Codes

The code already uses std::cin for input (this is a good thing since the standard C input and output std::cin and std::cout). This is another mismatch. If using printf for ouput than use scanf for input.

Dev C 2b 2b Sudoku Codes

C++Server Side ProgrammingProgramming Suppose we have a Sudoku grid and we have to solve this famous number maze problem, Sudoku. We know that Sudoku is a 9 x 9 number grid, and the whole grid are also divided into 3 x 3 boxes There are some rules to solve the Sudoku.

• We have to use digits 1 to 9 for solving this problem.

• One digit cannot be repeated in one row, one column or in one 3 x 3 box.

Using backtracking algorithm, we will try to solve Sudoku problem. When some cell is filled with a digit, it checks whether it is valid or not. When it is not valid, it checks for other numbers. If all numbers are checked from 1-9, and no valid digit found to place, it backtracks to previous option.

So if the input is like −

The output will be −

To solve this, we will follow these steps −

• Define a method called isPresentInCol(), this will take call and num

• for each row r in the grid, do

• if grid[r, col] = num, then return true

• return false otherwise

• Define a method called isPresentInRow(), this will take row and num

• for each column c in the grid, do

• if grid[row, c] = num, then return true

• return false otherwise

• Define a method called isPresentInBox() this will take boxStartRow, boxStartCol, num

• for each row r in boxStartRow to next 3 rows, do

• for each col r in boxStartCol to next 3 columns, do

• if grid[r, c] = num, then return true

• return false otherwise

• Define a method called findEmptyPlace(), this will take row and col

• for each row r in the grid, do

• for each column c in the grid, do

• if grid[r, c] = 0, then return true

• return false

• Define a method called isValidPlace(), this will take row, col, num

• if isPresentInRow(row, num) and isPresentInCol(col, num) and isPresntInBox(row – row mod 3, col – col mod 3, num) all are false, then return true

• Define a method called solveSudoku(), this will take the grid

• if no place in the grid is empty, then return true

• for number 1 to 9, do

• if isValidPlace(row, col, number), then

• grid[row, col] := number

• if solveSudoku = true, then return true

• grid[row, col] := 0

• return false

Example (C++)

Let us see the following implementation to get a better understanding −

Output

C Source code for solving sudoku using recursion, based on http://www.geeksforgeeks.org/backtracking-set-7-suduku/
sudoku.c
 #include #defineN9 #defineUNASSIGNED0 intis_exist_row(int grid[N][N], int row, int num){ for (int col = 0; col < 9; col++) { if (grid[row][col] num) { return1; } } return0; } intis_exist_col(int grid[N][N], int col, int num) { for (int row = 0; row < 9; row++) { if (grid[row][col] num) { return1; } } return0; } intis_exist_box(int grid[N][N], int startRow, int startCol, int num) { for (int row = 0; row < 3; row++) { for (int col = 0; col < 3; col++) { if (grid[row + startRow][col + startCol] num) { return1; } } } return0; } intis_safe_num(int grid[N][N], int row, int col, int num) { return !is_exist_row(grid, row, num) && !is_exist_col(grid, col, num) && !is_exist_box(grid, row - (row % 3), col - (col %3), num); } intfind_unassigned(int grid[N][N], int *row, int *col) { for (*row = 0; *row < N; (*row)++) { for (*col = 0; *col < N; (*col)++) { if (grid[*row][*col] 0) { return1; } } } return0; } intsolve(int grid[N][N]) { int row = 0; int col = 0; if (!find_unassigned(grid, &row, &col)){ return1; } for (int num = 1; num <= N; num++ ) { if (is_safe_num(grid, row, col, num)) { grid[row][col] = num; if (solve(grid)) { return1; } grid[row][col] = UNASSIGNED; } } return0; } voidprint_grid(int grid[N][N]) { for (int row = 0; row < N; row++) { for (int col = 0; col < N; col++) { printf('%2d', grid[row][col]); } printf('n'); } } intmain() { int grid[N][N] = {{0,0,0, 0,0,3, 2,9,0}, {0,8,6, 5,0,0, 0,0,0}, {0,2,0, 0,0,1, 0,0,0}, {0,0,3, 7,0,5, 1,0,0}, {9,0,0, 0,0,0, 0,0,8}, {0,0,2, 9,0,8, 3,0,0}, {0,0,0, 4,0,0, 0,8,0}, {0,4,7, 1,0,0, 0,0,0}}; if (solve(grid)) { print_grid(grid); } else { printf('no solution'); } return0; }

commented May 11, 2018

 Hello and thanks for your great codes . I really need help I dont understand the part if (solve(grid)) in function solve :( can you please help :)

commented Jun 14, 2020

 why does find_unassigned function takes pointer as paramater ??