3 ms·

I built my sudoku site using a pseudo random puzzle generator. I don't know the best algorithm to generate puzzles, so with some basic parameters for good puzz

I built my sudoku site using a pseudo random puzzle generator. I don't know the best algorithm to generate puzzles, so with some basic parameters for good puzzles, I let the puzzles fill out randomly. I generate, then test them for unique solutions and difficulty level. If the puzzle is invalid, I toss it. What I lack in algorithmic knowledge, I make up for with server resources :) http://sudokuisland.com http://sudokuisland.com I'm not a CS guy so reading this article made me feel a bit better, especially since it mentions sudoku.

Terr_ 12y ago
My gut-feeling is that building Sudoku puzzles shouldn't be too hard to generate, because every random choice you make reduces the space you need to pull from for the next choice. Whether they're "hard enough to solve", though....
- nicholas73 12y ago
  The difficulty comes from multiple solutions to your puzzles (which would force the player to guess). As it turned out, a purely randomly selected puzzle would 99.9%* of the time give you a puzzle with multiple solutions. I would have settled for 99%, but more was too much server resources to hog! And then add the screening for difficulty levels. *Not an exact figure =)
  - PeterisP 12y ago
    The sudoku difficulty can be very varied, but it doesn't rely on multiple solutions - a grid where multiple solutions are possible simply isn't a valid sudoku puzzle; a minimalistic puzzle is one where no numbers can be eliminated without losing uniqueness of the solution, but adding extra numbers to that minimalistic puzzle makes it easier.
    - nicholas73 12y ago
      All my puzzles have unique solutions. I said the difficulty of generating is from multiple solutions, not that the puzzles are difficult because of them.
      - PeterisP 12y ago
        Ah, I misunderstood you - true enough, the multiple solutions cases slow down a random generation as the candidates have to be checked and eliminated.
    - nicholas73 12y ago
      Would you happen to know of a minimalistic puzzle approach? I've read about some, like at least 17 squares and 8 out of 9 numbers presented. It didn't actually worked out in tests, so I abandoned that approach. At some point, testing theories became a viable way of generating puzzles, so I went with the random approach instead. But of course, for an efficient program, developing parameters for minimalist is best. I have parameters that increase the success rate to 25% or so...
  - Terr_ 12y ago
    > As it turned out, a purely randomly selected puzzle would 99.9%* of the time give you a puzzle with multiple solutions. Ah, I see what you mean, you're not talking about generating the intended solution, you're talking about which cells TO BLANK before giving it to the user.

Terr_ 12y ago

My gut-feeling is that building Sudoku puzzles shouldn't be too hard to generate, because every random choice you make reduces the space you need to pull from for the next choice. Whether they're "hard enough to solve", though....

nicholas73 12y ago
The difficulty comes from multiple solutions to your puzzles (which would force the player to guess). As it turned out, a purely randomly selected puzzle would 99.9%* of the time give you a puzzle with multiple solutions. I would have settled for 99%, but more was too much server resources to hog! And then add the screening for difficulty levels. *Not an exact figure =)
- PeterisP 12y ago
  The sudoku difficulty can be very varied, but it doesn't rely on multiple solutions - a grid where multiple solutions are possible simply isn't a valid sudoku puzzle; a minimalistic puzzle is one where no numbers can be eliminated without losing uniqueness of the solution, but adding extra numbers to that minimalistic puzzle makes it easier.
  - nicholas73 12y ago
    All my puzzles have unique solutions. I said the difficulty of generating is from multiple solutions, not that the puzzles are difficult because of them.
    - PeterisP 12y ago
      Ah, I misunderstood you - true enough, the multiple solutions cases slow down a random generation as the candidates have to be checked and eliminated.
  - nicholas73 12y ago
    Would you happen to know of a minimalistic puzzle approach? I've read about some, like at least 17 squares and 8 out of 9 numbers presented. It didn't actually worked out in tests, so I abandoned that approach. At some point, testing theories became a viable way of generating puzzles, so I went with the random approach instead. But of course, for an efficient program, developing parameters for minimalist is best. I have parameters that increase the success rate to 25% or so...
- Terr_ 12y ago
  > As it turned out, a purely randomly selected puzzle would 99.9%* of the time give you a puzzle with multiple solutions. Ah, I see what you mean, you're not talking about generating the intended solution, you're talking about which cells TO BLANK before giving it to the user.