doasku

Human-like solver for sudoku

git clone git://git.dimitrijedobrota.com/doasku.git

commit	3754de91370eff1f2b330dc9ea2eb2e63f95dd6d
parent	233d1d7f9309c2b6d806038da8e50b5ae25fdcd5
author	Dimitrije Dobrota <mail@dimitrijedobrota.com>
date	Fri, 14 Jun 2024 21:58:50 +0200

Add .clang-format, full reformat

Diffstat:

A	.clang-format	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M	main.cpp	\|	++++++++++++++++++++++++++++++++++++++++++-------------------------

2 files changed, 258 insertions(+), 25 deletions(-)

diff --git a/.clang-format b/.clang-format

@@ -0,0 +1,216 @@

---

Language: Cpp

# BasedOnStyle: Microsoft

AccessModifierOffset: -2

AlignAfterOpenBracket: Align

AlignArrayOfStructures: None

AlignConsecutiveAssignments:

Enabled: false

AcrossEmptyLines: false

AcrossComments: false

AlignCompound: false

PadOperators: true

AlignConsecutiveBitFields:

Enabled: false

AcrossEmptyLines: false

AcrossComments: false

AlignCompound: false

PadOperators: false

AlignConsecutiveDeclarations:

Enabled: false

AcrossEmptyLines: false

AcrossComments: false

AlignCompound: false

PadOperators: false

AlignConsecutiveMacros:

Enabled: false

AcrossEmptyLines: false

AcrossComments: false

AlignCompound: false

PadOperators: false

AlignEscapedNewlines: Right

AlignOperands: Align

AlignTrailingComments: true

AllowAllArgumentsOnNextLine: true

AllowAllParametersOfDeclarationOnNextLine: true

AllowShortEnumsOnASingleLine: false

AllowShortBlocksOnASingleLine: Always

AllowShortCaseLabelsOnASingleLine: true

AllowShortFunctionsOnASingleLine: true

AllowShortLambdasOnASingleLine: All

AllowShortIfStatementsOnASingleLine: AllIfsAndElse

AllowShortLoopsOnASingleLine: false

AlwaysBreakAfterDefinitionReturnType: None

AlwaysBreakAfterReturnType: None

AlwaysBreakBeforeMultilineStrings: false

AlwaysBreakTemplateDeclarations: MultiLine

AttributeMacros:

- __capability

BinPackArguments: true

BinPackParameters: true

BraceWrapping:

AfterCaseLabel: false

AfterClass: false

AfterControlStatement: false

AfterEnum: false

AfterFunction: false

AfterNamespace: false

AfterObjCDeclaration: false

AfterStruct: false

AfterUnion: false

AfterExternBlock: false

BeforeCatch: false

BeforeElse: false

BeforeLambdaBody: false

BeforeWhile: false

IndentBraces: false

SplitEmptyFunction: true

SplitEmptyRecord: true

SplitEmptyNamespace: true

BreakBeforeBinaryOperators: None

BreakBeforeConceptDeclarations: Always

BreakBeforeBraces: Custom

BreakBeforeInheritanceComma: false

BreakInheritanceList: BeforeColon

BreakBeforeTernaryOperators: true

BreakConstructorInitializersBeforeComma: false

BreakConstructorInitializers: BeforeColon

BreakAfterJavaFieldAnnotations: false

BreakStringLiterals: true

ColumnLimit: 79

CommentPragmas: '^ IWYU pragma:'

QualifierAlignment: Leave

CompactNamespaces: false

ConstructorInitializerIndentWidth: 4

ContinuationIndentWidth: 4

Cpp11BracedListStyle: true

DeriveLineEnding: true

DerivePointerAlignment: false

DisableFormat: false

EmptyLineAfterAccessModifier: Never

EmptyLineBeforeAccessModifier: LogicalBlock

ExperimentalAutoDetectBinPacking: false

PackConstructorInitializers: BinPack

BasedOnStyle: ''

ConstructorInitializerAllOnOneLineOrOnePerLine: false

AllowAllConstructorInitializersOnNextLine: true

FixNamespaceComments: true

ForEachMacros:

- foreach

- Q_FOREACH

- BOOST_FOREACH

IfMacros:

- KJ_IF_MAYBE

IncludeBlocks: Preserve

IncludeCategories:

- Regex: '^"(llvm|llvm-c|clang|clang-c)/'

Priority: 2

SortPriority: 0

CaseSensitive: false

- Regex: '^(<|"(gtest|gmock|isl|json)/)'

Priority: 3

SortPriority: 0

CaseSensitive: false

- Regex: '.*'

Priority: 1

SortPriority: 0

CaseSensitive: false

IncludeIsMainRegex: '(Test)?$'

IncludeIsMainSourceRegex: ''

IndentAccessModifiers: false

IndentCaseLabels: false

IndentCaseBlocks: false

IndentGotoLabels: true

IndentPPDirectives: None

IndentExternBlock: AfterExternBlock

IndentRequiresClause: true

IndentWidth: 4

IndentWrappedFunctionNames: false

InsertBraces: false

InsertTrailingCommas: None

JavaScriptQuotes: Leave

JavaScriptWrapImports: true

KeepEmptyLinesAtTheStartOfBlocks: true

LambdaBodyIndentation: Signature

MacroBlockBegin: ''

MacroBlockEnd: ''

MaxEmptyLinesToKeep: 1

NamespaceIndentation: None

ObjCBinPackProtocolList: Auto

ObjCBlockIndentWidth: 2

ObjCBreakBeforeNestedBlockParam: true

ObjCSpaceAfterProperty: false

ObjCSpaceBeforeProtocolList: true

PenaltyBreakAssignment: 2

PenaltyBreakBeforeFirstCallParameter: 19

PenaltyBreakComment: 300

PenaltyBreakFirstLessLess: 120

PenaltyBreakOpenParenthesis: 0

PenaltyBreakString: 1000

PenaltyBreakTemplateDeclaration: 10

PenaltyExcessCharacter: 1000000

PenaltyReturnTypeOnItsOwnLine: 1000

PenaltyIndentedWhitespace: 0

PointerAlignment: Right

PPIndentWidth: -1

ReferenceAlignment: Pointer

ReflowComments: true

RemoveBracesLLVM: false

RequiresClausePosition: OwnLine

SeparateDefinitionBlocks: Leave

ShortNamespaceLines: 1

SortIncludes: CaseSensitive

SortJavaStaticImport: Before

SortUsingDeclarations: true

SpaceAfterCStyleCast: false

SpaceAfterLogicalNot: false

SpaceAfterTemplateKeyword: true

SpaceBeforeAssignmentOperators: true

SpaceBeforeCaseColon: false

SpaceBeforeCpp11BracedList: false

SpaceBeforeCtorInitializerColon: true

SpaceBeforeInheritanceColon: true

SpaceBeforeParens: ControlStatements

SpaceBeforeParensOptions:

AfterControlStatements: true

AfterForeachMacros: true

AfterFunctionDefinitionName: false

AfterFunctionDeclarationName: false

AfterIfMacros: true

AfterOverloadedOperator: false

AfterRequiresInClause: false

AfterRequiresInExpression: false

BeforeNonEmptyParentheses: false

SpaceAroundPointerQualifiers: Default

SpaceBeforeRangeBasedForLoopColon: true

SpaceInEmptyBlock: false

SpaceInEmptyParentheses: false

SpacesBeforeTrailingComments: 1

SpacesInAngles: Never

SpacesInConditionalStatement: false

SpacesInContainerLiterals: true

SpacesInCStyleCastParentheses: false

SpacesInLineCommentPrefix:

Minimum: 1

Maximum: -1

SpacesInParentheses: false

SpacesInSquareBrackets: false

SpaceBeforeSquareBrackets: false

BitFieldColonSpacing: Both

Standard: Latest

StatementAttributeLikeMacros:

- Q_EMIT

StatementMacros:

- Q_UNUSED

- QT_REQUIRE_VERSION

TabWidth: 4

UseCRLF: false

UseTab: Never

WhitespaceSensitiveMacros:

- STRINGIZE

- PP_STRINGIZE

- BOOST_PP_STRINGIZE

- NS_SWIFT_NAME

- CF_SWIFT_NAME

...

diff --git a/main.cpp b/main.cpp

@@ -10,13 +10,16 @@

#include <iostream>

#include <vector>

template <class Input, class UnaryFunc> UnaryFunc for_each(Input input, UnaryFunc f) {

template <class Input, class UnaryFunc>

UnaryFunc for_each(Input input, UnaryFunc f) {

return std::for_each(begin(input), end(input), f);

}

struct cord_t {

cord_t(uint8_t row, uint8_t col) : value(row * 3 + col) { assert(row < 3 && col < 3); }

cord_t(uint8_t value) : value(value) { assert(value < 9); }

cord_t(uint8_t row, uint8_t col) : value(row * 3 + col) {

assert(row < 3 && col < 3);

}

operator uint8_t() const { return value; }

@@ -32,8 +35,11 @@ struct cord_t {

class acord_t {

public:

acord_t(cord_t subgrid, cord_t field) : subgrid_i(subgrid), field_i(field) {}

acord_t(uint8_t row, uint8_t col) : subgrid_i(row / 3, col / 3), field_i(row % 3, col % 3) {}

acord_t(cord_t subgrid, cord_t field)

: subgrid_i(subgrid), field_i(field) {}

acord_t(uint8_t row, uint8_t col)

: subgrid_i(row / 3, col / 3), field_i(row % 3, col % 3) {}

cord_t subgrid() const { return subgrid_i; }

cord_t field() const { return field_i; }

@@ -41,7 +47,9 @@ class acord_t {

uint8_t row() const { return subgrid_i.row() * 3 + field_i.row(); }

uint8_t col() const { return subgrid_i.col() * 3 + field_i.col(); }

std::tuple<cord_t, cord_t> relative() const { return {subgrid_i, field_i}; }

std::tuple<cord_t, cord_t> relative() const {

return {subgrid_i, field_i};

}

friend std::ostream &operator<<(std::ostream &os, acord_t acord) {

return os << std::format("(({}, {}))", acord.row(), acord.col());

@@ -53,14 +61,16 @@ class acord_t {

};

static std::tuple<uint8_t, uint8_t> other_subgrid_row(uint8_t subgrid) {

static std::tuple<uint8_t, uint8_t> mapping[9] = {{1, 2}, {0, 2}, {0, 1}, {4, 5}, {3, 5},

{3, 4}, {7, 8}, {6, 8}, {6, 7}};

static std::tuple<uint8_t, uint8_t> mapping[9] = {{1, 2}, {0, 2}, {0, 1},

{4, 5}, {3, 5}, {3, 4},

{7, 8}, {6, 8}, {6, 7}};

return mapping[subgrid];

}

static std::tuple<uint8_t, uint8_t> other_subgrid_col(uint8_t subgrid) {

static std::tuple<uint8_t, uint8_t> mapping[9] = {{3, 6}, {4, 7}, {5, 8}, {0, 6}, {1, 7},

{2, 8}, {0, 3}, {1, 4}, {2, 5}};

static std::tuple<uint8_t, uint8_t> mapping[9] = {{3, 6}, {4, 7}, {5, 8},

{0, 6}, {1, 7}, {2, 8},

{0, 3}, {1, 4}, {2, 5}};

return mapping[subgrid];

}

@@ -133,14 +143,15 @@ class Ref {

return res;

}

bool get_hidden(changes_t &res, uint8_t og, uint8_t number, uint8_t first, uint16_t val,

uint16_t mask) const {

bool get_hidden(changes_t &res, uint8_t og, uint8_t number, uint8_t first,

uint16_t val, uint16_t mask) const {

if (number != 0) {

for (uint8_t i = first; i < 9; i++) {

if (std::popcount(ref[i]) < 2) continue;

if (seen_hidden[og] & (1ul << i)) continue;

bool used = get_hidden(res, og, number - 1, i + 1, val | ref[i], mask | (1 << i));

bool used = get_hidden(res, og, number - 1, i + 1,

val | ref[i], mask | (1 << i));

if (!used) continue;

seen_hidden[og] |= 1ul << i;

@@ -162,7 +173,8 @@ class Ref {

}

for (uint8_t i = 0; i < og; i++) {

const uint16_t change = value[fields[i]] & ~(value[fields[i]] & mask);

const uint16_t change =

value[fields[i]] & ~(value[fields[i]] & mask);

if (!change) continue;

res.emplace_back(fields[i], change);

}

@@ -178,7 +190,8 @@ class Ref {

return res;

}

bool get_naked(changes_t &res, uint8_t og, uint8_t number, uint8_t first, uint16_t val) const {

bool get_naked(changes_t &res, uint8_t og, uint8_t number, uint8_t first,

uint16_t val) const {

static uint8_t seen[4] = {0};

if (number != 0) {

@@ -187,7 +200,8 @@ class Ref {

if (number == og && seen_naked[og] & (1ul << i)) continue;

seen[og - number] = i;

bool used = get_naked(res, og, number - 1, i + 1, val | value[i]);

bool used =

get_naked(res, og, number - 1, i + 1, val | value[i]);

if (!used) continue;

if (number == og) seen_naked[og] |= 1ul << i;

@@ -224,7 +238,9 @@ class Ref {

if ((seen_point[seen] & (1 << i)) == 0) {

uint16_t cmask = mask;

for (uint8_t k = 0; k < 3; k++, cmask <<= 3) {

if (std::popcount(uint16_t(cmask & ref[i])) != popcnt) continue;

if (std::popcount(uint16_t(cmask & ref[i])) != popcnt)

continue;

seen_point[seen] |= 1 << i;

res.emplace_back(k, i);

break;

@@ -238,15 +254,19 @@ class Ref {

static constexpr const std::int64_t mask_field = (1 << 9) - 1;

static constexpr const std::int64_t mask_value = 0x201008040201;

uint16_t value[9] = {mask_field, mask_field, mask_field, mask_field, mask_field,

mask_field, mask_field, mask_field, mask_field};

uint16_t value[9] = {mask_field, mask_field, mask_field,

mask_field, mask_field, mask_field,

mask_field, mask_field, mask_field};

uint16_t ref[9] = {mask_field, mask_field, mask_field, mask_field, mask_field,

mask_field, mask_field, mask_field, mask_field};

uint16_t ref[9] = {mask_field, mask_field, mask_field,

mask_field, mask_field, mask_field,

mask_field, mask_field, mask_field};

uint16_t res[9] = {0};

mutable uint16_t seen_hidden[4] = {0}, seen_naked[4] = {0}, seen_point[2] = {0};

mutable uint16_t seen_hidden[4] = {0};

mutable uint16_t seen_naked[4] = {0};

mutable uint16_t seen_point[2] = {0};

};

class Grid {

@@ -470,10 +490,7 @@ class Grid {

return true;

}

Ref subgrids[9];

Ref rows[9];

Ref cols[9];

Ref subgrids[9], rows[9], cols[9];

bool changed = false;

};