Member Avatar for 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.

Sudoku_Game.zip (73.37 KB)
  • 5 Contributors
  • 6 Replies
  • 785 Views
  • 11 Months Discussion Span
  • Latest Post Latest Post by William Hemsworth

Dani AI

Generated

A short, practical summary and a safe algorithmic plan that complements the discussion from , and .

The common, reliable approach is: create a full valid grid, then “dig” holes (remove clues) while checking that the puzzle still has exactly one solution. That digging method (remove in random order, restore any removal that creates a second solution) is standard; simple random-removal variants often leave multiple solutions unless each removal is tested. For solver/backtracking ideas see Norvig and practical generator notes. (norvig.com)

A short, safe generator (pseudocode):

generate_full_grid()         # backtracking fill or start from canonical grid + random transforms
order = shuffled(list of 81 cells)
for cell in order:
  save = cell.value; cell.value = 0
  if has_more_than_one_solution(limit=2):  # stop as soon as a 2nd solution is found
    cell.value = save
optionally try each remaining clue again to make puzzle minimal

Key points / implementation tips

  • Use a solver that can stop once it finds a second solution (do not fully enumerate all solutions every time). That yields big speedups when testing removals. (davidbau.com)
  • For very fast uniqueness checks use an exact-cover solver (Algorithm X / Dancing Links) or a well-optimized backtracker with constraint propagation. (en.wikipedia.org)
  • Difficulty is not just clue count. To make “easy/medium/hard” target which human techniques are required (singles/locked candidates → easy; pairs/triples/fish → medium; chains/forcing → hard). Use a rating/technique-aware solver (HoDoKu / Sudoku Explainer style) to filter generated puzzles into levels instead of trusting raw givens. ’s advice about distribution is useful: spread vs clustered givens changes human difficulty. (hodoku.sourceforge.net)

Advanced: if generating many puzzles or aiming for extreme minimality, study unavoidable-set / hitting-set pruning (used in exhaustive research). For theory on minimum givens see the 17‑clue result. (arxiv.org)

This plan keeps generation simple, guarantees uniqueness, and lets difficulty be defined by solver-techniques instead of naive clue counts.

Recommended Answers

All 6 Replies

Member Avatar for tux4life

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 !

Member Avatar for 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:

Member Avatar for 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.

Member Avatar for 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...

Member Avatar for WaltP

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

Member Avatar for 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.

Be a part of the DaniWeb community

We're a friendly, industry-focused community of developers, IT pros, digital marketers, and technology enthusiasts meeting, networking, learning, and sharing knowledge.