时间戳

首页 > 解决方案 > 解决数独的 C++ 程序

c++ - 解决数独的 C++ 程序

问题描述

我正在为数独求解器编写 C++ 代码。

该代码必须适用于 9x9、16x16 和 25x25 网格。我的代码仅适用于 9x9 网格。我不确定为什么。可能有人请帮助我。我想我需要以某种方式使 16x16 和 25x25 代码工作得更快。我该怎么做呢？

#include <iostream>
#include <vector>
#include <string>
#include <cmath>
using namespace std;

vector<int> tokenize(string s, string del);
void readAPuzzle(vector<vector<int>> &grid);
void printGrid(vector<vector<int>> grid);
bool isValid(int i, int j, vector<vector<int>> grid);
bool isValid(vector<vector<int>> grid);
bool search(vector<vector<int>> &grid);
int getFreeCellList(vector<vector<int>> grid, vector<pair<int, int>> &freeCellList);

int main()
{
  // Read a Sudoku puzzle
  vector<vector<int>> puzzle;
  readAPuzzle(puzzle);

  if (!isValid(puzzle))
    cout << "Invalid input" << endl;
  else if (search(puzzle)){
    printGrid(puzzle);
  }
  else
    cout << "No solution" << endl;

  return 0;
}

vector<int> tokenize(string s, string del)
{
    vector<int> row;

    int start = 0;
    int end = s.find(del);
    while (end != -1) {
        row.push_back(stoi( s.substr(start, end - start)));
        start = end + del.size();
        end = s.find(del, start);
    }
    row.push_back(stoi( s.substr(start, end - start)));
    return row;
}

void readAPuzzle(vector<vector<int>> &grid){
  string line;
  getline(cin, line);
  vector<int> firstRow = tokenize(line, " ");

  grid.push_back(firstRow);

  for(int i = 0; i < firstRow.size()-1; i++){
    getline(cin, line);
    vector<int> row = tokenize(line, " ");
    grid.push_back(row);
  }
}

/** Obtain a list of free cells from the puzzle */
int getFreeCellList(vector<vector<int>> grid, vector<pair<int, int>> &freeCellList)
{
  // 81 is the maximum number of free cells
  int numberOfFreeCells = 0;

  for (int i = 0; i < grid.size(); i++)
    for (int j = 0; j < grid.size(); j++)
      if (grid[i][j] == 0)
      {
        freeCellList[numberOfFreeCells].first = i;
        freeCellList[numberOfFreeCells].second = j;
        numberOfFreeCells++;
      }

  return numberOfFreeCells;
}

/** Print the values in the grid */
void printGrid(vector<vector<int>> grid)
{
  for (int i = 0; i < grid.size(); i++)
  {
    for (int j = 0; j < grid.size(); j++)
      cout << grid[i][j] << " ";
    cout << endl;
  }
}

/** Search for a solution */
bool search(vector<vector<int>> &grid)
{
  int k = 0; // Start from the first free cell
  bool found = false; // Solution found?

  const int n = grid.size();

  vector<pair<int, int>> freeCellList(n*n);

  int numberOfFreeCells = getFreeCellList(grid, freeCellList);

  while (!found)
  {
    int i = freeCellList[k].first;
    int j = freeCellList[k].second;
    if (grid[i][j] == 0)
      grid[i][j] = 1; // Start with 1

    if (isValid(i, j, grid))
    {
      if (k + 1 == numberOfFreeCells)
      { // No more free cells
        found = true; // A solution is found
      }
      else
      { // Move to the next free cell
        k++;
      }
    }
    else if (grid[i][j] < grid.size())
    {
      grid[i][j] = grid[i][j] + 1; // Check the next possible value
    }
    else
    { // grid[i][j] is 9, backtrack
      while (grid[i][j] == grid.size())
      {
        grid[i][j] = 0; // Reset to free cell
        if (k == 0)
        {
          return false; // No possible value
        }
        k--; // Backtrack
        i = freeCellList[k].first;
        j = freeCellList[k].second;
      }

      grid[i][j] = grid[i][j] + 1; // Check the next possible value
    }
  }

  return true; // A solution is found
}

/** Check whether grid[i][j] is valid in the grid */
bool isValid(int i, int j, vector<vector<int>> grid)
{
  // Check whether grid[i][j] is valid at the i's row
  for (int column = 0; column < grid.size(); column++)
    if (column != j && grid[i][column] == grid[i][j])
      return false;

  // Check whether grid[i][j] is valid at the j's column
  for (int row = 0; row < grid.size(); row++)
    if (row != i && grid[row][j] == grid[i][j])
      return false;


  int n = sqrt(grid.size());

  // Check whether grid[i][j] is valid in the 3 by 3 box
  for (int row = (i / n) * n; row < (i / n) * n + n; row++)
    for (int col = (j / n) * n; col < (j / n) * n + n; col++)
      if (row != i && col != j && grid[row][col] == grid[i][j])
        return false;

  return true; // The current value at grid[i][j] is valid
}

/** Check whether the fixed cells are valid in the grid */
bool isValid(vector<vector<int>> grid)
{
  // Check for duplicate numbers
  for (int i = 0; i < grid.size(); i++)
    for (int j = 0; j < grid.size(); j++)
      if (grid[i][j] != 0)
        if (!isValid(i, j, grid))
          return false;

  // Check whether numbers are in the range
  for (int i = 0; i < grid.size(); i++)
    for (int j = 0; j < grid.size(); j++)
      if ((grid[i][j] < 0) || (grid[i][j] > 9))
        return false;

  return true; // The fixed cells are valid
}

这是我到目前为止写的代码。

谢谢你。

标签： c++

解决方案

在bool isValid(vector<vector<int>>)你有

if ((grid[i][j] < 0) || (grid[i][j] > 9))
    return false;

即带有数字的网格> 9永远不会被认为是有效的。我不知道是否还有其他错误，但是当您只允许其中的数字时，[0,9]它不适用于16x16或25x25调整大小的网格。

您正在将网格按值传递给某些函数。您应该将它们作为 const 引用传递，以避免不必要的复制。

推荐阅读