Sudoku solver by graph coloring theory

[BRN]

Hello everybody!

I have to implement a sudoku solver in C ++ taking advantage by graph coloring theory, where each number to insert is a color of the associated graph node. In particular I would like to use the Welsh-Powell algorithm.

I find myself in trouble starting with this project and I ask you some advice.

I should start from the adjacency matrix associated to the graph of a sudoku 9x9. To build it by hand is a really boring job. Do you know some fastest technique to do this?

Once the graph is modeled, then, how could I manage the numbers (i.e. colors) already attributed to the graph nodes? The W-P algorithm must not color these nodes, because they are already, but must consider their presence...

Do you have any idea to give me?

Thanks so much!

 

[jedishrfu]

So the application solves a sudoku puzzle. It doesn't generate it right?

First, I would start by searching around for examples of how others have done it.

The reason being is that your question is rather like asking how to build a car from scratch.

 

[FactChecker]

I should start from the adjacency matrix associated to the graph of a sudoku 9x9. To build it by hand is a really boring job. Do you know some fastest technique to do this?

Once the graph is modeled, then, how could I manage the numbers (i.e. colors) already attributed to the graph nodes? The W-P algorithm must not color these nodes, because they are already, but must consider their presence...

You only have to program in the adjacency matrix once. It shouldn't take more than a half-hour. It would take longer than that to devise an algorithm to construct the matrix.

When you have code for the W-P algorithm, it might be possible to describe how to initialize the problem, but until then, it is difficult.

 

[pbuk]

You only have to program in the adjacency matrix once. It shouldn't take more than a half-hour. It would take longer than that to devise an algorithm to construct the matrix.

I'm not so sure, that's an $81^2$ matrix. Plenty of scope for human error.

Do you know some fastest technique to do this?

The obvious strategy is to add all row adjacencies, then all column adjacencies, then all square adjacencies. Each of these steps is a simple nest of iterators with carefully selected bounds and step size.

 

[FactChecker]

I'm not so sure, that's an $81^2$ matrix. Plenty of scope for human error.

Oh! I stand corrected. I made a Sudoku solver and stored the arrangement in a completely different manner. I confused it with another puzzle solver.
Yes, you should make an algorithm to generate the matrix.

 

[jedishrfu]

An easy way to generate new sudoku puzzles is to start with a known solution and apply sudoku allowed row col exchanges and remap the numbers.

 

[Baluncore]

I think it is time for the Latin Square.
https://en.wikipedia.org/wiki/Latin_square

 

[BRN]

Hi everyone and thank you for your answers.

I made steps forward and now I can generate the adjacency matrix in this way:

matrix Graph::makeAdjMatrix(int nNodes, int matOrder, int blkOrder)
{
    matrix adjacencyMatrix(nNodes);
    for (int i = 0; i < nNodes; i++)
    {
            adjacencyMatrix[i].resize(nNodes);
    }

    // Map nodes links in rows and columns
    for (unsigned int i = 0; i < nNodes; i++)
    {
        for(unsigned int j = 0; j < nNodes; j++)
        {
            if(j >= (i/matOrder)*matOrder && j < (i/matOrder)*matOrder + matOrder)
                adjacencyMatrix[i][j] = 1.;
            else
            if(j%matOrder == i%matOrder)
                adjacencyMatrix[i][j] = 1.;
            else
                adjacencyMatrix[i][j] = 0;

        }
    }

    // Map nodes links in every single block
    for (unsigned int i = 0; i < nNodes; i++)
    {
        for(unsigned int r = 0; r < blkOrder; r++)
        {
            for(unsigned int k = 0; k < blkOrder; k++)
            {
                if((i/matOrder)%blkOrder == 0 )
                    for(unsigned int j = 0; j < blkOrder; j ++)
                    {
                        adjacencyMatrix[i + matOrder * r][(i/blkOrder)*blkOrder + j + matOrder * k] = 1.;
                    }
            }
        }
    }

    return adjacencyMatrix;
}

However, now, I have a problem in loading a matrix ...
This my code:

matrix InputData::readMatrix(const std::string& nameFile)
{
    std::ifstream inFile;
    inFile.open(nameFile);
    int row, column;
    inFile >> row >> column;

    matrix inputMatrix(row);

    if (row == column)
    {
        for (int i = 0; i < row; ++i)
        {
            for (int j = 0; j < column; ++j)
            {
                inFile >> inputMatrix[i][j];
            }
        }
    }
    else
        std::cout << "Invalid dimension! Only square matrix allowed." << std::endl;

    inFile.close();
    return inputMatrix;
}

where with "matrix" I defined

typedef std::vector<std::vector<int>> matrix;

This code don't work. What's wrong?

 

[BRN]

Ok, maybe it's better if I open a new thread for this issue. Just to not create confusion in this.