Dev C%2b%2b Sudoku Code

  1. Dev C 2b 2b Sudoku Codes
  • Related Questions & Answers

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

  • Selected Reading
C++Server Side ProgrammingProgramming
Sudoku

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 −

Input

Output

C Source code for solving sudoku using recursion, based on http://www.geeksforgeeks.org/backtracking-set-7-suduku/
sudoku.c
#include<stdio.h>
#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 May 18, 2018

commented Jun 14, 2020

why does find_unassigned function takes pointer as paramater ??

Sign up for freeto join this conversation on GitHub. Already have an account? Sign in to comment
Comments are closed.