SuDoku algorithm blues <-- HELP!

[Hyperchild]

So its varsity holidays, I'm bored and teaching myself C#. and just for the hell of it making another Sudoku game. So my issues lie in populating the grid, how am i doing this? using a random number generator as I cycle through the grid checking if each number is allowed there and if not trying another, a bit simplified but you get my drift. this works fine except that for some ... ... reason the validation algorithm below doesn't quite work as it should, if you comment out any 2 of the 3 sections, the remaining section appears to work but it doesn't work all together.

Heres the validation checking method:

Code: Select all

* r is the value of the current grid position to check
* x & y are the current grid co-ordinates
*
        private bool validgridposition(int r, int x, int y)
        {


* check all x-axis values up till current position*

            for (int xi = 0; xi < x; xi++)
            {
                    if (grid_y__xi_.getValue() == r) return false;
            }

*check all y-axis values up till current position*

            for (int yi = 0; yi < y; yi++)
            {
                    if (grid_yi__x_.getValue() == r) return false;
            }

*creates a sub grid to search 
* eg: if a 9x9 grid,
* should produce a 3x3 subgrid 
* containing x and y
* where segments = sqrt(length of 1 side of the grid)
* as all elements exist im not getting nulls*

            int xoffset = (x / segments) * segments;
            int yoffset = (y / segments) * segments;
            for (int ys = yoffset; ys < yoffset + segments; ys++)
            {
                for (int xs = xoffset; xs < xoffset + segments; xs++)
                {
                    if (!((xs == x) && (ys == y)))
                    {
                        if (grid_ys__xs_.getValue() == r)
                            return false;
                    }
                }

            }
* if all checks pass*
            return true;
        }

excuse the underscores PHP NUKE was having a problems with the square brackets indexing my array thinking that they were tags

please someone tell me what the ---- im doing wrong because im stymied!
so any and all comments will be accepted!

[FBiT]

Just an Idea

I made simple sudoku generator in excell

I just randomly generated and randomly placed while checking for Sudoku rules

Most of the times the algorythm got stuck in a loop as there are lots of sequences that you start with that cannot be completed to fill so I used to swop either the current position with another position in the current row or in the current column and kept on doing it until I get to a point where the loop does not exist anymore.

It goes through that a few times and you have a randomly populated grid.

I know the explanation is not so good but I'll see if I can find the code (VBscript) if it will help.

I'm also not a professional programmer so the code is not that good - but you can still optimize it.

I'll be looking at the forum again after work.

[rustypup]

you need to check if a number between 1 and 9 exists in a set. that's the rule. simple.

each cell does not exist in isolation. the phase space for each cell is it's square,(3x3 grid), it's row and it's column. the same rule is applied to each of these entities. that makes for 3 distinct sets of 9 cells that co-exist on each cell... to place a valid piece, you would take a complete set, (1->9), then iterate over each of the co-dependent sets, removing any current entries. what remains are the valid selectables, from which you can randomly pick. (naturally, if the selectable size == 1, don't place it.. it's a giveaway).

assuming A is the current target, it's sets extend as : X(grid), Y(row) and Z(column)
XXX
XXX
XXAYYYYYY
__Z
__Z
__Z
__Z
__Z
__Z

split the problem space up into manageable units. trying to accomplish this in one method is going to give you grey hair while producing some tasty spaghetti... it's the source of most of the trouble..

Code: Select all

public short[][] getCommunity(short x, short y){
 //extract the grid, row and column for the specified cell from the board
}
public short[] validate(short[] x_set, short[] valids){
 // for each entry>0 in x_set that exists in valid, remove
 // return remainder
}

i suspect that there are more than a few solutions to this out there

[Hyperchild]

Once again its rusty to the rescue

@FBiT: I like your idea Id a similar thing in mind for my next attempt, random x, y and value then check against constraints. I'm currently just cycling through the grid sequentially, though as far as i can tell thats not my issue, theres something fishy in my above code that i cant figure out. And I already know ALL about it getting stuck...

@rustypup: Your reply has merit to, but what you've suggested is (i think) exactly what Ive done, though Ive just done it using the active grid and in a single method : the first for loop should check the horizontal constraint, the second the vertical and the last 2 the sub 3x3 grid to which the given co-ordinates belong, its top left co-ordinate given by xoffset and yoffset.

Im working to a solution that dictates that the cell can only consist of a single set (1-9), each new entry into the constraining area(row, column and subgrid) removes another entry from the set.

BUT I STILL GET DUPLICATES!

[FBiT]

*Bow to Rusty*

I'm good at complex algorythms and you make it simple

THAT's why Im not a progammer by profession!!

[rustypup]

after looking at this again, another approach, probably a little quicker... still brittle, and i haven't actually coded this so there are quite likely some mistooks in there somewhere...

Code: Select all

    public byte[] hints(int x, int y){
        if(x<0||x>8||y<0||y>8)
            return new byte[0];//constraints checking
        
        byte[] pegs = {1,2,3,4,5,6,7,8,9};//entry store
        int cap = pegs.length;//valid entry count
        
        //parse column
        for(int i = 8;i>=0;i--)
            if(board[x][i]>0){
                if(pegs[board[x][i]-1]>0){
                    cap--;//reduce valid entry count
                    pegs[board[x][i]-1]=0;//mark entry as invalid
                }
            }
        
        //parse row
        for(int i = 8;i>=0;i--)
            if(board[i][y]>0){
                if(pegs[board[i][y]-1]>0){
                    cap--;
                    pegs[board[i][y]-1]=0;//mark entry as invalid
                }
            }
        
        //get the pivot point of the target grid
        int pivotX = x-(x%3);
        int pivotY = y-(y%3);
        
        //parse grid
        for(int iy=0;iy<3;iy++){
            for(int ix=0;ix<3;ix++){
                if(board[pivotX][pivotY]>0){
                    if(pegs[board[pivotX][pivotY]-1]>0){
                        cap--;
                        pegs[board[pivotX][pivotY]-1]=0;//mark entry as invalid
                    }
                }
                pivotX++;
            }
            //next row
            pivotX-=3;<edit>failed to account for last pass</edit>
            pivotY++;
        }
        
        //parse the valid entries
        byte[] hints = new byte[cap];
        int indx = 0;
        for(byte b:pegs)
            if(b>0)
                hints[indx++]=b;
        return hints;
    }

[Anthro]

8O Looks at that and cries

[simmy]

[SoulBlade]

Now thats some serious coding!! 8O

I havent done that much chruncing since universaty! Thank God its over.