Jump to content
RTFC

A BitMask-based Sudoku Solver

Recommended Posts

Posted (edited)

The Short Version:

This set of well-annotated example scripts solves sudoku puzzles with simple, powerful bitmask functions applied on a massive scale, demonstrating both common solving techniques and highly-optimised brute-force.

All you need is:

XfilterSmall.png.dfa58473b5f768c223bc4ed230754759.png

Edited by RTFC

Share this post


Link to post
Share on other sites
Posted (edited)

The Longer Version:

Cells, Interlinked.

At the most basic level, all binary digital computing reduces to logical operations on individual bits, that is, the switches in circuitry that can be either 1 or 0 ("on" or "off", "True" or "False"). A grouped set of multiple on/off states can be called a bitmask (or "bit vector"), and when we apply logic to change the state of one bitmask by one or more other bitmasks, we can evaluate, in a single function call, as many bit-states as the targeted bitmask contains (in this case: over 362 thousand, see below). Moreover, multiple same-sized bitmasks can be aligned in a rectangular grid, allowing matrix functions to manipulate all bitmasks simultaneously in a single call. A powerful set of simple tools for this purpose is provided by Eigen4AutoIt (or E4A for short).

To demonstrate the bitmask prowess of E4A, this example script shows two independent approaches to solving sudoku puzzles. Sudoku's are mathematically simple problems, yet their solution can be computationally hard. Given ten example puzzles (external .sdk files can also be imported, see the Remarks section in the script), the Solver approach implements a number of well-documented sudoku-solving techniques, with which to reduce the number of candidate values per cell. These work well for easy sudoku's, but get stuck (example sudoku #6), or fail completely in harder cases (examples #9 and #10).

By contrast, Brute-Force consists of six nested loops (Why six? See below!), and will identify either the first, or all valid solutions (depending on whether "early-out upon first hit" is enabled). It will never fail (fingers crossed! o:)), but may take a long time for the hardest problems. For example, the (in)famous "Easter Monster" sudoku (example #9) takes this script over twenty minutes to solve, at least on my decrepit old laptop.:( But the main aim in writing it was clarity and legibility, not speed. Furthermore, the Brute-Force method contains some interesting and unusual features that I have not encountered in other such software, notably:

  • The chosen unit of permutation is the 3x3 sudoku block. One could alternatively have selected the 1x9 row, or the 9x1 column as foundation, and one possible extension of the method would be to consider all three units in parallel, and select the most effective type of unit for each problem separately. But here we consider only blocks; we do not care a rat's behind about the content of individual cells. Cells suck.

 

  • Each sudoku consists of 9 blocks (from TL to BR, see left panel in diagram 1 on the download page), and each block has 9 factorial ("9!") permutations, meaning the 9 unique digits 1-9 can be arranged within a block in exactly 362,880 unique configurations (see diagram 1, right panel). In other words, in the first-selected empty cell, all 9 digits are possible to place, followed by 8 remaining in the next (as one digit is used up in the first cell), then 7 choices are left, then 6, 5, 4, 3, 2, and the final cell is predetermined. We store these on file in a 9 x 362,880 matrix table called "blockpermuts.mat" (provided). The algorithm to generate it is included in the script.

 

  • A valid sudoku solution contains 9 of these 3x3 blocks, in a 3x3 grid that additionally satisfies the constraints of having 9 unique digits (1-9) in each row and in each column. Note that the same 9 blocks can be re-arranged in 3! x 3! = 6 x 6 = 36 different ways, by swapping block rows and/or block columns. So the same solution in terms of the 9 block permutation IDs (which is what we're after) can give rise to 36 different-looking sudoku's (we ignore rotations and mirroring here, because those operations would change the block IDs). This means we can ourselves swap block rows and cols of the presented puzzle as we see fit, without affecting the solution in terms of block IDs. Why is this important?

 

  • Any specific block imposes strong constraints on the validity of both neighbouring blocks in the same block row (horizontally in either direction), and in the same block column (vertically in either direction). For example, the left panel of diagram 2 shows the TL (top-left) block as unconstrained (362,880 permutations), but as soon as we choose any single one of these, the valid permutations of its immediate row neighbour (TC, see diagram 1) are reduced to 12,096, and likewise for its immediate col neighbour (CL). Even better, given chosen blocks for TC and CL as well, their respective next neighbours in the same block row (TR) and col (BL) have their valid permutations reduced (from over 362K) to a mere 216 each, because TL imposes additional constraints on them. The central block (CC) is more complicated, ranging from 384 to 448 valid permutations (depending on which TC and CL blocks are chosen), but the joint possibilities always yield a mean of 404. Best of all, given ANY six known blocks, the remaining three have their options reduced to either 0 (invalid configuration) or 1 (= sudoku solved).

 

  • Combining the previous two insights, we can optimise the blocks arrangement by swapping block rows and block cols, so that the two blocks with the highest number of remaining valid permutations (after processing the clues) end up on the block diagonal (here we use TL and BR, see diagram 2, right panel). Brute-Force then cycles through the (smaller-sized) valid permutations in the off-diagonal blocks at top-right (TC, TR, and CR) and at bottom-left (CL, BL, and BC). Inside the innermost loop, 6 out of 9 blocks are known, automatically defining the three diagonal blocks TL, CC, and BR without any further cycling or evaluation. We only need to check if the full solution is found. That is, we can completely ignore the two hardest blocks, of which we know least (plus a third on the diagonal that is selected automatically when we swap the second block to BR).

 

  • Brute-Force would still take a long time, if it wasn't for the properties of (in)valid block neighbours. Therefore, two provided digit tables ("digitInRows.mat" and "digitInCols.mat", see diagram 3) record as bitmasks the row c.q. col position inside a block of each digit (3 options x 9 digits = 27 rows), for all block permutations (362,880 cols). This is where the power of matrix operations really shines, because in two simple E4A function calls we can eliminate ALL invalid row/col neighbours of a block (see  diagram 4). Moreover, the resulting bitmasks can be stacked as multiple exclusion filters to further reduce the number of cycles in the nested loops (see diagram 4). So given a choice of TC, TR's options are reduced; given TR and CL, CR's options are reduced; and once BL is also selected, it constrains BC in tandem with TC. Most importantly, whenever any bitmask becomes zero for all bits (easily tested with E4A's _Eigen_IsZero function), we can exit the current nesting level prematurely and move on.


The final result is a succinct, highly-optimised algorithm that is (hopefully) easy to understand. It illustrates that you don't need a maths degree to get lots of mileage out of the E4A environment. It may not be the fastest sudoku solver out there (that probably wouldn't be written in AutoIt to begin with), but it shows how bitmasks can be gainfully employed to tackle a variety of programming challenges. For some other applications, you can study (and maybe improve or extend) the various solver methods, which all apply bitmask logic as well. Have Fun!

And remember, kids: Cells Suck, but Blocks Rock!

Edited by RTFC

Share this post


Link to post
Share on other sites

This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites
Posted (edited)

@jchd: Blast from the past, thanks for that! Haven't looked at APL since my student days at uni. Still remember being impressed it could squeeze a complete least-squares solver into a single line of code. Borderline illegible though, especially after a few months break. ("Who wrote that crap? Oh wait, that would be me.") I can see why it never appealed to the masses, it's like RegExp on steroids.;)

Yes, I can see the similarity with bitmasks. But I think it's actually closer in functionality to Knuth's Algorithm X approach of the exact cover problem, which is of course unbeatable for speed (mere ms), but which would fail on any and all underdetermined sudokus, whereas brute-force would happily barrel through (and collect) all possible solutions. Still, kind of humbling to see APL squeeze a solution into fewer than 10 lines of code, when mine needs over a thousand. But I'd argue that my code is a bit easier on the eyes...

Edited by RTFC
clarification

Share this post


Link to post
Share on other sites

I confess not having heavily used APL since the IBM 5100 (geez, almost 40 years ago!) mostly because it's an unreadable list of bizare symbols just few weeks after you wrote it.

If you like both easy to use, super-fast and completely cryptic code for solving sudoku, then you'll love the SQL version!

The SQL setup is complicated, mostly because we have no way to declare variables, arrays and such in pure SQL, but as always it boils down to requesting what the conforming result(s) should satisfy without explicitely specifying how to achieve that goal.


This wonderful site allows debugging and testing regular expressions (many flavors available). An absolute must have in your bookmarks.
Another excellent RegExp tutorial. Don't forget downloading your copy of up-to-date pcretest.exe and pcregrep.exe here
RegExp tutorial: enough to get started
PCRE v8.33 regexp documentation latest available release and currently implemented in AutoIt beta.

SQLitespeed is another feature-rich premier SQLite manager (includes import/export). Well worth a try.
SQLite Expert (freeware Personal Edition or payware Pro version) is a very useful SQLite database manager.
An excellent eBook covering almost every aspect of SQLite3: a must-read for anyone doing serious work.
SQL tutorial (covers "generic" SQL, but most of it applies to SQLite as well)
A work-in-progress SQLite3 tutorial. Don't miss other LxyzTHW pages!
SQLite official website with full documentation (may be newer than the SQLite library that comes standard with AutoIt)

Share this post


Link to post
Share on other sites
Posted (edited)

Yeah, I saw that when I did a brief survey what other AutoIt-based sudoku solvers were already out there. I like "easy, to use," love "super-fast", but am not too keen on "completely cryptic code" (except in a CodeCrypter context of course:D). And I lost my virginity to an IBM 370 mainframe (she was cold and not very tender). I remember those days well; the world was still a lush paradise, golden sunsets, warm breezes, and then that damned asteroid hit and wiped most of us out, and now those pesky mammals rule the roost (those bipeds are the worst!).

Edited by RTFC

Share this post


Link to post
Share on other sites

Version 1.1 is released, containing an additional stand-alone Brute-Force (BF) solver with an optimised algorithm and optional GUI.

Just couldn't shake a niggling suspicion:think: that the BF approach was still suboptimal, so I threw some heavier maths and stats at the problem, grinding through a sample of about a hundred sudoku's of varying complexity. Some interesting new features came to light, some of which have been incorporated into the new BF script; the BF approach in the original script remains untouched.

Share this post


Link to post
Share on other sites

Version 1.2 is released, with a new CrossFilter-based script (note: requires E4A v5.1) that drives a more colourful, mesmerising GUI (if you're very easily mesmerised, that is). That solver also contains an internal library of well over a hundred sudokus, from easy to extreme. Watching this is almost as soothing as staring at an aquarium, and at a fraction of the cost.

Share this post


Link to post
Share on other sites

Create an account or sign in to comment

You need to be a member in order to leave a comment

Create an account

Sign up for a new account in our community. It's easy!

Register a new account

Sign in

Already have an account? Sign in here.

Sign In Now

  • Recently Browsing   0 members

    No registered users viewing this page.

  • Similar Content

    • By RTFC
      The Eigen C++ template library is a great environment for matrix computing; it is fast, reliable, extensive, and well-documented. It is also completely free, and does not rely on any external dependencies. Unfortunately for AutoIt users, the term “template library” implies that any functions you call are only instantiated upon compilation (in C++). That means there's nothing to hook into.
      To make Eigen ’s most important functionality directly accessible from within AutoIt scripts (version 3.3.12+, download it here), I developed the Eigen4AutoIt environment. It runs on Windows and under Wine also on Linux and Mac (Ubuntu, Debian, Fedora, and MacOS supported by WineHQ), and SUSE, Slackware, and FreeBSD supported by the distros).
      >Download the latest version

      It consists of:
      1) Eigen4AutoIt.au3
      an AutoIt library of wrapper functions that contain extensive bounds checks, matrix management, file I/O, type conversion, and precision control, and two-way data exchange with files and native AutoIt arrays;
      2) Eigen-wrapper dlls (EigenDense.dll, EigenDense_x64.dll)
      re-maps matrices created in AutoIt as Eigen Matrix objects, then calls Eigen’s powerful core functions; in the spirit of open-source, the full C++ source code I wrote is included in the bundle (see subdirectory "source"). The basic functions consist of a single Eigen call; decompositions and statistics are more involved. 3) Additional materials:
      the user-interactive, animated Function Selector and MatrixViewer tools the MatrixFileConverter to read/write E4A matrices from/to .csv ASCII, Excel, and Xbase files. three libraries of scientific and mathematical constants online Help, with example code for every function Large (.chm) Help file (for offline access) Quickstart Manual (11-page pdf, updated) Test suite Tutorials from Basics to Advanced Please note:
      none of this is part of Eigen's own distribution you only need this bundle; you do not need to install Eigen. How it works:
      No matrix content is ever transferred, only memory pointers, meaning computations in AutoIt are virtually as fast as in Eigen’s native environment, with the added advantage of not having to be compiled first. The drawback is that Eigen's native ad-hoc expression templates (and their internal optimisations) cannot be exploited here; you have to construct your operations with the basic building blocks. These provide matrix creation, I/O, cellwise operations, reduction, multiplication, transformation, decomposition (LU, Householder, Choleski, and Jacobi SVD; these include general linear solvers) and a small statistics module by yours truly.

      IMPORTANT: Posting Rules for this thread:
       
      1) Do not post or PM me any matrix-, maths-, or Eigen-related questions. Eigen has its own User Forum for that (or try math.stackExchange.com). I am not your maths guru! If you post such questions, I will either ignore your post or remind you of this rule.

      2) Do not post or PM me your data sets and/or non-working Eigen4AutoIt scripts; I will not analyse your data or fix your scripts for you! There are many reasons why a linear algebra procedure might fail to produce the answer you expect. You are wielding great mathematical power here, so exploit the fantastic internet resources at your fingertips and learn how to use it. To get you started, I've listed a few video tutorials and other helpful materials in the header remarks of Eigen4AutoIt.au3. Also check out the test scripts, the Tutorials, and the Help file.

      3) I do warmly welcome all of the following:
      remarks, advice, suggestions for improvements, encouragement, cash; bug reports re. the Eigen4AutoIt interface (individual functions that don't work the way they should) and/or the associated dll code (ditto); your own working Eigen4AutoIt templates of general use that you'd like to see implemented in a future release. Regarding that last item, have a look at my PCA tutorial. After the step-by-step stage, I summarise the entire procedure in a "mini script" of Eigen4AutoIt calls. Then I introduce the two internal PCA functions I developed, which replace that script with two simple calls. You can do the same thing, and submit your own functional Eigen4AutoIt script in this thread. If I consider it of general use and can implement it, it may become a new Eigen4AutoIt function in the next release (with source acknowledgement, of course). This means that you'd get a precompiled dll version of your script that will likely run faster and be simpler to call. Thereby this thread would become an Eigen4AutoIt Example Scripts mini forum. It's just a thought.
       
      >Download the latest version (uncompressed size: 37.1 MB)
       
      How to Install
      You need AutoIt version 3.3.12 or later. Extraction (with 7-zip) creates subdirectory Eigen4AutoIt, where you'll find Eigen4AutoIt.ini. Open it in a text editor, find global variable $EIGEN_DLLPATH, and copy/paste the full absolute path (without trailing backslash) where the Eigen4AutoIt dlls are located on your machine (that is, wherever you extracted the files). Save the ini file, open the first tutorial ("intro") in Scite, and start it. This shows basic matrix I/O and mode switching (single versus double precision). If that runs, you're in business.
      NB to leverage the full power of x64 features, you'll also need to have the full Scite4AutoIt3 package installed. For more info, see sections "Bitness" and "Shared Memory" in the Help, main topic: "Work Environment" page.
    • By RTFC
      Eigen4AutoIt Features:
      free, fast matrix computing environment for Windows (runs under Wine on Linux and Mac) built upon the robust Eigen code base (open-source), with many enhancements simple, intuitive functions, with extensive online documentation supports integer, single, and double precision, in real and complex matrices Tutorials with scripts, plus Test scripts for each function section easily exchange data between native binary files (.mat) and ASCII, Excel, and Xbase files, or AutoIt arrays 32-bit (x86-mode) and 64-bit (x64-mode) support in x64-mode, matrices can be any size that fits into available virtual memory (>4GB), and can be shared between processes over one thousand alias wrappers for flexibility and ease-of-use  
      The Eigen4AutoIt thread is here:
      This computing environment allows you to do matrix I/O (memory & files), matrix arithmetic, transformation, reduction, and decomposition, solve systems of linear equations, and perform statistics. Most functions can act on integer, real, or complex matrices (or the latter's real/imaginary parts separately). Much of the actual complexity of using Eigen in its native C++ environment has been hidden for AutoIt users, through extensive bounds and error checks, an intuitive function-naming convention, a large help file, and detailed tutorials and test examples.
    • By AlecSadler
      Hello friends! I have been working on an encryption algorithm in autoit as a proof of concept for some time now. Basically the algorithm uses a progressive recursion to encode data inside a matrix using a key that changes according to the date-time of the system, which is extracted from a larger key array. Recently after a drive failure, I lost the source and had to start from scratch, now I can't quite get it working the way it was before, and I can't see what I'm doing wrong, if anyone who understands matrix math or encryption could help I would much appreciate it. The problem is that the values returned by the decryption (extraction) process are way too big.
       
      I have figured out the solution to my problem, it was a typo, please disregard this thread.
      I will post my project into example scripts when it's ready.
       
       
       
    • By Edano
      i searched the forum, but didn't find anything.
      has anyone an idea or ever done it with autoit ? simple image transforming, like sharpness, brightness, blurring etc. ?
      maybe, does gdiplus.dll feature that ?
      here is a tutorial on how to do it the hard (mathematical) way. http://lodev.org/cgtutor/filtering.html before i try that, i wanted to know if there is already an existing project or an idea or anyone has experiences.
      thx
    • By logmein
      Hi there!

      I have been learning linear algebra in my university for months. The subject was rather hard, I did't understand it much so I sent a email to my teacher to ask him. But I realized that typing a matrix by text was extremely hard. I don't want to make a LaTex function, save to a file, attach it to the mail, bla bla bla!!! It's complicated! So I spent 2 hours yesterday to make this tool. Just type the number of lines and columns and matrix values, it will generate a quite nice matrix in ASCII characters
      Enjoy!
      Notes: It will rearrage your numbers to straight columns.
      1x1 will cause error.


      ConsoleWrite (@CRLF & '------------------------------------MATRIX TEST-----------------------------------------' &@CRLF) Dim $c = 6;column Dim $l = 4;line Dim $n = '1,6,2,4,b,a,7,6,6,0,44,4,6,3,6,2,6,8,9,6,6,1,2,logmein' $split = StringSplit ($n,',') If $c * $l <> $split[0] Then ConsoleWrite ('! Matrix values number do not match the columns and lines !' & @CRLF) Exit EndIf Dim $char[$l][$c], $len[$l][$c], $maxlen[$c][3] For $i = 0 To $l-1 For $u = 0 To $c -1 $v = $i*($c) + $u +1 $char[$i][$u] = $split[$v] $len[$i][$u] = StringLen ($split[$v]) If $len[$i][$u] > $maxlen[$u][0] Then $maxlen[$u][0] = $len[$i][$u] $maxlen[$u][1] = $i $maxlen[$u][2] = $u EndIf Next Next Local $finallen For $u = 0 To $c - 1 $finallen += $maxlen[$u][0] Next ConsoleWrite (' _' & _Repeat(' ',$finallen + $c) & '_' & @CRLF) For $i = 0 To $l-1;write lines For $u = 0 To $c-1;write columns $v = $i*($c) + $u +1 $char[$i][$u] = $split[$v] Switch $u Case 0; the first column If StringLen ($char[$i][$u])<$maxlen[$u][0] Then ConsoleWrite ('| ' & $char[$i][$u] & _Repeat(' ', $maxlen[$u][0]-StringLen ($char[$i][$u])+1)) Else ConsoleWrite ('| ' & $char[$i][$u] & ' ') EndIf Case 1 To $c-2 ;middle columns If $i > 0 Then If StringLen ($char[$i][$u]) < $maxlen[$u][0] Then ConsoleWrite ($char[$i][$u] & _Repeat(' ', $maxlen[$u][0]-StringLen ($char[$i][$u])+1)) Else ConsoleWrite ($char[$i][$u] & ' ' ) EndIf Else If StringLen ($char[$i][$u]) < $maxlen[$u][0] Then ConsoleWrite ($char[$i][$u] & _Repeat(' ', $maxlen[$u][0]-StringLen ($char[$i][$u])+1)) Else ConsoleWrite ($char[$i][$u] & ' ' ) EndIf EndIf Case Else ; the last column If StringLen ($char[$i][$u])<$maxlen[$u][0] Then ConsoleWrite ($char[$i][$u] & _Repeat(' ', $maxlen[$u][0]-StringLen ($char[$i][$u])+1) & ' |' & @CRLF) Else ConsoleWrite ($char[$i][$u] & ' |' & @CRLF) EndIf EndSwitch Next Next ConsoleWrite ('|_' & _Repeat(' ',$finallen + $c ) & '_|' & @CRLF) Func _Repeat($chars, $times);repeat a character in a specified time Local $rChar For $a = 1 To $times $rChar &= $chars Next Return $rChar EndFunc ;==>_Repeat
×
×
  • Create New...