in reply to Re: Win32 development
in thread Win32 development

I want to do a puzzle generator that, basically, starts with an empty board and randomly inserts a number. It does this until it can solve the puzzle. Then, it presents the puzzle to the player. Depending on settings, it can also provide hints to the player because it already has the solution.

My Dad will be here for Christmas, so I could punt on the installation stuff because I can install it by hand on his laptop, but I was hoping to use this as a learning exercise. I suppose that just doing the Tk would be enough of a learning experience ...

My criteria for good software:
  1. Does it work?
  2. Can someone else come in, make a change, and be reasonably certain no bugs were introduced?

Replies are listed 'Best First'.
Re^3: Win32 development
by davido (Cardinal) on Dec 04, 2005 at 06:05 UTC

    The best Sudoku puzzles are written by humans. Computer Sudoku generators still have to be relatively sophisticated in order to achieve a target level of playability. The easiest Sudoku puzzles are rediculously simple, and the hardest literally require branch investigation down possibly multiple branches for a number of levels before the person solving the puzzle can determine which branch is going to play out to the end. In fact, some can be rendered unsolvable without resorting to guessing. Puzzles generated at random are going to sometimes be unsolvable unless a person gets out a pen and paper and starts making assumptions (guesses) and pursuing branches until they can be proven to not be a viable solution. In fact, in the worst cases, it may be impossble to take a set of 'givens' to the point of eliminating all but one solution.

    Part of the problem is in deciding what shall be the 'givens'. The givens have to be chosen in such a way as to make a puzzle solvable without pure guessing. In other words, they should set up a relationship that can only lead to one unique solution.

    The Wikipedia contributors have done a better job than I'm doing of explaining my point, and their eplanation can be read at http://en.wikipedia.org/wiki/Sudoku. In particular, the discussion of construction should be of interest. Of course you're a bright individual, and I wouldn't put it past you to develop a very well thought-out implementation. I just wanted to contribute a few caviets that might help you toward creating a more refined gadget.

    Good luck! I'd love to see the outcome.


    Dave

[reply]
      I've often wondered if you could create the grid by some method (brute force, trial-and-error) then overlay a mask from some other puzzle (or randomly pick X% of squares), then adapt one of the 'solver' algorithms to determine it's solvability.

      For example, if the solver ony ever uses just a basic single-link solution, then you call it 'basic' and store it someplace. Next if it uses only a few two-link lookups, call it 'easy', and so on. Basically once you have a puzzle, the solver is used to categorise it.

      Of course this doesn't really answer how to generate a 'simple' vs 'difficult' puzzle on the fly, but it would give you a method to provide pre-set puzzles ... and it gives a way to categorize them without human intervention.

[reply]

In Section Seekers of Perl Wisdom