Building a Sudoku Solver in C++: Lesson 1 on Grid Data Structures and the ImGui Render Loop

Every sudoku project starts with the same question: how do you store the board? Skip past std::vector<std::vector<int>> because it feels Pythonic. A sudoku grid is exactly 81 cells, known at compile time, and std::array<std::array<int, 9>, 9> gives you bounds-checkable, stack-allocated storage with zero heap allocations and no pointer indirection. That single choice cascades through the rest of the codebase, and Lesson 1 is about getting it right before any solver logic enters the picture.

By the end of this lesson you will have a working 9x9 board on screen, with a 3x3 checkerboard background, fixed clues rendered in immutable white text, and editable blank cells that accept exactly one digit. No solver yet. No puzzle file loader. Just the data layout and the render loop, locked in well enough to support everything that comes later.

Why std::array, not std::vector

For a 9x9 board the size is fixed at compile time. std::vector introduces heap allocation, a size field, and a capacity field you do not need. Two nested 9-element std::arrays compile to 81 ints contiguous in memory, which the optimizer can vectorize and which you can pass by const reference cheaply. Benchmarks at -O2 show std::array access compiling to a single addressing instruction; std::vector<std::vector<int>> requires two pointer dereferences per access, which adds up across the thousands of reads a solver performs.

A common alternative is a flat std::array<int, 81> indexed as grid[row * 9 + col]. Both layouts have the same memory footprint, and both vectorize well. Pick the nested form for readability: grid[row][col] reads more naturally in the rendering code, and the cost is zero at runtime.

Define the type once and alias it everywhere:

#include <array>

using Grid = std::array<std::array<int, 9>, 9>;

Now Grid flows through every signature. The solver will take Grid&, the renderer will take const Grid&, and you never write the full nested type again.

The FixedMap problem

A sudoku puzzle has two kinds of cells: pre-filled clues, which the user cannot edit, and blank cells, which the user fills in. Every render needs to know which is which so it can disable input on clues and color them differently.

The naive approach encodes "this cell is fixed" inside the Grid itself, using negative numbers or some sentinel like -1. Reject that. The grid stores puzzle state and nothing else. Mixing a fixed-ness flag into the cell value couples display logic to data logic and breaks every solver algorithm that assumes cells contain numbers from 0 to 9 (with 0 meaning blank).

Use a parallel structure instead:

using FixedMap = std::array<std::array<bool, 9>, 9>;

FixedMap[row][col] is true when the cell is a clue from the original puzzle. Build it once at puzzle load and never modify it after construction. The renderer reads from it. The solver reads from it. Nothing writes to it after construction. That separation will save you hours in Lesson 3 when you start writing the constraint propagator and want to assert that no solver step ever mutates a fixed cell.

If you find yourself wanting a third state ("user-edited but not yet verified"), resist the urge to extend FixedMap into an enum. Add a separate DraftMap or, better, keep the user's draft in a separate Grid and treat the original puzzle as immutable input. Lesson 2 will lean on that separation hard.

RAII for GLFW and ImGui

GLFW and ImGui are C libraries with paired init and teardown calls. Forget one and you leak a window or corrupt the OpenGL context on shutdown. Wrap them in a single RAII class so the destructor handles cleanup unconditionally, even when an exception unwinds the stack.

#include <GLFW/glfw3.h>
#include "imgui.h"
#include "imgui_impl_glfw.h"
#include "imgui_impl_opengl3.h"

class App {
public:
    App();
    ~App();
    App(const App&) = delete;
    App& operator=(const App&) = delete;

    void run();

private:
    GLFWwindow* window_ = nullptr;
    void render_frame();
};

Deleted copy and assignment operators matter. You never want two App instances holding the same GLFWwindow*, since that is a double-free waiting to happen. Mark them deleted at the class level and the compiler enforces the rule for you.

The constructor initializes both libraries in order:

App::App() {
    if (!glfwInit()) {
        throw std::runtime_error("glfwInit failed");
    }

    glfwWindowHint(GLFW_CONTEXT_VERSION_MAJOR, 3);
    glfwWindowHint(GLFW_CONTEXT_VERSION_MINOR, 3);
    glfwWindowHint(GLFW_OPENGL_PROFILE, GLFW_OPENGL_CORE_PROFILE);

    window_ = glfwCreateWindow(720, 720, "Sudoku", nullptr, nullptr);
    if (!window_) {
        glfwTerminate();
        throw std::runtime_error("glfwCreateWindow failed");
    }

    glfwMakeContextCurrent(window_);
    glfwSwapInterval(1); // vsync

    IMGUI_CHECKVERSION();
    ImGui::CreateContext();
    ImGui::StyleColorsDark();
    ImGui_ImplGlfw_InitForOpenGL(window_, true);
    ImGui_ImplOpenGL3_Init("#version 330");
}

App::~App() {
    ImGui_ImplOpenGL3_Shutdown();
    ImGui_ImplGlfw_Shutdown();
    ImGui::DestroyContext();
    if (window_) {
        glfwDestroyWindow(window_);
    }
    glfwTerminate();
}

Notice the asymmetry: if glfwCreateWindow fails we call glfwTerminate before throwing, because the destructor will not run for an object whose constructor threw. Anything constructed successfully before the throw point unwinds normally; anything after the throw never existed and cannot leak. This is the same pattern documented in the GLFW introduction guide under initialization and termination.

The destructor order is the reverse of construction: shut down ImGui backends first, then the ImGui context, then the GLFW window, then GLFW itself. Get this order wrong and the program crashes on close. Most often the symptom is a segfault inside glfwTerminate because ImGui still holds a reference to the destroyed window.

The render loop

run() is small because every interesting decision lives in render_frame():

void App::run() {
    while (!glfwWindowShouldClose(window_)) {
        glfwPollEvents();
        ImGui_ImplOpenGL3_NewFrame();
        ImGui_ImplGlfw_NewFrame();
        ImGui::NewFrame();

        render_frame();

        ImGui::Render();
        int w, h;
        glfwGetFramebufferSize(window_, &w, &h);
        glViewport(0, 0, w, h);
        glClearColor(0.1f, 0.1f, 0.1f, 1.0f);
        glClear(GL_COLOR_BUFFER_BIT);
        ImGui_ImplOpenGL3_RenderDrawData(ImGui::GetDrawData());
        glfwSwapBuffers(window_);
    }
}

vsync caps the loop at 60 fps on most displays, which gives you 16.6ms per frame. A sudoku grid render takes well under 1ms on any modern machine, so over 90% of that budget sits idle. Do not be tempted to skip vsync; without it you will spin a CPU core at 100% redrawing the same static board thousands of times per second, which the laptop's fan will let you know about within seconds.

Rendering the 9x9 ImGui Table

ImGui's Tables API gives you fixed-width columns and per-cell control. Open a table with 9 columns, push 81 cells in a nested loop, and you have a board. The Tables demo lives inside the official ImGui demo window; the source code is in the ImGui repository under imgui_demo.cpp (search for ShowDemoWindowTables).

void render_grid(const Grid& grid, const FixedMap& fixed, Grid& draft) {
    ImGui::Begin("Sudoku");

    ImGuiTableFlags flags = ImGuiTableFlags_Borders | ImGuiTableFlags_SizingFixedFit;
    if (ImGui::BeginTable("sudoku_grid", 9, flags)) {
        for (int row = 0; row < 9; ++row) {
            ImGui::TableNextRow();
            for (int col = 0; col < 9; ++col) {
                ImGui::TableSetColumnIndex(col);
                render_cell(row, col, grid, fixed, draft);
            }
        }
        ImGui::EndTable();
    }

    ImGui::End();
}

SizingFixedFit tells ImGui to size columns to the widest cell content rather than stretching to fill the window. With a sudoku board you want square cells, so combine SizingFixedFit with a fixed-width font and an explicit cell padding via ImGui::PushStyleVar(ImGuiStyleVar_CellPadding, ...) to get uniform geometry across the 81 cells.

3x3 checkerboard background

The visual trick that makes a sudoku board read correctly is alternating background tints on the nine 3x3 boxes. Without it the user cannot distinguish row 3 column 4 from row 4 column 4 at a glance. Compute the box index and shade accordingly:

static ImU32 box_color(int row, int col) {
    int box_index = (row / 3) + (col / 3);
    bool dark = (box_index % 2) == 0;
    return dark
        ? IM_COL32(40, 40, 50, 255)
        : IM_COL32(55, 55, 65, 255);
}

(row / 3) + (col / 3) produces the checkerboard pattern because adjacent boxes differ by 1 on one axis. Inside render_cell, paint the cell background before drawing any content:

void render_cell(int row, int col, const Grid& grid, const FixedMap& fixed, Grid& draft) {
    ImGui::TableSetBgColor(ImGuiTableBgTarget_CellBg, box_color(row, col));
    // ... draw cell content
}

TableSetBgColor with CellBg target paints just this cell, leaving table borders intact. The result is the familiar nine-box visual without any custom drawing primitives.

Fixed cells in white text

Fixed clues should look immutable: bold, white, not editable. Render them as plain text inside the cell:

if (fixed[row][col]) {
    ImGui::PushStyleColor(ImGuiCol_Text, IM_COL32(255, 255, 255, 255));
    ImGui::Text("%d", grid[row][col]);
    ImGui::PopStyleColor();
    return;
}

ImGui::Text is read-only and lays out at the cursor position, which TableSetColumnIndex already moved into the cell. No InputText, no editable state, no chance of the user accidentally typing into a clue.

Editable cells and the PushID/PopID problem

This is where most beginners get burned. ImGui identifies widgets by hashing their label string, and two InputText widgets with the same label collide: ImGui treats them as the same widget, focus jumps between them, and edits in cell (1,2) appear in cell (7,5). The standard fix is PushID / PopID, which mixes a unique integer into the widget's identifier hash:

int cell_id = row * 9 + col;
ImGui::PushID(cell_id);

char buf[2] = {0};
if (draft[row][col] != 0) {
    buf[0] = '0' + draft[row][col];
}

ImGui::SetNextItemWidth(40.0f);
ImGuiInputTextFlags input_flags = ImGuiInputTextFlags_CharsDecimal
                                | ImGuiInputTextFlags_AutoSelectAll;
if (ImGui::InputText("##cell", buf, sizeof(buf), input_flags)) {
    if (buf[0] >= '1' && buf[0] <= '9') {
        draft[row][col] = buf[0] - '0';
    } else if (buf[0] == '\0') {
        draft[row][col] = 0;
    }
}

ImGui::PopID();

Three details matter. The ##cell label hides the visible text (everything after ## is ID-only). PushID(cell_id) makes each cell's identifier unique across the 81-cell loop. CharsDecimal rejects letters at the input layer, so you only need to validate the 1-9 range rather than parsing arbitrary text.

AutoSelectAll is a small detail with a big UX payoff: when the user tabs into a cell, the existing digit is selected, so typing a new digit overwrites it instead of appending. Without that flag, entering 5 into a cell that already shows 3 produces 35 and then truncates because buf is only 2 bytes. The result feels broken even though no data is lost.

Pitfalls to flag before Lesson 2

The first pitfall is forgetting PopID for some early-return paths. If fixed[row][col] is true and you return from render_cell after PushID, the ID stack stays unbalanced and the next frame asserts in debug or silently corrupts widget state in release. Either move PushID after the fixed-cell branch, or pair it with an RAII guard:

struct IdGuard {
    explicit IdGuard(int id) { ImGui::PushID(id); }
    ~IdGuard() { ImGui::PopID(); }
    IdGuard(const IdGuard&) = delete;
    IdGuard& operator=(const IdGuard&) = delete;
};

The second pitfall is mutating grid directly from the input handler. Keep a draft Grid that the user edits and a separate puzzle Grid that holds the original clues. Lesson 2 will introduce a verify step that checks the draft against the solver's solution; if the user edits the same array the solver mutates, you cannot tell user input from solver output. Keep them separate from the start.

The third pitfall is sizing. Without SetNextItemWidth(40.0f), ImGui sizes the InputText to fill the cell, and the column widths drift as the user types longer values. Even with CharsDecimal limiting input to one character, the underlying buffer is sized for two, and the input field reserves space for both. Pin the width explicitly.

Verifying the render

Run the binary. You should see a 720x720 window with nine 3x3 boxes in a checkerboard pattern, fixed digits in bright white, blank cells with focus highlights when you click them. Type a digit into a blank cell, the digit appears. Tab to another blank cell, the previous edit persists. Tab into a fixed cell, nothing happens.

If editing one cell changes another cell's value, you have forgotten PushID somewhere. If the window flickers, you have a mismatched Begin / End or BeginTable / EndTable pair. If the program crashes on close, the destructor order in App::~App is wrong: ImGui shutdown must happen before glfwTerminate.

A working Lesson 1 ends here, with a board you can edit but no solver, no puzzle loader, and no validation. Lesson 2 will introduce the puzzle file format (one common choice is the 81-character text format used by Project Euler problem 96) and the backtracking solver that fills in blank cells while leaving fixed cells alone. The data layout choices made in this lesson, Grid as std::array<std::array<int, 9>, 9> and FixedMap as a parallel std::array<std::array<bool, 9>, 9>, are what make that solver clean to write.

References: