Win a copy of Mesos in Action this week in the Cloud/Virtualizaton forum!

# Checking arrays

Kalabaw moo
Ranch Hand
Posts: 61

Hi, I'm trying to create a 4x4 soduku solver. After I finish this, maybe I could try to create a 9x9 soduku solver.
The problem I'm facing is how to check the rows from left to right - vice versa and check the column up and down - vice versa -
to validate the value that should be placed in the "box[ row index ][ column index ]". And how should I validate the 4 boxes
that they must only have values 1, 2, 3, 4.

The solution for the above matrix.

The code I have is only displaying the matrix so I decided not to post it just yet. I hope someone could give some idea on how to resolve this.

Campbell Ritchie
Sheriff
Posts: 48953
60
You should tell us what you think will work, then we see how it could be improved.

Kalabaw moo
Ranch Hand
Posts: 61

What I have in mind is to have a nested for loop to traverse each cell in the array.

first loop x = 0, y = 0 - will use the loop to assign the value 1 to the cell
check if the index fourByFour[ x ][ y ] is equals to 0 if it is equal to zero - means it's blank
if it's not blank check if it's 1, 2, 3, 4, if so, skip those cells.
if it's blank then scan the row and column if there is any occurence of the same value.
ex. fourByFour[ 0 ][ 1 ] is blank - it should scan from fourByFour[ 0 ][ 0 ] to fourByFour[ 0 ][ 3 ] - four ByFour[ 0 ][ 3 ] to fourByFour[ 0 ][ 0 ]
to validate if there's any cell that has the value 1
if not, check the column from fourByFour[ 0 ][ 1 ] to fourByFour[ 0 ][ 3 ] and from fourByFour[ 0 ][ 3 ] to fourByFour[ 0 ][ 1 ]
{ 1, 0,0,2}
{ 0, 0, 1, 0 }
{ 0, 0, 0, 0 }
{ 2, 0, 3, 0 }
if validation is complete, it should know if the value to be assigned to that cell is legal or not.
if it's not legal don't put it and find a different cell to put it
if no legal move for value 1 then it means that all the group of ( 1,2,3, 4 ) box already have one on them
the same process will do for the values 2, 3 and 4
The only thing I can't think of an algorithm is how to check the 4 group of boxes if they are already filled with ( 1, 2, 3, 4 )
Those group of 4 boxes must not have duplicate values.
Ex:
 Move long description outside code tags[/edit]

Campbell Ritchie
Sheriff
Posts: 48953
60
That looks good.

Get the checking working before you even think of inserting values, which is probably better done with a recursive method. When you have checked that there are no values the same in a column, there will be no need to check whether you have got the row completely filled. This is of course, the brute-force method.
Remember you also have to check whether there are duplicates in each 2×2 box.

And your example quoted is ambiguous. It has two solutions

1342
4213
3421
2134

1342
4213
3124
2431

Kalabaw moo
Ranch Hand
Posts: 61

And your example quoted is ambiguous. It has two solutions

Sorry about that, I didn't know that the example I provided is not complete.

When you have checked that there are no values the same in a column, there will be no need to check whether you have got the row completely filled. This is of course, the brute-force method.

brute-force?

Remember you also have to check whether there are duplicates in each 2×2 box.

This is what I actually mean in my ambiguous example. I really can't think of an algorithm to check the 2x2 box to check if there's no duplication

Campbell Ritchie
Sheriff
Posts: 48953
60
Brute-force?

It checks every possible combination until it finds one that fits.

Remember the 2×2 box is

array[i / 2][i / 2], array[i / 2][i / 2 + 1], array [i / 2 + 1][i / 2], array[i / 2 + 1][i / 2 + 1]

Well, I think that's correct. You will find out soon enough if it isn't .

Kalabaw moo
Ranch Hand
Posts: 61
wow, good logic.. I never thought of that... I'm currently working out on my code. I know how to do recursive method though but I'm really having a hard time how will I do a recursive method to check each cells. I'll post my updated code soon, but I hope you could give me ideas.

Campbell Ritchie
Sheriff
Posts: 48953
60
Have you got the duplicate checking working? Get that working, then think about filling the grid.

Kalabaw moo
Ranch Hand
Posts: 61
not yet, because I don't have any idea how to check the cells using recursive method-I'm trying though. But I think I can do it with iterative solution.

Campbell Ritchie
Sheriff
Posts: 48953
60
You probably don't need recursion to check for duplicates.

Kalabaw moo
Ranch Hand
Posts: 61
That's what I'm actually thinking, I will start doing it with iterative solution. I'll keep you updated.