A 9×9 sudoku solver in C. The algorithm incorporates backtracking. Backtracking is a great technique to use when the problem is NP complete and the state space isn’t huge. It takes only a few seconds to solve a hard 9×9 sudoku puzzle on a 1.4GHz machine. The program in txt can be found here. Sadly I can only upload image files so the file is a PDF.
The program first reads in the sudoku puzzle from a file named “myfile.txt”. The algorithm begins by recursively fills up the puzzle, and if no feasible input can be found for an empty block before a solution is reached, it returns to the previous empty block and attempts with another feasible input. The heuristic is very straighforward, it just ensures the input does not appear in the same row, the same column, and the same square.
An important lesson I learnt after is that for NP complete problems, if brute force isn’t working, that’s because you’re not using enough, or you just need more hardware.
#1 by joxi on November 22, 2007 - 1:19 am
very thx for this code. useful!
#2 by Brandon on January 26, 2008 - 9:40 pm
The code is helpful for a class I am taking to get the idea of backtracking to solve NP problems. However I don’t know if this is a problem or not, but I attempted to give it a puzzle to complete and it was unable to do so. It was capable of placing 6 digits in locations but only 3 of which are in correct locations. Any suggestions?
#3 by Fazlay Rabbi on March 17, 2008 - 7:19 pm
Thanx for your code. It helps me to solve the 8 queens problem and gives me the implementation of backtracking.
#4 by nadia on April 18, 2008 - 8:35 am
#include
//#include
//#include
int i,j,k,a[10,10],o,x[100],y[100];
void display();
int getnum();
void solve(int [],int [],int);
int check(int ,int );
void main()
{
clrscr();
printf(“\n\nEnter the elements of SUDOKU in rowwise.\n[ Enter '0' if element is absent. ]“);
for(i=1;i<=9;i++)
for(j=1;j<=9;j++)
scanf(“%d”,&a[i][j]);
printf(“\n\nEntered SUDOKU\n\n”);
display();
printf(“\nEnter any key for solution….\n”);
getch();
o=getnum();
solve(x,y,1);
}
int getnum()
{
int c=0;
for(i=1;i<=9;i++)
{
for(j=1;j<=9;j++)
{
if(a[i][j]==0)
{
c++;
x[c]=i;
y[c]=j;
}
}
}
return(c);
}
void display()
{
for(i=1;i<=9;i++)
{
for(j=1;j<=9;j++)
{
if(a[i][j]!=0)
printf(” %d”,a[i][j]);
else
printf(” “);
}
printf(“\n\n”);
}
}
void solve(int p[100],int q[100],int n)
{
for(k=1;k<=9;k++)
for(i=p[n];i<=p[n];i++)
for(j=q[n];j<=q[n];j++)
{
a[i][j]=k;
if(n<0)
solve(p,q,n++);
int ch=check(1,0);
if(ch!=0)
{
display();
getch();
//exit(0);
}
}
}
}
int check(int n,int r)
{
int f=0,cont=0;
if(r==1)
{
for(k=1;k<=9;k++)
{
for(i=n;i<=n;i++)
for(j=1;j<=9;j++)
{
if(k==a[i][j])
f++;
}
if(f!=1)
return(0);
else
cont++;
f=0;
}
if(cont!=9)
return(0);
else if(n==9)
check(1,0);
else
check(n++,1);
}
else
{
for(k=1;k<=9;k++)
{
for(i=1;i<=9;i++)
for(j=n;j<=n;j++)
{
if(k==a[i][j])
f++;
}
if(f!=1)
return(0);
else
cont++;
f=0;
}
if(cont!=9)
return(0);
else if(n!=9)
check(n++,1);
}
}
#5 by oduikq bqjkl on July 10, 2008 - 1:03 am
ofxkq diyonfuk jlxmikzen xbspjnmv velqdg lemu dnqohguxt
#6 by george on February 6, 2009 - 6:19 pm
Your “input_value” can definitely be waaay simpler.
Try something like this:
/*Returns 1 if n is allowed in position [a,b] of sudoku[9][9]
and 0 if not*/
int can_put_n_here(int n, int sdku[][9] ,int a, int b)
{
int i;
for(i=0; i<9; ++i){
if(sdku[a][i]==n || sdku[i][b]==n || sdku[3*(a/3)][3*(b/3)+9*(i/3)+(i % 3)]==n)
return(0);
}
return(1);
}
For a given n, a and b and for a given 9X9 matrix sdku,
it checks if n is allowed to be put in the position[a][b].
If it is, it returns 1. If it is not, it returns 0.
#7 by Boss Resurfacing on September 6, 2009 - 9:00 pm
Off topic – Help with PM?
lost password
Boss Resurfacing
Boss Resurfacing
#8 by narendra umate on April 23, 2010 - 4:45 pm
[compact code for input_value]
int input_value(int ipos,int jpos,int value)
{
for(int k=0;k<9;k++)
if(outputArray[k][jpos]==value||outputArray[ipos][k]==value)
return 0;
int istart=(ipos/3)*3;
int jstart=(jpos/3)*3;
for(int i=istart;i<istart+3;i++)
for(int j=jstart;j<jstart+3;j++)
if(outputArray[i][j]==value)
return 0;
return value;
}
[also insert 'return 0;' before 2nd end bracket of the function backtrack]
saying this because my code worked well on ubuntu gcc but solaris was acting funny. so adding insert 0 explicitly does not hurt at all.
great code by the way helped me a lot. thanks
#9 by Anand on September 30, 2010 - 6:59 pm
I am unable to find the source code. Would you please let me know where the code is?
#10 by vital on December 15, 2010 - 7:13 am
just click on “here” in the text…
… The program in txt can be found –>here<– …
#11 by Me on January 14, 2011 - 4:37 am
How can i see the code? Clicking on “here”… doesn`t work..
#12 by Cyrus on April 4, 2011 - 10:15 am
//
// The following code is public domain (written in 2005 by Nick Smallbone)
// It can be found at http://www.8325.org/sudoku/
//
// It works by keeping track of which numbers can be used to fill the remaining
// cells in each row, column and block. It then will only fill a cell with a
// number that is valid for that row, column and block.
// On every recursion, it chooses the cell with the least possible number
// available to choose from. This has the rather nice effect that impossible
// cells are noticed straight away without any special cases, and cells with
// only one possibility are filled in straight away.
#include
#include
using namespace std;
FILE*input;
input=fopen(“input.txt”,”r”);
while((fscanf(input,”%d”,&ary[i])) !=EOF){
printf(“%d “,ary[i]);
i++ ;
}
// The size of the Sudoku game
static const unsigned blockSize = 3;
static const unsigned gridSize = blockSize * blockSize;
//
// Some functions for representing sets as bitfields
// (counting from 0)
//
typedef unsigned long bitfield;
// No bit we’ll be using is above this
static const bitfield maskMax = 1 << gridSize;
// A bitfield with all bits set
static const bitfield allSet = maskMax – 1;
// Returns the size of the set
static unsigned bitCount(bitfield bits) {
unsigned result = 0;
bitfield mask = 1;
while(mask != maskMax) {
if (bits & mask)
result++;
mask *= 2;
}
return result;
}
// Returns a bitfield representing {num}
static inline bitfield bitFor(unsigned num) {
return 1 << (num – 1);
}
class Puzzle {
// The value of any empty cell (i, j) comes from
// rows[i] & cols[j] & blocks[i/3][j/3]
bitfield rows[gridSize];
bitfield cols[gridSize];
bitfield blocks[blockSize][blockSize];
// This contains invalid if the cell is empty,
// its value otherwise.
unsigned cells[gridSize][gridSize];
public:
// This number is invalid, and represents an empty cell
static const unsigned invalid = gridSize + 1;
Puzzle() {
// Better initialise the arrays
unsigned i, j;
for (i = 0; i < gridSize; i++) rows[i] = allSet;
for (i = 0; i < gridSize; i++) cols[i] = allSet;
for (i = 0; i < blockSize; i++)
for (j = 0; j < blockSize; j++)
blocks[i][j] = allSet;
for (i = 0; i < gridSize; i++)
for (j = 0; j < gridSize; j++)
cells[i][j] = invalid;
}
// Return the set of values which could be at (i, j)
inline bitfield candidates(unsigned i, unsigned j) {
assert(cells[i][j] == invalid);
return rows[i] & cols[j] &
blocks[i/blockSize][j/blockSize];
}
// Fill in the cell at (i, j)
inline void set(unsigned i, unsigned j, unsigned n) {
bitfield bit = bitFor(n);
// Check this is a valid value for the cell
assert((candidates(i, j) & bit) != 0);
// No other cells in the row, column or block
// can now have this value
rows[i] &= ~bit;
cols[j] &= ~bit;
blocks[i/blockSize][j/blockSize] &= ~bit;
cells[i][j] = n;
}
// Erase the cell at (i, j)
inline void unset(unsigned i, unsigned j, unsigned n) {
bitfield bit = bitFor(n);
// Make sure it was already set
assert(cells[i][j] == n);
rows[i] |= bit;
cols[j] |= bit;
blocks[i/blockSize][j/blockSize] |= bit;
cells[i][j] = invalid;
}
// Find the cell with the lowest number of candidates
// in the specified rectangular area.
// It searches in iMin <= i < iMax
// and jMin <= j < jMax
// Return false if the grid is full.
bool findMin(unsigned iMin, unsigned iMax, unsigned jMin, unsigned jMax,
unsigned &outI, unsigned &outJ)
{
bool found = false;
unsigned count = 0;
for (unsigned i = iMin; i < iMax; i++)
for (unsigned j = jMin; j < jMax; j++)
if (cells[i][j] == invalid &&
(!found || bitCount(candidates(i, j)) < count))
{
count = bitCount(candidates(i, j));
outI = i;
outJ = j;
found = true;
}
return found;
}
// Returns the value of a certain cell, or invalid
inline unsigned getCell(unsigned i, unsigned j) { return cells[i][j]; }
};
// Tries to solve the puzzle in-place. It returns true if it could fill in
// all the squares between iMin and iMax and jMin and jMax, false otherwise.
// If destructive is false it will reverse all its changes once it
// finds a solution or gives up.
// If checkBlocks is true it will try to fill in each 3×3 block separately
// before it starts – if it can't do that then it can't solve the puzzle
bool solve(Puzzle &puzzle, unsigned iMin, unsigned iMax,
unsigned jMin, unsigned jMax, bool destructive, bool checkBlocks)
{
// Check that each block can be filled if we've been asked to
if (checkBlocks) {
for (unsigned i = 0; i < blockSize; i++)
for (unsigned j = 0; j < blockSize; j++)
if (!solve(puzzle,
i*blockSize, i*blockSize + blockSize,
j*blockSize, j*blockSize + blockSize,
false, false))
return false;
}
// Guess a good cell to brute-force with
unsigned i;
unsigned j;
if (!puzzle.findMin(iMin, iMax, jMin, jMax, i, j))
// We must have finished
return true;
// Iterate through the possible values this cell could have
unsigned num = 1;
unsigned mask = bitFor(num);
while(mask != maskMax) {
if (puzzle.candidates(i, j) & mask) {
// Try this number
puzzle.set(i, j, num);
bool solved = (solve(puzzle, iMin, iMax, jMin, jMax,
destructive, checkBlocks));
// Reverse the changes if needed
if (!solved || !destructive)
puzzle.unset(i, j, num);
if (solved)
return true;
}
// Advance to the next number
mask *= 2;
num++;
}
// None of the possibilities for cell (i,j) work
return false;
}
// Reads in a puzzle from standard input
void readPuzzle(Puzzle &p) {
for (unsigned i = 0; i < gridSize; i++) {
for (unsigned j = 0; j > c;
if (c >= ’1′ && c > endl;
}
}
// Prints out a (hopefully) completed puzzle
void printPuzzle(Puzzle &p) {
for (unsigned i = 0; i < gridSize; i++) {
for (unsigned j = 0; j < gridSize; j++) {
if (p.getCell(i, j) == p.invalid)
cout << " ";
else
cout << p.getCell(i, j);
}
cout << endl;
}
}
// Solve and print out a puzzle
void outputSolution(Puzzle &p) {
if (solve(p, 0, gridSize, 0, gridSize, true, true))
printPuzzle(p);
}
int main() {
Puzzle p;
readPuzzle(p);
outputSolution(p);
system ("pause");
return 0;
}
Does anyone can teach me how to put file*input and how to write the code inside this program..
#13 by manik on August 17, 2011 - 6:57 am
cn u plzz explain backtrack function a bit in detail…i could not understand it…how backtracking is occuring…??
#14 by kjh on December 21, 2011 - 4:58 pm
what do i need to do if i want to chenge the range of thevalid number from 1-9 to 0-8.
#15 by Hung on May 18, 2013 - 6:22 am
Wow, fantastic blog layout! How long have you been blogging for?
you make blogging look easy. The overall look of your
web site is wonderful, let alone the content!