Skip to content

Instantly share code, notes, and snippets.

@teju85
Created August 23, 2019 16:28
Show Gist options
  • Save teju85/2cfc3934f3697aaff324b77e693010a0 to your computer and use it in GitHub Desktop.
Save teju85/2cfc3934f3697aaff324b77e693010a0 to your computer and use it in GitHub Desktop.
Solve sudoku 3x3 boards using only elimination techniques
//
// Compilation: g++ -std=c++11 -o a.exe sudoku-3x3.cpp
// Run: ./a.exe "7 1 8 19 5 812 5 372 7 4 652 3 938 5 14 2 5 7"
// In order to solve the following board:
//
// 7 0 1 0 0 0 0 0 8
// 0 0 0 1 9 0 0 0 5
// 0 0 0 0 0 8 1 2 0
//
// 0 0 0 0 5 0 3 7 2
// 0 0 7 0 0 0 4 0 0
// 6 5 2 0 3 0 0 0 0
//
// 0 9 3 8 0 0 0 0 0
// 5 0 0 0 1 4 0 0 0
// 0 2 0 0 0 0 5 0 7
//
#include <stdio.h>
#include <string.h>
#include <vector>
#define USH unsigned short
static unsigned char BitsSet[256];
void initBitsSet() {
BitsSet[0] = 0;
for (int i = 1; i < 256; ++i) {
BitsSet[i] = (i & 1) + BitsSet[i >> 1];
}
}
struct Mask {
Mask() : val(0) {}
Mask(const Mask& other) : val(other.val) {}
Mask& operator+=(int pos) {
if (pos > 0) val |= (USH)(1 << pos);
return *this;
}
Mask& operator-=(int pos) {
if (pos > 0) val &= ~(USH)(1 << pos);
return *this;
}
void reset() { val = 0; }
void setAll() { val = 0x3fe; }
std::vector<USH> options() const {
std::vector<USH> ret;
for (int i = 1; i <= 9; ++i) {
if ((1 << i) & val) ret.push_back(i);
}
return ret;
}
int count() const { return (int)countBitsSet(val); }
USH numAt() const {
if(val <= 0 || !isPo2()) return 0;
for (int i = 1; i <= 9; ++i) {
if ((1 << i) & val) return i;
}
return 0;
}
USH raw() const { return val; }
private:
USH val;
USH countBitsSet(USH v) const {
auto* ptr = (unsigned char*)&v;
return BitsSet[ptr[0]] + BitsSet[ptr[1]];
}
bool isPo2() const { return !(val & (val - 1)); }
}; // end struct Mask
struct Board {
Mask b[9][9];
void read(const char* str) {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
USH v = str[i*9+j] == ' ' ? 0 : str[i*9+j] - '0';
b[i][j] += v;
}
}
initializeChoices();
pruneChoices();
}
void solve() {
while(findUniques()) {
pruneChoices();
}
}
void print(const char* msg, const char* indent=" ") const {
done() ? printBoard(msg, indent) : printWithChoices(msg, indent);
}
bool done() const {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) if (b[i][j].count() != 1) return false;
}
return true;
}
private:
bool findUniques() {
Mask hist[10];
// rows
for (int i = 0; i < 9; ++i) {
for (int k = 0; k < 10; ++k) hist[k].reset();
for (int j = 0; j < 9; ++j) {
if (b[i][j].count() <= 1) continue;
auto opts = b[i][j].options();
for (const auto& o : opts) hist[o] += j + 1;
}
for (int k = 1; k <= 9; ++k) {
if (hist[k].count() == 1) {
auto col = hist[k].numAt() - 1;
b[i][col].reset();
b[i][col] += k;
return true;
}
}
}
// cols
for (int i = 0; i < 9; ++i) {
for (int k = 0; k < 10; ++k) hist[k].reset();
for (int j = 0; j < 9; ++j) {
if (b[j][i].count() <= 1) continue;
auto opts = b[j][i].options();
for (const auto& o : opts) hist[o] += j + 1;
}
for (int k = 1; k <= 9; ++k) {
if (hist[k].count() == 1) {
auto row = hist[k].numAt() - 1;
b[row][i].reset();
b[row][i] += k;
return true;
}
}
}
// blocks
for (int i = 0; i < 9; i += 3) {
for (int j = 0; j < 9; j += 3) {
for (int k = 0; k < 10; ++k) hist[k].reset();
for (int bi = 0; bi < 3; ++bi) {
for (int bj = 0; bj < 3; ++bj) {
int posi = i + bi, posj = j + bj;
if (b[posi][posj].count() <= 1) continue;
auto opts = b[posi][posj].options();
int pos = bi * 3 + bj;
for (const auto& o : opts) hist[o] += pos + 1;
}
}
for (int k = 1; k <= 9; ++k) {
if (hist[k].count() == 1) {
auto pos = hist[k].numAt() - 1;
int bi = pos / 3, bj = pos % 3;
b[i + bi][j + bj].reset();
b[i + bi][j + bj] += k;
return true;
}
}
}
}
return false;
}
void initializeChoices() {
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (b[i][j].count() == 0) b[i][j].setAll();
}
}
}
void pruneChoices() {
bool changed = true;
while(changed) {
changed = false;
for (int i = 0; i < 9; ++i) {
for (int j = 0; j < 9; ++j) {
if (b[i][j].count() != 1) continue;
int bi = (i / 3) * 3, bj = (j / 3) * 3;
auto num = b[i][j].numAt();
for (int k = 0; k < 9; ++k) {
// row prune
if (k != i) changed = changed || pruneAt(k, j, num);
// col prune
if (k != j) changed = changed || pruneAt(i, k, num);
// blk prune
int ki = bi + k / 3;
int kj = bj + k % 3;
if (ki != i && kj != j) changed = changed || pruneAt(ki, kj, num);
}
}
}
}
}
bool pruneAt(int i, int j, USH num) {
auto prev = b[i][j].raw();
b[i][j] -= num;
return prev != b[i][j].raw();
}
void printBoard(const char* msg, const char* indent=" ") const {
printf("%s", msg);
for (int i = 0; i < 9; ++i) {
printf("%s", indent);
for (int j = 0; j < 9; ++j) {
printf("%u ", b[i][j].numAt());
if ((j + 1) % 3 == 0) printf(" ");
}
printf("\n");
if ((i + 1) % 3 == 0 && i < 8) printf("\n");
}
}
void printWithChoices(const char* msg, const char* indent=" ") const {
printf("%s", msg);
for (int i = 0; i < 9; ++i) {
printf("%s", indent);
for (int j = 0; j < 9; ++j) {
std::vector<USH> opts = b[i][j].options();
for (const auto& o : opts) printf("%u", o);
int nBits = 9 - b[i][j].count();
for (int k = 0; k < nBits; ++k) printf(" ");
printf(" ");
if ((j + 1) % 3 == 0) printf(" ");
}
printf("\n");
if ((i + 1) % 3 == 0 && i < 8) printf("\n");
}
}
};
void solveBoard(const char* str) {
Board input;
printf("Reading input matrix...\n");
printf("Input = '%s'\n", str);
input.read(str);
input.solve();
input.print("Final board:\n");
}
int main(int argc, char** argv) {
initBitsSet();
solveBoard(argv[1]);
return 0;
}
@teju85
Copy link
Author

teju85 commented Aug 23, 2019

A simple shell script to download sudoku boards from websudoku and solve them.

#!/bin/bash
level=${1:-2}
id=${2:-150395377}
url="https://show.websudoku.com/?level=${level}&set_id=${id}"
file=puzzle_${level}_${id}.html
src=sudoku-3x3.cpp
echo "Fetching the solver source..."
if [ ! -e "$src" ]; then
    wget "https://gist.githubusercontent.com/teju85/2cfc3934f3697aaff324b77e693010a0/raw/c984e85bae8810fdcef62489e49d5cb08b05561d/sudoku-3x3.cpp"
fi
echo "URL: $url"
if [ ! -e "$file" ]; then
    echo "Downloading puzzle..."
    wget -q "$url" -O "$file"
else
    echo "Puzzle already found"
fi
echo "Solving the board..."
g++ -std=c++11 -o sudoku_solver "$src"
time ./sudoku_solver "`grep _grid "$file" | tr '>' '\n' | grep INPUT | sed -e 's/.*READONLY VALUE="//' -e 's/" ID=.*//' -e 's/<INPUT .*/ /' | tr -d '\n'`"
echo "Cleaning up..."
rm -f "$file" sudoku_solver

@teju85
Copy link
Author

teju85 commented Aug 23, 2019

This appears to solve even the hard problems from websudoku.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment