Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I'm building a simple Sudoku game in Java which is based on a matrix (an array[9][9]) and I need to validate my board state according to these rules:

  • all rows have 1-9 digits
  • all columns have 1-9 digits.
  • each 3x3 grid has 1-9 digits.

This function should be efficient as possible for example if first case is not valid I believe there's no need to check other cases and so on (correct me if I'm wrong).

When I tried doing this I had a conflict. Should I do one large for loop and inside check columns and row (in two other loops) or should I do each test separately and verify every case by it's own?

(Please don't suggest too advanced solutions with other class/object helpers.)

This is what I thought about:

Main validating function (which I want pretty clean):

public boolean testBoard() {

        boolean isBoardValid = false;

        if (validRows())
        {
            if (validColumns())
            {
                if (validCube())
                {
                    isBoardValid = true;
                }
            }
        }
        return isBoardValid;
}

Different methods to do the specific test such as:

private boolean validRows() {
        int rowsDigitsCount = 0;

        for (int num = 1; num <= 9; num++) {
            boolean foundDigit = false;

            for (int row = 0; (row < board.length) && (!foundDigit); row++) {
                for (int col = 0; col < board[row].length; col++) {
                    if (board[row][col] == num) {
                        rowsDigitsCount++;
                        foundDigit = true;
                        break;
                    }
                }
            }
        }

        return rowsDigitsCount == 9 ? true : false;
    }

I don't know if I should keep doing tests separately because it looks like I'm duplicating my code.

share|improve this question

migrated from stackoverflow.com Nov 26 '11 at 7:18

This question came from our site for professional and enthusiast programmers.

1  
I would suggest other classes or object helpers. –  Hovercraft Full Of Eels Nov 26 '11 at 0:43
1  
Please show us what you've already tried –  Marco Nov 26 '11 at 0:45
1  
If this is for a class you should probably go ask your TA. I doubt your professor would be very happy if you just got a solution from the internet. FWIW, looking at your other questions it seems obvious this is homework. I've added that tag for you. Also, asking specific questions about problems you've encountered doing your homework is much better received than simply asking for us to do the work for you. –  tvanfosson Nov 26 '11 at 0:47
1  
A couple of for loops is indeed the easiest. One loop for horizontal, one for vertical, and a double nested loop for all the squares. –  GolezTrol Nov 26 '11 at 0:47
    
The down votes seem a bit rough: sodoku is actually quite an interesting problem, especially when you scale the problem up from 9x9 to sizes like 25x25 and you have to solve in less than 1 second. –  Anthony Blake Nov 26 '11 at 0:51

5 Answers 5

For purposes of this kind of checking, represent the content of each cell as a bitmask with only one of the nine possible bits set. Then OR ('|', not '||') together the contents of each row/column/block. If the result has all 9 bits set, you have a winner.

If you really don't want any other data structures, compute the bitmask on the fly as

1 << digit

where digit is between 0 and 9.

A winner is equal to 0x3fe, or 1022.

share|improve this answer
    
+1 for the elegance of a bitstream for this. It covers duplicate, missing, and just plain wrong values in one fell swoop. –  chaosTechnician Nov 26 '11 at 22:20
    
There is also the rule that each of the nine units has 1 to 9 to consider etc –  Will Nov 27 '11 at 9:14
    
@Will I'm not sure what you're getting at. Can you explain? If you're saying that there's a valid-solution requirement for each row/column/block that this doesn't test, I disagree. –  Ed Staub Nov 27 '11 at 16:33
    
Aha "block", my bad –  Will Nov 27 '11 at 18:18

It is best done with propositional logic. You make the 9x9 grid a 9x9x9 boolean cube, where each element in the third dimension is simple a boolean corresponding to each possible digit.

So if '1' was in a square, the bool corresponding to 1 for that square would be true, while the others would be false.

Representing Sudoku in this way means you can easily verify a solution as being valid/invalid with propositional logic. And you will also be well placed to solve sudoku, instead of simply verifying a solution as correct/incorrect.

See this paper for more info: http://my-svn.assembla.com/svn/disenosudoku/docs/a-sat-based-sudoku-solver.pdf

share|improve this answer

If you read Dr Pete Norvig's excellent sudoku solver you can understand how to solve sudoku whilst at the same time seeing how the experts do their validation, testing and reasoning.

Mentioning sudoku and unit testing in the same sentence is a classic ROTFL for those of us who fetched the popcorn when this happened: http://devgrind.com/2007/04/25/how-to-not-solve-a-sudoku/

More good reading on the TDD for design tangent I'm touching on is the more recent excellent talk by Rick Hickey about complexity.

share|improve this answer

I've written similar, but in C#. Without exact syntax for your java, I too basically have arrays... both 9x9 and 16x16 solutions. I created one function to return a string of all "Solved" values in a given row, another for "Solved" in a given column, and another for all in a given "Block" (3x3 or 4x4).

I would then have a master string "123456789" (or 0-9A-F for 4x4) and strip out every character returned from the cross-hairs. If only one number left, solved.

Sorry, I mis-understood... you are looking for a VALIDATION OF A COMPLETED BOARD... not trying to SOLVE a board. You were on a good approach, but here's a pseudo/code as I don't do Java, but C#/C++ are close, so you'll have to improvise...

private boolean validRows() 
{
   string baselineChars;
   for (int row = 0; row < board.length); row++) 
   {
      // prepare simple list of numbers we KNOW we should have 
      baselineChars = "123456789";

      // now check all columns on the given row...
      for (int col = 0; col < board.length; col++) 
         // IMPROVISE HERE...
         if( theValue at board[row][col] Still Exists in BaselineChars string)
            // strip so it will fail if the number already accounted for next round
            baselineChars = StripOutTheNumberYouJustFound;
         else
            // number no longer exists via already found, get out completely.
            return false;

    }
    // if still here after all 9 rows, we're good
    return true;
}

Likewise for column, but swap it col/row for loops.

For checking the "blocks" (3x3), it will be in a similar format

private boolean validBlocks() 
{
   int squareSize = 3;
   string baselineChars;
   // BR = BlockRow, BC = BlockCol
   for (int BR = 0; BR < squareSize; BR++) 
      for( int BC = 0; BC < squareSize); BC++ )
      {
         baselineChars = "123456789";
         // IBR = InnerBlockRow, IBC = InnerBlockCol
         for( IBR = 0; IBR < squareSize); IBR++ )
            for( IBC = 0; IBC < squareSize); IBC++ )
                // IMPROVISE HERE...
                if( the value at...
                    board[BR * squareSize + IBR][BC * squareSize + IBC]
                    is found in baselineChars )
                   // Strip it like that of rows and cols
                   baselineChars = StripOutTheNumberYouJustFound;
                else
                   // number no longer exists via already found, get out completely.
                   return false;

      }
      // if still here after all 9 rows, we're good
      return true;
}
share|improve this answer
    
Erm, :-( I did all my efforts and still can't solve this. –  Mico0 Nov 29 '11 at 23:19
    
@Mico0, see revised answer... not perfect, but PLENTY in the direction for just doing a BOARD VALIDATION –  DRapp Nov 30 '11 at 3:07

Take the elements of each row, each column, and each subbox and put them in a set or dictionary. Then verify that each set/dictionary has exactly nine elements (meaning that it has no duplicates).

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.