求助：如何重载<运算符实现基于中心值的8数码谜题状态比较？

Hey there! Let's work through this 8-puzzle state comparison problem you're having. From what you shared, you want to define one 3x3 board state as "less than" another only when its center cell value is smaller than the other's, and you're trying to store these states in a queue—but your overloaded < operator isn't behaving as expected. Let's break this down step by step.

First, a quick check: are you using std::priority_queue? Because a regular std::queue doesn't care about ordering (it just processes elements in insertion order), so overloading < won't do anything there. If you're using a priority queue, that's where the comparison operator comes into play for sorting elements by priority.

Common Pitfalls & Fixes #

Let's start with the key mistakes people often make when overloading this operator, then share a corrected code example matching your header file structure.

1. Forgetting const on the Operator

Your comparison shouldn't modify either state, so the operator must be declared as a const member function. Without this, the priority queue (which works with const references) won't be able to use your overload.

2. Wrong Center Cell Index

Remember, 3x3 arrays use 0-based indexing—so the center cell is at board[1][1] (not [0][0] or [2][2]). Mixing this up will obviously break your comparison logic.

3. Misunderstanding Priority Queue Behavior

By default, std::priority_queue is a max-heap—meaning the "largest" element (per your < operator) is at the top. If you want the smallest center value to come first, you'll need to use std::greater<State> as the comparator (we'll show that in a usage example).

Corrected State Class Code #

Here's how to implement the overload properly within your header structure:

#ifndef STATE_H_INCLUDE
#define STATE_H_INCLUDE

#include <iostream>

class State {
private:
    int board[3][3]; // Stores the 3x3 puzzle state
public:
    // Constructor to initialize the board
    State(int initial[3][3]) {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                board[i][j] = initial[i][j];
            }
        }
    }

    // Overload < operator as a const member function
    bool operator<(const State& other) const {
        // Compare center cells: this state < other state iff our center is smaller
        return this->board[1][1] < other.board[1][1];
    }

    // Optional: Helper function to print the board for debugging
    void printBoard() const {
        for (int i = 0; i < 3; ++i) {
            for (int j = 0; j < 3; ++j) {
                std::cout << board[i][j] << " ";
            }
            std::cout << "\n";
        }
    }
};

#endif // STATE_H_INCLUDE

Usage Example #

Here's how to use this class with a priority queue to see the ordering in action:

#include <queue>
#include "State.h"

int main() {
    // Example board states with different center values
    int board1[3][3] = {{1,2,3}, {4,5,6}, {7,8,0}}; // Center: 5
    int board2[3][3] = {{0,1,2}, {3,4,5}, {6,7,8}}; // Center:4
    int board3[3][3] = {{2,3,4}, {5,7,6}, {8,0,1}}; // Center:7

    State s1(board1), s2(board2), s3(board3);

    // Default priority queue (max-heap: largest center first)
    std::priority_queue<State> max_pq;
    max_pq.push(s1);
    max_pq.push(s2);
    max_pq.push(s3);

    std::cout << "Priority Queue (Largest Center First):\n";
    while (!max_pq.empty()) {
        max_pq.top().printBoard();
        std::cout << "---\n";
        max_pq.pop();
    }

    // Min-heap (smallest center first) using std::greater
    std::priority_queue<State, std::vector<State>, std::greater<State>> min_pq;
    min_pq.push(s1);
    min_pq.push(s2);
    min_pq.push(s3);

    std::cout << "\nPriority Queue (Smallest Center First):\n";
    while (!min_pq.empty()) {
        min_pq.top().printBoard();
        std::cout << "---\n";
        min_pq.pop();
    }

    return 0;
}

Quick Troubleshooting #

If it's still not working:

• Double-check that you're using a priority_queue (not a regular queue).
• Verify that you're accessing the correct center cell (board[1][1]).
• Make sure your operator is marked const—this is a super common oversight.

内容的提问来源于stack exchange，提问作者Al Jawad Nafad