C++

Forum

 
Making a sudoku 4x4 combinations lister

jadmacro (10)
I am trying to make a c++ program to list all possible combinations for a 4x4 sudoku solver. This is how a 4x4 sudoku works,

You have 16 numbers that make a square, each one is a different number 1-16. All numbers in row, column, and diagonal have to add up to 34, and the 4 squares have to add up to 34. Example:

1 4 14 15
13 16 2 3
8 5 11 10
12 9 7 6

So I'm trying to make a program that will find all the possible combinations, store them in a 2 dimensional array, and then print out a few of them to make sure it works.

Does anybody have any tips for me on how I could accomplish this? Or has anybody made/could make a program that already does this that I could look off of and learn from?

Thanks a lot.
Bazzy (6281)
Try with the next_permutation STL algorithm
http://www.cplusplus.com/reference/algorithm/next_permutation.html
Last edited on
tition (887)
Edited the code:

Edited the code a second time. I had overlooked that you need to check the diagonals too! Now it checks them as well

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
 
// tempCPP.cpp : Definiert den Einstiegspunkt für die Konsolenanwendung.
//

#include "stdafx.h"
#include <iostream>
#include <limits>
int NumSudokus=0;
struct FourByFourInts
{
public:
	int elements[4][4];
	FourByFourInts()
	{
		for (int i=0;i<4;i++)
		{
			for (int j=0;j<4;j++)
			{
				this->elements[i][j]=-1;
			}
		}
	}
};
void fillInPosition(bool* AlreadyUsed, int row, int col,FourByFourInts*sudoku);

int _tmain(int argc, _TCHAR* argv[])
{
	FourByFourInts sudoku;
	bool AlreadyUsed[16];
	for (int i=0;i<16;i++){AlreadyUsed[i]=false;}
	fillInPosition(AlreadyUsed,0,0,&sudoku);	
  std::cout << "Press ENTER to continue...";
  std::cin.ignore( std::numeric_limits<std::streamsize>::max(), '\n' );
	return 0;
}



void YourFavourite4x4arrayPrintOutFunction(FourByFourInts*sudoku, bool ShouldPause)
{
	for (int i=0;i<4;i++)
	{
		for (int j=0;j<4;j++)
		{
			std::cout <<sudoku->elements[i][j]<<" ";
		}
		std::cout<<"\n";
	}
	std::cout<<"\n";
	NumSudokus++;
	std::cout<<NumSudokus<<"\n";
}

bool Accumulate(int& Accumulator, int row, int col, FourByFourInts*sudoku)
{
	if (sudoku->elements[row][col]==-1)
	{return true;}
	Accumulator+=sudoku->elements[row][col];
	return false;
}

bool IsAPlausibleRow(int row, FourByFourInts*sudoku)
{
	int Accumulator=0;
	for (int i=0;i<4;i++)
	{
		if (Accumulate(Accumulator,row,i,sudoku)){return true;}
		if (Accumulator>34){return false;}
	}
	return (Accumulator==34);
}

bool IsAPlausibleCol(int col, FourByFourInts*sudoku)
{
	int Accumulator=0;
	for (int i=0;i<4;i++)
	{
		if (Accumulate(Accumulator,i,col,sudoku)){return true;}
		if (Accumulator>34){return false;}
	}
	return (Accumulator==34);
}
bool IsAPlausible2x2Square(int UpperRightCornerRow, int UpperRightCornerCol, FourByFourInts*sudoku)
{
	int	Accumulator=0;
	if (Accumulate(Accumulator,UpperRightCornerRow,UpperRightCornerCol,sudoku)){return true;}
	if (Accumulate(Accumulator,UpperRightCornerRow,UpperRightCornerCol+1,sudoku)){return true;}
	if (Accumulate(Accumulator,UpperRightCornerRow+1,UpperRightCornerCol,sudoku)){return true;}
	if (Accumulator>=34){return false;}
	if (Accumulate(Accumulator,UpperRightCornerRow+1,UpperRightCornerCol+1,sudoku)){return true;}
	return (Accumulator==34);
}

bool IsAPlausibleDiagonal1(FourByFourInts*sudoku)
{
	int	Accumulator=0;
	if (Accumulate(Accumulator,0,0,sudoku)){return true;}
	if (Accumulate(Accumulator,1,1,sudoku)){return true;}
	if (Accumulate(Accumulator,2,2,sudoku)){return true;}
	if (Accumulator>=34){return false;}
	if (Accumulate(Accumulator,3,3,sudoku)){return true;}
	return (Accumulator==34);
}

bool IsAPlausibleDiagonal2(FourByFourInts*sudoku)
{
	int	Accumulator=0;
	if (Accumulate(Accumulator,0,3,sudoku)){return true;}
	if (Accumulate(Accumulator,1,2,sudoku)){return true;}
	if (Accumulate(Accumulator,2,1,sudoku)){return true;}
	if (Accumulator>=34){return false;}
	if (Accumulate(Accumulator,3,0,sudoku)){return true;}
	return (Accumulator==34);
}


bool IsAPlausible(FourByFourInts*sudoku)
{
	for (int i=0;i<4;i++)
	{
		if (! IsAPlausibleRow(i,sudoku)){return false;}
		if (! IsAPlausibleCol(i,sudoku)){return false;}
	}
	if (! IsAPlausible2x2Square(0,0,sudoku)){return false;}
	if (! IsAPlausible2x2Square(2,0,sudoku)){return false;}
	if (! IsAPlausible2x2Square(0,2,sudoku)){return false;}
	if (! IsAPlausible2x2Square(2,2,sudoku)){return false;}
	if (! IsAPlausibleDiagonal1(sudoku)){return false;}
	if (! IsAPlausibleDiagonal2(sudoku)){return false;}
	return true;
}

void fillInPosition(bool* AlreadyUsed, int row, int col,FourByFourInts*sudoku)
{
	int nextCol, nextRow;		
	if (col<3)
	{ 
		nextCol= col+1; nextRow=row;
	}
	else
	{
		nextCol=0; nextRow=row+1;
	}
	for (int i=1;i<=16;i++)
	{
		if (! AlreadyUsed[i-1])
		{
			sudoku->elements[row][col]=i; 
			if (IsAPlausible(sudoku))
			{
				if (row==3&& col==3)
				{
					YourFavourite4x4arrayPrintOutFunction(sudoku,true);
					return;
				}
				else
				{	
					AlreadyUsed[i-1]=true;
/*turn on the following two lines of code if you want an illustration how this whole program works*/
//					std::system ("CLS");
/*					YourFavourite4x4arrayPrintOutFunction (sudoku,false);*/
					fillInPosition(AlreadyUsed,nextRow,nextCol, sudoku);

					AlreadyUsed[i-1]=false;
				}
			}
		}
	}
	sudoku->elements[row][col]=-1;
}
Last edited on
tition (887)
Bazzy, if you wanna generate all the 16! permutations and make a single computation for each, then you are in deep ... trouble :)


Just counted them to be 8200 exactly. The number is divisible by 8, and that is a good sign since there are exactly 8 ways to rotate or reflect a square onto itself.

http://en.wikipedia.org/wiki/Dihedral_symmetry
Last edited on
jadmacro (10)
Thanks for the help tition, but how can I make that program find all possible combinations of this and print out a few of them to make sure it worked? This only prints out one.

Thanks again.
tition (887)
Just editted the code to print out via cout all the sudokos...

You need to change the code of the

YourFavourite4x4arrayPrintOutFunction

if you would like it to print the sudokus in any format that you please. To do so you can look up the excellent reference

http://www.cplusplus.com/reference/clibrary/cstdio/FILE.html

(or any other that people would suggest?)

I myself have little (i.e. none) experience with file output under c++, could anyone help here?
tition (887)
I just noticed I had misread your original post; one must also check the diagonals!

I changed the code to do that. The count of the "non-diagonal" sudokus was 8200, but the number of "diagonal" ones is only 216 (which is again divisible by 8, which should always hold!)

By the way, 216 = 6^3, I wonder is this a coincidence or is there any simple explanation?
Topic archived. No new replies allowed.