Giter VIP home page Giter VIP logo

sudoku-solver's Introduction

Sudoku Solver

This Sudoku solver reads values in from CSV or TXT files that have been formatted as a 3x3 grid, and proceeds to evaluate it as a complete Sudoku.

Algorithm Design

The algorithm relies on the fairly straightforward approach of representing a matrix as a tensor of varying lengths in the 3rd dimension, representing and narrowing down all potential values until it can be reduced to 3x3x1, or this is proven impossible.

We argue for termination in one of two cases โ€“ either a discovery that the Sudoku is unsolvable, or in a perfectly solved Sudoku.

Termination

Termination occurs in one of two scenarios:

  1. A simple linear scan through the matrix reveals that all possible value tensors are reduced to exactly one layer.
  2. A comparison between the two most recently updated matrices reveals no change, showing a cessation in updates.

Case 1

This termination clause exists as per the defintion of a completed Sudoku. We can effectively flatten our tensor to a simple 3x3 matrix once the specified conditions have been met, and the algorithm terminates as per its own definiton.

Case 2

We argue for termination in failure the following way: Assume that our algorithm is injective, meaning M1 = M2 -> eval(M1) = eval(M2). Let our previous matrix be M1 and our current matrix be M2. eval(M1) = M2 โˆง M1 = M2

Proof Of Completion

sudoku-solver's People

Contributors

kabirsamsi avatar

Watchers

James Cloos avatar  avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.