也许有用之九宫格在线求解

前言

为什么要写这样一个工具，主要是我有一个朋友，他玩游戏的时候被九宫格坑了许久，找工具又发现全是介绍算法的，一气之下决心写个工具一劳永逸，正好我又会写点程序，于是我们一拍即合＼(￣▽￣)／。

在线访问：九宫格求解
项目地址：maybe-toolbox/jiugongge

一、基本概念

1. 问题定义

九宫格问题其实常被叫做八数码问题（8 puzzle problem），所以直接搜九宫格求解不一定会得到想要的结果。而当我们想描述该问题时可以给出以下定义：在一个3×3的棋盘上，摆有八个棋子，每个棋子上标有1至8的某一数字，不同棋子上标的数字不相同。棋盘上还有一个空格，与空格相邻的棋子可以移到空格中。要求解决的问题是：给出一个初始状态和一个目标状态，找出一种从初始转变成目标状态的移动棋子步数最少的移动步骤。

当然，具体的来看，由于不同游戏九宫格情况也不同，我们实际上需要面对的情况是，棋子上数字可能为 1-9 任一唯一数字，其中有一个数字会代表空白格，将其记为初始状态，保持代表空白格数字不变，改变数字顺序，最终确定下目标状态，其与初始状态间仅是数字顺序不同，找到这样的，从初始状态变为目标状态的移动步骤，即为求解成功。

2. 状态标识

在计算机中，我们可以用以下方式表示八数码问题的状态：

• 矩阵表示：使用3×3的二维数组
• 字符串表示：将矩阵按行展开成一维字符串
• 整数表示：将状态编码为9位数字（0表示空格）

3. 合法移动规则

• 空格只能与相邻的数字方块交换位置
• 相邻定义为上下左右四个方向
• 不能进行对角线移动
• 不能移出棋盘范围

4. 问题复杂度

• 总状态数：9! = 362880种可能状态
• 可达状态数：9!/2 = 181440种状态
• 状态空间巨大，需要高效的搜索算法

二、问题可解性判断

是的，九宫格问题可能是无解的，这就是在看岔了格子图片导致死活解不出来所收获的惨痛教训。而判断的方法很简单，就是计算棋盘逆序数，有请 《线性代数》之逆序数！

1. 逆序数定义

逆序数是指在一个序列中，前面的数字比后面的数字大的对数。在八数码问题中，我们计算除空格外的数字序列的逆序数以此判断初始状态及目标状态是否有解。

2. 奇偶性规则

• 如果初始状态和目标状态的逆序数奇偶性相同，则问题有解
• 如果奇偶性不同，则问题无解
• 这个规则可以避免对无解状态进行无效搜索

3. 实际应用示例

例如，对于状态：

2 8 3
1 6 4
7 0 5

计算逆序数时，将空格（0）排除，得到序列：2,8,3,1,6,4,7,5
逆序对：(2,1), (8,3), (8,1), (8,6), (8,4), (8,7), (8,5), (3,1), (6,4), (6,5), (7,5)
共11个逆序对，为奇数。

4. 为什么

我相信一定有好学宝宝想要知道为什么计算逆序数就可以判断九宫格是否有解。很遗憾，作为一个程序员，我暂时没研究明白。但是很高兴，有前人的智慧相助，请欣赏：

• 算法之美-八数码问题
• 八数码难题（8 puzzle）有无解的严格证明、求解算法设计及其他

三、IDA*算法求解

以下是基于 IDA* 算法求解九宫格问题的 nodejs 终端程序的具体实现，至于为什么是 IDA* 算法见上一段的 为什么 中的文章。

// 八数码问题求解程序 - 基于IDA*算法和曼哈顿距离
const readline = require('readline');

// 创建readline接口
const rl = readline.createInterface({
  input: process.stdin,
  output: process.stdout
});

// 设置输入输出编码为utf-8
process.stdin.setEncoding('utf-8');
process.stdout.setEncoding('utf-8');

// 封装readline.question为Promise
function question(prompt) {
  return new Promise((resolve) => {
    rl.question(prompt, (answer) => {
      resolve(answer);
    });
  });
}

// 封装keyInYNStrict为Promise
async function keyInYNStrict(prompt) {
  while (true) {
    const answer = await question(prompt);
    const normalized = answer.toLowerCase().trim();
    if (normalized === 'y' || normalized === 'yes') return true;
    if (normalized === 'n' || normalized === 'no') return false;
    console.log('请输入 y/n');
  }
}

// 汉化设置
const LANG = 'zh';
const TEXT = {
  zh: {
    title: '八数码问题求解程序',
    initialStatePrompt: '[初始状态输入]',
    targetStatePrompt: '[目标状态输入]',
    inputMethod: '请选择输入方式：',
    inputMethod1: '1) 完整输入（含0）',
    inputMethod2: '2) 指定数字+空白位置',
    selectOption: '选项：',
    inputFullState: '请输入完整状态（含0，空格分隔）：',
    inputNumbersPrompt: '请输入1-9的数字序列（空格分隔）：',
    inputBlankIndex: '请输入空白位置索引（0-8）：',
    solving: '正在求解中...',
    solutionFound: '✅ 找到最优解（%s步）',
    timeUsed: '🕒 耗时：%s秒',
    statesExplored: '🔍 探索状态数：%s',
    pathPreview: '🗺️ 路径预览：',
    stepFormat: 'Step %d (%s):',
    directionMap: { up: '↑', down: '↓', left: '←', right: '→' },
    noSolution: '❌ 无解：',
    inversionMismatch: '初始与目标状态的逆序数奇偶性不一致',
    inversionInfo: 'ℹ️ 初始逆序数：%s（%s） 目标逆序数：%s（%s）',
    oddEven: { odd: '奇', even: '偶' },
    invalidFormat: '格式错误：',
    duplicateDigits: '输入包含重复数字',
    missingDigits: '输入缺少必要数字',
    invalidBlank: '空白位置索引无效',
    outOfRange: '第%d个数字应为1-8，实际输入为%s',
    continuePrompt: '按Enter键继续...',
    searchTimeout: '搜索超时，是否继续？(y/n)：',
    maxStepsReached: '已达到最大搜索深度（%s步），复杂度较高',
  }
};

// 工具函数
function t(key, ...args) {
  const text = TEXT[LANG][key];
  if (typeof text === 'string' && args.length > 0) {
    return text.replace(/%s/g, () => args.shift());
  }
  return text;
}

// 打印3x3棋盘
function printBoard(state) {
  for (let i = 0; i < 3; i++) {
    console.log(state.slice(i * 3, i * 3 + 3).join(' '));
  }
}

// 打印移动步骤对比
function printStep(step, direction, prevState, nextState) {
  console.log(t('stepFormat', step, t('directionMap')[direction]));
  
  // 格式化为左右对比的形式
  for (let i = 0; i < 3; i++) {
    const left = prevState.slice(i * 3, i * 3 + 3).join(' ');
    const right = nextState.slice(i * 3, i * 3 + 3).join(' ');
    const separator = i === 1 ? ' → ' : '   ';
    console.log(`${left}${separator}${right}`);
  }
  console.log('');
}

// 计算逆序数
function getInversionCount(state) {
  const arr = state.filter(x => x !== 0); // 不考虑0
  let count = 0;
  
  for (let i = 0; i < arr.length; i++) {
    for (let j = i + 1; j < arr.length; j++) {
      if (arr[i] > arr[j]) {
        count++;
      }
    }
  }
  
  return count;
}

// 检查初始状态和目标状态是否可解
function isSolvable(initialState, targetState) {
  const initialInversion = getInversionCount(initialState);
  const targetInversion = getInversionCount(targetState);
  
  // 逆序数奇偶性必须一致
  return initialInversion % 2 === targetInversion % 2;
}

// 验证输入状态有效性
function validateState(state, isFullInput = true) {
  // 检查长度
  if (state.length !== 9) {
    return { valid: false, error: t('invalidFormat') };
  }
  
  // 检查数字范围和唯一性
  const digits = new Set();
  for (let i = 0; i < state.length; i++) {
    if (isFullInput && (state[i] < 0 || state[i] > 8)) {
      return { valid: false, error: t('outOfRange', i + 1, state[i]) };
    } else if (!isFullInput && (state[i] < 1 || state[i] > 9)) {
      return { valid: false, error: t('outOfRange', i + 1, state[i]) };
    }
    
    if (digits.has(state[i])) {
      return { valid: false, error: t('duplicateDigits') };
    }
    
    digits.add(state[i]);
  }
  
  if (isFullInput && !digits.has(0)) {
    return { valid: false, error: t('missingDigits') };
  }
  
  return { valid: true };
}

// 曼哈顿距离启发函数
function manhattanDistance(state, goal) {
  let distance = 0;
  
  // 为每个数字计算目标位置和当前位置之间的曼哈顿距离
  for (let i = 0; i < state.length; i++) {
    const value = state[i];
    if (value !== 0) { // 跳过空格
      const currentPos = { x: i % 3, y: Math.floor(i / 3) };
      
      // 在目标状态中找到该数字的位置
      const goalIndex = goal.indexOf(value);
      const goalPos = { x: goalIndex % 3, y: Math.floor(goalIndex / 3) };
      
      // 计算曼哈顿距离
      distance += Math.abs(currentPos.x - goalPos.x) + Math.abs(currentPos.y - goalPos.y);
    }
  }
  
  return distance;
}

// 获取可能的移动方向
function getPossibleMoves(state) {
  const blankIndex = state.indexOf(0);
  const x = blankIndex % 3;
  const y = Math.floor(blankIndex / 3);
  const moves = [];
  
  // 上
  if (y > 0) moves.push('up');
  // 下
  if (y < 2) moves.push('down');
  // 左
  if (x > 0) moves.push('left');
  // 右
  if (x < 2) moves.push('right');
  
  return moves;
}

// 应用移动并返回新状态
function applyMove(state, move) {
  const newState = [...state];
  const blankIndex = state.indexOf(0);
  const x = blankIndex % 3;
  const y = Math.floor(blankIndex / 3);
  
  let newBlankIndex;
  
  switch (move) {
    case 'up':
      newBlankIndex = blankIndex - 3;
      break;
    case 'down':
      newBlankIndex = blankIndex + 3;
      break;
    case 'left':
      newBlankIndex = blankIndex - 1;
      break;
    case 'right':
      newBlankIndex = blankIndex + 1;
      break;
  }
  
  // 交换空白位置和移动位置
  newState[blankIndex] = newState[newBlankIndex];
  newState[newBlankIndex] = 0;
  
  return newState;
}

// 生成状态哈希指纹 (数组转为字符串)
function getStateHash(state) {
  return state.join('');
}

// IDA* 算法实现
function idaStar(initialState, goalState) {
  const startTime = Date.now();
  let statesExplored = 0;
  let path = [];
  let bound = manhattanDistance(initialState, goalState);
  const maxDepth = 100; // 最大搜索深度
  let shouldContinue = true;
  
  // DFS 搜索函数
  function search(state, g, bound, path, visited) {
    statesExplored++;
    
    // 检查是否应该终止搜索
    if (!shouldContinue) {
      return { result: 'timeout', path, statesExplored };
    }
    
    // 检查是否超时（每10000个状态检查一次）
    if (statesExplored % 10000 === 0 && (Date.now() - startTime) > 5000) {
      console.log(t('maxStepsReached', path.length));
      // 这里需要异步交互，但在递归中使用异步会很复杂
      // 所以我们标记需要交互，并在顶层处理
      shouldContinue = false;
      return { result: 'need_input', path, statesExplored };
    }
    
    const f = g + manhattanDistance(state, goalState);
    
    // 如果评估函数值超过bound，返回新的bound
    if (f > bound) {
      return { result: 'bound', newBound: f };
    }
    
    // 如果达到目标状态，返回路径
    if (JSON.stringify(state) === JSON.stringify(goalState)) {
      return { result: 'found', path, statesExplored };
    }
    
    // 如果达到最大搜索深度
    if (g >= maxDepth) {
      return { result: 'depth_limit' };
    }
    
    // 记录当前状态的访问
    const stateHash = getStateHash(state);
    visited.add(stateHash);
    
    let min = Infinity;
    
    // 尝试所有可能的移动
    const moves = getPossibleMoves(state);
    for (const move of moves) {
      const nextState = applyMove(state, move);
      const nextStateHash = getStateHash(nextState);
      
      // 跳过已访问状态
      if (visited.has(nextStateHash)) continue;
      
      // 添加到路径
      path.push({ state: [...state], move, nextState: [...nextState] });
      
      // 递归搜索
      const result = search(nextState, g + 1, bound, path, new Set(visited));
      
      if (result.result === 'found' || result.result === 'timeout' || result.result === 'need_input') {
        return result;
      }
      
      if (result.result === 'bound') {
        min = Math.min(min, result.newBound);
      }
      
      // 从路径中移除
      path.pop();
    }
    
    return { result: 'bound', newBound: min };
  }
  
  // 修改为返回Promise，以支持异步交互
  return {
    async solve() {
      while (true) {
        path = [];
        shouldContinue = true;
        
        const result = search(initialState, 0, bound, path, new Set());
        
        if (result.result === 'found') {
          return { ...result, timeUsed: (Date.now() - startTime) / 1000 };
        }
        
        if (result.result === 'need_input') {
          // 处理需要用户交互的情况
          const continueSearch = await keyInYNStrict(t('searchTimeout'));
          if (!continueSearch) {
            return { result: 'timeout', path: result.path, statesExplored: result.statesExplored, timeUsed: (Date.now() - startTime) / 1000 };
          }
          
          // 继续搜索
          continue;
        }
        
        if (result.result === 'timeout') {
          return { ...result, timeUsed: (Date.now() - startTime) / 1000 };
        }
        
        if (result.result === 'depth_limit') {
          return { result: 'depth_limit', timeUsed: (Date.now() - startTime) / 1000 };
        }
        
        if (result.newBound === Infinity) {
          return { result: 'no_solution', timeUsed: (Date.now() - startTime) / 1000 };
        }
        
        bound = result.newBound;
      }
    }
  };
}

// 主函数改为异步
async function main() {
  console.clear();
  console.log(`\n===== ${t('title')} =====\n`);
  
  // ===== 初始状态输入 =====
  console.log(t('initialStatePrompt'));
  console.log(t('inputMethod'));
  console.log(t('inputMethod1'));
  console.log(t('inputMethod2'));
  const initialInputOption = await question(t('selectOption'));
  
  let initialState;
  
  if (initialInputOption === '1') {
    // 完整输入模式
    const input = await question(t('inputFullState'));
    initialState = input.trim().split(/\s+/).map(Number);
    
    const validation = validateState(initialState);
    if (!validation.valid) {
      console.log(validation.error);
      await question(t('continuePrompt'));
      rl.close();
      return;
    }
  } else if (initialInputOption === '2') {
    // 指定数字+空白位置模式
    const input = await question(t('inputNumbersPrompt'));
    const numbers = input.trim().split(/\s+/).map(Number);
    
    if (numbers.length !== 9) {
      console.log(t('invalidFormat'));
      await question(t('continuePrompt'));
      rl.close();
      return;
    }
    
    const validation = validateState(numbers, false);
    if (!validation.valid) {
      console.log(validation.error);
      await question(t('continuePrompt'));
      rl.close();
      return;
    }
    
    const blankIndexStr = await question(t('inputBlankIndex'));
    const blankIndex = parseInt(blankIndexStr);
    
    if (isNaN(blankIndex) || blankIndex < 0 || blankIndex > 8) {
      console.log(t('invalidBlank'));
      await question(t('continuePrompt'));
      rl.close();
      return;
    }
    
    // 复制数组并将空白位置设置为0
    initialState = [...numbers];
    initialState[blankIndex] = 0;
  } else {
    console.log(t('invalidFormat'));
    await question(t('continuePrompt'));
    rl.close();
    return;
  }
  
  console.log('\n初始状态:');
  printBoard(initialState);
  console.log('');
  
  // ===== 目标状态输入 =====
  console.log(t('targetStatePrompt'));
  console.log(t('inputMethod'));
  console.log(t('inputMethod1'));
  console.log(t('inputMethod2'));
  const targetInputOption = await question(t('selectOption'));
  
  let targetState;
  
  if (targetInputOption === '1') {
    // 完整输入模式
    const input = await question(t('inputFullState'));
    targetState = input.trim().split(/\s+/).map(Number);
    
    const validation = validateState(targetState);
    if (!validation.valid) {
      console.log(validation.error);
      await question(t('continuePrompt'));
      rl.close();
      return;
    }
  } else if (targetInputOption === '2') {
    // 指定数字+空白位置模式
    const input = await question(t('inputNumbersPrompt'));
    const numbers = input.trim().split(/\s+/).map(Number);
    
    if (numbers.length !== 9) {
      console.log(t('invalidFormat'));
      await question(t('continuePrompt'));
      rl.close();
      return;
    }
    
    const validation = validateState(numbers, false);
    if (!validation.valid) {
      console.log(validation.error);
      await question(t('continuePrompt'));
      rl.close();
      return;
    }
    
    const blankIndexStr = await question(t('inputBlankIndex'));
    const blankIndex = parseInt(blankIndexStr);
    
    if (isNaN(blankIndex) || blankIndex < 0 || blankIndex > 8) {
      console.log(t('invalidBlank'));
      await question(t('continuePrompt'));
      rl.close();
      return;
    }
    
    // 复制数组并将空白位置设置为0
    targetState = [...numbers];
    targetState[blankIndex] = 0;
  } else {
    console.log(t('invalidFormat'));
    await question(t('continuePrompt'));
    rl.close();
    return;
  }
  
  console.log('\n目标状态:');
  printBoard(targetState);
  console.log('');
  
  // ===== 验证可解性 =====
  if (!isSolvable(initialState, targetState)) {
    console.log(t('noSolution'), t('inversionMismatch'));
    
    const initialInversion = getInversionCount(initialState);
    const targetInversion = getInversionCount(targetState);
    
    console.log(
      t(
        'inversionInfo',
        initialInversion,
        t('oddEven')[initialInversion % 2 ? 'odd' : 'even'],
        targetInversion,
        t('oddEven')[targetInversion % 2 ? 'odd' : 'even']
      )
    );
    
    await question(t('continuePrompt'));
    rl.close();
    return;
  }
  
  // ===== 求解 =====
  console.log(t('solving'));
  console.log(initialState);
  const solver = idaStar(initialState, targetState);
  const solution = await solver.solve();
  
  if (solution.result === 'found') {
    console.log(t('solutionFound', solution.path.length));
    console.log(t('timeUsed', solution.timeUsed.toFixed(2)));
    console.log(t('statesExplored', solution.statesExplored));
    console.log(t('pathPreview'));
    
    console.log('Initial:');
    printBoard(initialState);
    console.log('');
    
    // 打印每一步
    for (let i = 0; i < solution.path.length; i++) {
      const step = solution.path[i];
      printStep(i + 1, step.move, step.state, step.nextState);
    }
  } else if (solution.result === 'no_solution') {
    console.log(t('noSolution'));
  } else if (solution.result === 'timeout') {
    console.log(t('maxStepsReached', solution.path.length));
  }
  
  await question(t('continuePrompt'));
  rl.close();
}

// 运行程序
main().catch(err => {
  console.error('程序发生错误:', err);
  rl.close();
});

四、总结

希望有用，我们下次再见 ヾ(￣▽￣)ByeBye

参考文献

1. Hart, P. E., Nilsson, N. J., & Raphael, B. (1968). A formal basis for the heuristic determination of minimum cost paths.
2. Korf, R. E. (1985). Depth-first iterative-deepening: An optimal admissible tree search.
3. Pearl, J. (1984). Heuristics: Intelligent Search Strategies for Computer Problem Solving.