Check if Sudoku solution is valid [closed]

Question

You're given a solution to a Sudoku puzzle. Write the code to check if it's a valid solution.

Your function signature should be:
boolean isValid(int starti, int startj, int endi, int endj)

Rules for those unfamiliar with Sudoku:

• Grid size is 9x9, divided into 9 regions of 3x3
• Each row must contain all digits from 1-9
• Each column must contain all digits from 1-9
• Each 3x3 square must contain all digits from 1-9

I wasn't asked this question, but saw it on several places. Checking the last rule might be the interesting part

Answer 1

// rows
for (int i=0; i<9; i++) {
    std::bitset<9> filled;
    for (int j=0; j<9; j++)
        filled.set(grid[i][j] - 1);
    if (filled.count() != 9)
        return false;
}

// ... similar with the loops "swapped" to get the columns
// (or do both in one loop)

for (int i=0; i<9; i += 3)
    for (int j=0; j<9; j += 3) {
        std::bitset<9> filled;
        for (int k=0; k<3; k++)
            for (int l=0; l<3; l++)
                filled.set(grid[i+k][j+l] - 1);
        if (filled.count() != 9)
            return false;
    }

return true;

Answer 2

Sorry, I know this must be homework, but I can't help myself. It's just too much fun to come up with something :-)

A spoon full of LINQ makes the medicine go down:

public class Sudoku
{
    private int[][] sudoku;

    public Sudoku(int[][] sudoku)
    { 
        // TODO: Validate bounds and values
        this.sudoku = sudoku;
    }

    public bool Validate() =>
        VerticalLines.All(IsValid)
        && HorizontalLines.All(IsValid)
        && Squares.All(IsValid);

    IEnumerable<IEnumerable<int>> VerticalLines =>
        from line in sudoku select line;

    IEnumerable<IEnumerable<int>> HorizontalLines =>
        from y in Enumerable.Range(0, 9)
        select (
            from x in Enumerable.Range(0, 9)
            select sudoku[x][y]);

    IEnumerable<IEnumerable<int>> Squares =>
        from x in Enumerable.Range(0, 3)
        from y in Enumerable.Range(0, 3)
        select GetSquare(x, y);

    IEnumerable<int> GetSquare(int x, int y) =>
        from squareX in Enumerable.Range(0, 3)
        from squareY in Enumerable.Range(0, 3)
        select sudoku[x * 3 + squareX][y * 3 + squareY];

    bool IsValid(IEnumerable<int> line) => !(
        from item in line
        group item by item into g
        where g.Count() > 1
        select g)
        .Any();
}

The nice thing about this solution is, that no teacher will believe you if you say you came up with this ;-)

Answer 3

SQL allows you to define the rules as CONSTRAINTS: invalid puzzels are forbidden and cannot exist.

        -- Domain with only values 1..9 allowed,
        -- used for both the {x,y,z} coordinates and the cell values.
CREATE DOMAIN one_nine
        AS INTEGER
        CHECK (value >= 1 AND value <= 9)
        ;

        -- Table containing exactly one sudoku puzzle.
        -- The zzz coordinate (the "box number") is formally redundant
        -- (since it is functionally dependant on {xxx,yyy})

DROP TABLE IF EXISTS sudoku3 CASCADE;
CREATE TABLE sudoku3
        ( yyy one_nine NOT NULL
        , xxx one_nine NOT NULL
        , zzz one_nine NOT NULL
        , val one_nine
        );

        -- First constraint: (x,y) is unique
ALTER TABLE sudoku3 ADD PRIMARY KEY (xxx,yyy);

        -- Three constraints for unique values for {rows,columns,boxes}
CREATE UNIQUE INDEX sudoku_xv ON sudoku3 (xxx,val);
CREATE UNIQUE INDEX sudoku_yv ON sudoku3 (yyy,val);
CREATE UNIQUE INDEX sudoku_zv ON sudoku3 (zzz,val);

        -- Create empty board.
INSERT INTO sudoku3 (yyy, xxx, zzz)
SELECT  1+(nn/9)
        , 1+(nn%9)
        , 1+3*((nn/3)%3)+1*(nn/27)
        -- generate_series() is postgres-specific
        FROM generate_series(0,80) AS nn;

Now, the ->val members can be updated, but the resulting table can never violate any of the four constraints (three are actually INDEXES, but that is unimportant here).

Checking for a completely valid filled-in table means: checking if there are 81 non-NULL entries:

SELECT 1 AS result -- COUNT(*) 
    FROM sudoku3
    WHERE val IS NOT NULL
    HAVING COUNT(*) = 81
      ;

Answer 4

A Java implementation using bit sets:

public static boolean isValid(int[][] board) {
  //Check rows and columns 
  for (int i = 0; i < board.length; i++) {
    BitSet bsRow = new BitSet(9);
    BitSet bsColumn = new BitSet(9);
    for (int j = 0; j < board[i].length; j++) {
      if (board[i][j] == 0 || board[j][i] == 0) continue;
      if (bsRow.get(board[i][j] - 1) || bsColumn.get(board[j][i] - 1))
        return false;
      else {
        bsRow.set(board[i][j] - 1);
        bsColumn.set(board[j][i] - 1);
      }
    }
  }
  //Check within 3 x 3 grid
  for (int rowOffset = 0; rowOffset < 9; rowOffset += 3) {
    for (int columnOffset = 0; columnOffset < 9; columnOffset += 3) {
      BitSet threeByThree = new BitSet(9);
      for (int i = rowOffset; i < rowOffset + 3; i++) {
        for (int j = columnOffset; j < columnOffset + 3; j++) {
          if (board[i][j] == 0) continue;
          if (threeByThree.get(board[i][j] - 1))
            return false;
          else
            threeByThree.set(board[i][j] - 1);
        }
      }  
    }
  }
  return true;
}

Answer 5

This would my solution in ruby

#Sudoku grid 9x9 with numbers between 1 and 9
#three rules:
#1) in any row all numbers between 1 and 9 have to be present
#2) in any columns all numbers between 1 and 9 have to be present
#3) in any of the 9 3x3 boxes all numbers between 1 and 9 have to be present 


sudoku_correct =[[8,3,5,4,1,6,9,2,7],
               [2,9,6,8,5,7,4,3,1],
               [4,1,7,2,9,3,6,5,8],
               [5,6,9,1,3,4,7,8,2],
               [1,2,3,6,7,8,5,4,9],
               [7,4,8,5,2,9,1,6,3],
               [6,5,2,7,8,1,3,9,4],
               [9,8,1,3,4,5,2,7,6],
               [3,7,4,9,6,2,8,1,5]]

sudoku_incorrect =[[8,3,5,4,1,6,9,2,7],
                 [2,9,6,8,5,7,4,3,1],
                 [4,1,7,2,9,3,6,5,8],
                 [5,6,9,1,3,4,7,8,2],
                 [1,2,3,6,7,8,5,4,9],
                 [7,4,8,5,2,9,1,6,3],
                 [6,5,2,7,8,1,3,9,4],
                 [9,8,1,3,4,5,2,7,6],
                 [3,7,4,9,6,2,8,1,1]]

class Sudoku
def initialize(s_arr)
  @sudoku_arr = s_arr
end

# given 9 integers makesure that you have 1 to 9
def valid_contents?(set)
  set.each do |e|
    return false unless (1..9).include?(e)
  end
  return true
end

# check if set has no duplicates
def has_no_duplicates?(set)
  set.uniq.size < set.size ? false : true
end

def valid_set?(set)
  valid_contents?(set) &&  has_no_duplicates?(set)
end

# obtain blocks of sudoku, given a grid
def get_blocks(s_grid)
  blocks = []
  s_grid.each_slice(3) do |row_set|
    blocks_temp = [[],[],[]]
    row_set.each do |row|
      row.each_slice(3).with_index  do|s,i|
        blocks_temp[i] = blocks_temp[i] + s
      end
    end
    blocks +=  blocks_temp
  end
  blocks
end


def valid?(s_arr = @sudoku_arr)
  #check for row validity
  s_arr.each do |set|
    return false unless valid_set?(set)
  end

  #check for block validity
  get_blocks(s_arr).each do |set|
    return false unless valid_set?(set)
  end

  #check column validity
  s_arr.transpose.each do |set|
    return false unless valid_set?(set)
  end

  true
end

end


puts  Sudoku.new(sudoku_correct).valid?
puts  Sudoku.new(sudoku_incorrect).valid? 
# output: True & False

Answer 6

the solution which use just one array iteration. through the whole iteration of array, posRec array is going to have each numbers availability in ROW/COL/GRID. if there is missing bit in posRec, we can say sudoku isn’t correct.

#include <stdio.h>

#define ROW 0
#define COL 1
#define GRID 2
#define TRUE 1
#define FALSE 0


char sudoku_correct[9][9] ={{8,3,5,4,1,6,9,2,7},
                            {2,9,6,8,5,7,4,3,1},
                            {4,1,7,2,9,3,6,5,8},
                            {5,6,9,1,3,4,7,8,2},
                            {1,2,3,6,7,8,5,4,9},
                            {7,4,8,5,2,9,1,6,3},
                            {6,5,2,7,8,1,3,9,4},
                            {9,8,1,3,4,5,2,7,6},
                            {3,7,4,9,6,2,8,1,5}};

char sudoku_incorrect[9][9] ={{8,3,5,4,1,6,9,2,7},
                              {2,9,6,8,5,7,4,3,1},
                              {4,1,7,2,9,3,6,5,8},
                              {5,6,9,1,3,4,7,8,2},
                              {1,2,3,6,7,8,5,4,9},
                              {7,4,8,5,2,9,1,6,3},
                              {6,5,2,7,8,1,3,9,4},
                              {9,8,1,3,4,5,2,7,6},
                              {3,7,4,9,6,2,8,1,1}};



short posRec[9][3];

int isValid(char a[][9]) {
   int i, j, val, gIndex;

   for(i=0; i <9; i++){
      posRec[i][ROW] = 0;
      posRec[i][COL] = 0;
      posRec[i][GRID] = 0;
   }


   for(i=0; i<9; i++) {
      for(j=0; j<9; j++) {
         val=a[i][j]-1; //convert to 0-8 array index
         if((posRec[val][ROW]>>i) & 0x1)
            return FALSE;
         posRec[val][ROW] |= (0x1<<i);


         if((posRec[val][COL]>>j) & 0x1)
            return FALSE;
         posRec[val][COL] |= (0x1<<j);

         gIndex = (j/3) + ((i/3) * 3);
         if((posRec[val][GRID]>>gIndex) & 0x1)
            return FALSE;
         posRec[val][GRID] |= (0x1<<gIndex);

      }
   }

   for(i=0; i<9;i++){

      if(posRec[i][COL] != 0x1ff ||
         posRec[i][ROW] != 0x1ff ||
         posRec[i][GRID] != 0x1ff)
         return FALSE;
   }

   return TRUE;

}

int main(){

   printf("correct sudoku check = %s \n", isValid(sudoku_correct)?"CORRECT":"INCORRECT");
   printf("incorrect sudoku check = %s \n", isValid(sudoku_incorrect)?"CORRECT":"INCORRECT");
   return 0;
}