Generating a unique sudoku

[William Hemsworth]

Hi,

I've been working on a sudoku game, which seems to be working pretty well so far. I've managed to make a basic solver, and the interface is pretty nice :icon_cheesygrin: But i'm having problems trying generate a random unique sudoku. I need to be able to create 3 different difficulty level sudoku's, and I don't want them to take long to generate.

For example, say I have these functions.

struct cell {
  int value;
};

struct sudoku {
  cell grid[9][9];
};

void solve_easy(sudoku &sud) {
  // Working
}

void generate_easy(sudoku &sud) {

  // Reset sudoku
  for (uint x = 0; x < 9; ++x) {
    for (uint y = 0; y < 9; ++y) {
      sud.grid[x][y] = 0;
    }
  }

  // How do I generate an easy sudoku here?
}

I was thinking to first totally fill up the grid with valid integers (which is the first problem), and then keep removing one random number from the grid until it is no longer solvable using my basic solver. At that point, I put back the last number I removed from the grid. Would that give me a unique sudoku?

If not, what other ways could I manage this? any help would be appreciated :icon_lol:

The project is over a 1000 lines and wouldn't help much anyway, but I will attach the executable (along with one previously saved sudoku to show the solver works) to show you what I mean a little better.

Thanks.

[mvmalderen]

Writing a Sudoku solver is a very interesting project, it's not as easy as it looks like I think...

Maybe the following link is useful for you: http://www.codeproject.com/KB/game/sudoku.aspx
(maybe just useful for the algorithm)

And this link might also be useful:
http://translate.google.com/translate?prev=hp&hl=en&u=http%3A%2F%2Fwww.keesmoerman.nl%2Fsudoku.html&sl=nl&tl=en
(translated from Dutch, you can download the source of it (in the source the comments are in English))

Have success with your Sudoku solver !

[William Hemsworth]

Thanks for your reply :]

But I didn't find those links too useful. I've already managed to make a function to solve the sudoku's, but I need to figure out how to generate them with different difficulties. I've already looked around on the net for quite a while, but couldn't find too much information on how to generate sudoku's. And the first link was in C#, and was hard to understand for me :icon_eek:

[verruckt24]

I haven't had much experience generating these puzzles but to comment on the difficulty levels, here's what I think:
The first thing that comes to my mind is, the more the number of empty cells the higher the difficulty. Second is the placement of the various initial numbers. Initial numbers evenly spaced apart make for simpler puzzles, whereas difficult puzzles often have numbers clustered in groups.

So if you are able to programatically control these two characteristics you could control the difficulty of the puzzles.

[Gachmari]

Hello, can u help me doing generation in sudoku? if it is possible may i know how to use the graphics u had in ur exe file? or how to generate random numbers in sudoku?

I would appriciate your help as I'm a new C++ learner but love stuff like this...

[WaltP]

Resurrecting and hijacking an old post is not a good way to introduce yourself.

[William Hemsworth]

Hello, can u help me doing generation in sudoku? if it is possible may i know how to use the graphics u had in ur exe file? or how to generate random numbers in sudoku?

I would appriciate your help as I'm a new C++ learner but love stuff like this...

My graphics is purely Windows API, and took alot of work and practice in this case. Don't expect to be able to do something like this if you're just starting, if you dont know how to generate a random number by yourself, you're not ready.

There's lots of maths involved in this, I suggest you learn how the basics before anything else.