## Using my Sudoku Solver to generate new puzzles (part 2)

Following on from Part 1, I’ve been looking at some alternative approaches to generating new Sudoku puzzles. It turns out that having a working and effective solver is essential in generating new puzzles, because you need to know if you’ve generated a valid puzzle, meaning a puzzle with only a single solution.

The generally accepted approach to creating new puzzles is to generate a completed grid and then remove values from cells, checking at each step that you still have a valid puzzle and then stop at a point where you’ve generated a puzzle with the required difficulty. Grading a puzzle ‘easy’ through ‘difficult’ is another topic unto itself, so I’ll come back to this later.

Here’s a summary of possible (but not exhaustive) approaches to generate a completed grid:

### Brute force approach with backtracking

• fill each cell with a random number
• check puzzle is valid
• if puzzle is not valid, go back to previous cell and try another random number

Although this approach would work, it’s obviously not the most efficient approach. Brute force algorithms usually take advantage of the speed of today’s CPUs to offset the inefficiency of trying every combination until you get what you’re looking for.

### Running a solver against an empty grid

• run solver against empty grid
• ensure solver is picking a random candidate column from it’s exact cover matrix (see previous posts for how this is used by the solver)

This approach is interesting as it reuses the Solver, and instead of solving a puzzle with a limited number of givens, the puzzle has zero givens. My Solver uses the same approach with Knuth’s Algorithm X to ‘solve’ an empty grid, it doesn’t make much difference whether there’s a minimum of 17 givens for a valid puzzle or zero puzzle, it will still fill the grid.

The downside of my current Solver approach though is that it will always fill the grid with the same combination of numbers due to the way it always picks the next value based on the next unmet constraint with the least number of remaining possible candidates. While this approach sames significant time solving a valid puzzle, it does mean the approach has a predictable result and doesn’t produce random filled grids. This could be updated to add some randomness, but I think there’s an easier approach.

### Run solver against a partially populated grid

• Populate row 1 in the grid with a random combination of 1 through 9
• Run the solver against this ‘seeded’ grid

Like the previous approach, this reuses the solver. However, by ‘seeding’ the first row with a random combination of 1 through 9, this does result in different grids being generated. Without any closer investigation however, due to the predictable results from my Solver, I think at best this probably means this approach will only generate 9! combinations (362880). While this is enough puzzles to keep you busy for a least a few weeks (!), there still has to be a better approach.

### Conclusions

Since I already have a working solver, I’m going to use the ‘seeded’ partially populated grid approach, run my seeder against it, then remove a number of candidates, then run a ‘difficulty grader’ against it. I’ve been working on the ‘grader’ for a while now, I’ll post an update on the approach I’m taking with that in another post.

## Implementing simple sort algorithms in ARM Assembly (part 1)

A while back I started to learn some ARM assembly on the Raspberry Pi (out of curiosity, for no other better reason). I thought it would be interesting to couple this with re-learning some of the basic/standard/common algorithm at the same time, such as common sort algorithms.

So as my first step, since this is turning out to be far more work than I expected (!), here’s my ARM ASM source so far to iterate through a list of 4 byte integer values and print the values to the console using C’s printf. I’ll post further updates as I make progress:

[code]
.global main
main:
push {ip, lr}
MOV R6, #0 @offset to data
loop:
LDR R5, =nums @ addr of string to R5
LDR R4,[R5,R6] @load current num from R5 with offset R6
MOV R1,R4 @move num for output
BL printf
CMP R6,#16 @ 0 plus 4*4bytes for 5 entries in array
ADD R6,R6, #4 @inc offset by 4 bytes
BNE loop
_exit:
POP {ip, lr}
MOV R1, #0
MOV R7, #1
SWI 0
nums:
.word 5,2,7,1,8
.data
output:
.asciz "%d\n"
[/code]

I’m sure there’s better ways I can approach this limited code so far, but I’ll come back and revisit this again later. If anyone wants to pull or browse the source so far (and other snippets), it’s on github here: https://github.com/kevinhooke/learning-arm-asm

## Sometimes the simplest solutions are the best solutions

How many times have you seen or written code like this (in any language):

[code]
if(someFlag){
someFlag = false;
}
else{
someFlag = true;
}
[/code]

I’ve written code myself like this many times, and seen it in many places too. Usually for toggling display of some content: “if it’s hidden, show it; otherwise, hide it”.

Recently I’ve been spending a lot of time learning and coding an app using AngularJS and I keep seeing this pattern repeatedly in many code examples:

[code]

someFlag = !someFlag;

[/code]

When I first saw a statement like this it took me a couple of seconds to understand the purpose, but then when it clicked I laughed out loud in one of those ‘ahah!’ moments, as the outcome of this code is exactly the same as the code above.

When we translate design to code, sometimes thinking in logical, procedural steps hurts the ability to translate to code that best uses the features of the language or platform that you are running on. Sometimes the simplest solutions really are the best solutions, although maybe it takes a different thought process to get there.