Valid Sudoku - C Solution

1. Introduction

This post delves into a common puzzle-solving problem in C programming - validating a Sudoku board. Sudoku is a logic-based, combinatorial number-placement puzzle, and the challenge here is to check whether a given 9x9 Sudoku board is valid according to standard Sudoku rules.

Problem

Given a 9x9 Sudoku board, determine if it is valid. Only the filled cells need to be validated based on three rules: each row must contain the digits 1-9 without repetition, each column must also contain the digits 1-9 without repetition, and each of the nine 3x3 sub-boxes of the grid must contain the digits 1-9 without repetition.

2. Solution Steps

1. Create three hash tables to track the numbers in each row, column, and 3x3 sub-box.

2. Iterate over each cell in the 9x9 board.

3. For each filled cell, check whether the number has already appeared in the current row, column, or sub-box.

4. If a number is repeated in any row, column, or sub-box, the Sudoku board is invalid.

5. If no violations are found, the board is valid.

3. Code Program

#include <stdio.h>
#include <stdlib.h>

// Function to check if a Sudoku board is valid
int isValidSudoku(char** board, int boardSize, int* boardColSize) {
    int row[9][9] = {0}, col[9][9] = {0}, box[9][9] = {0};

    for (int i = 0; i < boardSize; i++) {
        for (int j = 0; j < boardColSize[i]; j++) {
            if (board[i][j] != '.') {
                int num = board[i][j] - '1'; // Convert char to int
                int boxIndex = (i / 3) * 3 + j / 3;

                if (row[i][num] || col[j][num] || box[boxIndex][num]) {
                    return 0; // Invalid if number is already seen in row, col or box
                }

                row[i][num] = col[j][num] = box[boxIndex][num] = 1; // Mark the number as seen
            }
        }
    }
    return 1; // Valid Sudoku board
}

// Main function to test the isValidSudoku function
int main() {
    char* board[9] = {
        "53..7....",
        "6..195...",
        ".98....6.",
        "8...6...3",
        "4..8.3..1",
        "7...2...6",
        ".6....28.",
        "...419..5",
        "....8..79"
    };
    int boardColSize[9] = {9, 9, 9, 9, 9, 9, 9, 9, 9};
    printf("Is Valid Sudoku: %s\n", isValidSudoku(board, 9, boardColSize) ? "true" : "false");

    return 0;
}

Output:

Is Valid Sudoku: true

Explanation:

1. Initialize hash tables row, col, and box to track seen numbers in each row, column, and sub-box.

2. Iterate through each cell of the Sudoku board.

3. For filled cells, convert the character to an integer and check if it's already seen in the corresponding row, column, and sub-box.

4. If a repetition is found, return false indicating an invalid board.

5. If no repetitions are found after checking all cells, return true indicating a valid board.

6. The main function tests the isValidSudoku function with a sample board and prints the result.