Scribd
Upload
186 views

Source Code For Sudoku Solver

This document contains the code for a Sudoku solver program. It includes function definitions for printing the Sudoku puzzle, finding empty cells, checking if a number can be used in a cell, and recursively solving the puzzle. The main function initializes an example puzzle grid, prints it, calls the solving function and prints the solved grid if a solution is found or reports no solution exists.

Uploaded by

api-292892066
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
186 views

Source Code For Sudoku Solver

This document contains the code for a Sudoku solver program. It includes function definitions for printing the Sudoku puzzle, finding empty cells, checking if a number can be used in a cell, and recursively solving the puzzle. The main function initializes an example puzzle grid, prints it, calls the solving function and prints the solved grid if a solution is found or reports no solution exists.

Uploaded by

api-292892066
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 3

#include <stdio.

h>
#include <iostream>
#include <stdlib.h>
#include <time.h>
using namespace std;
// for ease: global variables
const int empty = 0;
// what an empty cell counts as
const int N = 9;
// side length of puzzle
// function prototypes:
// prints the puzzle to the console;
void printPuzzle(unsigned int puzzle[N][N]);
// finds next available empty cell
bool findEmptyCell(unsigned int puzzle[N][N], unsigned int &row, unsigned int &col);
// checks if guess is acceptable
bool okayNumberToUse(unsigned int puzzle[N][N], unsigned int row, unsigned int col,
unsigned int num);
// the actual solving algorithm
bool SolveSudoku(unsigned int puzzle[N][N]);

int main(){
// 0 means empty cell
unsigned int puzzle[N][N] = {
{ 0, 9, 0, 0, 4, 0, 0,
{ 3, 0, 0, 7, 0, 5, 0,
{ 0, 0, 6, 0, 0, 0, 5,
{ 0, 3, 0, 0, 9, 0, 0,
{ 6, 0, 0, 4, 0, 2, 0,
{ 0, 5, 0, 0, 3, 0, 0,
{ 0, 0, 2, 0, 0, 0, 7,
{ 1, 0, 0, 9, 0, 6, 0,
{ 0, 8, 0, 0, 2, 0, 0,

8,
0,
0,
1,
0,
4,
0,
0,
6,

0
4
0
0
3
0
0
8
0

},
},
},
},
},
},
},
},
} };

printPuzzle(puzzle);
if (SolveSudoku(puzzle)){
printPuzzle(puzzle);
} // end if (SolveSudoku(puzzle))
else{
printf("No solution exists\n");
} // end else if (SolveSudoku(puzzle))
return 0;
} // end int main()

void printPuzzle(unsigned int puzzle[N][N]){


cout << "\n\t-------------------------" << endl;
for (int row = 0; row < N; row++)
{
cout << "\t";
if (row == 3 || row == 6){
cout << "--------+-------+--------" << endl << "\t";
} // end if (row == 3 || row == 6)
for (int col = 0; col < N; col++){
if (col == 0 || col == 3 || col == 6){
cout << "| ";
} // end if (col == 0 || col == 3 || col == 6)
if (puzzle[row][col] != 0){
cout << puzzle[row][col] << " ";
} // end if (puzzle[row][col] != 0)
else{
cout << "_ ";
} // end else if (puzzle[row][col] != 0)
if (col == 8){
cout << "|";
} // end if (col == 8)
} // end for(int col = 0; col < N; col++)
cout << endl;
} // end for(int row = 0; row < N; row++)
cout << "\t-------------------------" << endl;
cout << endl;
} // end void printPuzzle(unsigned int puzzle[N][N])
bool SolveSudoku(unsigned int puzzle[N][N]){
unsigned int row, col;
// 1. find an empty cell
//
-- if there isn't one, we've solved the puzzle
if (!findEmptyCell(puzzle, row, col)){
return true; // success!
} // end if (!findEmptyCell(puzzle, row, col))
for (int num = 1; num <= N; num++){
// the number "num" is a valid guess
if (okayNumberToUse(puzzle, row, col, num)){
// assign num to the empty cell
puzzle[row][col] = num;
// assume this guess is correct
if (SolveSudoku(puzzle)){
return true;
} // end if (SolveSudoku(puzzle))
else{
// if this guess doesn't branch into a correct solution
// backtrack
puzzle[row][col] = empty;
} // end else if (SolveSudoku(puzzle))
} // end if (okayNumberToUse(puzzle, row, col, num))
} // end for (int num = 1; num <= N; num++)
// enables back tracking when the
// search tree reaches the end of a branch.
return false;
} // end bool SolveSudoku(unsigned int puzzle[N][N])]

bool findEmptyCell(unsigned int puzzle[N][N], unsigned int &row, unsigned int &col){
for (row = 0; row < N; row++){
for (col = 0; col < N; col++){
if (puzzle[row][col] == empty){
return true;
} // end if (puzzle[row][col] == empty)
} // end for (col = 0; col < N; col++)
} // end for (row = 0; row < N; row++)
return false;
} // end bool findEmptyCell(unsigned int puzzle[N][N], unsigned int &row, unsigned int
&col)
bool okayNumberToUse(unsigned int puzzle[N][N], unsigned int row, unsigned int col,
unsigned int num){
// check cells row and column;
for (int idx = 0; idx < N; idx++){
if (puzzle[row][idx] == num || puzzle[idx][col] == num){
return false;
} // end if (puzzle[row][idx] == num || puzzle[idx][col] == num)
} // end for (int idx = 0; idx < N; idx++)

// find which box it's in.


int sqrtN = sqrt(N);
int boxRowStart = row - row % sqrtN;
int boxColStart = col - col % sqrtN;
// check the box
for (int rowcheck = boxRowStart; rowcheck < boxRowStart + 3; rowcheck++){
for (int colcheck = boxColStart; colcheck < boxColStart + 3; colcheck++){
if (puzzle[rowcheck][colcheck] == num){
return false;
} // end if (puzzle[rowcheck][colcheck] == num)
} // end for (int colcheck = boxColStart; colcheck < boxColStart + 3;
colcheck++)
} // for (int rowcheck = boxRowStart; rowcheck < boxRowStart + 3; rowcheck++)
return true;
} // end bool okayNumberToUse(unsigned int puzzle[N][N], unsigned int row, unsigned int
col, unsigned int num)

You might also like