Sudoku Generator Logic For Mobile Game Developer

CodeTiger

Generating sudoku puzzle using low CPU power: Puzzle generator completely depends on the solver technique in terms of efficiency. So we are half the way through. for solver logic see here. The generator logic is bit easy. Usually these are two common ways to generate Sudoku puzzle.
One: filling an empty grip partially with random numbers in random cells and trying to solve it, if there is a unique solution, the puzzle is ready. Else add another number and try solving. if this fails to produce unique solution puzzle try again with filling a different random numbers in random cells. This method is not suitable for mobile phones, coz this takes along time.
Two: take a filled solution grid and hide some cells now try solving it, if more than one solution is possible then hide more cells, if there is a unique solution then stop hiding more cells. This method is simple and faster but requires some code on generating filled solution grid. To generate a filled solution grid you have to use some matrix theorem rather than filling a grid by random numbers. This is the most deciding part of the methods we have used. We have crossed all major tasks now. Your code efficiency and CPU usage depends on this piece of code. I have tried two extremes of coding in this part which results to generation time of 10 mins and the simplest (the on I have implemented now) which takes at the max 3 seconds on a 35 MHz processor.

Mobile Game Developer

The Ostrich · Posted: Sat May 20, 2006 1:54 am Post subject:

My generator takes an average of 4 ms per random (ungraded) puzzle on a 2 GHz processor, which is equivalent to about 0.25s on a 35 MHz processor, so your efficiency is a bit low.

gsf · Posted: Sat May 20, 2006 3:35 am Post subject:

The Ostrich · Posted: Sun May 21, 2006 11:28 pm Post subject:

Heja gsf.

The puzzles are minimal. The speed is subject to symmetry - puzzles with higher orders of symmetry are naturally faster to generate (the no symmetry at all puzzles have efficiency ratings of about 50% and take 4-5 ms, whereas the puzzles with 8-way symmetry have efficiency ratings in excess of 100%, making them over twice as fast to generate).

I don't actually use the random ungraded output for anything. Instead, the program allows the user to specify a symmetry type, a difficulty and imposes a quality rating based on those selections. So if you choose a hard puzzle with no symmetry, you get a puzzle with less than or equal to 22 givens out, whereas if you specify 8-way symmetry, it allows up to 28 givens.

The algorithms are balanced so that it never takes more than about half a second to find a puzzle of the selected difficulty meeting the quality requirement. I've described the methods I used to achieve this performance in other places

<a>A useful measure of efficiency for generators</a>

<a>17 givens... How?</a>

But basically, the 1-neighbourhood search allows me to reduce the number of givens in a puzzle that hits my difficulty window without changing the difficulty (in general). This means that I can throw puzzles away while they don't hit the difficulty window, and when I find one that does, there is a good chance that it will be reductible by 1-neighbourhood search to hit the quality threshold.

MCondron · Posted: Mon Jul 17, 2006 2:15 am Post subject: CPU speed scaling

anttiahola