commit ceb5fe11e2184d69bfa9fd82433efeb61d2ff288
parent e3aa186b08e7ccdf1f4b6b89aa1724864df0bff7
Author: mpizzzle <m@michaelpercival.xyz>
Date: Tue, 29 Sep 2020 18:43:36 +0100
safety commit, problem 96 complete
Diffstat:
5 files changed, 788 insertions(+), 2 deletions(-)
diff --git a/Euler.h b/Euler.h
@@ -88,4 +88,5 @@ public:
int AmicableChains();
uint64_t ArrangedProbability();
uint64_t CubeDigitPairs();
+ int Sudoku();
};
diff --git a/Euler_96.cpp b/Euler_96.cpp
@@ -0,0 +1,283 @@
+#include <array>
+#include <fstream>
+#include <sstream>
+#include <unordered_set>
+
+#include "Euler.h"
+
+typedef std::array<std::array<int, 9>, 9> sudoku;
+
+bool check(sudoku bifurcation) {
+ for (int i = 0; i < 9; ++i) {
+ std::unordered_set<int> horizontal_digits;
+ std::unordered_set<int> vertical_digits;
+
+ for (int j = 0; j < 9; ++j) {
+ horizontal_digits.insert(bifurcation[i][j]);
+ vertical_digits.insert(bifurcation[j][i]);
+ }
+
+ if (horizontal_digits.size() < 9 || vertical_digits.size() < 9) {
+ return false;
+ }
+ }
+
+ for (int l = 0; l < 3; ++l) {
+ for (int k = 0; k < 3; ++k) {
+ std::unordered_set<int> subgroup_digits;
+
+ for (int i = l * 3; i < (l * 3) + 3; ++i) {
+ for (int j = k * 3; j < (k * 3) + 3; ++j) {
+ subgroup_digits.insert(bifurcation[i][j]);
+ }
+ }
+
+ if (subgroup_digits.size() < 9) {
+ return false;
+ }
+ }
+ }
+
+ return true;
+}
+
+sudoku reduce(sudoku puzzle) {
+ bool reduced;
+ bool vert = true;
+ do {
+ reduced = false;
+
+ std::array<std::unordered_set<int>, 9> horizontal_digits;
+ std::array<std::unordered_set<int>, 9> vertical_digits;
+
+ for (int i = 0; i < 9; ++i) {
+ for (int j = 0; j < 9; ++j) {
+ horizontal_digits[i].insert(puzzle[i][j]);
+ vertical_digits[i].insert(puzzle[j][i]);
+ }
+ }
+
+ for (int l = 0; l < 3; ++l) {
+ for (int k = 0; k < 3; ++k) {
+ std::unordered_set<int> missing_digits;
+ std::unordered_set<int> subgroup_digits;
+
+ for (int i = l * 3; i < (l * 3) + 3; ++i) {
+ for (int j = k * 3; j < (k * 3) + 3; ++j) {
+ subgroup_digits.insert(puzzle[i][j]);
+ }
+ }
+
+ for (int i = 1; i <= 9; ++i) {
+ if (subgroup_digits.find(i) == subgroup_digits.end()) {
+ missing_digits.insert(i);
+ }
+ }
+
+
+ if (missing_digits.size() > 0) {
+ for (int i = l * 3; i < (l * 3) + 3; ++i) {
+ for (int j = k * 3; j < (k * 3) + 3; ++j) {
+ if (puzzle[i][j] <= 0) {
+ if (missing_digits.size() == 1) {
+ puzzle[i][j] = *missing_digits.begin();
+ reduced = true;
+ vert = true;
+ std::cout << "reduced i: " << i + 1 << ", j: " << j + 1 << " = " << *missing_digits.begin() << std::endl;
+
+ for (int q = 0; q < 9; ++q) {
+ horizontal_digits[q].clear();
+ vertical_digits[q].clear();
+
+ for (int p = 0; p < 9; ++p) {
+ horizontal_digits[q].insert(puzzle[q][p]);
+ vertical_digits[q].insert(puzzle[p][q]);
+ }
+ }
+
+ subgroup_digits.clear();
+ for (int q = l * 3; q < (l * 3) + 3; ++q) {
+ for (int p = k * 3; p < (k * 3) + 3; ++p) {
+ subgroup_digits.insert(puzzle[q][p]);
+ }
+ }
+
+ break;
+ }
+ if (missing_digits.size() <= 9) {
+ std::unordered_set<int> matches;
+ for (int x : missing_digits) {
+ if (horizontal_digits[i].find(x) != horizontal_digits[i].end()) {
+ matches.insert(x);
+ }
+ if (vertical_digits[j].find(x) != vertical_digits[j].end()) {
+ matches.insert(x);
+ }
+ }
+
+ std::unordered_set<int> match_matches;
+ for (int x : missing_digits) {
+ if (matches.find(x) == matches.end()) {
+ match_matches.insert(x);
+ }
+ }
+
+ if (match_matches.size() == 1) {
+ puzzle[i][j] = *match_matches.begin();
+ reduced = true;
+ vert = true;
+ std::cout << "reduced i: " << i + 1 << ", j: " << j + 1 << " = " << *match_matches.begin() << std::endl;
+
+ for (int q = 0; q < 9; ++q) {
+ horizontal_digits[q].clear();
+ vertical_digits[q].clear();
+
+ for (int p = 0; p < 9; ++p) {
+ horizontal_digits[q].insert(puzzle[q][p]);
+ vertical_digits[q].insert(puzzle[p][q]);
+ }
+ }
+
+ subgroup_digits.clear();
+ for (int q = l * 3; q < (l * 3) + 3; ++q) {
+ for (int p = k * 3; p < (k * 3) + 3; ++p) {
+ subgroup_digits.insert(puzzle[q][p]);
+ }
+ }
+
+ break;
+ }
+ }
+ for (int x : missing_digits) {
+ if (subgroup_digits.find(x) == subgroup_digits.end()) {
+ if (((puzzle[(l * 3) + ((i + 1) % 3)][j] > 0 && !vert)
+ || horizontal_digits[(l * 3) + ((i + 1) % 3)].find(x) != horizontal_digits[(l * 3) + ((i + 1) % 3)].end())
+ && ((puzzle[(l * 3) + ((i + 2) % 3)][j] > 0 && !vert)
+ || horizontal_digits[(l * 3) + ((i + 2) % 3)].find(x) != horizontal_digits[(l * 3) + ((i + 2) % 3)].end())
+ && ((puzzle[i][(k * 3) + ((j + 1) % 3)] > 0 && vert)
+ || vertical_digits[(k * 3) + ((j + 1) % 3)].find(x) != vertical_digits[(k * 3) + ((j + 1) % 3)].end())
+ && ((puzzle[i][(k * 3) + ((j + 2) % 3)] > 0 && vert)
+ || vertical_digits[(k * 3) + ((j + 2) % 3)].find(x) != vertical_digits[(k * 3) + ((j + 2) % 3)].end())) {
+ puzzle[i][j] = x;
+ reduced = true;
+ vert = true;
+ std::cout << "reduced i: " << i + 1 << ", j: " << j + 1 << " = " << x << std::endl;
+
+ for (int q = 0; q < 9; ++q) {
+ horizontal_digits[q].clear();
+ vertical_digits[q].clear();
+
+ for (int p = 0; p < 9; ++p) {
+ horizontal_digits[q].insert(puzzle[q][p]);
+ vertical_digits[q].insert(puzzle[p][q]);
+ }
+ }
+
+ subgroup_digits.clear();
+ for (int q = l * 3; q < (l * 3) + 3; ++q) {
+ for (int p = k * 3; p < (k * 3) + 3; ++p) {
+ subgroup_digits.insert(puzzle[q][p]);
+ }
+ }
+
+ break;
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ }
+ if (!reduced && vert) {
+ vert = false;
+ reduced = true;
+ }
+ } while (reduced);
+
+
+
+ return puzzle;
+}
+
+sudoku bifurcate(sudoku bifurcation) {
+ if (!check(bifurcation)) {
+ sudoku blep = {};
+ return blep;
+ }
+
+ for (int i = 0; i < 9; ++i) {
+ for (int j = 0; j < 9; ++j) {
+ if (bifurcation[i][j] <= 0) {
+ for (int k = 0; k < 9; ++k) {
+ bifurcation[i][j] = k + 1;
+
+ sudoku candidate = bifurcate(bifurcation);
+
+ if (check(candidate)) {
+ return candidate;
+ }
+ }
+ }
+ }
+ }
+
+ return bifurcation;
+}
+
+void print(sudoku puzzle) {
+ for (int k = 0; k < 9; ++k) {
+ if (k % 3 == 0) {
+ std::cout << "-------------------" << std::endl;
+ }
+ for (int l = 0; l < 9; ++l) {
+ std::cout << ((l % 3 == 0) ? "|" : " ") << ((puzzle[k][l] < 0) ? 0 : puzzle[k][l]);
+ }
+ std::cout << "|" << std::endl;
+ }
+ std::cout << "-------------------" << std::endl << std::endl;
+}
+int Euler::Sudoku()
+{
+ std::array<sudoku, 50> sudokus;
+ std::ifstream file;
+ std::string temp;
+ int i = -1, j = 0, empty = 0, sum = 0;
+
+ file.open("files/p096_sudoku.txt");
+
+ while(std::getline(file, temp)) {
+ if (temp[0] == 'G') {
+ i++; j = 0; empty = 0; continue;
+ }
+
+ for (int k = 0; k < 9; ++k) {
+ sudokus[i][j][k] = ((temp[k] - 48) != 0) ? temp[k] - 48 : empty--;
+ }
+
+ j++;
+ }
+
+ file.close();
+
+ for (int j = 0; j < 50; ++j) {
+ std::cout << "next puzzle " << j << ":" << std::endl;
+ sudoku puzzle = sudokus[j];
+ print(puzzle);
+ sudoku reduced = reduce(puzzle);
+ std::cout << "reduced:" << std::endl;
+ print(reduced);
+ sudoku solution = bifurcate(reduced);
+ std::cout << "solution:" << std::endl;
+ print(solution);
+ std::stringstream ss;
+ ss << solution[0][0] << solution[0][1] << solution[0][2];
+ int temp;
+ ss >> temp;
+ sum += temp;
+
+ }
+
+ return sum;
+}
diff --git a/Makefile b/Makefile
@@ -13,7 +13,7 @@ _OBJ = main.o
Euler_61.o Euler_62.o Euler_63.o Euler_64.o Euler_68.o Euler_69.o Euler_70.o
Euler_71.o Euler_72.o Euler_73.o Euler_74.o Euler_75.o Euler_76.o Euler_77.o Euler_79.o Euler_80.o
Euler_86.o Euler_87.o Euler_90.o
- Euler_94.o Euler_95.o Euler_100.o
+ Euler_94.o Euler_95.o Euler_96.o Euler_100.o
EulerUtility.o
OBJ = $(patsubst %,$(ODIR)/%,$(_OBJ))
diff --git a/files/p096_sudoku.txt b/files/p096_sudoku.txt
@@ -0,0 +1,500 @@
+Grid 01
+003020600
+900305001
+001806400
+008102900
+700000008
+006708200
+002609500
+800203009
+005010300
+Grid 02
+200080300
+060070084
+030500209
+000105408
+000000000
+402706000
+301007040
+720040060
+004010003
+Grid 03
+000000907
+000420180
+000705026
+100904000
+050000040
+000507009
+920108000
+034059000
+507000000
+Grid 04
+030050040
+008010500
+460000012
+070502080
+000603000
+040109030
+250000098
+001020600
+080060020
+Grid 05
+020810740
+700003100
+090002805
+009040087
+400208003
+160030200
+302700060
+005600008
+076051090
+Grid 06
+100920000
+524010000
+000000070
+050008102
+000000000
+402700090
+060000000
+000030945
+000071006
+Grid 07
+043080250
+600000000
+000001094
+900004070
+000608000
+010200003
+820500000
+000000005
+034090710
+Grid 08
+480006902
+002008001
+900370060
+840010200
+003704100
+001060049
+020085007
+700900600
+609200018
+Grid 09
+000900002
+050123400
+030000160
+908000000
+070000090
+000000205
+091000050
+007439020
+400007000
+Grid 10
+001900003
+900700160
+030005007
+050000009
+004302600
+200000070
+600100030
+042007006
+500006800
+Grid 11
+000125400
+008400000
+420800000
+030000095
+060902010
+510000060
+000003049
+000007200
+001298000
+Grid 12
+062340750
+100005600
+570000040
+000094800
+400000006
+005830000
+030000091
+006400007
+059083260
+Grid 13
+300000000
+005009000
+200504000
+020000700
+160000058
+704310600
+000890100
+000067080
+000005437
+Grid 14
+630000000
+000500008
+005674000
+000020000
+003401020
+000000345
+000007004
+080300902
+947100080
+Grid 15
+000020040
+008035000
+000070602
+031046970
+200000000
+000501203
+049000730
+000000010
+800004000
+Grid 16
+361025900
+080960010
+400000057
+008000471
+000603000
+259000800
+740000005
+020018060
+005470329
+Grid 17
+050807020
+600010090
+702540006
+070020301
+504000908
+103080070
+900076205
+060090003
+080103040
+Grid 18
+080005000
+000003457
+000070809
+060400903
+007010500
+408007020
+901020000
+842300000
+000100080
+Grid 19
+003502900
+000040000
+106000305
+900251008
+070408030
+800763001
+308000104
+000020000
+005104800
+Grid 20
+000000000
+009805100
+051907420
+290401065
+000000000
+140508093
+026709580
+005103600
+000000000
+Grid 21
+020030090
+000907000
+900208005
+004806500
+607000208
+003102900
+800605007
+000309000
+030020050
+Grid 22
+005000006
+070009020
+000500107
+804150000
+000803000
+000092805
+907006000
+030400010
+200000600
+Grid 23
+040000050
+001943600
+009000300
+600050002
+103000506
+800020007
+005000200
+002436700
+030000040
+Grid 24
+004000000
+000030002
+390700080
+400009001
+209801307
+600200008
+010008053
+900040000
+000000800
+Grid 25
+360020089
+000361000
+000000000
+803000602
+400603007
+607000108
+000000000
+000418000
+970030014
+Grid 26
+500400060
+009000800
+640020000
+000001008
+208000501
+700500000
+000090084
+003000600
+060003002
+Grid 27
+007256400
+400000005
+010030060
+000508000
+008060200
+000107000
+030070090
+200000004
+006312700
+Grid 28
+000000000
+079050180
+800000007
+007306800
+450708096
+003502700
+700000005
+016030420
+000000000
+Grid 29
+030000080
+009000500
+007509200
+700105008
+020090030
+900402001
+004207100
+002000800
+070000090
+Grid 30
+200170603
+050000100
+000006079
+000040700
+000801000
+009050000
+310400000
+005000060
+906037002
+Grid 31
+000000080
+800701040
+040020030
+374000900
+000030000
+005000321
+010060050
+050802006
+080000000
+Grid 32
+000000085
+000210009
+960080100
+500800016
+000000000
+890006007
+009070052
+300054000
+480000000
+Grid 33
+608070502
+050608070
+002000300
+500090006
+040302050
+800050003
+005000200
+010704090
+409060701
+Grid 34
+050010040
+107000602
+000905000
+208030501
+040070020
+901080406
+000401000
+304000709
+020060010
+Grid 35
+053000790
+009753400
+100000002
+090080010
+000907000
+080030070
+500000003
+007641200
+061000940
+Grid 36
+006080300
+049070250
+000405000
+600317004
+007000800
+100826009
+000702000
+075040190
+003090600
+Grid 37
+005080700
+700204005
+320000084
+060105040
+008000500
+070803010
+450000091
+600508007
+003010600
+Grid 38
+000900800
+128006400
+070800060
+800430007
+500000009
+600079008
+090004010
+003600284
+001007000
+Grid 39
+000080000
+270000054
+095000810
+009806400
+020403060
+006905100
+017000620
+460000038
+000090000
+Grid 40
+000602000
+400050001
+085010620
+038206710
+000000000
+019407350
+026040530
+900020007
+000809000
+Grid 41
+000900002
+050123400
+030000160
+908000000
+070000090
+000000205
+091000050
+007439020
+400007000
+Grid 42
+380000000
+000400785
+009020300
+060090000
+800302009
+000040070
+001070500
+495006000
+000000092
+Grid 43
+000158000
+002060800
+030000040
+027030510
+000000000
+046080790
+050000080
+004070100
+000325000
+Grid 44
+010500200
+900001000
+002008030
+500030007
+008000500
+600080004
+040100700
+000700006
+003004050
+Grid 45
+080000040
+000469000
+400000007
+005904600
+070608030
+008502100
+900000005
+000781000
+060000010
+Grid 46
+904200007
+010000000
+000706500
+000800090
+020904060
+040002000
+001607000
+000000030
+300005702
+Grid 47
+000700800
+006000031
+040002000
+024070000
+010030080
+000060290
+000800070
+860000500
+002006000
+Grid 48
+001007090
+590080001
+030000080
+000005800
+050060020
+004100000
+080000030
+100020079
+020700400
+Grid 49
+000003017
+015009008
+060000000
+100007000
+009000200
+000500004
+000000020
+500600340
+340200000
+Grid 50
+300200000
+000107000
+706030500
+070009080
+900020004
+010800050
+009040301
+000702000
+000008006+
No newline at end of file
diff --git a/main.cpp b/main.cpp
@@ -92,7 +92,8 @@ int main() {
//std::cout << "problem 87: " << e.PrimePowerTriples() << std::endl;
//std::cout << "problem 90: " << e.CubeDigitPairs() << std::endl; //in progress
//std::cout << "problem 94: " << e.AlmostEquilateralTriangles() << std::endl; //in progress
- std::cout << "problem 95: " << e.AmicableChains() << std::endl; //in progress
+ //std::cout << "problem 95: " << e.AmicableChains() << std::endl;
+ std::cout << "problem 96: " << e.Sudoku() << std::endl; //in progress
//std::cout << "problem 100: " << e.ArrangedProbability() << std::endl; //in progress
std::cout << "duration: " << 1000.0 * (std::clock() - start) / CLOCKS_PER_SEC << "ms" << std::endl;
