IcoSoKu solver

margin-left: 30px;

Faces example

I wrote a simple javascript IcoSoKu solver. You can enter the configuration of the 12 yellow pins in the text boxes and click “Solve IcoSoKu” to calculate the solution. For example if you have the yellow pin 5 on vertex A (the top vertex), you must type 5 in the Pin A text box. The faces are identified with their three yellow pins (see a small example on the right).

The 20 white tiles are identified with their black dots; for example (2,2,0) represents the tile with two black dots in the first and second corner and zero dots on the third.If the solution says put tile (1,2,3) on face [11,12,7], then you must put the white tile on the bottom-left face, and rotate it until 1 black dot is on yellow pin 11, 2 black dots are on yellow pin 12 and 3 black dots are on yellow pin 7. You can also generate a random yellow pins configuration clicking “Random IcoSoKu”.

Pin A:

 Pin B:  Pin C:  Pin D:  Pin E:  Pin F:

 Pin G:  Pin H:  Pin I:  Pin J:  Pin K:

Pin L:

 

 



 

I didn’t tested the solver too much, so if you find a wrong solution or a pin configuration that doesn’t produce a solution, please post a comment below to help me fix the bugs.

UPDATE 14/08/2021: since my solver was published on this blog, a few papers have been published about IcoSoKu:

  • Nicola Rizzo, Agostino Dovier: 3coSoKu and its Logic Programming Modeling. CILC 2020: 5-20 (the paper can be downloaded here)
  • Ke Liu, Sven Löffler, Petra Hofstedt: Exploring Properties of Icosoku by Constraint Satisfaction Approach. DECLARE 2019: 99-105 (the paper can be downloaded from arXiv)

38 thoughts on “IcoSoKu solver

    • Don’t worry, I completely rewrote the layout: now vertices are marked with letters and the faces in the solution refer to pins (this should result in a more readable solution).

  1. Wonderful! I assume that your solution for any given pin arrangement is unique, but I’m not sure if solutions are in fact unique for all pin arrangements. Have you figured out any graph theory approach that would answer that question? I’d like to use this puzzle as an example of a deterministic game which students could apply basic graph analysis to solve. Easy to say, but I’m not sure yet how difficult that would be. Anyway … thanks for the solution page. Some arrangements were driving me batty!

    • > I assume that your solution for any given pin arrangement is unique

      Yes, the solver doesn’t use random values.

      > I’m not sure if solutions are in fact unique for all pin arrangements

      No, there are (I think many … perhaps all) pin arrangements that have more than one solution (using a constraint solver I found one of them just out of curiosity )

      >Have you figured out any graph theory approach that would answer that question?

      No, but I think that a complete analysis of the game would be interesting.

      >I’d like to use this puzzle as an example of a deterministic
      >game which students could apply basic graph analysis to solve
      >Easy to say, but I’m not sure yet how difficult that would be

      … you just have to try to find out 🙂 🙂
      Instead I thought of a possible generalization of the game to study its complexity … but for now I have not arrived at any maningful conclusion.

  2. The game is very interesting but mathematically difficult…
    And this solver is also a good job!
    Now let me report a bug case;
    Pin A:9
    Pin B:4 Pin C:10 Pin D:12 Pin E:7 Pin F:8
    Pin G:5 Pin H:6 Pin I:2 Pin J:1 Pin K:3
    Pin L:11
    (When I try the case, the solver freezes.)

    • Thank you for the test case; it is probably an “hard” instance and the solver takes too much time to solve it.
      But if you put the icosoku upside-down (A:11, B:5, C:6,…) it will give the correct solution quickly:

      SOLUTION OF GAME [11,5,6,2,1,3,4,10,12,7,8,9]:
      Put tile (3,3,0) on face [11,6,2], tile (3,0,0) on face [11,2,1], tile (0,1,1) on face [11,1,3], tile (2,0,1) on face [11,3,5], tile (3,1,2) on face [11,5,6], tile (0,2,2) on face [6,10,12], tile (0,2,1) on face [6,12,2], tile (1,2,3) on face [2,12,7], tile (0,0,0) on face [2,7,1], tile (0,1,2) on face [1,7,8], tile (0,0,1) on face [1,8,3], tile (1,2,0) on face [3,8,4], tile (0,0,2) on face [3,4,5], tile (1,0,2) on face [5,4,10], tile (0,2,1) on face [5,10,6], tile (3,3,3) on face [10,9,12], tile (3,2,1) on face [12,9,7], tile (2,2,2) on face [7,9,8], tile (2,1,3) on face [8,9,4], tile (1,1,1) on face [4,9,10]

      When I have enough time I’ll try to improve the algorithm adding an heuristic to solve instances like the one you’ve found.

  3. I would be very interested to know how the program achieves the solution. Is it an algorithm? Or is it perhaps that the solution for pin arrangements is based on a distortion of an already existing solution?

  4. Would you mind including a brief documentation of the this method. How did you manage to approach this problem beforehand, and what optimizations are used to reduce the time taken to solve the puzzle?

    • I didn’t analyze neither the complexity of the problem nor tried to find optimization heuristics; actually it is a simple brute force algorithm. Perhaps it would be interesting to see if the problem can be generalized to instances of arbitrary size, and then study the computational complexity of the related decision problem: “Given a partially filled IcoSoKu instance, decide if it admits a valid solution”. Let me know if you’re going to work on it.

      • I am actually doing this for my maths project this year, so I am wondering if there are really any special properties for this puzzle which enables one person to use a algorithm to solve it manually (like a rubrics cube for instance). Currently we are trying to use smaller platonic solids to attempt to find some clues, but we are not really sure yet.

  5. Bugged case? Or am I misinterpreting your output
    SOLUTION OF GAME [1,10,9,6,7,8,11,3,5,2,4,12]:
    Put tile (0,3,3) on face [1,9,6]
    Put tile (0,0,2) on face [1,6,7]
    Put tile (0,1,1) on face [1,7,8]
    Put tile (1,2,3) on face [1,8,10]
    Put tile (0,2,1) on face [1,10,9]
    Put tile (1,1,1) on face [9,3,5]
    Put tile (2,1,3) on face [9,5,6]
    Put tile (0,0,0) on face [6,5,2]
    Put tile (0,0,3) on face [6,2,7]
    Put tile (0,0,1) on face [7,2,4]
    Put tile (1,2,0) on face [7,4,8]
    Put tile (2,0,2) on face [8,4,11]
    Put tile (3,3,3) on face [8,11,10]
    Put tile (1,2,0) on face [10,11,3]
    Put tile (1,0,2) on face [10,3,9]
    Put tile (0,2,1) on face [3,12,5]
    Put tile (2,3,1) on face [5,12,2]
    Put tile (1,2,0) on face [2,12,4]
    Put tile (1,3,2) on face [4,12,11]
    Put tile (2,2,2) on face [11,12,3]

    Why are there faces 1,9,6
    How is that even possible

  6. The icosaku solver is unfortunately wrong in many instances. Contrary to popular opinion the icosaku puzzle has only 1200 verifiable solutions not 479,001,600. The puzzle is actually very simple mathematically since it concerns only 20 equilateral tiles containing only 78 utilizable dots out of a total of 180. 102 of which replace the term “zero”. I doubt the inventor of this puzzle realizes the mathematical implications it has in the theoretical realms.

    • What do you mean that “The icosoku solver is unfortunately wrong in many instances”? Did you find some instances for which the above solver doesn’t output a correct solution? If yes, please email me such instances, and I’ll check them.

      In the previous Camber “wrong” example, if you type the game [1,10,9,6,7,8,11,3,5,2,4,12], you see that face [1,9,6] refers to face [A C D] in the figure. Probably to make things clearer I should add a simple reverse mapping and represents the face list of the solution with the corresponding letters in the figure.

  7. Sorry for the abruptness of my assertions. I will respond by next Tuesday morning with some interesting mathematical observations regarding the regular icosahedron generally and the Icosaku puzzle specifically. I sincerely appreciate your efforts in this realm. The Icosaku puzzle has far deeper mathematical significance than most people realize. It is related to problems I have worked on for decades. Your humble servant, Marc.

  8. Out of the 20 triangular tiles that comprise this puzzle, 16 are trivalent and the remaining 4 are monovalent. For example, tile 210 can actually be 021 and 102 depending on context. Whereas tiles 000, 111, 222, and 333 will always retain their monovalent identities regardless. Now, randomly focusing on tile 210, for example, we see that as a tile it can assume one of twenty positions on our icosahedral base and can be rotated to assume alternative identities 021 and 102. The group of 16 tiles to which tile 210 belongs can all assume three different identities depending on vertexial context.

  9. Each one of these 16 tiles can, therefore, assume 48 positional identities for a group total of 960 or 16x3x20. The remaining 4 monovalent tiles 000, 111, 222, 333 can assume 20 positional identities each for a group total of 80 positional identities. Total positional identities for all 20 tiles in this puzzle is 1040. Now, any given icosahedral vertex consists of 5 joining tiles with total vertexial values of 1 through 12 as a limiting factor.

  10. Now, for the group of 16 trivalent tiles, there are four subgroups of identical tiles. Namely, three 210 tiles, three 201 tiles, two 312 tiles, and two 321 tiles. The remaining tiles 100, 110, 200, 022, 033, and 300 are all singular tiles. Several conclusions can now be drawn. Common sense dictates that there are 479,001,600 possible outcomes for this puzzle. But the vast majority of the 479,001,600 outcomes are incorrect and are not valid solutions.

  11. Repetitive vertex sums and sums exceeding 12, such as 13, 14, or 15 are the most common transgressions with zero sums being less common. Given the limiting factors of 20 white tiles with a total of 78 black dots that can converge at 12 nodes with total valuations of 1 through 12, we are left with 319,334,400 incorrect outcomes and 159,667,200 correct puzzle solutions. Statistically 2/3 vs 1/3.

  12. Notice how the statistical breakdown is 2/3 vs. 1/3. I wonder if this would remain valid in a polyhedral puzzle of, let’s say, any of the Archimedean solids as opposed to the rest of the Platonic solids, with the vertexial values equalling the number of vertices for that given polyhedron.

  13. Pull all 12 yellow pins out and strip Icosaku of all 20 tiles. Insert all 12 pins completely at random. Your chance of selecting the right tile and placing it in perfect orientation is .000961538% or 962 out of 1 million. Your second selection, since you have a reference and only 19 tiles to choose from has grown to .001020408% or 102 out of 100,000. Keep going and you realize how truly difficult this puzzle is.

  14. Now that we have established that there are 479,001,600 possible pin arrangements. I note that the manufacturer of Icosaku asserts that there is a verifiable solution for every pin configuration. I accept this without further scrutiny. However, for ease of calculation, consider all 20 tiles as rotationally trivalent- meaning all can be rotated 120, 240, and 360 degrees and placed in any position on the icosahedral matrix. This gives us a staggering 7.298706025 x 10 to the 18 the power of tile positions.

  15. The number of correct solutions is obviously a fraction of possible tile arrangements and demonstrates the limiting factors 12 numbered vertices and 78 out of 180 dots exerts. If we remove the constraint of matching our 12 numbered vertices and RANDOMLY slapping on all 20 tiles in true mindless fashion 15 times over, we notice an interesting numerical trend which could be useful as a key to manually solving the puzzle as intended.

  16. Out of 15 trials only 12 out of 180 tile sums matched the numbered vertices, or 1 out of 15. Because of the design of the puzzle, the sum 7 appeared 19.444% of the time. 8 appeared 16.111% of the time. The sums 4,5,6,9 each appeared at least 12.222 to 12.777 % of the time with 11 and the prohibited 13 being the rarest. This all makes perfect sense since the average distribution of the 78 dots is 6.5.

  17. 7,298,706,025,000,000,000 unconstrained possible tile positions in relation to the icosahedral base and to one another. 479,001,600 possible pin arrangements with at least one correct solution per pin arrangement means 1 in every 15,237,331,200 tile arrangement is a bona fide puzzle solution. The manual solution of this puzzle involves some skill yet to be named specifically by anyone.

  18. Let’s give it a go. Recognize that there are two groups of tiles,16 trivalent and 4 monovalent. The system as designed wants to produce sums in the 5 to 8 range since the average is 6.5. Separate out your 000, 111, 222, 333 tiles- use them last. Solve pins 12 and 1 first wherever they are. Pay attention to 2/3 the puzzle at any given moment with particular attention to pins 7 and 9.

  19. Clarification is necessary. The 15 test runs were done with all 12 pins in the same order as they appear in the diagram at the top of this page.
    7,298,706,025,000,000,000 as the number of possible tile arrangements is slightly higher than it should be because it treats the four monovalent tiles as trivalent. It is mathematically very difficult to isolate out the rotational neutrality of just 4 of the 20 tiles. 000, 111, 222, 333 if rotated always retain their numerical identities.

  20. 7,298,706,025,000,000,000 as it turns out is identical to (20!) or 20 factorial multiplied by 3. Subtracting the influence of 4 monovalents originally counted as trivalents we are left with this many possibilities:
    7,298,706,025,000,999,840 possible iterations versus
    479,001,600 pin arrangements. Correct Icosaku solutions being mere fraction of total possible tile arrangements.

  21. My final corrected analysis of the Icosaku will be posted in the coming days. Consideration of a similar mathematical puzzle using the pentagonal dodecahedron which has 12 sides, 20 vertices, and 30 edges will also be considered and proposed to a manufacturer. The real mystery of the Icosaku, however, is the DISTRIBUTION of the 78 black dots among the 20 tiles, not the SUM of 78 which is merely the sum of the numbers 1 through 12.

  22. How the distribution of the 78 black dots was arrived at by the inventor of the Icosaku deserves careful analysis since it has bearing on the creation of any subsequent polyhedral mathematical puzzles I am about to propose to a domestic manufacturer. Off the cuff, I would say that the dodecahedral puzzle should utilize 210 black dots from a limit of 300 as a ceiling.

  23. Thanks for what you’ve done.
    I tried to invert simply the two pins 1 and 12.

    Cannot find a solution quickly, please post this string in a comment below to help me improve the solver: [12,6,5,4,3,2,11,7,9,8,10,1]

  24. I found an interesting combination through playing with the random generator. Try it:

    A7, B3, C8, D10, E1, F2, G5, H11, I4, J6, K12, L9.

    It never produces a solution. However, usually your program works very fast. How exactly does your program work? I tried looking at the code, but don’t know Java so well.

    • It’s a simple brute-force recursive + backtracking solver; nothing special. A generalization of Icosoku has been proved to be NP-complete: see Nicola Rizzo and Agostino Dovier, 3coSoKu and its Logic Programming Modeling, 2020.

  25. Hello.

    The following failed to find a solution: [1,11,4,10,3,2,8,7,9,5,12,6]

    I ported your code over to C and found a solution at itt = 394,757,774.

  26. Hello again.

    Bad timing. Right after I submitted my comment, the following popped up:

    Cannot find a solution quickly, please post this string in a comment below to help me improve the solver: [1,11,4,12,3,2,6,5,7,8,10,9]

    I believe you find a solution at itt = 1,952,149,599

Leave a Reply

Your email address will not be published. Required fields are marked *