# sudoku solver help with 3x3 boxes

Page 1 of 1

## 5 Replies - 18024 Views - Last Post: 22 February 2008 - 10:13 AMRate Topic: //<![CDATA[ rating = new ipb.rating( 'topic_rate_', { url: 'http://www.dreamincode.net/forums/index.php?app=forums&module=ajax&section=topics&do=rateTopic&t=43331&amp;s=3d17f56b1bc2cd199556a07cca042a90&md5check=' + ipb.vars['secure_hash'], cur_rating: 0, rated: 0, allow_rate: 0, multi_rate: 1, show_rate_text: true } ); //]]>

### #1 stayscrisp

• フカユ

Reputation: 1029
• Posts: 4,286
• Joined: 14-February 08

# sudoku solver help with 3x3 boxes

Posted 14 February 2008 - 07:20 PM

hi i am currently working on a sudoku solver which is a basic brute force method, i will post my code but i think where im having trouble is the 3x3 box checking function which is called BadBox() i have got this code working on a 4x4 grid and just cant seem to get it right with a 9x9 any help on this function would be greatly appreciated

```#include <iostream>

// Print out a 4x4 grid using one loop, from 0 to 15
void PrintGrid(int squares[])
{
int num = 0;
for (int i = 0; i < 81; i++)
{
std::cout << squares[i] << " ";
num++;
if (num == 9)
{
std::cout << "\n";
num = 0;
}
}
}

// Print out the 4x4 grid but using 2 nested loops.
// This does the same as the function above - it's just a slightly different
//  way of doing it.
void PrintNested(int squares[])
{
// Nested loop
int num = 0;
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
std::cout << squares[num] << " ";
num++;
}
std::cout << "\n";
}
}

// Check if we have a Bad Column: if any square in the same column as squareNum
//  contains the same value as squareNum, this column is bad, because it has the
//  same number in it more than once.
{
int top = squareNum % 9;
for (int i = 0; i < 9; i++)
{
// Don't check squareNum with itself! If the 'top' square number is the same
//  as squareNum, just go on to the next square.
if (top == squareNum)
{
top += 9;
continue;
}

if (solution[top] == solution[squareNum])
{
return true;
}
top += 9;
}
return false;
}

// Check if we have a bad row: if any square in the same row as squareNum contains
//  the same value as in squareNum, this is a bad row.
{
int left = (squareNum / 9) * 9;
for (int i = 0; i < 9; i++)
{
// Same as for BadColumn(), we don't want to check squareNum against itself.
if (left == squareNum)
{
left++;
continue;
}

if (solution[left] == solution[squareNum])
{
return true;
}
left++;
}
return false;
}

// Check if a 2x2 box is bad
{
// Get the top-left position: either 0 or 8
int topLeft = (squareNum / 27) * 27;
// Now add 2 if the box is to the right - so we now have a top-left position
//  of 0, 2, 8 or 10.
if ((squareNum % 9) > 1)
{
topLeft += 3;
}
else
{
if ((squareNum % 9) > 4)
{
topLeft += 3;
}
}

// Count through the 4 squares in the box
for (int i = 0; i < 9; i++)
{
// Again, we don't want to test squareNum against itself.
// This time we are not using continue, for some exciting variety.
if (topLeft != squareNum)
{
if (solution[topLeft] == solution[squareNum])
{
return true;
}
}

// Slightly more complicated than for row and column, we add 3 to the topLef square
//  if i is 1, to go the leftmost square of the next row in the box.
if (i == 1)
{
topLeft += 4;
}
else
{
topLeft++;
}
}
return false;
}

// Check if a square is bad: it is bad if we have a duplicate in the row, column or box
//  that squareNum occupies.
{
{
return true;
}
{
return true;
}
{
return true;
}
// Column, Row and Box are all good - so this is NOT a bad square.
return false;
}

// Check if we have found a solution for a sudoku.
// The way this works is: we check each square. If all the squares are 'good' we have
//  solved the puzzle.
// A good square means it does not have a duplicated value in the same row, column or
//  box.
bool IsSolved(int solution[])
{
// Check every square. For a 4x4 sudoku, that means 16 squares, right?!
for (int i = 0; i < 81; i++)
{
// If we find a bad square, the puzzle is not solved.
{
return false;
}
}
// No bad squares - the puzzle is solved!
return true;
}

// Test function: work out if a grid has a valid puzzle solution in it.
// We can use this to make sure IsSolved() works as we want it to.
void Test(int grid[])
{
if (IsSolved(grid))
{
std::cout << "This is a good solution:\n";
}
else
{
std::cout << "This is a bad solution:\n";
}
PrintGrid(grid);
}

int main()
{
// Test our IsSolved() function by testing a good puzzle solution, and a
// This gives us some confidence but the best way to check it is to step
//  through the code - we did this in class and found bugs!
int good[] =
{
9, 6, 1, 5, 4, 8, 2, 7, 3,
8, 7, 2, 9, 3, 1, 6, 4, 5,
4, 5, 3, 6, 2, 7, 8, 9, 1,
5, 4, 9, 3, 8, 2, 1, 6, 7,
2, 8, 6, 7, 1, 5, 4, 3, 9,
1, 3, 7, 4, 9, 6, 5, 8, 2,
6, 9, 4, 1, 5, 3, 7, 2, 8,
3, 2, 5, 8, 7, 4, 9, 1, 6,
7, 1, 8, 2, 6, 9, 3, 5, 4

};
// Test the good puzzle - we expect Test() to say that this is a good solution.
Test(good);

{
1, 2, 3, 4, 5, 6, 7, 8, 9,
3, 1, 2, 3, 3, 4, 5, 6, 9,
4, 4, 4, 2, 4, 5, 6, 7, 9,
2, 3, 1, 1, 6, 7, 7, 8, 9,
3, 4, 1, 2, 3, 4, 5, 6, 9,
1, 2, 3, 4, 5, 6, 7, 8, 9,
1, 2, 3, 4, 5, 6, 7, 8, 9,
1, 2, 3, 4, 5, 6, 7, 8, 9,
1, 2, 3, 4, 5, 6, 7, 8, 9,
};
// Test the bad puzzle - we expect Test() to say that this is a bad solution.

}

```

sorry most of the comments are from my 4x4 version but they should still be of some help.
so at the moment it doesnt actually solve the sudoku for you, it is simply trying out wether or not it recognises when the puzzle is solved or not and as you see the good grid i have is definetley a valid sudoku. once this is working i can get onto the rest of my code

This post has been edited by stayscrisp: 14 February 2008 - 08:22 PM

Is This A Good Question/Topic? 0

## Replies To: sudoku solver help with 3x3 boxes

### #2 Nykc

• Gentleman of Leisure

Reputation: 736
• Posts: 8,646
• Joined: 14-September 07

## Re: sudoku solver help with 3x3 boxes

Posted 16 February 2008 - 09:17 PM

I personally can't help with this question but I think I can guide you.

In the tutorials section there are some sudoku tutorials. Check them out, they might help you find the answer as well.

### #3 NickDMax

Reputation: 2254
• Posts: 9,245
• Joined: 18-February 07

## Re: sudoku solver help with 3x3 boxes

Posted 16 February 2008 - 10:37 PM

might I also suggest searching the forum for "sodoku solver" this a very common assignment.

So this BadBox function takes in a squareNum (0-80) and the grid. Then it calculates the topleft corner for the given 3x3 square that the box is in.

So (squareNum/27)*27 tells you (in the world of the 3x3 boxes) which row the squareNum is in.

now I don't understand your logic to finish the topleft calculation.

so let say:

majorRow = (squareNum / 27) -- the 3x3 row (0-2)
majorColoum = ((squareNum % 9) /3) - the 3x3 column (0-2)

so the topLeft square for the 3x3 box would be:

topLeft = majorRow * 27 + majorCol * 3;

### #4 stayscrisp

• フカユ

Reputation: 1029
• Posts: 4,286
• Joined: 14-February 08

## Re: sudoku solver help with 3x3 boxes

Posted 17 February 2008 - 04:47 PM

I have worked it out after much testing, but thanks for the help anyway guys
heres the finished boxCheck Function a lot better and works like a charm

```#
// Check if a 2x2 box is bad
#
#
{
#
//get row and col or requested square
#
int row = (int)(squareNum / 9);
#
int col = squareNum % 9;
#
//get the topleft square in the box
#
int topLeft = (row - row%3)*9 + (col - col%3);
#

#
// Count through the 9 squares in the box
#
int curSquare = topLeft;
#
for (int i = 0; i < 9; i++)
#
{
#
// Again, we don't want to test squareNum against itself.
#
// This time we are not using continue, for some exciting variety.
#
if (curSquare != squareNum)
#
{
#
if (solution[curSquare] == solution[squareNum])
#
{
#
return true;
#
}
#
}
#

#
//go to the next square in the box. If i is at the border of the 3x3
#
//box, bump up the curSquare to the next line (add 9 and subtract the
#
#
if (i % 3 == 2)
#
curSquare += 7;
#
else
#
curSquare++;
#

#
}
#
return false;
#
}

```

This post has been edited by stayscrisp: 18 February 2008 - 01:14 PM

### #5 selloorhari

Reputation: 5
• Posts: 68
• Joined: 07-February 08

## Re: sudoku solver help with 3x3 boxes

Posted 22 February 2008 - 04:59 AM

For my personal Interest, I am asking this question...

What is the mode of your input?
Is it
• By Row-wise
• By Column- wise
• By Block-wise

I am doing a SUDOKU Checker in C..
(i.e) A solved sudoku is my input.
My program is to check Whether the input is Correct or not!!!
Ok. For this I have to check it by row-wise,column-wise as well as block-wise..
The row-wise& Column-wise checking are working properly..
But I failed in the block-wise checking..

So can you help me in block-wise checking!!!

### #6 stayscrisp

• フカユ

Reputation: 1029
• Posts: 4,286
• Joined: 14-February 08

## Re: sudoku solver help with 3x3 boxes

Posted 22 February 2008 - 10:13 AM

Ok well first of all how does your input work, is it inputted using a text file or is it using arrays? arrays i can help with.

ok so if your using arrays such as a [9][9] then it is relatively simple,

start off with your print grid function which prints out the array and can have parameters sent

```void PrintGrid(int squares[])

{

int num = 0;

for (int i = 0; i < 81; i++)

{

std::cout << squares[i] << " ";

num++;

if (num == 9)

{

std::cout << "\n";

num = 0;

}

}

}

```

then declare and define your Column and row checking functions

then comes the tricky part, but also the part that will give you the most satisfaction once you solve, i will point you in the right direction, think of it as rows and columns of 3 so say that the row is squareNumber /9 and that the column is squareNumber %9; now think about how to work out the top left of a certain box, ooo tricky then you need a loop which checks through this box from the top left so you wont want it to go further than the row of the box, add 7 and youll be at the next row, get what i mean, or you could just copy my code if you want

Page 1 of 1

 .related ul { list-style-type: circle; font-size: 12px; font-weight: bold; } .related li { margin-bottom: 5px; background-position: left 7px !important; margin-left: -35px; } .related h2 { font-size: 18px; font-weight: bold; } .related a { color: blue; }