Aggregated APDU List

python/pyscard EMV tool pack
@ https://github.com/davidbarkhuizen/py_emv_utils

Cheef's Grand APDU List Smartcard Selected Information APDU list

#------------+------------------------+------------------------+----------------------+--------------------------------+
|ClaIns P1 P2|Lc Send Data            |Le  Recv Data           | Specification        | Description                    |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    04                                                        | ISO 7816-9 6.3       | DEACTIVATE FILE                |
| A0 04 00 00 00                                               | 3GPP TS 11.11        | INVALIDATE                     |
| A0 04 00 00 00                                               | SAGEM SCT U34 6.15   | INVALIDATE                     |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 0D xx xx 08 xxxx xxxx xxxx xxxx                           | SAGEM SCT U34        | VERIFY TRANSPORT CODE          |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    0C                                                        | ISO 7816-4 7.3.6     | ERASE RECORD (S)               |
| 80 0C 00 xx                          xx                      | SAGEM SCT U34 8.1.2  | CHECK (flash)                  |
| 80 0C 01 xx                          xx                      | SAGEM SCT U34 8.1.2  | CHECK (EEPROM)                 |
| 80 0C 02 xx                          xx                      | SAGEM SCT U34 8.1.2  | CHECK (checksum of file)       |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    0E                                                        | ISO 7816-4 8.2.4     | ERASE BINARY                   |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    10                                                        | ISO 7816-7           | PERFORM SCQL OPERATION         |
| 00 10 00 80 xx table name, ...                               | ISO 7816-7 7.1       | CREATE TABLE                   |
| 00 10 00 81 xx view name, table name                         | ISO 7816-7 7.2       | CREATE VIEW                    |
| 00 10 00 82 xx dictionary name                               | ISO 7816-7 7.3       | CREATE DICTIONARY              |
| 00 10 00 83 xx table name                                    | ISO 7816-7 7.4       | DROP TABLE                     |
| 00 10 00 84 xx view or dictionary                            | ISO 7816-7 7.5       | DROP VIEW                      |
| 00 10 00 85 xx privileges                                    | ISO 7816-7 7.6       | GRANT                          |
| 00 10 00 86 xx privileges                                    | ISO 7816-7 7.7       | REVOKE                         |
| 00 10 00 87 xx data                                          | ISO 7816-7 7.8       | DECLARE CURSOR                 |
| 00 10 00 88                                                  | ISO 7816-7 7.9       | OPEN                           |
| 00 10 00 89                                                  | ISO 7816-7 7.10      | NEXT                           |
| 00 10 00 8A                          xx D, fixing N (columns)| ISO 7816-7 7.11      | FETCH                          |
| 00 10 00 8B                          xx D, fixing N (columns)| ISO 7816-7 7.12      | FETCH NEXT                     |
| 00 10 00 8C xx data                                          | ISO 7816-7 7.13      | INSERT                         |
| 00 10 00 8D xx data                                          | ISO 7816-7 7.14      | UPDATE                         |
| 00 10 00 8E                                                  | ISO 7816-7 7.15      | DELETE                         |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    12                                                        | ISO 7816-7           | PERFORM TRANSACTION OPERATION  |
| 00 12 00 80                                                  | ISO 7816-7 8.2.1     | BEGIN                          |
| 00 12 00 81                                                  | ISO 7816-7 8.2.2     | COMMIT                         |
| 00 12 00 82                                                  | ISO 7816-7 8.2.3     | ROLLBACK                       |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    14                                                        | ISO 7816-7           | PERFORM USER OPERATION         |
| 00 14 00 80 xx User ID, ...                                  | ISO 7816-7 9.2.1     | PRESENT USER                   |
| 00 14 00 81 xx User ID, profile, ...                         | ISO 7816-7 9.2.2     | CREATE USER                    |
| 00 14 00 82 xx User ID                                       | ISO 7816-7 9.2.3     | DELETE USER                    |
| 80 14 xx xx 00                                               | GEMPLUS MPCOS-EMV    | Switch Protocol                |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 84 16 00 00 xx MAC                                           | VSDC                 | CARD BLOCK                     |
| 80 16 0X 00 05 xxxx xxxx xx                                  | GEMPLUS MPCOS-EMV    | Freeze Access Conditions       |
| 84 16 0X 00 08 xxxx xxxx xxxx xxxx                           | GEMPLUS MPCOS-EMV    | Freeze Access Conditions       |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 84 18 00 00 xx MAC                                           | VSDC                 | APPLICATION UNBLOCK            |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 84 1E 00 00 xx MAC                                           | VSDC                 | APPLICATION BLOCK              |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    20                                                        | ISO 7816-4 8.5.5     | VERIFY                         |
| 00 20 00 80 08 xxxx xxxx xxxx xxxx                           | VSDC                 | VERIFY (Transaction PIN data)  |
| A0 20 00 xx 08 CHV Value                                     | 3GPP TS 11.11        | VERIFY                         |
| A0 20 00 xx 08 CHV Value                                     | SAGEM SCT U34 6.10   | VERIFY                         |
| 80 20 00 xx 08 ADM Value                                     | SAGEM SCT U34 8.1.4  | VERIFY ADM                     |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 21 00 xx 08 ADM Value                                     | SAGEM SCT U34 8.1.4  | VERIFY ADM                     |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    22                                                        | ISO 7816-4 8.5.10    | MANAGE SECURITY ENVIRONMENT    |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    24                                                        | ISO 7816-4 8.5.6     | CHANGE CHV                     |
| 84 24 00 00 xx PIN data + MAC                                | VSDC                 | PIN CHANGE/UNBLOCK             |
| A0 24 00 xx 10 Old CHV, New CHV                              | 3GPP TS 11.11        | CHANGE CHV                     |
| A0 24 00 xx 10 Old CHV, New CHV                              | SAGEM SCT U34 6.11   | CHANGE CHV                     |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    26                                                        | ISO 7816-4 8.5.8     | DISABLE CHV1                   |
| A0 26 00 01 08 CHV1 value                                    | 3GPP TS 11.11        | DISABLE CHV1                   |
| A0 26 00 01 08 CHV1 value                                    | SAGEM SCT U32 6.12   | DISABLE CHV1                   |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    28                                                        | ISO 7816-4 8.5.7     | ENABLE CHV1                    |
| A0 28 00 01 08 CHV1 value                                    | 3GPP TS 11.11        | ENABLE CHV1                    |
| A0 28 00 01 08 CHV1 value                                    | SAGEM SCT U34 6.13   | ENABLE CHV1                    |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    2A                                                        | ISO 7816-8 5.2       | PERFORM SECURITY OPERATION     |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    2C                                                        | ISO 7816-4 8.5.9     | UNBLOCK CHV                    |
| A0 2C 00 xx 10 Unblock CHV(PUK), New CHV                     | 3GPP TS 11.11        | UNBLOCK CHV                    |
| A0 2C 00 xx 10 Unblock CHV(PUK), New CHV                     | SAGEM SCT U34 6.14   | UNBLOCK CHV                    |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| A0 2E 00 0# 01 Data                                          | 3GPP TS 11.11        | WRITE CODE STATUS              |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| A0 32 00 00 03 Value to be added.                            | 3GPP TS 11.11        | INCREASE                       |
| A0 32 00 00 03 Value to be added.                            | SAGEM SCT U34 6.9    | INCREASE                       |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    39                                                        |                      | java Authentificate User Comman|
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    44                                                        | ISO 7816-9 6.4       | ACTIVATE FILE                  |
| A0 44 00 00 00                                               | 3GPP TS 11.11        | REHABILIDATE                   |
| A0 44 00 00 00                                               | SAGEM SCT U34 6.16   | REHABILIDATE                   |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    46                                                        | ISO 7816-8 5.1       | GENERATE ASYMMETRIC KEY PAIR   |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 50 xx xx 08 Host challenge        00                      | GlobalPlatform       | INITIALIZE UPDATE then [C0]    |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    70                                                        | ISO 7816-4 8.1.2     | MANAGE CHANNEL                 |
| 00 70 xx xx                          xx                      | GlobalPlatform       | MANAGE CHANNEL                 |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 78 00 03 xx                                               | GlobalPlatform       | END R-MAC SESSION              |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 7A xx 01 xx Data and C-MAC, if needed                     | GlobalPlatform       | BEGIN R-MAC SESSION            |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    82                                                        | ISO 7816-4 8.5.3     | EXTERNAL AUTHENTICATE          |
| 84 82 00 00 10 Host cryptogram and MAC                       | GlobalPlatform       | EXTERNAL AUTHENTICATE          |
| 84 82 00 00 0A Authentication-related data                   | VSDC                 | EXTERNAL AUTHENTICATE          |
| 00 82 00 xx 06 Manual                                        | GEMPLUS MPCOS-EMV    | EXTERNAL AUTHENTICATE          |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    84                                                        | ISO 7816-4 8.5.2     | GET CHALLENGE                  |
| 00 84 00 00                          08 Rnd Num              | VSDC                 | GET CHALLENGE                  |
| 00 84 xx xx                          08 Rnd Num              | GEMPLUS MPCOS-EMV    | GET CHALLENGE                  |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    86                                                        | ISO 7816-4 8.5.4     | GENERAL AUTHENTICATE           |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    88                                                        | ISO 7816-4 8.5.1     | INTERNAL AUTHENTICATE          |
| 00 88 XX xx 0A Manual                                        | GEMPLUS MPCOS-EMV    | INTERNAL AUTHENTICATE          |
| A0 88 00 00 10 RAND : Rnd num        xx  SRES( 4B) , Kc (8B) | 3GPP TS 11.11        | RUN GSM ALGORITHM              |
| A0 88 00 00 10 RAND : Rnd num        xx  SRES( 4B) , Kc (8B) | SAGEM SCT U34 6.17   | RUN GSM ALGORITHM              |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    A0                                                        | ISO 7816-4 8.2.5     | SEARCH BINARY                  |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    A2                                                        | ISO 7816-4 8.3.5     | SEEK                           |
| A0 A2 00 xx xx Pattern               xx                      | 3GPP TS 11.11        | SEEK                           |
| A0 A2 00 xx xx Pattern               xx                      | SAGEM SCT U34 6.8    | SEEK                           |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    A4                                                        | ISO 7816-4 8.1.1     | SELECT                         |
| 00 A4 04 00 xx AID                   00                      | GlobalPlatform       | SELECT                         |
| 00 A4 00 xx xx File ID || Name       00  Manual              | VSDC                 | SELECT                         |
| A0 A4 00 00 02 File ID                                       | 3GPP TS 11.11        | SELECT                         |
| A0 A4 00 00 02 File ID                                       | SAGEM SCT U34 6.1    | SELECT                         |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 A8 00 00 00                       00                      | VSDC                 | GET PROCESSING OPTIONS         |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 AE 00 xx Transaction-related data                         | VSDC                 |                                |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    B0                                                        | ISO 7816-4 8.2.1     | READ BINARY                    |
| 00 B0 xx xx                          xx                      | GEMPLUS MPCOS-EMV    | READ BINARY                    |
| A0 B0 xx xx                          xx                      | 3GPP TS 11.11        | READ BINARY                    |
| A0 B0 xx xx                          xx                      | SAGEM SCT U34 6.4    | READ BINARY                    |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    B2                                                        | ISO 7816-4 8.3.1     | READ RECORD                    |
| 00 B2 xx                             00                      | VSDC                 | READ RECORD                    |
| A0 B2 xx xx                          xx                      | 3GPP TS 11.11        | READ RECORD                    |
| A0 B2 xx xx                          xx                      | SAGEM SCT U34 6.6    | READ RECORD                    |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    B4                                                        |                      | java Component Data            |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    B8                                                        |                      | java Create Applet             |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    BA                                                        |                      | java CAP end                   |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    BC                                                        |                      | java Component end             |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    BE                                04 Data                 | GEMPLUS GemClub-MEMO | READ                           |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    C0                                                        | ISO 7816-4 8.6.1     | GET RESPONSE                   |
| 00 C0                                1C Key Info             | GlobalPlatform       | GET RESPONSE                   |
| 00 C0 00 00                          00                      | VSDC                 | GET RESPONSE                   |
| 80 C0 00 00                          xx                      | GEMPLUS MPCOS-EMV    | Get Info on Get Response       |
| 80 C0 02 A0                          08 Chip SN              | GEMPLUS MPCOS-EMV    | Get Info                       |
| 80 C0 02 A1                          08 Card SN              | GEMPLUS MPCOS-EMV    | Get Info                       |
| 80 C0 02 A2                          08 Issuer SN            | GEMPLUS MPCOS-EMV    | Get Info                       |
| 80 C0 02 A3                          04 Iss.Ref.N            | GEMPLUS MPCOS-EMV    | Get Info                       |
| 80 C0 02 A4                          0D Chip Inf             | GEMPLUS MPCOS-EMV    | Get Info                       |
| 80 C0 02 A5                          xx Keys                 | GEMPLUS MPCOS-EMV    | Get Info                       |
| 80 C0 02 A6                          02 Last DF/EF           | GEMPLUS MPCOS-EMV    | Get Info                       |
| A0 C0 00 00                          xx                      | 3GPP TS 11.11        | GET RESPONSE                   |
| A0 C0 00 00                          xx                      | SAGEM SCT U34 6.3    | GET RESPONSE                   |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    C2                                                        | ISO 7816-4 8.6.2     | ENVELOPE                       |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    C4                                                        |                      | java Delete Applets            |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    CA                                                        | ISO 7816-4 8.4.1     | GET DATA                       |
| 00 CA 00 xx xx MAC, if present                               | GlobalPlatform       | GET DATA                       |
| 80 CA xx xx xx                                               | VSDC                 | GET DATA                       |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    D0                                                        | ISO 7816-4 8.2.2     | WRITE BINARY                   |
| 80 D0 xx xx xx Data to be written in EEPROM                  | VSDC                 | LOAD STRUCTURE                 |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    D2                                                        | ISO 7816-4 8.3.2     | WRITE RECORD                   |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    D6                                                        | ISO 7816-4 8.2.3     | UPDATE BINARY                  |
| A0 D6 xx xx xx Data to be written in EEPROM                  | 3GPP TS 11.11        | UPDATE BINARY                  |
| A0 D6 xx xx xx Data to be written in EEPROM                  | SAGEM SCT U34 6.5    | UPDATE BINARY                  |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 D8 xx xx xx KEY Date (and MAC)    00                      | GlobalPlatform       | PUT KEY                        |
|    D8                                                        | EMV                  | Set Card Status(personalization|
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    DA                                                        | ISO 7816-4 8.4.2     | PUT DATA                       |
| 00 DA xx xx xx Data                                          | VSDC                 | PUT DATA                       |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    DC                                                        | ISO 7816-4           | UPDATE RECORD                  |
| 00 DC xx xx xx Data (and MAC)                                | VSDC                 | UPDATE RECORD                  |
| A0 DC xx xx xx Data to be written in EEPROM                  | 3GPP TS 11.11        | UPDATE RECORD                  |
| A0 DC xx xx xx Data to be written in EEPROM                  | SAGEM SCT U34 6.7    | UPDATE RECORD                  |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    DE       04 Data                                          | GEMPLUS GemClub-MEMO | UPDATE                         |
| A0 DE 00 00 03 Data                                          | 3GPP TS 11.11        | LOAD AoC(SICAP)                |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    E0                                                        | ISO 7816-9 6.1       | CREATE FILE                    |
| 80 E0 02 00 0C Manual                                        | GEMPLUS MPCOS-EMV    | CREATE FILE                    |
| 80 E0 xx xx xx FCI length                                    | 3GPP TS 11.11        | CREATE FILE                    |
| 80 E0 xx xx xx FCI length                                    | SAGEM SCT U34        | CREATE FILE                    |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    E2                                                        | ISO 7816-4 8.3.4     | APPEND RECORD                  |
| 80 E2 00 00 xx Record (and MAC)                              | GlobalPlatform       | APPEND RECORD                  |
| 00 E2 00 00 xx Record                                        | VSDC                 | APPEND RECORD                  |
| 00 E2 00 00 xx Record                                        | GEMPLUS MPCOS-EMV    | APPEND RECORD                  |
| 00 E2 00 00 xx Record                                        | 3GPP TS 11.11        | APPEND RECORD                  |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    E4                                                        | ISO 7816-9 6.2       | DELETE FILE                    |
| 80 E4 00 00 xx TLV coded name                                | GlobalPlatform       | DELETE FILE                    |
| A0 E4 00 00 02 xx xx                                         | 3GPP TS 11.11        | DELETE FILE                    |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    E6                                                        | ISO 7816-9 6.5       | TERMINATE DF                   |
| 80 E6 xx 00 xx Manual                                        | GlobalPlatform       | INSTALL                        |
| A0 E6 xx xx 00                                               | 3GPP TS 11.11        | LOCK RECORD                    |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    E8                                                        | ISO 7816-9 6.6       | TERMINATE EF                   |
| 80 E8 00 00 xx Record                                        | GlobalPlatform       | LOAD                           |
| A0 E8 00 xx 10 Data                                          | 3GPP TS 11.11        | READ DIRECTORY                 |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 EA 00 00 xx Data                                          | 3GPP TS 11.11        | CREATE BINARY                  |
| 80 EA 00 00 xx Data                                          | SAGEM SCT U34        | CREATE BINARY                  |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 EE 00 xx 00                                               | VSDC                 | WRITE LOCK                     |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 F0 xx xx xx AID of Application (and MAC)                  | GlobalPlatform       | SET STATUS                     |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| A0 F2 00 00 xx                                               | 3GPP TS 11.11        | GET STATUS                     |
| A0 F2 00 00 xx                                               | SAGEM SCT U34 6.2    | GET STATUS                     |
| 80 F2 xx xx                                                  | GlobalPlatform       | GET STATUS                     |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 F8 xx xx                          xx                      | SAGEM SCT U34 8.1.1  | DIR                            |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| A0 FA 00 00 00                                               | 3GPP TS 11.11        | SLEEP                          |
| A0 FA 00 00 00                                               | SAGEM SCT U34 6.18   | SLEEP                          |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 FB xx xx                          xx                      | SAGEM SCT U34 8.1.1  | DIR                            |
+------------+------------------------+------------------------+----------------------+--------------------------------+
| 80 FC xx xx                          10                      | SAGEM SCT U34 8.1.3  | READ INFO                      |
+------------+------------------------+------------------------+----------------------+--------------------------------+
|    FE                                                        | ISO 7816-9 6.7       | TERMINATE CARD USAGE           |
| 80 FE xx xx 00                                               | SAGEM SCT U34        | BLOW FUSE                      |
+------------+------------------------+------------------------+----------------------+--------------------------------+

Dynamite Knight's Tour in F# - Tom Wells

An Ungodly Fast Solution in F# to the Knights Tour

I would suggest that you consider coding the solution up in F#, as my friend Tom Wells has done.  His solution finds all solutions for the 5x5 board in under 5 minutes.

let boardsize = 7

// Setup board in 2d array setting all elements to true
//  ___________________
// |0,4|1,4|2,4|3,4|4,4| (x,y)
// |0,3|1,3|2,3|3,3|4,3|
// |0,2|1,2|2,2|3,2|4,2|
// |0,1|1,1|2,1|3,1|4,1|
// |0,0|1,0|2,0|3,0|4,0|
//  -------------------
//
let referenceboard = Array2D.init boardsize boardsize (fun x y -> true)

let legalmoves x y =
    // Generate every move (impossible or not)
    //
    let possibles = [(x - 1, y - 2); (x - 2, y - 1);
                     (x + 1, y - 2); (x + 2, y - 1);
                     (x + 1, y + 2); (x + 2, y + 1);
                     (x - 1, y + 2); (x - 2, y + 1);]
    
    // Prune the ones falling outside of the board
    //
    possibles |> List.filter (fun (x, y) -> x >= 0 && y >= 0 && x < boardsize && y < boardsize)

// Is a particular move still available to us? ie not already used
//
let availablemove x y (board : bool[,]) =
    board.[x,y] = true

let rec hunt startx starty (board : bool[,]) (history : List<(int*int)>) foundsolutionfunc = 
    // Mark the position we're at as being taken
    //
    board.[startx,starty] <- false

    // Check if we have a solution (ie we've covered the entire board)
    //
    if history.Length = boardsize * boardsize then
        foundsolutionfunc (history) |> ignore
    else
        // Calculate the set of available moves from this point, filtering by positions which we've already used
        //
        let availablemoves = legalmoves startx starty |> List.filter (fun (x,y) -> availablemove x y board)

        // For each available move, recurse
        //
        for (x,y) in availablemoves do
            hunt x y (Array2D.copy board) ((x,y) :: history) foundsolutionfunc

[<EntryPoint>]
let main args =
    
    let starttime = System.DateTime.Now

    let solutions = new System.Collections.Generic.List<System.Tuple<int,int>>()
    for x in seq { 0 .. Array2D.length1 referenceboard - 1 } do
        for y in seq { 0 .. Array2D.length2 referenceboard - 1 } do
            printf "(%d,%d)" x y

            hunt x y (Array2D.copy referenceboard) [(x,y)] (fun solution ->
                solutions.Add(new System.Tuple<int,int>(x,y))
                printf "."
            )    

    let endtime = System.DateTime.Now

    printfn "\nFound %d solutions (took %03f seconds)" solutions.Count (endtime - starttime).TotalSeconds
    
    printfn "Enter to quit"
    System.Console.In.ReadLine() |> ignore

    0

EMV / Smart-Card Development with pyscard / python

python/pyscard EMV tool pack
@ https://github.com/davidbarkhuizen/py_emv_utils

EMV Resources
- EMV Entry on Wikipedia

ATR = Answer To Reset
Standard/Spec = ISO7816-3
OnLine ATR Byte String Parser
ATR @ Wikipedia

PySCard Resources
- Project @ SourceForge

pyscard on ubuntu
1. install pcscd :  sudo apt-get install pcscd
2. start daemon : sudo /etc/init.d/pcscd start

PY_EMV_UTILS - python pyscard emv smartcard utilities
svn checkout svn://svn.code.sf.net/p/pyemvutils/code/trunk pyemvutils-code

The Knights Tour Problem - Multi-Processor Algorithmic Parallelism with Python

Resources
- Wikipedia Entry.
- Stefan Behnel's page [What the Chess Knight is Doing] features some handy info on the solution space.

A Brief Introduction to the Knight's Tour Problem

A Knight's Tour is a traversal of an 8x8 chess-board by the Knight / Horse piece, where the Knight touches each and every square once and only once during the tour, and makes only its characteristic L-shaped legal moves.

Open Knights Tour on 5x5 Board
[Graphic Linked from Wikipedia Entry]

The problem can be further generalised by varying board parameters - to produce arbitrarily sized square NxN grids, and also arbitrarily-sized rectangular NxM grids.

There is also the closely-related problem of finding closed tours - where the Knight must be in a position on the final square of its open tour to theoretically return again to the first square of that tour by a legal move [closing the tour].

Closed Knights Tour on 8x8 Board
[Graphic Linked from Wikipedia Entry]

The Knights Tour Problem is a specific instance of the more general problem of finding a Hamiltonian Path (i.e. a connected path that touches each vertex once and only once) [open tour problem], and a finding a Hamiltonian cycle [closed tour problem].

The Solution Space

NxN Square Board - Count of Open Undirected Tours

4x4 => 0
5x5 => 1728
6x6 => 6,637,920
7x7 => 165,575,218,320
8x8 => 19,591,828,170,979,904


Brute Force Solution Approach

A brute force approach is typically only practical in the case of the 5x5 board, and is not generally useful for the higher dimensional problems, due to the fact the the solution space explodes with increasing problem dimensions.  From the Wikipedia entry:  "For a regular 8x8 chess board, there are approximately 4×10^51 possible move sequences, and it would take an unfathomable amount of time to iterate through such a large number of moves."

The ration of solutions to possible move sequences is small.

A Useful Heuristic - Warnsdorff's Rule [Wikipedia]

Warnsdorff's rule is a heuristic method for finding a knight's tour. Briefly, one moves the knight according to the following rule: always proceed to the square from which the knight will have the fewest onward moves.  It is, of course, possible to have two or more choices for which the number of onward moves is equal; there are various methods for breaking such ties, including one devised by Pohl and another by Squirrel and Cull.  This rule may also more generally be applied to any graph. In graph-theoretic terms, each move is made to the adjacent vertex with the least degree. Although the Hamiltonian path problem is NP-hard in general, on many graphs that occur in practice this heuristic is able to successfully locate a solution in linear time.  The knight's tour is a special case.  The heuristic was first described in "Des Rösselsprungs einfachste und allgemeinste Lösung" by H. C. von Warnsdorff in 1823.

Brute-Force / Depth First Search

Finding of All Open Tours

in 5 x 5 Case

Solution Description

A back-tracker / depth-first searcher was developed in Python 2.7.

A Definition of Back-Tracking from the Wikipedia:

Backtracking is a general algorithm for finding all (or some) solutions to some computational problem, that incrementally builds candidates to the solutions, and abandons each partial candidate c ("backtracks") as soon as it determines that c cannot possibly be completed to a valid solution.

A Definition of State Space Search from the Wikipedia:


State space search is a process used in the field of computer science, including artificial intelligence (AI), in which successive configurations or states of an instance are considered, with the goal of finding a goal state with a desired property.

Problems are often modelled as a state space, a set of states that a problem can be in. The set of states forms a graph where two states are connected if there is an operation that can be performed to transform the first state into the second.

State space search often differs from traditional computer science search methods because the state space is implicit: the typical state space graph is much too large to generate and store in memory. Instead, nodes are generated as they are explored, and typically discarded thereafter. A solution to a combinatorial search instance may consist of the goal state itself, or of a path from some initial state to the goal state.


A General Description of the Specific Back-Tracker Implementation

Essentially the tracker successively explores the state space, collecting solutions as it goes.

Considering the 5x5 grid case, and starting from a blank board:

It is first noted that there are 25 possible first moves than can be made, since the knight can be placed on any of the 5 x 5 = 25 squares.

From each of these 25 possible first moves, uniquely different (although sometimes symmetrical) second moves can be made.  Now, the number of possible second moves is not the same for every possible first move, for example first moves to edge squares will have less possible second moves than first moves to the centre square (or centre squares, in the case of even-dimensioned square boards).

Then for each of the possible second moves, there are a number of possible third moves, and so on, until either the knight gets stuck or successfully untangles a Hamiltonian path.

Thus the solution space can be thought of as a tree structure, with the blank board as the root node, and each of the 25 possible first choices as nodes adjacent to the root node.  Each of the possible second choices are then nodes adjacent to their respective first-choice nodes, and so on.  Knight's tours will then be Hamiltonian paths of length 25 [= N^2 = NxN], and aborted attempts will correspond to shorter paths.

The back-tracker dynamically and successively generates this tree structure - exploring a particular branch, until a dead-end is reached, then back-tracking until the first unexplored branch is encountered, pruning the fully examined branch off the tree and discarding it to minimize persistence (memory/disc) utilisation, before continuing forward again to explore another remaining unexamined branch.

Parallelisation with Python's Multiprocessing Module

The Knights tour problem just screams parallelisation, but how to do this given the restrictions imposed by Python's crummy Global Interpreter Lock (GIL) on the language's support for true multi-threading ?  With the standard library's multiprocessing module:

multiprocessing is a package that supports spawning processes using an API similar to the threading module. The multiprocessing package offers both local and remote concurrency, effectively side-stepping the Global Interpreter Lock by using subprocesses instead of threads. Due to this, the multiprocessing module allows the programmer to fully leverage multiple processors on a given machine. It runs on both Unix and Windows.

So, what multiprocessing actually gives you is a set of independent operating-system level processes, each with it's own Python VM, and some infrastructure for both passing objects and (save us) directly sharing memory between these distinct processes.

Design Pattern

The design I've chosen utilises a single co-ordinating process, which spawns agent processes that are responsible for the execution of the actual business of exploring the solution space.

In the simplest case each agent process is assigned a different first choice, and it generates, examines and prunes the branch associated with that specific first choice, communicating solutions found back to the co-ordinating process, and finally notifying it of completion (total exploration of assigned solution space).

When the co-ordinating process is informed of successfully termination of an agent process, it will then spawn a new agent and assign them to examine a different branch of the tree.

When all branches have been examined, the solution space can be considered exhausted and all solutions found, and the coordinating process will report to file, and terminate.

Communication between the coordinating processes and its agents is achieved via use of the duplex pipe object available in the multiprocessing module.

Test

The Test
Exhaustively searching for and identifying all 1728 Knight's Tours on the 5x5 board.

Test Machine
I5-4x2.3GHz-8MB = Intel i5-2410M 2.3GHz with 8 GB
Test Machine Syn features an Intel i5 array of 4 cores at 2.3 GHz, with 8 GB memory available, running 64bit Windows 7, and 32 bit Python 2.7.

The Results

Single Process, No Threading - Effectively 1 Core

First off, the performance of the basic unthreaded, singleton-process back-tracker.

Total Time = 1hr46mins = 106 mins = 6360 seconds
Total Solution Count = 1728
Average Rate of Solution Finding = 0.27 solutions per second
Average Time to Find Next Solution = 3.68 seconds per solution

1 Controller Core + 3 x Agent Cores


Total Time = 41 mins = 2460 seconds
Total Solution Count = 1728
Average Rate of Solution Finding = 0.70 solutions per second
Average Time to Find Next Solution = 1.42 seconds per solution


Comparison - Singleton Process versus Multi-Process [1 Controller, 3 Agents]

So, the question is, from a quantitative perspective, what gains have been achieved by parallelising the algorithm ?

Since the test machine has 4 cores available, and the algorithm uses one of them for co-ordination, and farms out the work to 3 agent processes, we expect to see about a 3-fold gain in speed / decrease in total time.

Actually Observed Performance Ratio = 6360 / 2460 ~  2.59
Theoretical Maximum Performance Ratio = 3 [going from 1 to 3 worker cores]

So, overall our increase in performance is not too bad, we didn't quite achieve the maximum ratio of 3, but we're not too far off at 2.59.  Quantitatively we have achieved ~ 86% of the maximum theoretically possible increase in performance.

POST SCRIPT

"So, overall our increase in performance is not too bad" - Unfortunately, this is a blatant lie, see the next post on this topic for damning details.