sudoku solver help with 3x3 boxes

i am working on a sudoku solver and cant get the 3x3 box check to work

Page 1 of 1

5 Replies - 12522 Views - Last Post: 22 February 2008 - 10:13 AM Rate Topic: -----

#1 stayscrisp  Icon User is offline

  • フカユ
  • member icon

Reputation: 994
  • View blog
  • Posts: 4,158
  • 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.
bool BadColumn(int squareNum, int solution[])
{
	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.
bool BadRow(int squareNum, int solution[])
{
	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
bool BadBox(int squareNum, int solution[])
{
	// 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.
bool BadSquare(int squareNum, int solution[])
{
	if (BadColumn(squareNum, solution))
	{
		return true;
	}
	if (BadRow(squareNum, solution))
	{
		return true;
	}
	if (BadBox(squareNum, solution))
	{
		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.
		if (BadSquare(i, solution))
		{
			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
	//  bad solution.
	// 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);

	int bad[] = 
	{
		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.
	Test(bad);

	

}



it should return the good solution as being good and the bad as bad, but it always returns the good as bad please help :s
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  Icon User is offline

  • Gentleman of Leisure
  • member icon

Reputation: 725
  • View blog
  • Posts: 8,638
  • 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.
Was This Post Helpful? 0
  • +
  • -

#3 NickDMax  Icon User is online

  • Can grep dead trees!
  • member icon

Reputation: 2246
  • View blog
  • Posts: 9,236
  • 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;
Was This Post Helpful? 0
  • +
  • -

#4 stayscrisp  Icon User is offline

  • フカユ
  • member icon

Reputation: 994
  • View blog
  • Posts: 4,158
  • 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
#
bool BadBox(int squareNum, int solution[])
#
{
#
//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
#
//2 we already added)
#
if (i % 3 == 2)
#
curSquare += 7;
#
else
#
curSquare++;
#
 
#
}
#
return false;
#
}


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

Was This Post Helpful? 0
  • +
  • -

#5 selloorhari  Icon User is offline

  • D.I.C Head

Reputation: 5
  • View blog
  • 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. :blink:
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!!! :rolleyes:
Was This Post Helpful? 0
  • +
  • -

#6 stayscrisp  Icon User is offline

  • フカユ
  • member icon

Reputation: 994
  • View blog
  • Posts: 4,158
  • 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 :)
Was This Post Helpful? 0
  • +
  • -

Page 1 of 1