Author Topic: How to generate a valid Sudoku table (Javascript)  (Read 3624 times)

0 Members and 1 Guest are viewing this topic.

Offline saildev

  • Jr. Member
  • **
  • Posts: 60
  • Developing Qt5 applications for SailfishOS.
    • View Profile
  • Phone model: Jolla
How to generate a valid Sudoku table (Javascript)
« on: November 22, 2013, 09:33:42 AM »
If you're not really into math related problems or discussions this thread may not be for you - unless you want to learn about math in Sudoku.

Introduction
One day I got a message from a friend of mine. He talked to me about Sudoku and he said I couldn't beat him in that game. I took it as a challenge.

I started to play it every single day and now I can solve the most hardest Sudoku I've found on newspaper. I know I'm not the only one who is capable to do so but at least I beat my friend. he wasn't very happy about it so he thought to push it a little further. Few weeks later he called me again and said ".. now I understand how Sudoku tables are created!". I asked him can you create one from out of nothing? He mumbled.

I said to him I could give it a try. He suggested that if I can't create a valid Sudoku table generator in 5 days I'd have to offer him a night in a bar. However if I manage to do so he won't question my capability to solve math related problems.

It took me 2 days (11 hours of coding, to be precise ..) to create a valid Sudoku table generator. That wasn't enough for me, though. I wanted to make the code much shorter and faster. That's why I spend another 2 days to make it even better.

I have to admit I'm more then surprised of what I achieved. I tried a lot of different methods I could think of and the results were... Well, amazing.

How fast it is?
First of all I'd like to make one thing clear. The thing was not to create a Sudoku game. The whole idea was to create a valid Sudoku table. So basically that means it's kind of a already-solved Sudoku.

Another thing I would like to mention is that I chose Javascript because I'm about to create a game for Sailfish so it's easy to continue my work here.

The code itself is only about 60 lines long - or should I stay short - and it creates a valid Sudoku table immediately. I did almost 100 tests to create 1,000 valid Sudoku tables.

Guess how many seconds it took? Approximately 5 seconds each time. That means it takes 0,005 seconds to create one. Impressive, huh?

What's next?
There are several different methods how a valid Sudoku table can be created and I will write a short guide on one of them - the one I used.

This thread will hold a several posts because I don't have time to explain it all in one post. So be patient and stay tunes. ;)
« Last Edit: November 22, 2013, 11:07:41 AM by saildev »
“First, solve the problem. Then, write the code.” - John Johnson

Offline saildev

  • Jr. Member
  • **
  • Posts: 60
  • Developing Qt5 applications for SailfishOS.
    • View Profile
  • Phone model: Jolla
Re: How to generate a valid Sudoku table (Javascript)
« Reply #1 on: November 22, 2013, 09:37:21 AM »
I'd also like to point out that I may not give the full, complete source code. I've never asked for ready answers where someone does the job for me and I just copy the code.

Therefore I'll tell you how I started this whole project, what you need to consider and what methods and algorithms I used. If you need help of course I'll help some more. :)
“First, solve the problem. Then, write the code.” - John Johnson

Offline saildev

  • Jr. Member
  • **
  • Posts: 60
  • Developing Qt5 applications for SailfishOS.
    • View Profile
  • Phone model: Jolla
Re: How to generate a valid Sudoku table (Javascript)
« Reply #2 on: November 22, 2013, 10:16:51 AM »
I forgot to add one more thing, so I'll do that before we move on to next chapter ...

All the tests has been doen using an old computer (Intel Atom 1,60GHz and 1Gb of RAM). I tested it with my high-end laptop and it managed to create 1,000 valid Sudoku tables in about 3 seconds.

How to create the code
Every time I start a new math related problem I think of it all the way through with all possible turnarounds. In this case it means I needed to figure out what to do when this thing happens.

Here's my plan how I created it:

Code: [Select]
- Create default Sudoku values.

- IF less than 81 cells are filled:

- IF all possible integers [1-9] have been used in current cell:

- Clear used integers in a current cell.
- Move one step back.
- Load already used integers IF any.

-- Call the function again.

- ELSE:

- Mark an error boolean to 'false'.
- Generate a random integer to current cell from a list of possible integers.

- IF current integer is same than in ...

* 3x3 group of blocks.
* a same row.
* a same column.

- THEN Mark an error boolean to 'true'.

- END

- IF no errors:

- Add current integer to a Sudoku array.
- Add current integer to an array of used integers.
- Move one step forward.
- Clear possible integers. / Back to default.

-- Call the function again.

- ELSE:

- Remove the integer from possible values.

-- Call the function again.

- END

- END

- ELSE:

[Ready!] A valid Sudoku table is done.

- END

For some of you it may be a little bit unclear but I believe for those who are familiar with coding should know this.

On next post I'll explain the methods and algorithms I used to achieve this in less than 65 lines of code.
“First, solve the problem. Then, write the code.” - John Johnson

Offline saildev

  • Jr. Member
  • **
  • Posts: 60
  • Developing Qt5 applications for SailfishOS.
    • View Profile
  • Phone model: Jolla
Re: How to generate a valid Sudoku table (Javascript)
« Reply #3 on: November 22, 2013, 10:28:36 AM »
Notice!
The most important part of creating a valid Sudoku table is a method called backtracking. It means that if you've tried all possible integers in a current cell you need to step back. If you've tried all possible integers in that cell as well, you go back again. ---

Therefore you need to store all used integers in each cell. For that I use a multi-dimensional array usedArray[m][n1,n2,...] where 'm' stands for cell ordinal and nx for used integers.

So whenever I need to move back one step I make sure I don't try integers that has already been tried. Also you need to make sure that you remove the used integer array for a cell you're currently at before moving back one step. Because when you try a new possible integer it changes the game itself.

Another thing you should notice is that I could use a random number (in a range of 1-9 ..) every time I call the function to try a new integer in current cell. This avoids you to try the number all over again. Therefore I use an array of possible integers whenever I move forward to a next cell.

If I need to step back I can use the array of already used integers to remove those numbers from an array that holds the possible integers. This saves time a lot. I gave it a test run that I didn't use an array which keeps record of possible integers and it slowed down the whole process of generating 1,000 valid Sudoku tables for about 3-4 seconds.

Conclusion
So the keys to create a fast code to generate a valid Sudoku table are:

  • Backtracking
  • Keep record of already tried integers for each cell.
“First, solve the problem. Then, write the code.” - John Johnson

Offline saildev

  • Jr. Member
  • **
  • Posts: 60
  • Developing Qt5 applications for SailfishOS.
    • View Profile
  • Phone model: Jolla
Re: How to generate a valid Sudoku table (Javascript)
« Reply #4 on: November 22, 2013, 11:06:50 AM »
Backtracking and used integers
Backtracking may sound a little weird for most of you but it's one of the most important actions to create a valid Sudoku table fast. An array of used integers in specific cells is not required but it speeds it up a lot.

I would like to give a little bit more details about both of these - especially backtracking.

You need backtracking when you have a situation where you have no possible integers left. Without backtracking you'd have to start everything all over again. The more numbers you get the less possible integers you actually have.

So this is where backtracking comes in. You take a step back and try another number. If you still run out of possible integers you take a step back, again.

You also keep record of all used integers. Otherwise if you step back and you use random integers in a range of 1-9 you might end up in a same situation all over again if you have some bad luck. So if you keep record of all used integers in all cells you don't have this problem where you do the same mistake again, and again, and again, ...

I hope this clears it up and I think you'll understand more when - or actually if - I leak a little bit of my code :)
“First, solve the problem. Then, write the code.” - John Johnson

Offline saildev

  • Jr. Member
  • **
  • Posts: 60
  • Developing Qt5 applications for SailfishOS.
    • View Profile
  • Phone model: Jolla
Re: How to generate a valid Sudoku table (Javascript)
« Reply #5 on: November 24, 2013, 09:25:30 PM »
I started to post in here already earlier this afternoon. For some reason I ended up making my code even faster.

I changed few methods and it creates 1,000 arrays of valid Sudoku tables in less than a second. I tested it about 50 times and only few time the timer went over one second - but it was never over 1,5.

I think I'm getting really close for what I was after...

That's the reason why I didn't post here nothing today. Yesterday I thought I will but I got an idea how I could improve my code. And this is the result.

But I hope I manage to get some time next week to actually start talking about the code part itself. I think that'll be the most important and interesting part about this, right?
“First, solve the problem. Then, write the code.” - John Johnson