I am trying to make a Sudoku game for the TI-83. It shouldn't be very hard I guess, but I'm kinda stuck. I need to generate a full puzzle before the player can even begin to play the game.

Check this for an example: http://www.websudoku.com/

I started with making the first 3x3 part in a matrix and from there remove all the numbers that aren't allowed anymore from a list {1,2,3,4,5,6,7,8,9}. I can now make two 3x3 parts that are right, but it generates too fucking slow.

I want to start all over. Should I work with the matrices and lists? Or strings and just cut off the numbers that aren't allowed? Suggestions are appreciated

I think matrices would be the best way to go. I made a SuDoku solver, and Jon was working on a creator I believe, but surprisingly a creator is harder to code than a solver.

Heh, I didn't even go for the solver, because that seemed too hard, so no wonder I got stuck. Do you still have the source of those two programs? I'd like to have a look at it so I know which way to go.

Yeah, a creator is ridiculously hard to make in BASIC. I gave up.

Basically, the creator is so much harder because you have to make sure that nothing makes the puzzle impossible to solve and yet only allows for one solution. Solving is easier to make for everything up to moderate puzzles. After you have to start using complicated logic, the coding gets insanely complex. And then you have to account for places where you have to guess and keep the matrix before the guess, and so on. This is why I'll be making the all-in-one program on the 68k calcs where I can use C.

Ok, forget about the puzzlecreator then

But how about making a 9x9 matrix where the rules of a solved sudoku apply? I was pretty disappointed in myself that I couldn't pull this off Any suggestions in this direction? (I'm still a n00b, I want to learn)

It's a very complex project, I commend your ambition, but even I couldn't pull off a creator in less than about 20k of spaghetti logic.

<400 byte Sudoku Solver in BASIC.
Interesting code. Simple but complex.

"Simple but complex" - logically sound but paradoxical.

Simple in that the code doesn't use any radically strange or arcane commands/methods, complex in that the system it uses is redundant and slow.

lol, a solver could just "brute force" itself a solution, trial-and-error style

Yes, but that's unnecessary for any sanely made puzzles. Pure logic can be used for many of the puzzles. If guessing is needed, then there's probably something overlooked.

I made my solver able to do anything except one particular solution method used in very hard puzzles that uses insane recursion. :/

It probably is not too hard to make a creator that generates a puzzle, but then the part that involves working backwords (to the players starting point) is almost impossible (atleast in BASIC)

The main problem is making a solvable puzzle in a reasonable amount of time. Impossible in Basic.

Indeed. It can be done in ASM though, and probably will be by someone soon. I know that one of the French programmers succeeded in making both a creator and solver in C for the 89 series.

You know this has already been done in BASIC right?

The problem with that one is that the puzzles don't always work. There's about a 50-50 chance of having a solveable puzzle. Otherwise it's a valient effort, but to make it always solvable would be impractical in TIBASIC. And to expand I what exactly I mean when I say it isn't solvable: When I tried playing it the first time, I solved it a good part of the way and then glanced and found two 5's in the same row. Now, I'm sure I did nothing wrong in solving it, I'm usually really good at solving them, and I checked every step I made.

Edit: After playing a few more, I realized the random generation is flawed as well. Here's an untouched puzzle:

Yeah, i see what you mean.. 2 sevens in a row and 2 in a column, 2 sevens in a square (gosh it seems like it has got something against sevens!).


P.S. after my exams are finished (and after i have played my Guild Wars Factions CE) I will try to make a Sudoku generator that generates a full puzzle, but it will be completed. It would be up to someone else to try to make a program that worked backwards! (it will probably be incredibly slow... generates a number than crosschecks it in all directions (and checks to see if it is in the list) ... so slow it would probably take about 10-20 minutes to generate a puzzle, and then to work backwards... THE HORROR

There's actually a better way to do it if I remember correctly. I'd have to jfgi to find the algorithm though. I believe it works by placing a number, checking if it made the board illegal, then keep doing that until the board is full, and finally remove some of them and give it to the user. Then you have both the problem and the solution at the same time.