For whom it may concern

First problem recognized: Annotations require 9 bits/cell!

 

Thats 81*9 bits = ~92 bytes!

Michael Rideout was working on a 2600 version of Sudoku, but apparently it's dead now. You can take a look of four pages' worth of stuff here.

I was designing a Sudoku game awhile ago. Then decided to bow out to allow Mr. Rideout to do his. But if he isn't maybe I should attack mine again. Nice kernel that shows the 9x9 grid of big numbers (using blinds) in two colors without flicker (or four colors with flicker).

 

My plan for generating puzzles would be to have a set of puzzles in ROM, and then apply various isomorphic transformations:

 

-1- Permute the rows within each group of three and the 3-high groups of rows. 6^4 possibilities.

 

-2- Permute the columns within each group of 3, and the 3-high groups of columns. 6^4 possibilities.

 

-3- Permute the digits 1-9 (9! possibilities)

 

-4- Swap rows and columns (two possibilities)

 

Were it not for the inner 3x3 boxes, the system could apply other isomorphic transformations including convolution. As it is, I can't figure out any way to fold or convolve the grid that wouldn't break things. Even so, the above transformations alone would allow one Sudoku puzzle to be transformed into about a trillion different ones. If there were only one 'starting' puzzle, a player would quickly learn to recognize the isomorphic transformation used and solve the puzzle. For example, if the puzzle had one row or one column that had two of the three boxes in each subgroup filled in, and if the player knew that in a differently-morphed version of the puzzle the numbers in the subgroups were 1/3, 5/7, and 2/8, the player would know that one pair of numbers should appear in all the places that 1 and 3 did in the other puzzle, another pair in the places 5 and 7 appeared, and the other where 2 and 8 appeared. A simple process of elimination would quickly show which pair went where, and voila--six of the nine numbers solved without breaking a sweat. Further, once those numbers were solved, it would be obvious which rows were swapped with which other rows, thus allowing the entire puzzle to be solved in short order.

 

On the other hand, if there were 80 starting puzzles (about 4K worth) at each of six skill levels, I would expect few players would be able to recognize whether they'd seen a particular puzzle before. Some patterns might show through, but the effects of that could be minimized if a number of the "seed" puzzles were chosen to be similar (so that a player might think he recognized part of the solution pattern, but get tripped up when other parts didn't match expectations).

 

I wonder what the best way would be to store Sudoku boards. If the 2600 doesn't need to 'know' the solution, they might be stored fairly compactly by using a bitmap of which cells are given along with a list of just the values that go in those cells. If it's necessary to include the whole grid in ROM (not just the starting squares) an arithmetic code might get things down to reasonable size but would be a pain to uncompress.

My plan for generating puzzles would be to have a set of puzzles in ROM, and then apply various isomorphic transformations:...

Interesting approach. I dunno exactly how a human brain would react on this, probably it wouldn't recognize identical puzzles. But the mini-puzzles inside the big puzzle would be repeating (even if transformed), so maybe one would get used to that.

 

BTW: I wouldn't create different puzzles for different difficulties. Just remove more or less digits form the solutions and use more initial puzzles instead.

 

I wonder what the best way would be to store Sudoku boards...

If it's necessary to include the whole grid in ROM (not just the starting squares) an arithmetic code might get things down to reasonable size but would be a pain to uncompress.

For a solved puzzle, you could use some very efficient huffman encoding.

E.g. 9 possibilities for column 1 (~3.2 bits), 8 for column 2 (3 bits), 7 for column 3 etc. for the top row.

In the 2nd row you start with 6 possibilites for column 1, 5 for column 2, 4 for column 3. From column 4 on, you would have to calculate the possibilities, something between 3 and 6.

3rd row: 3 possibilities for column 1, 2 for column 2 and column 3 is for free.

Etc. pp.

 

I haven't calculated that, but if you use different huffman encodings for each number of possibilities, the result should be pretty compact. Maybe 10 to 15 bytes/grid. I did something similar for Jammed and compressed 600 completely unrelated puzzles into ~2.5k.

 

To define the initial puzzle you would also need 81 bits for the initial difficulty and less and less for the following difficulties.

BTW: I wouldn't create different puzzles for different difficulties. Just remove more or less digits form the solutions and use more initial puzzles instead.

 

The difficult part of making a good puzzle generator isn't in generating the solutions--it's in generating the combinations of squares that one is given to start with.

 

That having been said, it might not be a bad idea to have some number of solved puzzles, and then for each have one variant per skill level which started with different numbers filled in. I would think that isomorphic puzzles would likely be recognizable if they were solved via the same sequence of steps, but isomorphic solutions would not be recognized if the sequence of steps needed to derive them was different.

 

Storing a number grid would probably take about 28 bytes (because of isomorphism, I believe one could assume the topmost row contains "123456789" in that order). The rightmost column and bottom row can easily be derived from the other eight. The set of starting squares would probably be 10-11 bytes.

The difficult part of making a good puzzle generator isn't in generating the solutions--it's in generating the combinations of squares that one is given to start with.

 

That having been said, it might not be a bad idea to have some number of solved puzzles, and then for each have one variant per skill level which started with different numbers filled in. I would think that isomorphic puzzles would likely be recognizable if they were solved via the same sequence of steps, but isomorphic solutions would not be recognized if the sequence of steps needed to derive them was different.

That makes sense, yes.

 

Storing a number grid would probably take about 28 bytes.

Why that much? I'd expect maybe 15 bytes (or less) for each grid.

 

The set of starting squares would probably be 10-11 bytes.

Yup, just one bit/square.

 

Anyway, I don't want to store precalculated grids anyway.

First binary posted (see 1st post).

 

I have a basic display kernel (flickering) and can a generate complete Sudoku grid (press SELECT for more) within 1 to ~20 seconds. This is done by a pretty simple brute force algorithm.

 

Now I am going to implement some intelligence into this algorithm, e.g. recognizing simple Sudoku patterns (Singles/Hidden Singles) and hope this will accelerate quite it a bit.

 

The next step after this will be the initial puzzle generation by removing digits from the generated grid.

The next step after this will be the initial puzzle generation by removing digits from the generated grid.

 

I guess I'm somewhat skeptical as to whether the 2600 will be able to do a really good job of generating good puzzles by generating a full grid and then removing numbers. It's possible I suppose, but many factors make puzzles easy or difficult, and I don't see any good way for the 2600 to balance them.

I guess I'm somewhat skeptical as to whether the 2600 will be able to do a really good job of generating good puzzles by generating a full grid and then removing numbers.

Me too. Memory restrictions make a lot of optimizations impossible.

 

It's possible I suppose, but many factors make puzzles easy or difficult, and I don't see any good way for the 2600 to balance them.

Here I am more optimistic. The source codes I checked just remove a number of digits and the generated puzzles played pretty good.

Version 0.11 posted!

This one now generates (pretty easy) Sudoku puzzles, using 3 different symmetries.

 

Current memory usage during generation:

- 41 bytes for the grid (81*4 bits = 40 bytes, 4 bits)

- 11 bytes for remembering original digits (81*1 bits = 10 bytes, 1 bit)

- 12 temporary bytes (lots of bits unused)

 

It get's rather slow, but it is completely unoptimized. E.g.

- it is calculating valid digits from scratch instead of storing hints

- it is clearing cells randomly and doesn't remember those already tried before

 

Valid digits for each cell are impossible to store (81*9 bits!), but I could do it for each row, column and block instead (27*9 bits).

Remembering already tried cells would require another 81*1 bits.

 

I am sure some bugs are still hidden in there.

Version 0.12

 

Dramatically improved generation performance (especially by remembering allowed digits for each row, column and block). Now a medium difficulty Sudoku is calculated in 3 to 10 seconds. To reduce average time for really difficult Sudokus, I abandon the solver if it takes too long and restart the generation from scratch. Still those Sudokus often take minutes to generate and I am not sure if and how this impacts the difficulty.

 

Implementing an intelligent solver turned out to be pretty impossible due to memory restrictions. I am already using ~94 bytes during generation, so there is not much space left.

 

Also added some eye-candy (useful for debugging too) during generation.

 

Next steps:

1. Trying to optimize memory consumption (to allow 2.)

2. Further speed improvements

3. Final digit permutation to hide generation orders

4. A better, non-flickering kernel

No new update this time.

 

It did some necessary code cleanup. Currently I am trying to find a nasty bug which causes the generator to create puzzle with more than one possible solution.

Found one bug:

ROW_BIT90	   = %1
COLUMN_BIT90	= %01
BLOCK_BIT90	 = %001

Solutions are still not always unique.

Ok, generator works now without making mistakes. Some tuning etc. is still required.

 

Now I am wondering about the best display kernel. Key requirements:

1. minimal to no flicker

2. good distinction between numbers

3. no markers required (due to lacking memory)

4. IMO a different background for given numbers is not required

5. variable cursor color (e.g. for indicating given numbers or errors)

 

Sprites would allow the best solution for 1., but without at least a little flicker they are not possible. I did some experiments and came out with this arrangement (0, 1 = GRP0, 1):

line 1: 01 |01 |01  
line 2:  01| 01| 01
line 3: 0 1|0 1|0 1

With the lines alternating each frame. So each pixel gets displayed 2 out of 3 frame.

 

Still I found the flicker irritating.

 

Then I checked John's YASK. But I didn't like how stiped the numbers looked. This could be overcome with alternating lines, but then we had flicker again. Also the cursor seemed limitated.

 

Finally I decided to have a closer look at Robert's 13 characters kernel. It offers pretty large and still good readable digits. But the cursor looks like a probem.

 

Currently I am trying to adopt it to my special requirements.

Then I checked John's YASK. But I didn't like how stiped the numbers looked. This could be overcome with alternating lines, but then we had flicker again. Also the cursor seemed limitated.

 

It's been awhile since I've looked at YASK. Yeah, Venetian Blinds aren't perfect, but the numbers are readable enough. It should be possible to show four colors with barely-noticeable flicker. As for the cursor, what was your problem with it? It uses the Ball, which means it uses the Playfield color, but I don't see why that should be objectionable.

It's been awhile since I've looked at YASK. Yeah, Venetian Blinds aren't perfect, but the numbers are readable enough. It should be possible to show four colors with barely-noticeable flicker.

Sure, but I am pretty sensitive to flicker, so I will try to avoid flicker at all costs. See the 3x3 demo above, IMO even that flickers too much.

 

As for the cursor, what was your problem with it? It uses the Ball, which means it uses the Playfield color, but I don't see why that should be objectionable.

But can it display different colors?

One week later and I still haven't found a kernel I am happy with.