NEED HELP with C++ Sudoku Solver

Last edited on

Last edited on

Last edited on

Do you really want Puzzle to be an alias for a 9x9 array of sets? Put another way, does a Puzzle really consist of 81 sets of numbers?

Each row can contain the numbers 1-9 and there are 9 rows; that's nine sets of digits.
Each column can contain the numbers 1-9 and there are 9 columns; that's nine sets of digits.
Each section can contain the numbers 1-9 and there are 9 sections; that's nine sets of digits.

If you add those up, you get 27 sets. Where do the other 54 come into play?

Last edited on

I've said this before and I'll say it again. My favourite SuDoku method - The bool grids solution. Here is a rough outline of how to do it (I put it all in code tags to preserve formatting):

//Declare the grids. 
bool grids[9][9][9]; //You can declare it as a 3d array (I find that a bit confusing)
bool grid1[9][9], grid2[9][9], grid3[9][9] //etc... More typing, less confusing. 
//Make sure to set all these grids all equal to zero in every cell! 

//TACTIC ONE

//Each grid represent places where that number can and cannot go. Let's take your 
//puzzle as an example.
/*
1 - - 4 8 9 - - 6
7 3 - - - - - 4 -
- - - - - 1 2 9 5
- - 7 1 2 - 6 - -
5 - - 7 - 3 - - 8
- - 6 - 9 5 7 - -
9 1 4 6 - - - - -
- 2 - - - - - 3 7
8 - - 5 1 2 - - 4

We then look at each number in turn and mark = 1 on the appropriate grid where the number CANNOT go. Let's look at grid1[9][9] 
(I tried to format it nicely so you can see clearly): 
1 1 1  1 1 1  1 1 1 
1 1 1  1 1 1  0 1 0 
1 1 1  1 1 1  1 1 1

1 1 1  1 1 1  1 1 1 
1 1 0  1 1 1  1 0 0
1 1 1  1 1 1  0 0 0

1 1 1  1 1 1  1 1 1
1 1 1  1 1 1  0 1 1
1 1 1  1 1 1  1 1 1 
*/

Stage 1: You can mark off where numbers cannot go by searching the grid cell by cell for each number in turn. In this case, we would look for 1s in the grid. Each time a 1 is found, mark the entire row, column and 3x3 block as 1 (full) in the bool grid. If you find another number, mark that individual cell as 1 (full).
Stage 2 of tactic one: Any row, column or 3x3 cell in which only contains one zero (i.e. total of section == 8) can have that missing 0 filled in as the number on the grid. In this case, you can see we can immediately mark cell (3,5) and cell (7,8) as being 1s also.
Stage 3: If any cells were modified during stage 2, go back to stage 1. Keep doing this until either the puzzle is solved or we cannot fill any more squares in like this.

This is not the only method, but I like it (hope it was explained ok). I must admit, I don't understand what tactic 2 is? The way I understand it, it would be covered in tactic 1 anyway... So I must be not understanding it.

Last edited on

Try running the program for yourself and you'll see what i mean. The issue that i am having is not that this program as it is now is wrong, it works just fine: asks for a 9x9 sudoku and outputs a 9x9 sudoku.

The issue i have is how to make a function that goes through each row, column, and 3x3 square and performs tactic one and tactic two.

So, the logic isn't wrong... it just doesn't do what you want? Each row, column and 3x3 square consist of 9 sets of digits. Explain how your "tactic" should work, given that.

Script Coder (1468)

You could try a backtracking solution. I know it may not be the most efficient, but it will certainly teach you something about algorithms. Also, Mats do you have a link to where you learnt that?

Last edited on

@Script Coder - I just came up with it myself. I think that text I wrote outlines it quite well though (I think?). The method won't solve all puzzles, but where it doesn't solve, it gives you candidate numbers for when you need to find a solution with brute force.

@Ask Questions - Can you clarify method 2?

Last edited on

Last edited on

Can you just give me an example of actually doing tactic 2 on a row or whatever? I really don't understand lol. I can't give you advice on how to code a method I don't understand.

My solution posted above is an implementation of your tactic 1 btw.

Last edited on

ahh I was understanding tactic 2 successfully. That is already thoroughly covered in what I posted as a method for tactic 1. Perhaps my method is not the best for solving this for your class (even though it solves grids very very quickly!) because it won't do exactly what your assignment says. =/

Last edited on

I have redressed my understanding of the problem. While it isn't how I would approach the problem, I see what is required now, with the sets.

Is the signature for "tactic" functions supplied in the requirements, or can those be adjusted?

One of the major things your missing is that if you pass an object by value (which makes a copy of the object,) any change made to the copy will not be propagated to the original object. Have you encountered the idea of references yet?

[Edit: I seem to have misspoke again here. Since the "objects" you are passing are arrays, they follow a different set of rules. I guess that's a testament to how little I use arrays as opposed to other containers any more.]

Last edited on

Last edited on

In tacticOneOnSection on line 4 you create a local Puzzle object that has no relation to the Puzzle object you should be working on. I also believe you could simplify the function quite a bit.

Try the following:

bool tacticOneOnSection(PuzzleSection section)
{
    bool changed = false;

    for (unsigned i = 0; i < 9; ++i)
    {
        SetOfSmallInts* cell = section[i];

        if (isSingleton(*cell))
        {
            const int number = onlyMember(*cell);

            for (unsigned j = 0; j < 9; ++j)
                if (i != j && member(number, *section[j]))
                {
                    *section[j] = remove(number, *section[j]);
                    changed = true;
                }
        }
    }

    return changed;
}

bool tacticOne(Puzzle puzzle)
{
    bool changed = false;

    for (unsigned i = 0; i < 9; ++i)
    {
            PuzzleSection section;

            getRow(section, puzzle, i);
            if (tacticOneOnSection(section))
                changed = true;

            getColumn(section, puzzle, i);
            if (tacticOneOnSection(section))
                changed = true;

            getSquare(section, puzzle, i);
            if (tacticOneOnSection(section))
                changed = true;
    }

    return changed;
}

// test drive 'em.
int main()
{
    Puzzle p;
    readPuzzle(p);
    printPuzzle(p);
    std::cout << '\n';

    showPuzzle(p);
    std::cout << '\n';

    while (tacticOne(p))
    {
        showPuzzle(p);
        std::cout << '\n';

        printPuzzle(p);
        std::cout << '\n';
    }
}

With the puzzle you supplied above, the results look like this (with a slightly modified showPuzzle):

1-- 489 --6
73- --- -4-
--- --1 295

--7 12- 6--
5-- 7-3 --8
--6 -95 7--

914 6-- ---
-2- --- -37
8-- 512 --4

[1] [123456789] [123456789] [4] [8] [9] [123456789] [123456789] [6]
[7] [3] [123456789] [123456789] [123456789] [123456789] [123456789] [4] [123456789]
[123456789] [123456789] [123456789] [123456789] [123456789] [1] [2] [9] [5]
[123456789] [123456789] [7] [1] [2] [123456789] [6] [123456789] [123456789]
[5] [123456789] [123456789] [7] [123456789] [3] [123456789] [123456789] [8]
[123456789] [123456789] [6] [123456789] [9] [5] [7] [123456789] [123456789]
[9] [1] [4] [6] [123456789] [123456789] [123456789] [123456789] [123456789]
[123456789] [2] [123456789] [123456789] [123456789] [123456789] [123456789] [3] [7]
[8] [123456789] [123456789] [5] [1] [2] [123456789] [123456789] [4]

[1] [5] [25] [4] [8] [9] [3] [7] [6]
[7] [3] [2589] [2] [56] [6] [18] [4] [1]
[46] [468] [8] [3] [367] [1] [2] [9] [5]
[34] [489] [7] [1] [2] [48] [6] [5] [39]
[5] [49] [129] [7] [46] [3] [149] [12] [8]
[234] [4] [6] [8] [9] [5] [7] [12] [123]
[9] [1] [4] [6] [37] [78] [58] [258] [2]
[6] [2] [5] [89] [4] [48] [158] [3] [7]
[8] [67] [3] [5] [1] [2] [9] [6] [4]

15- 489 376
73- 2-6 -41
--8 3-1 295

--7 12- 65-
5-- 7-3 --8
-46 895 7--

914 6-- --2
625 -4- -37
8-3 512 964

[1] [5] [2] [4] [8] [9] [3] [7] [6]
[7] [3] [9] [2] [5] [6] [8] [4] [1]
[4] [6] [8] [3] [7] [1] [2] [9] [5]
[3] [8] [7] [1] [2] [4] [6] [5] [9]
[5] [9] [1] [7] [6] [3] [4] [2] [8]
[23] [4] [6] [8] [9] [5] [7] [1] [3]
[9] [1] [4] [6] [3] [7] [5] [8] [2]
[6] [2] [5] [9] [4] [8] [1] [3] [7]
[8] [7] [3] [5] [1] [2] [9] [6] [4]

152 489 376
739 256 841
468 371 295

387 124 659
591 763 428
-46 895 713

914 637 582
625 948 137
873 512 964

[1] [5] [2] [4] [8] [9] [3] [7] [6]
[7] [3] [9] [2] [5] [6] [8] [4] [1]
[4] [6] [8] [3] [7] [1] [2] [9] [5]
[3] [8] [7] [1] [2] [4] [6] [5] [9]
[5] [9] [1] [7] [6] [3] [4] [2] [8]
[2] [4] [6] [8] [9] [5] [7] [1] [3]
[9] [1] [4] [6] [3] [7] [5] [8] [2]
[6] [2] [5] [9] [4] [8] [1] [3] [7]
[8] [7] [3] [5] [1] [2] [9] [6] [4]

152 489 376
739 256 841
468 371 295

387 124 659
591 763 428
246 895 713

914 637 582
625 948 137
873 512 964

Last edited on