-
Sudoku program
I'm trying to make a program that makes sudoku fields. If you don't know what that is, i'll explain. This is the first version, and it only checks if the number is possible for the rows or the columns. I don't understand why it doesn't work.
Code:
#include "SudokuField.h"
#include <cstdlib>
#include <iostream>
bool SudokuField::fillfield() {
char random;
for(int r = 0; r < 9; r++)
for(int k =0; k < 9; k++)
for(int i = 1; i < 10; i++) {
random = rand() % 9 + 1;
if(checkpossible(r, k, random)) {
field[r][k] = random;
break;
};
if(i == 9)
return false;
};
return true;
};
bool SudokuField::checkpossible(numdata row, numdata column, numdata num) {
for(int i = 0; i < 9; i++)
if(field[i][column] == static_cast<short>(num))
return false;
for(i = 0; i < 9; i++)
if(field[row][i] == static_cast<short>(num))
return false;
printfield();
return true;
};
void SudokuField::printfield() {
std::cout << std::endl;
for(int r = 0; r < 9; r++) {
for(int k = 0; k < 9; k++) {
std::cout << static_cast<short>(field[r][k]);
if((k + 1) % 3 == 0)
std::cout << " ";
};
std::cout << std::endl;
if((r + 1) % 3 == 0)
std::cout << std::endl;
};
};
typedef short numdata;
class SudokuField {
private:
numdata field [9][9];
public:
SudokuField() {
for(int i = 0; i <9; i++)
for(int j = 0; j < 9; j++)
field[i][j] = 0;
};
bool fillfield();
bool checkpossible(numdata row, numdata column, numdata num);
void printfield();
};
EDIT: whoops, <code> is now [ code ]
-
psst its [code][/code] not <code> </code>
-
Ok, I got your program to work. There are basically 2 problems.
1st you are generating random number to try to fill in the puzzle and you "give-up" after 10 tries have failed. The problem with this is that you are going to fail often, because within 10 tries some number won't even be tried while others may be repeatedly tried.
Secondly, trying to fill in the puzzle randomly is difficlut even if you do try each digit at each position. It really needs some logic to make it efficient, however with that said. I have modify your code to randomly keep trying till it does hit upon a solution. Here it is
Code:
#include <cstdlib>
#include <iostream>
#include <algorithm>
#include <ctime>
typedef short numdata;
class SudokuField
{
private:
numdata field [9][9];
public:
SudokuField()
{
for(int i = 0; i <9; i++)
for(int j = 0; j < 9; j++)
field[i][j] = 0;
};
bool fillfield();
bool checkpossible(numdata row, numdata column, numdata num);
void printfield();
void clear()
{
for(int i = 0; i <9; i++)
for(int j = 0; j < 9; j++)
field[i][j] = 0;
}
};
bool SudokuField::fillfield()
{
for(int r = 0; r < 9; r++)
for(int k =0; k < 9; k++)
{
numdata random[] = {1,2,3,4,5,6,7,8,9};
std::random_shuffle(random,random+9);
for(int i = 0; i < 9; i++)
{
if(checkpossible(r, k, random[i]))
{
field[r][k] = random[i];
break;
}
if(i == 8)
return false;
}
}
return true;
};
bool SudokuField::checkpossible(numdata row, numdata column, numdata num)
{
for(int i = 0; i < 9; i++)
if(field[i][column] == num)
return false;
for(int i = 0; i < 9; i++)
if(field[row][i] == num)
return false;
int xsect = 3*(column/3);
int ysect = 3*(row/3);
for (int i = xsect;i< xsect+3;i++)
for (int j = ysect; j < ysect+3; j++)
if (field[j][i]==num)
return false;
return true;
};
void SudokuField::printfield()
{
std::cout << std::endl;
for(int r = 0; r < 9; r++)
{
for(int k = 0; k < 9; k++)
{
std::cout << static_cast<short>(field[r][k]);
if((k + 1) % 3 == 0)
std::cout << " ";
};
std::cout << std::endl;
if((r + 1) % 3 == 0)
std::cout << std::endl;
};
};
int main()
{
srand((unsigned)time(0));
SudokuField s;
while(!s.fillfield())
s.clear();
s.printfield();
}
ok, modified program to do check mentioned below. Now it's really ineeficient and I'm not even sure if it can generate a solution in a reasonable amount of time.
edit2 - slight error, had my column and rows mixed up.
Now it fully works and generates puzzle fairly quickly.
-
There's another problem with your method. Besides not duplicating a number in a row or column, you should also check that a number is not duplicated in each of the 9 3x3 grids
239
913
741
here the 9, 3 and 1 is duplicated in this section though not in same row or column.
edit: Modified code above to solve this
-
Thanks! I understand what i was doing wrong. Next problem: making a puzzle out of it ;). But I try to solve that myself.