[Project Idea]Sudoku - ComputerCraft Forums (archive)

SuicidalSTDz #1

1511 posts

Location Pennsylvania

Posted 10 March 2013 - 05:38 PM

I think it's about time for someone to make Sudoku in CC! Who's up for the challenge? I'm talking selective difficulties, random number generation, the whole 9 yards! I'm no pro at the Math Library so I would never dare to take on such a task. ^_^/> I'm also aware Orwell has made a sudoku generator, maybe one could use that and take it to the next level.

Azhf #2

177 posts

Location Murrika

Posted 10 March 2013 - 05:52 PM

lol whoever accepts good l;uck

Cranium #3

Cranium's profile picture

3790 posts

Location Lincoln, Nebraska

Posted 10 March 2013 - 07:09 PM

Actually, this is not a bad idea. If I were any good at sudoku i might take a stab at it, but i'm not super interested in destroying my mind with math.

oeed #4

oeed's profile picture

2151 posts

Location Auckland, New Zealand

Posted 10 March 2013 - 07:53 PM

Why hasn't this been done yet. Now, I'm not aware of the complexity of the maths, but I'm gona take a stab at it.

BigSHinyToys #5

992 posts

Posted 10 March 2013 - 08:02 PM

I'm thinking a lot of math.random() should do it I will also be trying this … ow and yes I'm still here just not as active (work / life / other interferences.) You know how it is.

Dlcruz129 #6

Dlcruz129's profile picture

1619 posts

Posted 10 March 2013 - 08:11 PM

Cranium, on 10 March 2013 - 07:09 PM said:
Actually, this is not a bad idea. If I were any good at sudoku i might take a stab at it, but i'm not super interested in destroying my mind with math.

Counting to 9, real difficult math. :P/>/>

I wish everyone who tries this the best of luck!

Kingdaro #7

Kingdaro's profile picture

1688 posts

Location 'MURICA

Posted 10 March 2013 - 08:20 PM

I tried. The first algorithm I came up with would get stuck 90 percent of the time, because of situations like this:


. . . . . . . . 1
. . . . . . . . 2
. . . . . . . . 9
. . . . . . . . 4
1 2 3 4 5 6 7 8 ?

The code basically goes through the current row, column, and box it's in, and finds all possible numbers that can fit in that box, then throws in a random number from those possibilities. However here, you see the only possibility for the fifth row is 9, yet that's already taken in the 9th column.

My second algorithm, choosing a bunch of random rows while continually checking if it fits the puzzle, works, but is slow as hell. Takes 30 seconds to make one puzzle, and that's without checking boxes of 3x3.
Good luck to whoever can take this on and succeed better than I could.

BigSHinyToys #8

992 posts

Posted 11 March 2013 - 12:08 AM

Kingdaro, on 10 March 2013 - 08:20 PM said:
I tried. The first algorithm I came up with would get stuck 90 percent of the time, because of situations like this:
. . . . . . . . 1
. . . . . . . . 2
. . . . . . . . 9
. . . . . . . . 4
1 2 3 4 5 6 7 8 ?
The code basically goes through the current row, column, and box it's in, and finds all possible numbers that can fit in that box, then throws in a random number from those possibilities. However here, you see the only possibility for the fifth row is 9, yet that's already taken in the 9th column.

My second algorithm, choosing a bunch of random rows while continually checking if it fits the puzzle, works, but is slow as hell. Takes 30 seconds to make one puzzle, and that's without checking boxes of 3x3.
Good luck to whoever can take this on and succeed better than I could.

I am having the same problem
my code so far.
It generates a game with nil elements because it runs out of possibility.
http://pastebin.com/UWpYhmvR
and with that I have no idea where to turn ??

Kryptanyte #9

122 posts

Location New Zealand

Posted 11 March 2013 - 01:40 AM

Couldn't you just make a random generation of numbers for vert or horizontal lines then insert the opposite (aka if you generated horizontal random number lines then you insert vertical lines) into a table, like;


123
312
231

We end up with 6 tables;

Horizontal Tables:
hLine1 = {1,2,3}
hLine2 = {3,1,3}
hLine3 = {2,3,1}

Vertical Tables:
vLine1 = {1,3,2}
vLine2 = {2,1,3}
vLine3 = {3,2,1}

Then if runs checks with each table, looking for double ups or even triple ups, then looks for what numbers are missing in that particular line. Taking said variables from the checks it regenerates the numbers with an algorithm designed to take both X and Y axis and figure out which particular number can fit in both at a certain point.

My method could just be over thought and I can see some issues when running an algorithm for the redrawing of numbers, for example you might have nothing that can fit in both lines because you have something like
1
1,2,3,0,5,6,7,8,9
3
4
5
6
7
8
9

Where there is the number 4 missing in the X line but in the Y the number 2 is missing.

Again, its just my train of thought on how to do this, I'm not really thinking about it too hard, too early in the morning

ikke009 #10

309 posts

Location Sliding between sunbeams

Posted 11 March 2013 - 02:24 AM

The way I would do this is generate a 3x3 cell at random, check if it is possible, if so: put it in, if not: generate a new cell.
Repeat untill youve got 9 valid cells..
Then remove random numbers to complete the puzzle.
this would give 2 problems:
It is not certain if the puzzle is solvable (you would need to make a sudoku solver to check this)
It is not certain if there is only one solution (this would need an even more advanced sudoku solver)

I will have to try this method out soon…

SuicidalSTDz #11

1511 posts

Location Pennsylvania

Posted 11 March 2013 - 04:19 AM

Lol, i'm glad everyone is trying their luck at this. I wish you all the best of luck ^_^/>

BigSHinyToys #12

992 posts

Posted 11 March 2013 - 04:46 AM

The way I trying was having a table with 1 to 9 for each row and column and box then testing what numbers are valid for each X,Y then making those false in the row / column / box tables so next time that number wont be picked. then randomly picking from the available numbers. the problems is don't work and ends up with no possible numbers for some squares ?? kinda random.

Maybe the fresh light of day will help.

Bubba #13

Bubba's profile picture

1190 posts

Location RHIT

Posted 11 March 2013 - 05:02 AM

You guys should take a look at this. Although it is written in Visual Basic (?), he has a good method for generating puzzles.

SuicidalSTDz #14

1511 posts

Location Pennsylvania

Posted 11 March 2013 - 05:04 AM

Well like I said, Orwell made a generator. So i'm not sure if you could use that, then take a few numbers away. Have all the numbers (1-9) at the bottom, so when they click that number, then click a box, that number will appear.

Dlcruz129 #15

Dlcruz129's profile picture

1619 posts

Posted 11 March 2013 - 05:35 AM

Bubba, on 11 March 2013 - 05:02 AM said:
You guys should take a look at this. Although it is written in Visual Basic (?), he has a good method for generating puzzles.

I'd port this if I knew VB. Visual Basic's Syntax Reminds Me Of Those People Who Capitalize The First Letter Of Every Word They Say.

ikke009 #16

309 posts

Location Sliding between sunbeams

Posted 11 March 2013 - 07:15 AM

[media]http://www.youtube.com/watch?v=MlyTq-xVkQE[/media]
This (quite interesting) video shows some of the requirements for a valid sudoku puzzle..
EDIT: so now that we know what to keep in mind when creating a sudoku, and we have ourselves a valid sudoku generator (Orwell's generator uses the method described be bubba's link), the next step is to make the valid sudoku grid into a puzzle!
So we can erase numbers (or make them invisible) untill at least 17 numbers remain, of which 1 number is part of the magic pair or whatever numberphile called it..

Kryptanyte #17

122 posts

Location New Zealand

Posted 13 March 2013 - 01:08 AM

Call me crazy, but Challenge Accepted.

It won't be pretty and anyone who is actually good at LUA will probably think what the hell am I doing with random lines of useless code everywhere.

Dlcruz129 #18

Dlcruz129's profile picture

1619 posts

Posted 13 March 2013 - 03:22 AM

Kryptanyte, on 13 March 2013 - 01:08 AM said:
Call me crazy, but Challenge Accepted.

It won't be pretty and anyone who is actually good at LUA will probably think what the hell am I doing with random lines of useless code everywhere.

The hardest part is going to be writing an algorithm to make sure the puzzle is actually solvable.

Kryptanyte #19

122 posts

Location New Zealand

Posted 13 March 2013 - 07:41 AM

Well according to numberphile all you need is 17 numbers, there is no need to have specific ones except when you get an "Unavoidable Square" when there are two pairs numbers exactly the same on the same lines but flipped so like:

425
168
973
—–
842
791
356

See the 9 and the 7? thats what I mean

Kryptanyte #20

122 posts

Location New Zealand

Posted 15 March 2013 - 12:16 AM

Double post bump with help request?
http://www.computercraft.info/forums2/index.php?/topic/11133-sudoku-gamechecking-vert-tables-for-double-data/

LuaEclipser #21

LuaEclipser's profile picture

233 posts

Location Cleveland, Ohio

Posted 15 March 2013 - 09:53 AM

my brain hurts just thinking on how to do it

there have been many attempts, and many fails. who will succeed?

CHALLENGE.ACCEPTED

Kryptanyte #22

122 posts

Location New Zealand

Posted 15 March 2013 - 06:14 PM

LuaEclipser, I think I may have an idea for an algorithm for leaving the numbers on the screen, so its an actual playable sudoku I'll try and come up with it and send it to you if you are able to do the rest?

Zanoab #23

Zanoab's profile picture

5 posts

Posted 16 March 2013 - 06:19 PM

I think I'll take on this challenge as well. Funny thing is that generating a random valid solution is just as difficult as turning a solution into a puzzle without multiple solutions.

While writing my board object initialization code, I realized you can't just up and put random numbers. I did a quick test on paper and if you don't restrict your number generation after generating the first few numbers, it is possible for the board to end up with "bubbles" and instantly becomes an invalid solution.

What I mean:

Spoiler

Here is a quick 2d example (squares and rows):
1 2 3 | 4 5 6 | 7 8 9

Let's say you then generate the first 3 numbers of the next row:
5 6 7 |

It is now possible to trap your random number generator if you don't check the available placements:
1 2 3 | 4 5 6 | 7 8 9
5 6 7 | 1 2 3 | 4

In order to prevent this, you would have to analyze the available number placements:
4 can't be placed in Square 2 so it must be placed in Square 3
8 and 9 can't be placed in Square 3 so it must be placed in Square 2
1 2 3 | 4 5 6 | 7 8 9 (0's will be used as blanks)
5 6 7 | 8 9 0 | 4 0 0

Now let's do Row 3:
1 2 3 | 4 5 6 | 7 8 9
5 6 7 | 8 9 0 | 4 0 0
4 8 9 | 7 0 0 | 5 6 0

Now we can fill the remaining spots with 1, 2, and 3 and the board is 33% filled.

On the bright side, the fun doesn't stop there (sarcasm). That example was only a 2d example (rows and squares) when the complete board is 3d (rows, columns, and squares). Once you start adding all the details to reduce the chances of generating an invalid solution…

td;dr version: we are literally writing a sudoku solver that supports blank boards (strategically and/or bruteforce). :lol:/>

SuicidalSTDz #24

1511 posts

Location Pennsylvania

Posted 16 March 2013 - 06:22 PM

Glad to see people taking an interest in this.