doasku

Human-like solver for sudoku

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

commit	4595a3d8cf36dcc69ae1d659a6c4ff48c5ea22b9
parent	8f55dc256a616127fe139c92c22c6ceffc8bdd70
author	Dimitrije Dobrota <mail@dimitrijedobrota.com>
date	Fri, 21 Jun 2024 17:32:56 +0200

Use cmake-init and modernize codebase

Diffstat:

M	.clang-format	\|	+++++++++++++++++++++++++++++++++++-----------------------------------------------
A	.clang-tidy	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	.codespellrc	\|	++++++
M	.gitignore	\|	+++++++++++--
A	BUILDING.md	\|	++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
M	CMakeLists.txt	\|	++++++++++++++++++++++++++++++++----------
A	CMakePresets.json	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	CODE_OF_CONDUCT.md	\|	+++++
A	CONTRIBUTING.md	\|	++++++++++++++
A	HACKING.md	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	LICENSE.md	\|	+++++++++++++++++++++
A	README.md	\|	+++++++++++++++
A	cmake/coverage.cmake	\|	+++++++++++++++++++++++++++++++++
A	cmake/dev-mode.cmake	\|	++++++++++++++++++
A	cmake/folders.cmake	\|	+++++++++++++++++++++
A	cmake/install-rules.cmake	\|	++++++++
A	cmake/lint-targets.cmake	\|	+++++++++++++++++++++++++++++++++
A	cmake/lint.cmake	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++
A	cmake/prelude.cmake	\|	++++++++++
A	cmake/project-is-top-level.cmake	\|	++++++
A	cmake/spell-targets.cmake	\|	++++++++++++++++++++++
A	cmake/spell.cmake	\|	+++++++++++++++++++++++++++++
A	cmake/variables.cmake	\|	++++++++++++++++++++++++++++
D	include/cord.hpp	\|	---------------------------------------------
D	include/grid.hpp	\|	--------------------------------------------
D	include/ref.hpp	\|	---------------------------------------------------------------
A	source/cord.hpp	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	source/grid.cpp	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	source/grid.hpp	\|	++++++++++++++++++++++++++++++++++++++++++++++
A	source/main.cpp	\|	+++++++++++++++++++
A	source/ref.cpp	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
A	source/ref.hpp	\|	+++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++++
D	src/CMakeLists.txt	\|	--------
D	src/grid.cpp	\|	---------------------------------------------------------------------------------
D	src/main.cpp	\|	---------------
D	src/ref.cpp	\|	---------------------------------------------------------------------------------

36 files changed, 1681 insertions(+), 730 deletions(-)

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

@@ -1,216 +1,178 @@

---

Language: Cpp

# BasedOnStyle: Microsoft

Language: Cpp

# BasedOnStyle: Chromium

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

AlignConsecutiveMacros: false

AlignConsecutiveAssignments: false

AlignConsecutiveBitFields: false

AlignConsecutiveDeclarations: false

AlignEscapedNewlines: DontAlign

AlignOperands: DontAlign

AlignTrailingComments: false

AllowAllArgumentsOnNextLine: true

AllowAllConstructorInitializersOnNextLine: false

AllowAllParametersOfDeclarationOnNextLine: true

AllowShortEnumsOnASingleLine: false

AllowShortBlocksOnASingleLine: Always

AllowShortCaseLabelsOnASingleLine: true

AllowShortFunctionsOnASingleLine: true

AllowShortBlocksOnASingleLine: Empty

AllowShortCaseLabelsOnASingleLine: false

AllowShortFunctionsOnASingleLine: Inline

AllowShortLambdasOnASingleLine: All

AllowShortIfStatementsOnASingleLine: AllIfsAndElse

AllowShortIfStatementsOnASingleLine: true

AllowShortLoopsOnASingleLine: false

AlwaysBreakAfterDefinitionReturnType: None

AlwaysBreakAfterReturnType: None

AlwaysBreakBeforeMultilineStrings: false

AlwaysBreakTemplateDeclarations: MultiLine

AttributeMacros:

- __capability

BinPackArguments: true

BinPackParameters: true

AlwaysBreakBeforeMultilineStrings: true

AlwaysBreakTemplateDeclarations: Yes

BinPackArguments: false

BinPackParameters: false

BraceWrapping:

AfterCaseLabel: false

AfterClass: false

AfterControlStatement: false

AfterEnum: false

AfterFunction: false

AfterNamespace: false

AfterCaseLabel: false

AfterClass: true

AfterControlStatement: MultiLine

AfterEnum: true

AfterFunction: true

AfterNamespace: true

AfterObjCDeclaration: false

AfterStruct: false

AfterUnion: false

AfterExternBlock: false

BeforeCatch: false

BeforeElse: false

BeforeLambdaBody: false

BeforeWhile: false

IndentBraces: false

AfterStruct: true

AfterUnion: true

AfterExternBlock: true

BeforeCatch: false

BeforeElse: false

BeforeLambdaBody: true

BeforeWhile: false

IndentBraces: false

SplitEmptyFunction: true

SplitEmptyRecord: true

SplitEmptyNamespace: true

BreakBeforeBinaryOperators: None

BreakBeforeConceptDeclarations: Always

BreakBeforeBinaryOperators: NonAssignment

BreakBeforeBraces: Custom

BreakBeforeInheritanceComma: false

BreakInheritanceList: BeforeColon

# BreakBeforeInheritanceComma: true

BreakInheritanceList: BeforeComma

BreakBeforeTernaryOperators: true

BreakConstructorInitializersBeforeComma: false

BreakConstructorInitializers: BeforeColon

BreakAfterJavaFieldAnnotations: false

BreakConstructorInitializersBeforeComma: true

BreakConstructorInitializers: BeforeComma

BreakAfterJavaFieldAnnotations: true

BreakStringLiterals: true

ColumnLimit: 79

CommentPragmas: '^ IWYU pragma:'

QualifierAlignment: Leave

ColumnLimit: 79

CommentPragmas: '^ IWYU pragma:'

CompactNamespaces: false

ConstructorInitializerAllOnOneLineOrOnePerLine: false

ConstructorInitializerIndentWidth: 4

ContinuationIndentWidth: 4

Cpp11BracedListStyle: true

DeriveLineEnding: true

DeriveLineEnding: false

DerivePointerAlignment: false

DisableFormat: false

EmptyLineAfterAccessModifier: Never

EmptyLineBeforeAccessModifier: LogicalBlock

DisableFormat: false

ExperimentalAutoDetectBinPacking: false

PackConstructorInitializers: BinPack

BasedOnStyle: ''

ConstructorInitializerAllOnOneLineOrOnePerLine: false

AllowAllConstructorInitializersOnNextLine: true

FixNamespaceComments: true

ForEachMacros:

- foreach

- Q_FOREACH

- BOOST_FOREACH

IfMacros:

- KJ_IF_MAYBE

IncludeBlocks: Preserve

IncludeBlocks: Regroup

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)?$'

# Standard library headers come before anything else

- Regex: '^<[a-z_]+>'

Priority: -1

- Regex: '^<.+\.h(pp)?>'

Priority: 1

- Regex: '^<.*'

Priority: 2

- Regex: '.*'

Priority: 3

IncludeIsMainRegex: ''

IncludeIsMainSourceRegex: ''

IndentAccessModifiers: false

IndentCaseLabels: false

IndentCaseLabels: true

IndentCaseBlocks: false

IndentGotoLabels: true

IndentPPDirectives: None

IndentExternBlock: AfterExternBlock

IndentRequiresClause: true

IndentWidth: 4

IndentPPDirectives: AfterHash

IndentExternBlock: NoIndent

IndentWidth: 2

IndentWrappedFunctionNames: false

InsertBraces: false

InsertTrailingCommas: None

JavaScriptQuotes: Leave

InsertTrailingCommas: Wrapped

JavaScriptQuotes: Double

JavaScriptWrapImports: true

KeepEmptyLinesAtTheStartOfBlocks: true

LambdaBodyIndentation: Signature

KeepEmptyLinesAtTheStartOfBlocks: false

MacroBlockBegin: ''

MacroBlockEnd: ''

MaxEmptyLinesToKeep: 1

NamespaceIndentation: None

ObjCBinPackProtocolList: Auto

ObjCBinPackProtocolList: Never

ObjCBlockIndentWidth: 2

ObjCBreakBeforeNestedBlockParam: true

ObjCSpaceAfterProperty: false

ObjCSpaceBeforeProtocolList: true

PenaltyBreakAssignment: 2

PenaltyBreakBeforeFirstCallParameter: 19

PenaltyBreakBeforeFirstCallParameter: 1

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

PenaltyReturnTypeOnItsOwnLine: 200

PointerAlignment: Left

RawStringFormats:

- Language: Cpp

Delimiters:

- cc

- CC

- cpp

- Cpp

- CPP

- 'c++'

- 'C++'

CanonicalDelimiter: ''

BasedOnStyle: google

- Language: TextProto

Delimiters:

- pb

- PB

- proto

- PROTO

EnclosingFunctions:

- EqualsProto

- EquivToProto

- PARSE_PARTIAL_TEXT_PROTO

- PARSE_TEST_PROTO

- PARSE_TEXT_PROTO

- ParseTextOrDie

- ParseTextProtoOrDie

- ParseTestProto

- ParsePartialTestProto

CanonicalDelimiter: ''

BasedOnStyle: google

ReflowComments: true

SortIncludes: true

SortUsingDeclarations: true

SpaceAfterCStyleCast: false

SpaceAfterLogicalNot: false

SpaceAfterTemplateKeyword: true

SpaceAfterTemplateKeyword: false

SpaceBeforeAssignmentOperators: true

SpaceBeforeCaseColon: false

SpaceBeforeCpp11BracedList: false

SpaceBeforeCpp11BracedList: true

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

SpaceBeforeParens: ControlStatementsExceptForEachMacros

SpaceBeforeRangeBasedForLoopColon: true

SpaceInEmptyBlock: false

SpaceInEmptyParentheses: false

SpacesBeforeTrailingComments: 1

SpacesInAngles: Never

SpacesBeforeTrailingComments: 2

SpacesInAngles: false

SpacesInConditionalStatement: false

SpacesInContainerLiterals: true

SpacesInContainerLiterals: false

SpacesInCStyleCastParentheses: false

SpacesInLineCommentPrefix:

Minimum: 1

Maximum: -1

SpacesInParentheses: false

SpacesInSquareBrackets: false

SpaceBeforeSquareBrackets: false

BitFieldColonSpacing: Both

Standard: Latest

StatementAttributeLikeMacros:

- Q_EMIT

Standard: Auto

StatementMacros:

- Q_UNUSED

- QT_REQUIRE_VERSION

TabWidth: 4

UseCRLF: false

UseTab: Never

TabWidth: 8

UseCRLF: false

UseTab: Never

WhitespaceSensitiveMacros:

- STRINGIZE

- PP_STRINGIZE

- BOOST_PP_STRINGIZE

- NS_SWIFT_NAME

- CF_SWIFT_NAME

...

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

@@ -0,0 +1,165 @@

---

# Enable ALL the things! Except not really

# misc-non-private-member-variables-in-classes: the options don't do anything

# modernize-use-nodiscard: too aggressive, attribute is situationally useful

Checks: "*,\

-altera-*,\

-fuchsia-*,\

-llvmlibc-*,\

-*-braces-around-statements,\

-bugprone-argument-comment,\

-bugprone-easily-swappable-parameters,\

-cppcoreguidelines-avoid-magic-numbers,\

-hicpp-signed-bitwise,\

-llvm-header-guard,\

-llvm-include-order,\

-modernize-use-nodiscard,\

-modernize-use-trailing-return-type,\

-readability-function-cognitive-complexity,\

-readability-magic-numbers,\

fuchsia-multiple-inheritance,\

-misc-no-recursion,\

-misc-non-private-member-variables-in-classes"

WarningsAsErrors: ''

CheckOptions:

- key: 'bugprone-argument-comment.StrictMode'

value: 'true'

# Prefer using enum classes with 2 values for parameters instead of bools

- key: 'bugprone-argument-comment.CommentBoolLiterals'

value: 'true'

- key: 'bugprone-misplaced-widening-cast.CheckImplicitCasts'

value: 'true'

- key: 'bugprone-sizeof-expression.WarnOnSizeOfIntegerExpression'

value: 'true'

- key: 'bugprone-suspicious-string-compare.WarnOnLogicalNotComparison'

value: 'true'

- key: 'readability-simplify-boolean-expr.ChainedConditionalReturn'

value: 'true'

- key: 'readability-simplify-boolean-expr.ChainedConditionalAssignment'

value: 'true'

- key: 'readability-uniqueptr-delete-release.PreferResetCall'

value: 'true'

- key: 'cppcoreguidelines-init-variables.MathHeader'

value: '<cmath>'

- key: 'cppcoreguidelines-narrowing-conversions.PedanticMode'

value: 'true'

- key: 'readability-else-after-return.WarnOnUnfixable'

value: 'true'

- key: 'readability-else-after-return.WarnOnConditionVariables'

value: 'true'

- key: 'readability-inconsistent-declaration-parameter-name.Strict'

value: 'true'

- key: 'readability-qualified-auto.AddConstToQualified'

value: 'true'

- key: 'readability-redundant-access-specifiers.CheckFirstDeclaration'

value: 'true'

# These seem to be the most common identifier styles

- key: 'readability-identifier-naming.AbstractClassCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ClassCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ClassConstantCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ClassMemberCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ClassMethodCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ConstantCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ConstantMemberCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ConstantParameterCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ConstantPointerParameterCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ConstexprFunctionCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ConstexprMethodCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ConstexprVariableCase'

value: 'lower_case'

- key: 'readability-identifier-naming.EnumCase'

value: 'lower_case'

- key: 'readability-identifier-naming.EnumConstantCase'

value: 'lower_case'

- key: 'readability-identifier-naming.FunctionCase'

value: 'lower_case'

- key: 'readability-identifier-naming.GlobalConstantCase'

value: 'lower_case'

- key: 'readability-identifier-naming.GlobalConstantPointerCase'

value: 'lower_case'

- key: 'readability-identifier-naming.GlobalFunctionCase'

value: 'lower_case'

- key: 'readability-identifier-naming.GlobalPointerCase'

value: 'lower_case'

- key: 'readability-identifier-naming.GlobalVariableCase'

value: 'lower_case'

- key: 'readability-identifier-naming.InlineNamespaceCase'

value: 'lower_case'

- key: 'readability-identifier-naming.LocalConstantCase'

value: 'lower_case'

- key: 'readability-identifier-naming.LocalConstantPointerCase'

value: 'lower_case'

- key: 'readability-identifier-naming.LocalPointerCase'

value: 'lower_case'

- key: 'readability-identifier-naming.LocalVariableCase'

value: 'lower_case'

- key: 'readability-identifier-naming.MacroDefinitionCase'

value: 'UPPER_CASE'

- key: 'readability-identifier-naming.MemberCase'

value: 'lower_case'

- key: 'readability-identifier-naming.MethodCase'

value: 'lower_case'

- key: 'readability-identifier-naming.NamespaceCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ParameterCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ParameterPackCase'

value: 'lower_case'

- key: 'readability-identifier-naming.PointerParameterCase'

value: 'lower_case'

- key: 'readability-identifier-naming.PrivateMemberCase'

value: 'lower_case'

- key: 'readability-identifier-naming.PrivateMemberPrefix'

value: 'm_'

- key: 'readability-identifier-naming.PrivateMethodCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ProtectedMemberCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ProtectedMemberPrefix'

value: 'm_'

- key: 'readability-identifier-naming.ProtectedMethodCase'

value: 'lower_case'

- key: 'readability-identifier-naming.PublicMemberCase'

value: 'lower_case'

- key: 'readability-identifier-naming.PublicMethodCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ScopedEnumConstantCase'

value: 'lower_case'

- key: 'readability-identifier-naming.StaticConstantCase'

value: 'lower_case'

- key: 'readability-identifier-naming.StaticVariableCase'

value: 'lower_case'

- key: 'readability-identifier-naming.StructCase'

value: 'lower_case'

- key: 'readability-identifier-naming.TemplateParameterCase'

value: 'CamelCase'

- key: 'readability-identifier-naming.TemplateTemplateParameterCase'

value: 'CamelCase'

- key: 'readability-identifier-naming.TypeAliasCase'

value: 'lower_case'

- key: 'readability-identifier-naming.TypedefCase'

value: 'lower_case'

- key: 'readability-identifier-naming.TypeTemplateParameterCase'

value: 'CamelCase'

- key: 'readability-identifier-naming.TypeTemplateParameterIgnoredRegexp',

value: 'expr-type'

- key: 'readability-identifier-naming.UnionCase'

value: 'lower_case'

- key: 'readability-identifier-naming.ValueTemplateParameterCase'

value: 'CamelCase'

- key: 'readability-identifier-naming.VariableCase'

value: 'lower_case'

- key: 'readability-identifier-naming.VirtualMethodCase'

value: 'lower_case'

...

diff --git a/.codespellrc b/.codespellrc

@@ -0,0 +1,6 @@

[codespell]

builtin = clear,rare,en-GB_to_en-US,names,informal,code

check-filenames =

check-hidden =

skip = */.git,*/build,*/prefix

quiet-level = 2

diff --git a/.gitignore b/.gitignore

@@ -1,2 +1,11 @@

build

.cache

**/.DS_Store

.idea/

.vs/

.vscode/

build/

cmake-build-*/

prefix/

.clangd

CMakeLists.txt.user

CMakeUserPresets.json

compile_commands.json

diff --git a/BUILDING.md b/BUILDING.md

@@ -0,0 +1,60 @@

# Building with CMake

## Build

This project doesn't require any special command-line flags to build to keep

things simple.

Here are the steps for building in release mode with a single-configuration

generator, like the Unix Makefiles one:

```sh

cmake -S . -B build -D CMAKE_BUILD_TYPE=Release

cmake --build build

```

Here are the steps for building in release mode with a multi-configuration

generator, like the Visual Studio ones:

```sh

cmake -S . -B build

cmake --build build --config Release

```

### Building with MSVC

Note that MSVC by default is not standards compliant and you need to pass some

flags to make it behave properly. See the `flags-msvc` preset in the

[CMakePresets.json](CMakePresets.json) file for the flags and with what

variable to provide them to CMake during configuration.

### Building on Apple Silicon

CMake supports building on Apple Silicon properly since 3.20.1. Make sure you

have the [latest version][1] installed.

## Install

This project doesn't require any special command-line flags to install to keep

things simple. As a prerequisite, the project has to be built with the above

commands already.

The below commands require at least CMake 3.15 to run, because that is the

version in which [Install a Project][2] was added.

Here is the command for installing the release mode artifacts with a

single-configuration generator, like the Unix Makefiles one:

```sh

cmake --install build

```

Here is the command for installing the release mode artifacts with a

multi-configuration generator, like the Visual Studio ones:

```sh

cmake --install build --config Release

```

[1]: https://cmake.org/download/

[2]: https://cmake.org/cmake/help/latest/manual/cmake.1.html#install-a-project

diff --git a/CMakeLists.txt b/CMakeLists.txt

@@ -1,20 +1,42 @@

cmake_minimum_required(VERSION 3.25.2)

set(CMAKE_EXPORT_COMPILE_COMMANDS ON)

cmake_minimum_required(VERSION 3.14)

include(cmake/prelude.cmake)

project(

doasku

VERSION 0.0.2

VERSION 0.0.3

DESCRIPTION "Sudoku madness"

HOMEPAGE_URL https://git.dimitrijedobrota.com/doasku.git

HOMEPAGE_URL "https://git.dimitrijedobrota.com/doasku.git"

LANGUAGES CXX

)

set(CMAKE_CXX_STANDARD 20)

set(CMAKE_CXX_STANDARD_REQUIRED ON)

set(CMAKE_CXX_EXTENSIONS OFF)

include(cmake/project-is-top-level.cmake)

include(cmake/variables.cmake)

# ---- Declare executable ----

add_executable(doasku_exe source/main.cpp source/grid.cpp source/ref.cpp)

add_executable(doasku::exe ALIAS doasku_exe)

set_property(TARGET doasku_exe PROPERTY OUTPUT_NAME doasku)

target_compile_features(doasku_exe PRIVATE cxx_std_20)

# ---- Install rules ----

if(NOT CMAKE_SKIP_INSTALL_RULES)

include(cmake/install-rules.cmake)

endif()

# ---- Developer mode ----

if(NOT CMAKE_BUILD_TYPE)

set(CMAKE_BUILD_TYPE Release CACHE STRING "Build type" FORCE)

if(NOT doasku_DEVELOPER_MODE)

return()

elseif(NOT PROJECT_IS_TOP_LEVEL)

message(

AUTHOR_WARNING

"Developer mode is intended for developers of doasku"

)

endif()

add_subdirectory(src)

include(cmake/dev-mode.cmake)

diff --git a/CMakePresets.json b/CMakePresets.json

@@ -0,0 +1,159 @@

{

"version": 2,

"cmakeMinimumRequired": {

"major": 3,

"minor": 14,

"patch": 0

"configurePresets": [

{

"name": "cmake-pedantic",

"hidden": true,

"warnings": {

"dev": true,

"deprecated": true,

"uninitialized": true,

"unusedCli": true,

"systemVars": false

"errors": {

"dev": true,

"deprecated": true

}

{

"name": "dev-mode",

"hidden": true,

"inherits": "cmake-pedantic",

"cacheVariables": {

"doasku_DEVELOPER_MODE": "ON"

}

{

"name": "cppcheck",

"hidden": true,

"cacheVariables": {

"CMAKE_CXX_CPPCHECK": "cppcheck;--inline-suppr"

}

{

"name": "clang-tidy",

"hidden": true,

"cacheVariables": {

"CMAKE_CXX_CLANG_TIDY": "clang-tidy;--header-filter=^${sourceDir}/"

}

{

"name": "ci-std",

"description": "This preset makes sure the project actually builds with at least the specified standard",

"hidden": true,

"cacheVariables": {

"CMAKE_CXX_EXTENSIONS": "OFF",

"CMAKE_CXX_STANDARD": "20",

"CMAKE_CXX_STANDARD_REQUIRED": "ON"

}

{

"name": "flags-gcc-clang",

"description": "These flags are supported by both GCC and Clang",

"hidden": true,

"cacheVariables": {

"CMAKE_CXX_FLAGS": "-U_FORTIFY_SOURCE -D_FORTIFY_SOURCE=3 -D_GLIBCXX_ASSERTIONS=1 -fstack-protector-strong -fcf-protection=full -fstack-clash-protection -Wall -Wextra -Wpedantic -Wconversion -Wsign-conversion -Wcast-qual -Wformat=2 -Wundef -Werror=float-equal -Wshadow -Wcast-align -Wunused -Wnull-dereference -Wdouble-promotion -Wimplicit-fallthrough -Wextra-semi -Woverloaded-virtual -Wnon-virtual-dtor -Wold-style-cast",

"CMAKE_EXE_LINKER_FLAGS": "-Wl,--allow-shlib-undefined,--as-needed,-z,noexecstack,-z,relro,-z,now,-z,nodlopen",

"CMAKE_SHARED_LINKER_FLAGS": "-Wl,--allow-shlib-undefined,--as-needed,-z,noexecstack,-z,relro,-z,now,-z,nodlopen"

}

{

"name": "flags-appleclang",

"hidden": true,

"cacheVariables": {

"CMAKE_CXX_FLAGS": "-fstack-protector-strong -Wall -Wextra -Wpedantic -Wconversion -Wsign-conversion -Wcast-qual -Wformat=2 -Wundef -Werror=float-equal -Wshadow -Wcast-align -Wunused -Wnull-dereference -Wdouble-promotion -Wimplicit-fallthrough -Wextra-semi -Woverloaded-virtual -Wnon-virtual-dtor -Wold-style-cast"

}

{

"name": "flags-msvc",

"description": "Note that all the flags after /W4 are required for MSVC to conform to the language standard",

"hidden": true,

"cacheVariables": {

"CMAKE_CXX_FLAGS": "/sdl /guard:cf /utf-8 /diagnostics:caret /w14165 /w44242 /w44254 /w44263 /w34265 /w34287 /w44296 /w44365 /w44388 /w44464 /w14545 /w14546 /w14547 /w14549 /w14555 /w34619 /w34640 /w24826 /w14905 /w14906 /w14928 /w45038 /W4 /permissive- /volatile:iso /Zc:inline /Zc:preprocessor /Zc:enumTypes /Zc:lambda /Zc:__cplusplus /Zc:externConstexpr /Zc:throwingNew /EHsc",

"CMAKE_EXE_LINKER_FLAGS": "/machine:x64 /guard:cf"

}

{

"name": "ci-linux",

"inherits": ["flags-gcc-clang", "ci-std"],

"generator": "Unix Makefiles",

"hidden": true,

"cacheVariables": {

"CMAKE_BUILD_TYPE": "Release"

}

{

"name": "ci-darwin",

"inherits": ["flags-appleclang", "ci-std"],

"generator": "Xcode",

"hidden": true

{

"name": "ci-win64",

"inherits": ["flags-msvc", "ci-std"],

"generator": "Visual Studio 17 2022",

"architecture": "x64",

"hidden": true

{

"name": "coverage-linux",

"binaryDir": "${sourceDir}/build/coverage",

"inherits": "ci-linux",

"hidden": true,

"cacheVariables": {

"ENABLE_COVERAGE": "ON",

"CMAKE_BUILD_TYPE": "Coverage",

"CMAKE_CXX_FLAGS_COVERAGE": "-Og -g --coverage -fkeep-inline-functions -fkeep-static-functions",

"CMAKE_EXE_LINKER_FLAGS_COVERAGE": "--coverage",

"CMAKE_SHARED_LINKER_FLAGS_COVERAGE": "--coverage"

}

{

"name": "ci-coverage",

"inherits": ["coverage-linux", "dev-mode"],

"cacheVariables": {

"COVERAGE_HTML_COMMAND": ""

}

{

"name": "ci-sanitize",

"binaryDir": "${sourceDir}/build/sanitize",

"inherits": ["ci-linux", "dev-mode"],

"cacheVariables": {

"CMAKE_BUILD_TYPE": "Sanitize",

"CMAKE_CXX_FLAGS_SANITIZE": "-U_FORTIFY_SOURCE -O2 -g -fsanitize=address,undefined -fno-omit-frame-pointer -fno-common"

}

{

"name": "ci-build",

"binaryDir": "${sourceDir}/build",

"hidden": true

{

"name": "ci-multi-config",

"description": "Speed up multi-config generators by generating only one configuration instead of the defaults",

"hidden": true,

"cacheVariables": {

"CMAKE_CONFIGURATION_TYPES": "Release"

}

{

"name": "ci-macos",

"inherits": ["ci-build", "ci-darwin", "dev-mode", "ci-multi-config"]

{

"name": "ci-ubuntu",

"inherits": ["ci-build", "ci-linux", "clang-tidy", "cppcheck", "dev-mode"]

{

"name": "ci-windows",

"inherits": ["ci-build", "ci-win64", "dev-mode", "ci-multi-config"]

}

]

}

diff --git a/CODE_OF_CONDUCT.md b/CODE_OF_CONDUCT.md

@@ -0,0 +1,5 @@

# Code of Conduct

* You will be judged by your contributions first, and your sense of humor

second.

* Nobody owes you anything.

diff --git a/CONTRIBUTING.md b/CONTRIBUTING.md

@@ -0,0 +1,14 @@

# Contributing

## Code of Conduct

Please see the [`CODE_OF_CONDUCT.md`](CODE_OF_CONDUCT.md) document.

## Getting started

Helpful notes for developers can be found in the [`HACKING.md`](HACKING.md)

document.

In addition to he above, if you use the presets file as instructed, then you

should NOT check it into source control, just as the CMake documentation

suggests.

diff --git a/HACKING.md b/HACKING.md

@@ -0,0 +1,149 @@

# Hacking

Here is some wisdom to help you build and test this project as a developer and

potential contributor.

If you plan to contribute, please read the [CONTRIBUTING](CONTRIBUTING.md)

guide.

## Developer mode

Build system targets that are only useful for developers of this project are

hidden if the `doasku_DEVELOPER_MODE` option is disabled. Enabling this

option makes tests and other developer targets and options available. Not

enabling this option means that you are a consumer of this project and thus you

have no need for these targets and options.

Developer mode is always set to on in CI workflows.

### Presets

This project makes use of [presets][1] to simplify the process of configuring

the project. As a developer, you are recommended to always have the [latest

CMake version][2] installed to make use of the latest Quality-of-Life

additions.

You have a few options to pass `doasku_DEVELOPER_MODE` to the configure

command, but this project prefers to use presets.

As a developer, you should create a `CMakeUserPresets.json` file at the root of

the project:

```json

{

"version": 2,

"cmakeMinimumRequired": {

"major": 3,

"minor": 14,

"patch": 0

"configurePresets": [

{

"name": "dev",

"binaryDir": "${sourceDir}/build/dev",

"inherits": ["dev-mode", "ci-<os>"],

"cacheVariables": {

"CMAKE_BUILD_TYPE": "Debug"

}

"buildPresets": [

{

"name": "dev",

"configurePreset": "dev",

"configuration": "Debug"

}

"testPresets": [

{

"name": "dev",

"configurePreset": "dev",

"configuration": "Debug",

"output": {

"outputOnFailure": true

}

]

}

```

You should replace `<os>` in your newly created presets file with the name of

the operating system you have, which may be `win64`, `linux` or `darwin`. You

can see what these correspond to in the

[`CMakePresets.json`](CMakePresets.json) file.

`CMakeUserPresets.json` is also the perfect place in which you can put all

sorts of things that you would otherwise want to pass to the configure command

in the terminal.

> **Note**

> Some editors are pretty greedy with how they open projects with presets.

> Some just randomly pick a preset and start configuring without your consent,

> which can be confusing. Make sure that your editor configures when you

> actually want it to, for example in CLion you have to make sure only the

> `dev-dev preset` has `Enable profile` ticked in

> `File > Settings... > Build, Execution, Deployment > CMake` and in Visual

> Studio you have to set the option `Never run configure step automatically`

> in `Tools > Options > CMake` **prior to opening the project**, after which

> you can manually configure using `Project > Configure Cache`.

### Configure, build and test

If you followed the above instructions, then you can configure, build and test

the project respectively with the following commands from the project root on

any operating system with any build system:

```sh

cmake --preset=dev

cmake --build --preset=dev

ctest --preset=dev

```

If you are using a compatible editor (e.g. VSCode) or IDE (e.g. CLion, VS), you

will also be able to select the above created user presets for automatic

integration.

Please note that both the build and test commands accept a `-j` flag to specify

the number of jobs to use, which should ideally be specified to the number of

threads your CPU has. You may also want to add that to your preset using the

`jobs` property, see the [presets documentation][1] for more details.

### Developer mode targets

These are targets you may invoke using the build command from above, with an

additional `-t <target>` flag:

#### `coverage`

Available if `ENABLE_COVERAGE` is enabled. This target processes the output of

the previously run tests when built with coverage configuration. The commands

this target runs can be found in the `COVERAGE_TRACE_COMMAND` and

`COVERAGE_HTML_COMMAND` cache variables. The trace command produces an info

file by default, which can be submitted to services with CI integration. The

HTML command uses the trace command's output to generate an HTML document to

`<binary-dir>/coverage_html` by default.

#### `docs`

Available if `BUILD_MCSS_DOCS` is enabled. Builds to documentation using

Doxygen and m.css. The output will go to `<binary-dir>/docs` by default

(customizable using `DOXYGEN_OUTPUT_DIRECTORY`).

#### `format-check` and `format-fix`

These targets run the clang-format tool on the codebase to check errors and to

fix them respectively. Customization available using the `FORMAT_PATTERNS` and

`FORMAT_COMMAND` cache variables.

#### `run-exe`

Runs the executable target `doasku_exe`.

#### `spell-check` and `spell-fix`

These targets run the codespell tool on the codebase to check errors and to fix

them respectively. Customization available using the `SPELL_COMMAND` cache

variable.

[1]: https://cmake.org/cmake/help/latest/manual/cmake-presets.7.html

[2]: https://cmake.org/download/

diff --git a/LICENSE.md b/LICENSE.md

@@ -0,0 +1,21 @@

MIT License

Permission is hereby granted, free of charge, to any person obtaining a copy

of this software and associated documentation files (the "Software"), to deal

in the Software without restriction, including without limitation the rights

to use, copy, modify, merge, publish, distribute, sublicense, and/or sell

copies of the Software, and to permit persons to whom the Software is

furnished to do so, subject to the following conditions:

The above copyright notice and this permission notice shall be included in all

copies or substantial portions of the Software.

THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR

IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,

FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE

AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER

LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,

OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE

SOFTWARE.

diff --git a/README.md b/README.md

@@ -0,0 +1,15 @@

# doasku

This is the doasku project.

# Building and installing

See the [BUILDING](BUILDING.md) document.

# Contributing

See the [CONTRIBUTING](CONTRIBUTING.md) document.

# Licensing

This project is licensed under the MIT License - see the LICENSE.md file for details

diff --git a/cmake/coverage.cmake b/cmake/coverage.cmake

@@ -0,0 +1,33 @@

# ---- Variables ----

# We use variables separate from what CTest uses, because those have

# customization issues

set(

COVERAGE_TRACE_COMMAND

lcov -c -q

-o "${PROJECT_BINARY_DIR}/coverage.info"

-d "${PROJECT_BINARY_DIR}"

--include "${PROJECT_SOURCE_DIR}/*"

CACHE STRING

"; separated command to generate a trace for the 'coverage' target"

)

set(

COVERAGE_HTML_COMMAND

genhtml --legend -f -q

"${PROJECT_BINARY_DIR}/coverage.info"

-p "${PROJECT_SOURCE_DIR}"

-o "${PROJECT_BINARY_DIR}/coverage_html"

CACHE STRING

"; separated command to generate an HTML report for the 'coverage' target"

)

# ---- Coverage target ----

add_custom_target(

coverage

COMMAND ${COVERAGE_TRACE_COMMAND}

COMMAND ${COVERAGE_HTML_COMMAND}

COMMENT "Generating coverage report"

VERBATIM

)

diff --git a/cmake/dev-mode.cmake b/cmake/dev-mode.cmake

@@ -0,0 +1,18 @@

include(cmake/folders.cmake)

add_custom_target(

run-exe

COMMAND doasku_exe

VERBATIM

)

add_dependencies(run-exe doasku_exe)

option(ENABLE_COVERAGE "Enable coverage support separate from CTest's" OFF)

if(ENABLE_COVERAGE)

include(cmake/coverage.cmake)

endif()

include(cmake/lint-targets.cmake)

include(cmake/spell-targets.cmake)

add_folders(Project)

diff --git a/cmake/folders.cmake b/cmake/folders.cmake

@@ -0,0 +1,21 @@

set_property(GLOBAL PROPERTY USE_FOLDERS YES)

# Call this function at the end of a directory scope to assign a folder to

# targets created in that directory. Utility targets will be assigned to the

# UtilityTargets folder, otherwise to the ${name}Targets folder. If a target

# already has a folder assigned, then that target will be skipped.

function(add_folders name)

get_property(targets DIRECTORY PROPERTY BUILDSYSTEM_TARGETS)

foreach(target IN LISTS targets)

get_property(folder TARGET "${target}" PROPERTY FOLDER)

if(DEFINED folder)

continue()

endif()

set(folder Utility)

get_property(type TARGET "${target}" PROPERTY TYPE)

if(NOT type STREQUAL "UTILITY")

set(folder "${name}")

endif()

set_property(TARGET "${target}" PROPERTY FOLDER "${folder}Targets")

endforeach()

endfunction()

diff --git a/cmake/install-rules.cmake b/cmake/install-rules.cmake

@@ -0,0 +1,8 @@

install(

TARGETS doasku_exe

RUNTIME COMPONENT doasku_Runtime

)

if(PROJECT_IS_TOP_LEVEL)

include(CPack)

endif()

diff --git a/cmake/lint-targets.cmake b/cmake/lint-targets.cmake

@@ -0,0 +1,33 @@

set(

FORMAT_PATTERNS

source/*.cpp source/*.hpp

include/*.hpp

test/*.cpp test/*.hpp

CACHE STRING

"; separated patterns relative to the project source dir to format"

)

set(FORMAT_COMMAND clang-format CACHE STRING "Formatter to use")

add_custom_target(

format-check

COMMAND "${CMAKE_COMMAND}"

-D "FORMAT_COMMAND=${FORMAT_COMMAND}"

-D "PATTERNS=${FORMAT_PATTERNS}"

-P "${PROJECT_SOURCE_DIR}/cmake/lint.cmake"

WORKING_DIRECTORY "${PROJECT_SOURCE_DIR}"

COMMENT "Linting the code"

VERBATIM

)

add_custom_target(

format-fix

COMMAND "${CMAKE_COMMAND}"

-D "FORMAT_COMMAND=${FORMAT_COMMAND}"

-D "PATTERNS=${FORMAT_PATTERNS}"

-D FIX=YES

-P "${PROJECT_SOURCE_DIR}/cmake/lint.cmake"

WORKING_DIRECTORY "${PROJECT_SOURCE_DIR}"

COMMENT "Fixing the code"

VERBATIM

)

diff --git a/cmake/lint.cmake b/cmake/lint.cmake

@@ -0,0 +1,51 @@

cmake_minimum_required(VERSION 3.14)

macro(default name)

if(NOT DEFINED "${name}")

set("${name}" "${ARGN}")

endif()

endmacro()

default(FORMAT_COMMAND clang-format)

default(

PATTERNS

source/*.cpp source/*.hpp

include/*.hpp

test/*.cpp test/*.hpp

)

default(FIX NO)

set(flag --output-replacements-xml)

set(args OUTPUT_VARIABLE output)

if(FIX)

set(flag -i)

set(args "")

endif()

file(GLOB_RECURSE files ${PATTERNS})

set(badly_formatted "")

set(output "")

string(LENGTH "${CMAKE_SOURCE_DIR}/" path_prefix_length)

foreach(file IN LISTS files)

execute_process(

COMMAND "${FORMAT_COMMAND}" --style=file "${flag}" "${file}"

WORKING_DIRECTORY "${CMAKE_SOURCE_DIR}"

RESULT_VARIABLE result

${args}

)

if(NOT result EQUAL "0")

message(FATAL_ERROR "'${file}': formatter returned with ${result}")

endif()

if(NOT FIX AND output MATCHES "\n<replacement offset")

string(SUBSTRING "${file}" "${path_prefix_length}" -1 relative_file)

list(APPEND badly_formatted "${relative_file}")

endif()

set(output "")

endforeach()

if(NOT badly_formatted STREQUAL "")

list(JOIN badly_formatted "\n" bad_list)

message("The following files are badly formatted:\n\n${bad_list}\n")

message(FATAL_ERROR "Run again with FIX=YES to fix these files.")

endif()

diff --git a/cmake/prelude.cmake b/cmake/prelude.cmake

@@ -0,0 +1,10 @@

# ---- In-source guard ----

if(CMAKE_SOURCE_DIR STREQUAL CMAKE_BINARY_DIR)

message(

FATAL_ERROR

"In-source builds are not supported. "

"Please read the BUILDING document before trying to build this project. "

"You may need to delete 'CMakeCache.txt' and 'CMakeFiles/' first."

)

endif()

diff --git a/cmake/project-is-top-level.cmake b/cmake/project-is-top-level.cmake

@@ -0,0 +1,6 @@

# This variable is set by project() in CMake 3.21+

string(

COMPARE EQUAL

"${CMAKE_SOURCE_DIR}" "${PROJECT_SOURCE_DIR}"

PROJECT_IS_TOP_LEVEL

)

diff --git a/cmake/spell-targets.cmake b/cmake/spell-targets.cmake

@@ -0,0 +1,22 @@

set(SPELL_COMMAND codespell CACHE STRING "Spell checker to use")

add_custom_target(

spell-check

COMMAND "${CMAKE_COMMAND}"

-D "SPELL_COMMAND=${SPELL_COMMAND}"

-P "${PROJECT_SOURCE_DIR}/cmake/spell.cmake"

WORKING_DIRECTORY "${PROJECT_SOURCE_DIR}"

COMMENT "Checking spelling"

VERBATIM

)

add_custom_target(

spell-fix

COMMAND "${CMAKE_COMMAND}"

-D "SPELL_COMMAND=${SPELL_COMMAND}"

-D FIX=YES

-P "${PROJECT_SOURCE_DIR}/cmake/spell.cmake"

WORKING_DIRECTORY "${PROJECT_SOURCE_DIR}"

COMMENT "Fixing spelling errors"

VERBATIM

)

diff --git a/cmake/spell.cmake b/cmake/spell.cmake

@@ -0,0 +1,29 @@

cmake_minimum_required(VERSION 3.14)

macro(default name)

if(NOT DEFINED "${name}")

set("${name}" "${ARGN}")

endif()

endmacro()

default(SPELL_COMMAND codespell)

default(FIX NO)

set(flag "")

if(FIX)

set(flag -w)

endif()

execute_process(

COMMAND "${SPELL_COMMAND}" ${flag}

WORKING_DIRECTORY "${CMAKE_SOURCE_DIR}"

RESULT_VARIABLE result

)

if(result EQUAL "65")

message(FATAL_ERROR "Run again with FIX=YES to fix these errors.")

elseif(result EQUAL "64")

message(FATAL_ERROR "Spell checker printed the usage info. Bad arguments?")

elseif(NOT result EQUAL "0")

message(FATAL_ERROR "Spell checker returned with ${result}")

endif()

diff --git a/cmake/variables.cmake b/cmake/variables.cmake

@@ -0,0 +1,28 @@

# ---- Developer mode ----

# Developer mode enables targets and code paths in the CMake scripts that are

# only relevant for the developer(s) of doasku

# Targets necessary to build the project must be provided unconditionally, so

# consumers can trivially build and package the project

if(PROJECT_IS_TOP_LEVEL)

option(doasku_DEVELOPER_MODE "Enable developer mode" OFF)

endif()

# ---- Warning guard ----

# target_include_directories with the SYSTEM modifier will request the compiler

# to omit warnings from the provided paths, if the compiler supports that

# This is to provide a user experience similar to find_package when

# add_subdirectory or FetchContent is used to consume this project

set(warning_guard "")

if(NOT PROJECT_IS_TOP_LEVEL)

option(

doasku_INCLUDES_WITH_SYSTEM

"Use SYSTEM modifier for doasku's includes, disabling warnings"

)

mark_as_advanced(doasku_INCLUDES_WITH_SYSTEM)

if(doasku_INCLUDES_WITH_SYSTEM)

set(warning_guard SYSTEM)

endif()

diff --git a/include/cord.hpp b/include/cord.hpp

@@ -1,45 +0,0 @@

#ifndef DOASKO_CORD_HPP

#define DOASKO_CORD_HPP

#include <cassert>

#include <cinttypes>

#include <utility>

struct cord_t {

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; }

uint8_t row() const { return value / 3; }

uint8_t col() const { return value % 3; }

uint8_t value;

};

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) {}

cord_t subgrid() const { return subgrid_i; }

cord_t field() const { return field_i; }

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};

}

private:

cord_t subgrid_i;

cord_t field_i;

};

#endif

diff --git a/include/grid.hpp b/include/grid.hpp

@@ -1,44 +0,0 @@

#ifndef DOASKU_GRID_HPP

#define DOASKU_GRID_HPP

#include <string>

#include <utility>

#include "cord.hpp"

#include "ref.hpp"

class Grid {

public:

Grid(const std::string &s);

bool solve();

void print() const;

private:

using operation_t = std::tuple<acord_t, uint16_t>;

void op_set(operation_t op);

void op_mask(operation_t op);

void op_clear(operation_t op);

void op_clear_row(operation_t op);

void op_clear_col(operation_t op);

void op_clear_row_rel(operation_t op);

void op_clear_col_rel(operation_t op);

void _set(acord_t ab, uint8_t value);

void _mask(acord_t ab, uint16_t mask);

void _clear(acord_t ab, uint8_t value);

void _clear_row(cord_t sg, uint8_t row, uint8_t value);

void _clear_col(cord_t sg, uint8_t col, uint8_t value);

bool _is_finished(uint8_t subgrid);

bool _is_finished();

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

bool changed = false;

};

#endif

diff --git a/include/ref.hpp b/include/ref.hpp

@@ -1,63 +0,0 @@

#ifndef DOASKU_REF_HPP

#define DOASKU_REF_HPP

#include <cstdint>

#include <utility>

#include <vector>

class Ref {

public:

using change_t = std::tuple<uint8_t, uint16_t>;

using changes_t = std::vector<change_t>;

uint16_t get(uint8_t field) const { return value[field]; }

uint16_t get_ref(uint8_t value) const { return ref[value]; }

uint16_t get_value(uint8_t field) const { return res[field]; }

void clear(uint8_t field, uint8_t value);

void set(uint8_t field, uint8_t value);

changes_t get_hidden_singles() const;

changes_t get_naked_singles() const;

auto get_hidden_pairs() const { return get_hidden(2); }

auto get_hidden_triplets() const { return get_hidden(3); }

auto get_hidden_quads() const { return get_hidden(4); }

auto get_naked_pairs() const { return get_naked(2); }

auto get_naked_triplets() const { return get_naked(3); }

auto get_naked_quads() const { return get_naked(4); }

auto get_pointing_row() const { return get_pointing(0x7, 0); }

auto get_pointing_col() const { return get_pointing(0x49, 1); }

private:

changes_t get_naked(int number) const;

changes_t get_hidden(int number) const;

changes_t get_pointing(uint16_t mask, bool seen) const;

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

uint16_t val, uint16_t mask) const;

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

uint16_t val) const;

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 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};

mutable uint16_t seen_naked[4] = {0};

mutable uint16_t seen_point[2] = {0};

};

#endif

diff --git a/source/cord.hpp b/source/cord.hpp

@@ -0,0 +1,65 @@

#ifndef DOASKO_CORD_HPP

#define DOASKO_CORD_HPP

#include <cassert>

#include <cinttypes>

#include <utility>

struct cord_t

{

explicit cord_t(uint8_t value)

: m_value(value)

{

assert(value < 9);

}

cord_t(uint8_t row, uint8_t col)

: m_value(static_cast<uint8_t>(row * 3 + col))

{

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

}

// NOLINTNEXTLINE

operator uint8_t() const { return m_value; }

uint8_t row() const { return m_value / 3; }

uint8_t col() const { return m_value % 3; }

uint8_t m_value;

};

class acord_t

{

public:

acord_t(cord_t subgrid, cord_t field)

: m_subgrid(subgrid)

, m_field(field)

{

}

acord_t(uint8_t row, uint8_t col)

: m_subgrid(row / 3, col / 3)

, m_field(row % 3, col % 3)

{

}

cord_t subgrid() const { return m_subgrid; }

cord_t field() const { return m_field; }

uint8_t row() const

{

return static_cast<uint8_t>(m_subgrid.row() * 3 + m_field.row());

}

uint8_t col() const

{

return static_cast<uint8_t>(m_subgrid.col() * 3 + m_field.col());

}

std::tuple<cord_t, cord_t> relative() const { return {m_subgrid, m_field}; }

private:

cord_t m_subgrid;

cord_t m_field;

};

#endif

diff --git a/source/grid.cpp b/source/grid.cpp

@@ -0,0 +1,281 @@

#include <algorithm>

#include <bitset>

#include <functional>

#include <iostream>

#include "grid.hpp"

template<class Input, class UnaryFunc>

UnaryFunc for_each(Input input, UnaryFunc func)

{

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

}

using other_t = std::tuple<uint8_t, uint8_t>;

other_t other_subgrid_row(uint8_t subgrid)

{

static const auto mapping = std::to_array<other_t>({{1, 2},

{0, 2},

{0, 1},

{4, 5},

{3, 5},

{3, 4},

{7, 8},

{6, 8},

{6, 7}});

return mapping.at(subgrid);

}

other_t other_subgrid_col(uint8_t subgrid)

{

static const auto mapping = std::to_array<other_t>({{3, 6},

{4, 7},

{5, 8},

{0, 6},

{1, 7},

{2, 8},

{0, 3},

{1, 4},

{2, 5}});

return mapping.at(subgrid);

}

grid::grid(const std::string& str)

{

std::size_t idx = 0;

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

for (uint8_t j = 0; j < 9; j++, idx++) {

if (str[idx] == '0') continue;

set({i, j}, static_cast<uint8_t>(str[idx] - '1'));

}

bool grid::solve()

{

// clang-format off

static const auto sub_op =

[this](auto opr, const auto func) {

for(uint8_t subgrid = 0; subgrid < 9; subgrid++) {

for_each(std::invoke(func, m_subgrids.at(subgrid)), [&](auto& chng) {

std::invoke(opr, this, operation_t({cord_t(subgrid), cord_t(std::get<0>(chng))}, std::get<1>(chng)));

});

}

return m_changed;

};

static const auto row_op =

[this](auto opr, const auto func) {

for(uint8_t row = 0; row < 9; row++) {

for_each(std::invoke(func, m_rows.at(row)), [&](auto& chng) {

std::invoke(opr, this, operation_t({row, std::get<0>(chng)}, std::get<1>(chng)));

});

}

return m_changed;

};

static const auto col_op =

[this](auto opr, const auto func) {

for(uint8_t col = 0; col < 9; col++) {

for_each(std::invoke(func, m_cols.at(col)), [&](auto &chng) {

std::invoke(opr, this, operation_t({std::get<0>(chng), col}, std::get<1>(chng)));

});

}

return m_changed;

};

static const auto all_op =

[this](auto opr, const auto func) {

sub_op(opr, func), row_op(opr, func), col_op(opr, func);

return m_changed;

};

// clang-format on

m_changed = true;

while (m_changed) {

m_changed = false;

if (sub_op(&grid::op_set, &ref::get_naked_singles)) continue;

if (all_op(&grid::op_set, &ref::get_hidden_singles)) continue;

if (sub_op(&grid::op_clear_row, &ref::get_pointing_row)) continue;

if (sub_op(&grid::op_clear_col, &ref::get_pointing_col)) continue;

if (all_op(&grid::op_mask, &ref::get_hidden_pairs)) continue;

if (all_op(&grid::op_mask, &ref::get_hidden_triplets)) continue;

if (all_op(&grid::op_mask, &ref::get_hidden_quads)) continue;

if (all_op(&grid::op_clear, &ref::get_naked_pairs)) continue;

if (all_op(&grid::op_clear, &ref::get_naked_triplets)) continue;

if (all_op(&grid::op_clear, &ref::get_naked_quads)) continue;

row_op(&grid::op_clear_row_rel, &ref::get_pointing_row);

col_op(&grid::op_clear_col_rel, &ref::get_pointing_row);

}

return is_finished();

}

void grid::print() const

{

// clang-format off

static const auto print_i = [](const auto& refs, uint16_t (ref::*func)(uint8_t) const, bool bits) {

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

for (uint8_t j = 0; j < 9; j++) {

const cord_t subgrid = {static_cast<uint8_t>(i / 3), static_cast<uint8_t>(j / 3)};

const cord_t field = {static_cast<uint8_t>(i % 3), static_cast<uint8_t>(j % 3)};

const uint16_t value = std::invoke(func, refs.at(subgrid), field);

const std::bitset<9>bts(value);

if (bits) std::cout << bts << " ";

else std::cout << value << " ";

if (j % 3 == 2) std::cout << " ";

}

std::cout << std::endl;

if (i % 3 == 2) std::cout << std::endl;

}

};

// clang-format on

std::cout << "Field: " << std::endl;

print_i(m_subgrids, &ref::get, true);

std::cout << "Refs: " << std::endl;

print_i(m_subgrids, &ref::get_ref, true);

std::cout << "Board: " << std::endl;

print_i(m_subgrids, &ref::get_value, false);

}

void grid::op_set(operation_t opr)

{

set(std::get<0>(opr), static_cast<uint8_t>(std::get<1>(opr)));

m_changed = true;

}

void grid::op_mask(operation_t opr)

{

mask(std::get<0>(opr), std::get<1>(opr));

m_changed = true;

}

void grid::op_clear(operation_t opr)

{

clear(std::get<0>(opr), static_cast<uint8_t>(std::get<1>(opr)));

m_changed = true;

}

void grid::op_clear_row(operation_t opr)

{

const auto val = static_cast<uint8_t>(std::get<1>(opr));

const auto abs = std::get<0>(opr);

const auto [r1, r2] = other_subgrid_row(abs.subgrid());

clear_row(cord_t(r1), abs.field(), val);

clear_row(cord_t(r2), abs.field(), val);

m_changed = true;

}

void grid::op_clear_col(operation_t opr)

{

const auto val = static_cast<uint8_t>(std::get<1>(opr));

const auto abs = std::get<0>(opr);

const auto [c1, c2] = other_subgrid_col(abs.subgrid());

clear_col(cord_t(c1), abs.field(), val);

clear_col(cord_t(c2), abs.field(), val);

m_changed = true;

}

void grid::op_clear_row_rel(operation_t opr)

{

const auto val = static_cast<uint8_t>(std::get<1>(opr));

const auto abs = std::get<0>(opr);

const auto [r1, r2] = other_subgrid_row(abs.row());

clear_row(cord_t((r1 / 3), abs.col()), r1 % 3, val);

clear_row(cord_t((r2 / 3), abs.col()), r2 % 3, val);

m_changed = true;

}

void grid::op_clear_col_rel(operation_t opr)

{

const auto val = static_cast<uint8_t>(std::get<1>(opr));

const auto abs = std::get<0>(opr);

const auto [c1, c2] = other_subgrid_row(abs.col());

clear_col(cord_t(abs.row(), c1 / 3), c1 % 3, val);

clear_col(cord_t(abs.row(), c2 / 3), c2 % 3, val);

m_changed = true;

}

void grid::set(acord_t abs, uint8_t value)

{

m_rows.at(abs.row()).set(abs.col(), value);

m_cols.at(abs.col()).set(abs.row(), value);

m_subgrids.at(abs.subgrid()).set(abs.field(), value);

clear_row(abs.subgrid(), 0, value);

clear_row(abs.subgrid(), 1, value);

clear_row(abs.subgrid(), 2, value);

const auto [r1, r2] = other_subgrid_row(abs.subgrid());

clear_row(cord_t(r1), abs.field().row(), value);

clear_row(cord_t(r2), abs.field().row(), value);

const auto [c1, c2] = other_subgrid_col(abs.subgrid());

clear_col(cord_t(c1), abs.field().col(), value);

clear_col(cord_t(c2), abs.field().col(), value);

}

void grid::mask(acord_t abs, uint16_t mask)

{

while (mask != 0) {

const auto idx = static_cast<uint8_t>(std::countr_zero(mask));

clear(abs, idx);

mask ^= 1ULL << idx;

}

void grid::clear(acord_t abs, uint8_t value)

{

m_subgrids.at(abs.subgrid()).clear(abs.field(), value);

m_rows.at(abs.row()).clear(abs.col(), value);

m_cols.at(abs.col()).clear(abs.row(), value);

}

void grid::clear_row(cord_t sbgrd, uint8_t row, uint8_t value)

{

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

clear({sbgrd, {row, i}}, value);

}

void grid::clear_col(cord_t sbgrd, uint8_t col, uint8_t value)

{

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

clear({sbgrd, {i, col}}, value);

}

bool grid::is_finished(uint8_t subgrid)

{

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

if (m_subgrids.at(subgrid).get_value(i) == 0) return false;

}

return true;

}

bool grid::is_finished()

{

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

if (!is_finished(i)) return false;

}

return true;

}

diff --git a/source/grid.hpp b/source/grid.hpp

@@ -0,0 +1,46 @@

#ifndef DOASKU_GRID_HPP

#define DOASKU_GRID_HPP

#include <array>

#include <string>

#include <utility>

#include "cord.hpp"

#include "ref.hpp"

class grid

{

public:

explicit grid(const std::string& str);

bool solve();

void print() const;

private:

using operation_t = std::tuple<acord_t, uint16_t>;

void op_set(operation_t opr);

void op_mask(operation_t opr);

void op_clear(operation_t opr);

void op_clear_row(operation_t opr);

void op_clear_col(operation_t opr);

void op_clear_row_rel(operation_t opr);

void op_clear_col_rel(operation_t opr);

void set(acord_t abs, uint8_t value);

void mask(acord_t abs, uint16_t mask);

void clear(acord_t abs, uint8_t value);

void clear_row(cord_t sbgrd, uint8_t row, uint8_t value);

void clear_col(cord_t sbgrd, uint8_t col, uint8_t value);

bool is_finished(uint8_t subgrid);

bool is_finished();

std::array<ref, 9> m_subgrids, m_rows, m_cols;

bool m_changed = false;

};

#endif

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

@@ -0,0 +1,19 @@

#include <iostream>

#include <span>

#include "grid.hpp"

int main(const int argc, const char* argv[])

{

const std::span args(argv, static_cast<size_t>(argc));

for (const auto& arg : args.subspan(1)) {

grid sudoku(arg);

sudoku.print();

std::cout << (sudoku.solve() ? "solved" : "unable to solve") << std::endl;

sudoku.print();

}

return 0;

}

diff --git a/source/ref.cpp b/source/ref.cpp

@@ -0,0 +1,182 @@

#include <cassert>

#include <stdexcept>

#include "ref.hpp"

void ref::clear(uint8_t field, uint8_t value)

{

m_value.at(field) &= static_cast<uint16_t>(~(1U << value));

m_ref.at(value) &= static_cast<uint16_t>(~(1U << field));

}

void ref::set(uint8_t field, uint8_t value)

{

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

m_ref.at(i) &= static_cast<uint16_t>(~(1U << field));

}

m_ref.at(value) = 0;

m_value.at(field) = 0;

m_res.at(field) = value + 1;

}

ref::changes_t ref::get_hidden_singles() const

{

changes_t res;

for (uint8_t candidate = 0; candidate < 9; candidate++) {

if (std::popcount(m_ref.at(candidate)) != 1) continue;

res.emplace_back(std::countr_zero(m_ref.at(candidate)), candidate);

}

return res;

}

ref::changes_t ref::get_naked_singles() const

{

changes_t res;

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

const auto values = get(i);

if (std::popcount(values) != 1) continue;

const auto value = static_cast<size_t>(std::countr_zero(values));

if (m_ref.at(value) == 0) continue;

res.emplace_back(i, value);

}

return res;

}

ref::changes_t ref::get_hidden(uint8_t number) const

{

assert(number > 1 && number <= 4);

changes_t res;

get_hidden(res, number, number, 0, 0, 0);

return res;

}

bool ref::get_hidden(changes_t& res,

uint8_t orig,

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(m_ref.at(i)) < 2) continue;

if ((m_seen_hidden.at(orig - 1) & (1UL << i)) != 0) continue;

const bool used = get_hidden(res,

orig,

number - 1,

i + 1,

val | m_ref.at(i),

mask | static_cast<uint16_t>(1U << i));

if (!used) continue;

m_seen_hidden.at(orig - 1) |= 1UL << i;

if (number != orig) return true;

}

return false;

}

if (std::popcount(val) != orig) return false;

static std::array<uint8_t, 9> fields;

uint8_t size = 0;

while (val != 0) {

const auto idx = static_cast<uint8_t>(std::countr_zero(val));

fields.at(size++) = idx;

val ^= 1ULL << idx;

}

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

const uint16_t change =

m_value.at(fields.at(i)) & ~(m_value.at(fields.at(i)) & mask);

if (change == 0) continue;

res.emplace_back(fields.at(i), change);

}

return true;

}

ref::changes_t ref::get_naked(uint8_t number) const

{

assert(number > 1 && number <= 4);

changes_t res;

get_naked(res, number, number, 0, 0);

return res;

}

bool ref::get_naked(changes_t& res,

uint8_t orig,

uint8_t number,

uint8_t first,

uint16_t val) const

{

static std::array<uint8_t, 4> seen = {0};

if (number != 0) {

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

if (m_res.at(i) != 0) continue;

if (number == orig && (m_seen_naked.at(orig - 1) & (1UL << i)) != 0)

continue;

seen.at(orig - number) = i;

const bool used =

get_naked(res, orig, number - 1, i + 1, val | m_value.at(i));

if (!used) continue;

if (number == orig) m_seen_naked.at(orig - 1) |= 1UL << i;

if (number != orig) return true;

}

return false;

}

if (std::popcount(val) != orig) return false;

while (val != 0) {

const auto idx = static_cast<uint8_t>(std::countr_zero(val));

for (uint8_t pos = 0, i = 0; pos < 9; pos++) {

if ((m_value.at(pos) & idx) == 0) continue;

for (i = 0; i < orig; i++) {

if (pos == seen.at(i)) break;

}

if (i == orig) res.emplace_back(pos, idx);

}

val ^= 1ULL << idx;

}

return true;

}

ref::changes_t ref::get_pointing(uint16_t mask, std::size_t seen) const

{

changes_t res;

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

const auto popcnt = std::popcount(m_ref.at(i));

if (popcnt < 2 || popcnt > 3) continue;

if ((m_seen_point.at(seen) & (1UL << i)) == 0) {

uint16_t cmask = mask;

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

const uint16_t lmask = cmask & m_ref.at(i);

const auto cpopcnt = std::popcount(lmask);

if (cpopcnt != popcnt) continue;

m_seen_point.at(seen) |= 1U << i;

res.emplace_back(k, i);

break;

}

return res;

}

diff --git a/source/ref.hpp b/source/ref.hpp

@@ -0,0 +1,84 @@

#ifndef DOASKU_REF_HPP

#define DOASKU_REF_HPP

#include <array>

#include <cstdint>

#include <utility>

#include <vector>

class ref

{

public:

using change_t = std::tuple<uint8_t, uint16_t>;

using changes_t = std::vector<change_t>;

uint16_t get(uint8_t field) const { return m_value.at(field); }

uint16_t get_ref(uint8_t value) const { return m_ref.at(value); }

uint16_t get_value(uint8_t field) const { return m_res.at(field); }

void clear(uint8_t field, uint8_t value);

void set(uint8_t field, uint8_t value);

changes_t get_hidden_singles() const;

changes_t get_naked_singles() const;

auto get_hidden_pairs() const { return get_hidden(2); }

auto get_hidden_triplets() const { return get_hidden(3); }

auto get_hidden_quads() const { return get_hidden(4); }

auto get_naked_pairs() const { return get_naked(2); }

auto get_naked_triplets() const { return get_naked(3); }

auto get_naked_quads() const { return get_naked(4); }

auto get_pointing_row() const { return get_pointing(0x7, 0); }

auto get_pointing_col() const { return get_pointing(0x49, 1); }

private:

changes_t get_naked(uint8_t number) const;

changes_t get_hidden(uint8_t number) const;

changes_t get_pointing(uint16_t mask, size_t seen) const;

bool get_hidden(changes_t& res,

uint8_t orig,

uint8_t number,

uint8_t first,

uint16_t val,

uint16_t mask) const;

bool get_naked(changes_t& res,

uint8_t orig,

uint8_t number,

uint8_t first,

uint16_t val) const;

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

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

std::array<uint16_t, 9> m_value = {mask_field,

mask_field,

mask_field};

std::array<uint16_t, 9> m_ref = {mask_field,

mask_field,

mask_field};

std::array<uint16_t, 9> m_res = {0};

mutable std::array<uint16_t, 4> m_seen_hidden = {0};

mutable std::array<uint16_t, 4> m_seen_naked = {0};

mutable std::array<uint16_t, 2> m_seen_point = {0};

};

#endif

diff --git a/src/CMakeLists.txt b/src/CMakeLists.txt

@@ -1,8 +0,0 @@

add_executable(doasku main.cpp ref.cpp grid.cpp)

target_include_directories(doasku PRIVATE ../include)

set_target_properties(doasku PROPERTIES

VERSION ${PROJECT_VERSION}

SOVERSION ${PROJECT_VERSION_MAJOR}

RUNTIME_OUTPUT_DIRECTORY "${CMAKE_BINARY_DIR}/bin"

)

diff --git a/src/grid.cpp b/src/grid.cpp

@@ -1,241 +0,0 @@

#include <algorithm>

#include <bitset>

#include <functional>

#include <iostream>

#include "grid.hpp"

template <class Input, class UnaryFunc>

UnaryFunc for_each(Input input, UnaryFunc f) {

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

}

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}};

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}};

return mapping[subgrid];

}

Grid::Grid(const std::string &s) {

int idx = 0;

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

for (uint8_t j = 0; j < 9; j++, idx++) {

if (s[idx] == '0') continue;

_set({i, j}, s[idx] - '1');

}

bool Grid::solve() {

// clang-format off

static const auto sub_op =

[this](auto op, const auto f) {

for(uint8_t subgrid = 0; subgrid < 9; subgrid++) {

for_each(std::invoke(f, subgrids[subgrid]), [&](auto& ch) {

std::invoke(op, this, operation_t({cord_t(subgrid), cord_t(std::get<0>(ch))}, std::get<1>(ch)));

});

}

return changed;

};

static const auto row_op =

[this](auto op, const auto f) {

for(uint8_t row = 0; row < 9; row++) {

for_each(std::invoke(f, rows[row]), [&](auto& ch) {

std::invoke(op, this, operation_t({row, std::get<0>(ch)}, std::get<1>(ch)));

});

}

return changed;

};

static const auto col_op =

[this](auto op, const auto f) {

for(uint8_t col = 0; col < 9; col++) {

for_each(std::invoke(f, cols[col]), [&](auto &ch) {

std::invoke(op, this, operation_t({std::get<0>(ch), col}, std::get<1>(ch)));

});

}

return changed;

};

static const auto all_op =

[this](auto op, const auto f) {

sub_op(op, f), row_op(op, f), col_op(op, f);

return changed;

};

// clang-format on

changed = true;

while (changed) {

changed = false;

if (sub_op(&Grid::op_set, &Ref::get_naked_singles)) continue;

if (all_op(&Grid::op_set, &Ref::get_hidden_singles)) continue;

if (sub_op(&Grid::op_clear_row, &Ref::get_pointing_row)) continue;

if (sub_op(&Grid::op_clear_col, &Ref::get_pointing_col)) continue;

if (all_op(&Grid::op_mask, &Ref::get_hidden_pairs)) continue;

if (all_op(&Grid::op_mask, &Ref::get_hidden_triplets)) continue;

if (all_op(&Grid::op_mask, &Ref::get_hidden_quads)) continue;

if (all_op(&Grid::op_clear, &Ref::get_naked_pairs)) continue;

if (all_op(&Grid::op_clear, &Ref::get_naked_triplets)) continue;

if (all_op(&Grid::op_clear, &Ref::get_naked_quads)) continue;

row_op(&Grid::op_clear_row_rel, &Ref::get_pointing_row);

col_op(&Grid::op_clear_col_rel, &Ref::get_pointing_row);

}

return _is_finished();

}

void Grid::print() const {

// clang-format off

static const auto print_i = [this](const Ref refs[9], uint16_t (Ref::*f)(uint8_t) const, bool bits) {

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

for (uint8_t j = 0; j < 9; j++) {

const cord_t subgrid = {uint8_t(i / 3), uint8_t(j / 3)};

const cord_t field = {uint8_t(i % 3), uint8_t(j % 3)};

uint16_t value = (refs[subgrid].*(f))((uint8_t)field);

if (bits) std::cout << std::bitset<9>(value) << " ";

else std::cout << value << " ";

if (j % 3 == 2) std::cout << " ";

}

std::cout << std::endl;

if (i % 3 == 2) std::cout << std::endl;

}

};

// clang-format on

std::cout << "Field: " << std::endl;

print_i(subgrids, &Ref::get, true);

std::cout << "Refs: " << std::endl;

print_i(subgrids, &Ref::get_ref, true);

std::cout << "Board: " << std::endl;

print_i(subgrids, &Ref::get_value, false);

}

void Grid::op_set(operation_t op) {

_set(std::get<0>(op), std::get<1>(op));

changed = true;

}

void Grid::op_mask(operation_t op) {

_mask(std::get<0>(op), std::get<1>(op));

changed = true;

}

void Grid::op_clear(operation_t op) {

_clear(std::get<0>(op), std::get<1>(op));

changed = true;

}

void Grid::op_clear_row(operation_t op) {

const auto [ab, val] = op;

const auto [r1, r2] = other_subgrid_row(ab.subgrid());

_clear_row(r1, ab.field(), val);

_clear_row(r2, ab.field(), val);

changed = true;

}

void Grid::op_clear_col(operation_t op) {

const auto [ab, val] = op;

const auto [c1, c2] = other_subgrid_col(ab.subgrid());

_clear_col(c1, ab.field(), val);

_clear_col(c2, ab.field(), val);

changed = true;

}

void Grid::op_clear_row_rel(operation_t op) {

const auto [ab, val] = op;

const auto [r1, r2] = other_subgrid_row(ab.row());

_clear_row((r1 / 3) * 3 + ab.col(), r1 % 3, val);

_clear_row((r2 / 3) * 3 + ab.col(), r2 % 3, val);

changed = true;

}

void Grid::op_clear_col_rel(operation_t op) {

const auto [ab, val] = op;

const auto [c1, c2] = other_subgrid_row(ab.col());

_clear_col(ab.row() * 3 + c1 / 3, c1 % 3, val);

_clear_col(ab.row() * 3 + c2 / 3, c2 % 3, val);

changed = true;

}

void Grid::_set(acord_t ab, uint8_t value) {

rows[ab.row()].set(ab.col(), value);

cols[ab.col()].set(ab.row(), value);

subgrids[ab.subgrid()].set(ab.field(), value);

_clear_row(ab.subgrid(), 0, value);

_clear_row(ab.subgrid(), 1, value);

_clear_row(ab.subgrid(), 2, value);

const auto [r1, r2] = other_subgrid_row(ab.subgrid());

_clear_row(r1, ab.field().row(), value);

_clear_row(r2, ab.field().row(), value);

const auto [c1, c2] = other_subgrid_col(ab.subgrid());

_clear_col(c1, ab.field().col(), value);

_clear_col(c2, ab.field().col(), value);

}

void Grid::_mask(acord_t ab, uint16_t mask) {

while (mask) {

const uint8_t idx = std::countr_zero(mask);

_clear(ab, idx);

mask ^= 1ull << idx;

}

void Grid::_clear(acord_t ab, uint8_t value) {

subgrids[ab.subgrid()].clear(ab.field(), value);

rows[ab.row()].clear(ab.col(), value);

cols[ab.col()].clear(ab.row(), value);

}

void Grid::_clear_row(cord_t sg, uint8_t row, uint8_t value) {

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

_clear({sg, {row, i}}, value);

}

void Grid::_clear_col(cord_t sg, uint8_t col, uint8_t value) {

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

_clear({sg, {i, col}}, value);

}

bool Grid::_is_finished(uint8_t subgrid) {

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

if (!subgrids[subgrid].get_value(i)) return false;

}

return true;

}

bool Grid::_is_finished() {

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

if (!_is_finished(i)) return false;

}

return true;

}

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

@@ -1,15 +0,0 @@

#include <iostream>

#include "grid.hpp"

int main(const int argc, const char *argv[]) {

for (int i = 1; i < argc; i++) {

Grid g(argv[i]);

g.print();

std::cout << (g.solve() ? "solved" : "unable to solve") << std::endl;

g.print();

}

return 0;

}

diff --git a/src/ref.cpp b/src/ref.cpp

@@ -1,156 +0,0 @@

#include <cassert>

#include "ref.hpp"

void Ref::clear(uint8_t field, uint8_t value) {

this->value[field] &= ~(1 << value);

ref[value] &= ~(1 << field);

}

void Ref::set(uint8_t field, uint8_t value) {

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

ref[i] &= ~(1 << field);

}

this->value[field] = ref[value] = 0;

res[field] = value + 1;

}

Ref::changes_t Ref::get_hidden_singles() const {

changes_t res;

for (uint8_t candidate = 0; candidate < 9; candidate++) {

if (std::popcount(ref[candidate]) != 1) continue;

res.emplace_back(std::countr_zero(ref[candidate]), candidate);

}

return res;

}

Ref::changes_t Ref::get_naked_singles() const {

changes_t res;

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

const auto values = get(i);

if (std::popcount(values) != 1) continue;

const auto value = std::countr_zero(values);

if (!ref[value]) continue;

res.emplace_back(i, value);

}

return res;

}

Ref::changes_t Ref::get_hidden(int number) const {

assert(number > 1 && number <= 4);

changes_t res;

get_hidden(res, number, number, 0, 0, 0);

return res;

}

bool Ref::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));

if (!used) continue;

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

if (number != og) return true;

}

return false;

}

if (std::popcount(val) != og) return false;

static uint8_t fields[9];

uint8_t size = 0;

while (val) {

const uint8_t idx = std::countr_zero(val);

fields[size++] = idx;

val ^= 1ull << idx;

}

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

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

if (!change) continue;

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

}

return true;

}

Ref::changes_t Ref::get_naked(int number) const {

assert(number > 1 && number <= 4);

changes_t res;

get_naked(res, number, number, 0, 0);

return res;

}

bool Ref::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) {

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

if (this->res[i]) continue;

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]);

if (!used) continue;

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

if (number != og) return true;

}

return false;

}

if (std::popcount(val) != og) return false;

while (val) {

const uint8_t idx = std::countr_zero(val);

for (uint8_t pos = 0, i; pos < 9; pos++) {

if ((value[pos] & idx) == 0) continue;

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

if (pos == seen[i]) break;

}

if (i == og) res.emplace_back(pos, idx);

}

val ^= 1ull << idx;

}

return true;

}

Ref::changes_t Ref::get_pointing(uint16_t mask, bool seen) const {

changes_t res;

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

const uint8_t popcnt = std::popcount(ref[i]);

if (popcnt < 2 || popcnt > 3) continue;

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;

seen_point[seen] |= 1 << i;

res.emplace_back(k, i);

break;

}

return res;

}