Solve sudoku 3x3 boards using only elimination techniques

sudoku-3x3.cpp

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

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

This appears to solve even the hard problems from websudoku.