Check if Sudoku solution is valid [closed]

问题:

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

回答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;

回答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 ;-)

回答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
      ;

回答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;
}

回答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

回答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;
}

回答7:

package Questions;

public class SudukoSonChek {

    public static void main(String args[]) {

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

        System.out.println(check(a));
    }

    public static boolean check(int arr[][]) {
        int i, j;
        int count[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        int count1[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0 };
        boolean b = true;
        for (i = 0; i < 9; i++) {
            for (j = 0; j < 9; j++) {

                if (count[arr[j][i]] > i) {
                    b = false;
                    return b;
                }
                if (count1[arr[i][j]] > i) {
                    b = false;
                    return b;
                }
                count1[arr[i][j]]++;
                count[arr[j][i]]++;
            }

        }
        return b;
    }

}

回答8:

In reference to the excellent answer from @Stephen, here is a solution in C# without resorting to LINQ, to show the difference between the two approaches.

This solution handles both 4x4 and 9x9 Sodoku boards.

using System;
using System.Collections.Generic;
using System.IO;
using System.Linq;

namespace Sodoku
{
    class Program
    {
        static void Main(string[] args)
        {
            List<string> lines = new List<string>();
            lines.Add("4;1,4,2,3,2,3,1,4,4,2,3,1,3,1,4,2");
            lines.Add("4;2,1,3,2,3,2,1,4,1,4,2,3,2,3,4,1");
            lines.Add("9;5,3,4,6,7,8,9,1,2,6,7,2,1,9,5,3,4,8,1,9,8,3,4,2,5,6,7,8,5,9,7,6,1,4,2,3,4,2,6,8,5,3,7,9,1,7,1,3,9,2,4,8,5,6,9,6,1,5,3,7,2,8,4,2,8,7,4,1,9,6,3,5,3,4,5,2,8,6,1,7,9");
            lines.Add("9;8,7,1,4,6,9,3,5,2,4,2,6,3,5,1,8,9,7,5,9,3,7,2,8,4,6,1,3,5,2,9,4,7,6,1,8,6,4,9,1,8,2,5,7,3,1,8,7,5,3,6,2,4,9,9,6,4,2,1,3,7,8,5,7,3,8,6,9,5,1,2,4,2,1,5,8,7,4,9,3,6");
            lines.Add("9;1,2,7,5,3,9,8,4,6,4,5,3,8,6,1,7,9,2,8,9,6,4,7,2,1,5,3,2,8,9,3,1,7,4,6,5,3,6,5,2,8,4,9,1,7,7,4,1,9,5,6,3,2,8,9,7,4,6,2,8,5,3,1,5,1,2,7,4,3,6,8,9,6,3,8,1,9,5,2,7,4");
            lines.Add("4;1,4,4,3,2,3,4,4,3,2,3,1,3,1,4,2");

            foreach (var line in lines)
            {
                var tokens = line.Split(';');

                var NxN = int.Parse(tokens[0]);
                var nums = tokens[1].Trim().Split(',').Select(int.Parse).ToArray();

                // Copy into Grid. Input is in row major form.
                var grid = new int[NxN, NxN];
                {
                    int i = 0;
                    for (int row = 0; row < NxN; row++)
                    {
                        for (int col = 0; col < NxN; col++)
                        {
                            grid[row, col] = nums[i];
                            i++;
                        }
                    }
                }

                int violations = 0;

                // Check if each column passes tests for Sodoku.
                {                   
                    for (int row = 0; row < NxN; row++)
                    {
                        var tempArray = new int[NxN];

                        for (int col = 0; col < NxN; col++)
                        {
                            tempArray[col] = grid[row, col];
                        }

                        if (IfArrayPassesSodoku(tempArray) == false)
                        {
                            violations++;
                        }
                    }
                }

                // Check if each row passes tests for Sodoku.
                {
                    for (int row = 0; row < NxN; row++)
                    {
                        var tempArray = new int[NxN];

                        for (int col = 0; col < NxN; col++)
                        {
                            tempArray[col] = grid[col, row];
                        }

                        if (IfArrayPassesSodoku(tempArray) == false)
                        {
                            violations++;
                        }
                    }
                }

                // Check if each sub-grid passes tests for Sodoku.
                // In 9x9 Sodoku, there are 9 subgrids of 3x3 each.
                {
                    int NxNsub = (int)Math.Sqrt(NxN); // Length of side of sub-grid, for a 9x9 board this will be 3.

                    for (int row = 0; row < NxN; row += NxNsub)
                    {
                        for (int col = 0; col < NxN; col += NxNsub)
                        {
                            var tempArray = new int[NxN];
                            int index = 0;
                            for (int i = 0; i < NxNsub; i++)
                            {
                                for (int j = 0; j < NxNsub; j++)
                                {
                                    tempArray[index] = grid[i + col, j + row];
                                    index++;
                                }    
                            }
                            if (IfArrayPassesSodoku(tempArray) == false)
                            {
                                violations++;
                            }
                        }
                    }

                }

                Console.WriteLine(violations == 0 ? "True" : "False");

                // Correct output is:
                // True
                // False
                // True
                // True
                // True
                // False
            }

            Console.ReadKey();
        }

        /// <summary>
        /// Checks to see if one-dimensional array passes Sodoku rules:
        /// 1. Digits range from 1 to N.
        /// 2. No repeating digits.        
        /// Could be way more efficient, but this solution is more readable compared to other concise forms.
        /// </summary>
        /// <param name="array">Array.</param>
        /// <returns>True if one-dimensional array passes Sodoku rules.</returns>
        static bool IfArrayPassesSodoku(int[] array)
        {
            int violations = 0;

            // Check for repeating digits.
            bool ifRepeatedDigits = (array.Distinct().ToArray().Length != array.Length);
            if (ifRepeatedDigits == true)
            {
                return false;
            }

            // Check to see that it contains the digits 1 to N.
            var sorted = array.OrderBy(o => o).ToArray();

            if (array.Length == 4)
            {
                if (sorted[0] != 1 || sorted[3] != 4)
                {
                    return false;
                }
            }
            else if (array.Length == 9)
            {
                if (sorted[0] != 1 || sorted[8] != 9)
                {
                    return false;
                }
            }
            else
            {
                Console.Write("Error E5234. Invalid grid size.\n");
                return false;
            }

            return true;
        }
    }
}

回答9:

I had a similar task, input coming from standard input.

I used sets. Put the element to the right row, column, and square (called box in my code). If all 3 set's size is 9, it's valid.

#include <iostream>
#include <set>

int main()
{

//decl
std::set<int> row[9];
std::set<int> column[9];
std::set<int> box[9];


//read & store
for (int i = 0; i < 9; ++i)
{
    for (int j = 0; j < 9; ++j)
    {
        int val;
        std::cin >> val;
        if ((val >= 1) && (val <= 9))
        {
            row[i].insert(val);
            column[j].insert(val);
            int k = j / 3 + i / 3 + i / 3 + i / 3;
            box[k].insert(val);
        }
    }
}

//check
bool l = true;
int i = 0;
while (l && i < 9)
{
    l = row[i].size() == 9;
    ++i;
}

if (!l) std::cout << "Invalid" << std::endl;
else
{
    bool l = true;
    int i = 0;
    while (l && i < 9)
    {
        l = column[i].size() == 9;
        ++i;
    }

    if (!l) std::cout << "Invalid" << std::endl;
    else
    {
        bool l = true;
        int i = 0;
        while (l && i < 9)
        {
            l = box[i].size() == 9;
            ++i;
        }

        if (!l) std::cout << "Invalid" << std::endl;
        else std::cout << "Valid" << std::endl;
    }
}

return 0;

}

回答10:

I thought my solution was terse, but apparently so if everyone else's. Anyways, I think this is a very clear and easy to read answer in ruby I made for an interview question on 7/11/2014:

## Returns true iff the given string is a valid sudoku solution
def is_valid_solution(grid)
  return false unless grid.is_a? String and grid.size == 9 * 9
  validate_rows(grid) and validate_columns(grid) and validate_boxes(grid)
end

## Returns true iff the set is the chars "1", "2", ..., "9"
def is_valid_set(set)
  return false if set.size != 9
  (1..9).each do | x |
    return false unless set.include?(x.to_s)
  end
  true
end

def validate_rows(grid)
  (0...9).each do | row |
    index = row * 9
    return false unless is_valid_set(grid[index, 9])
  end
  true
end

def validate_columns(grid)
  (0...9).each do | index |
    column = (index...81).step(9).to_a.map { | i | grid[i] }.join
    return false unless is_valid_set(column)
  end
  true
end

## This is ugly, but I'm running out of time...
TOP_LEFT_INDICES =  [ 0,  1,  2,  9, 10, 11, 18, 19, 20]
TOP_MID_INDICES =   [ 3,  4,  5, 12, 13, 14, 21, 22, 23]
TOP_RIGHT_INDICES = [ 6,  7,  8, 15, 16, 17, 24, 25, 26]
MID_LEFT_INDICES =  [27, 28, 29, 36, 37, 38, 45, 46, 47]
MID_MID_INDICES =   [30, 31, 32, 39, 40, 41, 48, 49, 50]
MID_RIGHT_INDICES = [33, 34, 35, 42, 43, 44, 51, 52, 53]
BOT_LEFT_INDICES =  [54, 55, 56, 63, 64, 65, 72, 73, 74]
BOT_MID_INDICES =   [57, 58, 59, 66, 67, 68, 75, 76, 77]
BOT_RIGHT_INDICES = [60, 61, 62, 69, 70, 71, 78, 79, 80]
BOX_INDICES = [TOP_LEFT_INDICES, TOP_MID_INDICES, TOP_RIGHT_INDICES,
               MID_LEFT_INDICES, MID_MID_INDICES, MID_RIGHT_INDICES,
               BOT_LEFT_INDICES, BOT_MID_INDICES, BOT_RIGHT_INDICES]

def validate_boxes(grid)
  BOX_INDICES.each do | indices |
    box = indices.map { | i | grid[i] }.join
    return false unless is_valid_set(box)
  end
  true
end

回答11:

The rows and columns can be validated in a single loop

public class SudokuChecker {

static int[][] sMatrix = {

    {5,3,4,6,7,8,9,1,2},
    {6,7,2,1,9,5,3,4,8},
    {1,9,8,3,4,2,5,6,7},
    {8,5,9,7,6,1,4,2,3},
    {4,2,6,8,5,3,7,9,1},
    {7,1,3,9,2,4,8,5,6},
    {9,6,1,5,3,7,2,8,4},
    {2,8,7,4,1,9,6,3,5},
    {3,4,5,2,8,6,1,7,9}

};

public static void main(String[] args) {
    if (rowColumnCheck() && boxCheck()) {
        System.out.println("Valid!");
    } else {
        System.out.println("Invalid!");
    }
}

private static boolean boxCheck() {
    for (int i = 0; i < sMatrix.length; i += 3) {
        for (int j = 0; j < sMatrix.length; j += 3) {
            boolean[] gridMatrix = new boolean[9];
            for (int k = i; k < 3 + i; k++) {
                for (int l = j; l < 3 + j; l++) {
                    int currentNumber = sMatrix[k][l];
                    if (currentNumber < 1 || currentNumber > 9) {
                        return false;
                    }
                    gridMatrix[currentNumber - 1] = true;
                }
            }
            for (boolean booleanValue : gridMatrix) {
                if (!booleanValue) {
                    return false;
                }
            }
        }
    }
    return true;
}

private static boolean rowColumnCheck() {
    for (int i = 0; i < 9; i++) {
        boolean[] rowArray = new boolean[9];
        boolean[] columnArray = new boolean[9];
        for (int j = 0; j < 9; j++) {
            int currentNumberRow = sMatrix[i][j];
            int currentNumberColumn = sMatrix[j][i];
            if ((currentNumberRow < 1 || currentNumberRow > 9) && (currentNumberColumn < 1 || currentNumberColumn > 9)) {
                return false;
            }
            rowArray[currentNumberRow - 1] = true;
            columnArray[currentNumberColumn - 1] = true;

        }
        for (boolean booleanValue : rowArray) {
            if (!booleanValue) {
                return false;
            }
        }
        for (boolean booleanValue : columnArray) {
            if (!booleanValue) {
                return false;
            }
        }
    }
    return true;
}

}