Sudoku solver in C

_compile_and_run.sh

gcc -O3 -march=native -flto -funroll-loops -ffast-math -fomit-frame-pointer -finline-functions -fmerge-all-constants -falign-functions=32 -mtune=native -fno-rtti -o sudoku_solver sudoku.c 

chmod +x ./sudoku_solver

./sudoku_solver --board=530070000600195000098000060800060003400803001700020006060000280000419005000080079

job_script.slurm

#!/bin/bash
#SBATCH --job-name=sudoku_solver
#SBATCH --output=output.txt
#SBATCH --time=00:05:00
#SBATCH --ntasks=1
#SBATCH --cpus-per-task=1
#SBATCH --mem-per-cpu=2GB

make

BOARD="530070000600195000098000060800060003400803001700020006060000280000419005000080079"
./sudoku_solver --board=$BOARD

Makefile

# Makefile for Sudoku Solver

# Compiler
CC = gcc

# Compiler Flags
CFLAGS = -O3 -march=native -flto -funroll-loops -ffast-math -fomit-frame-pointer -finline-functions -fmerge-all-constants -ffunction-sections -fdata-sections -fstack-protector-strong -falign-functions=32

# Target executable
TARGET = sudoku_solver

# Source files
SRCS = sudoku.c

# Object files
OBJS = $(SRCS:.c=.o)

# Profile data directory
PROF_DIR = prof_data

# Profile data file
PROF_FILE = $(PROF_DIR)/default.profraw

# Default target
all: $(TARGET)

# Build the target executable
$(TARGET): $(OBJS)
	$(CC) $(CFLAGS) -o $(TARGET) $(OBJS)

# Compile source files to object files
%.o: %.c
	$(CC) $(CFLAGS) -c $< -o $@

# Clean target to remove generated files
clean:
	rm -f $(TARGET) $(OBJS)

# Profile guided optimization (PGO) steps
pgo_gen: $(SRCS)
	$(CC) $(CFLAGS) -fprofile-generate=$(PROF_DIR) -o $(TARGET)_gen $(SRCS)
	./$(TARGET)_gen --board=530070000600195000098000060800060003400803001700020006060000280000419005000080079

pgo_use: $(SRCS)
	$(CC) $(CFLAGS) -fprofile-use=$(PROF_DIR) -o $(TARGET) $(SRCS)

# PGO full process
pgo: pgo_gen pgo_use

# Phony targets
.PHONY: all clean pgo_gen pgo_use pgo

sudoku.c

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

#define SIZE 9

void print_board(int board[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        if (i % 3 == 0) {
            printf("+-------+-------+-------+\n");
        }
        for (int j = 0; j < SIZE; j++) {
            if (j % 3 == 0) {
                printf("| ");
            }
            printf("%d ", board[i][j]);
        }
        printf("|\n");
    }
    printf("+-------+-------+-------+\n");
}

int find_empty(int board[SIZE][SIZE], int *row, int *col) {
    for (*row = 0; *row < SIZE; (*row)++) {
        for (*col = 0; *col < SIZE; (*col)++) {
            if (board[*row][*col] == 0) {
                return 1;
            }
        }
    }
    return 0;
}

int is_valid(int board[SIZE][SIZE], int num, int row, int col) {
    for (int i = 0; i < SIZE; i++) {
        if (board[row][i] == num || board[i][col] == num) {
            return 0;
        }
    }

    int box_row_start = (row / 3) * 3;
    int box_col_start = (col / 3) * 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (board[box_row_start + i][box_col_start + j] == num) {
                return 0;
            }
        }
    }
    return 1;
}

int solve(int board[SIZE][SIZE]) {
    int row, col;
    if (!find_empty(board, &row, &col)) {
        return 1;
    }

    for (int num = 1; num <= SIZE; num++) {
        if (is_valid(board, num, row, col)) {
            board[row][col] = num;

            if (solve(board)) {
                return 1;
            }

            board[row][col] = 0;
        }
    }
    return 0;
}

void parse_board(const char *input, int board[SIZE][SIZE]) {
    for (int i = 0; i < SIZE * SIZE; i++) {
        board[i / SIZE][i % SIZE] = input[i] - '0';
    }
}

int main(int argc, char *argv[]) {
    if (argc != 2 || strncmp(argv[1], "--board=", 8) != 0) {
        printf("Usage: %s --board=530070000...\n", argv[0]);
        return 1;
    }

    const char *input = argv[1] + 8;
    if (strlen(input) != SIZE * SIZE) {
        printf("The board must be exactly 81 characters long.\n");
        return 1;
    }

    int board[SIZE][SIZE];
    parse_board(input, board);

    printf("Sudoku puzzle:\n");
    print_board(board);

    clock_t start_time = clock();

    if (solve(board)) {
        clock_t end_time = clock();
        double time_spent = (double)(end_time - start_time) / CLOCKS_PER_SEC * 1000; // Convert to milliseconds
        printf("\nSolved Sudoku puzzle:\n");
        print_board(board);
        printf("\nExecution time: %.3f ms\n", time_spent);
    } else {
        printf("No solution exists\n");
    }

    return 0;
}

sudoku_solver.md

Sudoku Solver

This project contains a C program to solve a Sudoku puzzle using a backtracking algorithm. It includes enhancements for printing the board in a specific format and measuring the execution time of the solver.

Algorithm

The algorithm employed is a classic backtracking approach:

1. Find Empty Cell: Search for the first empty cell (a cell with a value of 0) in the Sudoku grid.
2. Check Validity: For the current empty cell, attempt placing numbers from 1 to 9. For each number, check if placing that number violates the Sudoku rules:
   • The number must not already be present in the same row.
   • The number must not be present in the same column.
   • The number must not be present in the 3x3 subgrid that contains the cell.
3. Recursive Attempt: If placing the number is valid, place the number and recursively attempt to solve the rest of the grid.
4. Backtrack: If placing the number does not lead to a solution (i.e., the recursive call fails), remove the number (reset the cell to 0) and try the next number.
5. Solution Found: If all cells are filled correctly, the algorithm terminates, indicating that the solution is found.
6. No Solution: If the algorithm exhausts all possibilities and no valid number can be placed, it backtracks. If it backtracks from the first cell, it means no solution exists.

Files

• sudoku.c: The main C program containing the Sudoku solver and timing code.
• Makefile: Makefile to compile the C program.
• job_script.slurm: SLURM job script to build and run the Sudoku solver.
• README.txt: This file.

How to Compile and Run

To compile the Sudoku solver, you can use the provided Makefile. Simply run the following command in your terminal:

make

This will compile the sudoku.c program and create an executable named sudoku. You can then run the program using the following command:

./sudoku_solver --board=530070000600195000098000060800060003400803001700020006060000280000419005000080079

The output should look like the following:

Sudoku puzzle:
+-------+-------+-------+
| 5 3 0 | 0 7 0 | 0 0 0 |
| 6 0 0 | 1 9 5 | 0 0 0 |
| 0 9 8 | 0 0 0 | 0 6 0 |
+-------+-------+-------+
| 8 0 0 | 0 6 0 | 0 0 3 |
| 4 0 0 | 8 0 3 | 0 0 1 |
| 7 0 0 | 0 2 0 | 0 0 6 |
+-------+-------+-------+
| 0 6 0 | 0 0 0 | 2 8 0 |
| 0 0 0 | 4 1 9 | 0 0 5 |
| 0 0 0 | 0 8 0 | 0 7 9 |
+-------+-------+-------+

Solved Sudoku puzzle:
+-------+-------+-------+
| 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 |
+-------+-------+-------+

On a M3 Pro Macbook, the average runtime is 500us; on an Intel(R) Xeon(R) Gold 6226R CPU, this gets reduced to 250us.

Example:

./sudoku_solver --board=530070000600195000098000060800060003400803001700020006060000280000419005000080079