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

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;

}

Answer 2

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

Answer 3

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

}

Answer 4

// 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 5

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 6

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