Sudoku solver
in [ASM]
|
Prev: the screen light of my portable pc is off
Next: Is PSHUFW instruction MMX or SSE or SSE2? Is NASM manual correct?
From: Evenbit on 19 Dec 2007 21:15 On Dec 19, 6:47 pm, "[ DocJeff ]" <y2kp...(a)hotmail.com> wrote: > Anyone happen to have assembler-level code for such a beast? I'd like > to see how it's done. Thanks in advance. > > /Doc See this thread: http://groups.google.com/group/alt.lang.asm/browse_frm/thread/0a99a12ada96207e/de27329ac08527d3#de27329ac08527d3 Nathan.
From: Terence on 20 Dec 2007 01:36 On Dec 20, 1:15 pm, Evenbit <nbaker2...(a)charter.net> wrote: > On Dec 19, 6:47 pm, "[ DocJeff ]" <y2kp...(a)hotmail.com> wrote: > > > Anyone happen to have assembler-level code for such a beast? I'd like > > to see how it's done. Thanks in advance. > > > /Doc > > See this thread: > > http://groups.google.com/group/alt.lang.asm/browse_frm/thread/0a99a12... > > Nathan. I already have Herbert Kleebauer's 32-bit Asm code, which is smart and efficient, but I still don't know why it doesn't get stuck. He states, and the code shows it, that he guesses one value, if the algorithm sees no imediate solution. That should only work 50% of the time in a two-way alternative at best, so I don't know what is happening of if it really gets a solution every time uder those cercumstances - it shouldn't! ... I wrote a solver in 16-bit Fortran myself, a different, human-rule application, and show steps and rules as it solves, and has a second toggle screen to see possibilities. If also saves and searches for puzzles and allows hand entry and human take-over at any point.
From: Terence on 21 Dec 2007 17:11 Update. I found it helps a solver enormously to add a bit-counter function to provide a parallel array of 81 bit counts to match the bit maps of possible local solutions. (A bit is the bit poistion representing a digit 1-9). And so to my AND, OR, NOT, XOR,ISHR asm-coded functions that are not in F77,I've just added an efficient NBIT 16-bit bit counter based on SHL The reason is that a pair of 2-bit counts in a row/column or subsquare (houses) allows youto to remove these possibilities from the house set being wored on, set and also from the subsquare set if they both belong.to it Then, a trio of 3-3-3 or 3-3-4 with the same 3 bits has the same elimination argument. Finally a quad of 2-3-4-4 or 3-4-4-4 or 2-4-4-4, being the only boxes with these 4 bits of possibilities present, also can apply that elimination rule, including 3 in a line in a subsquare and the fourth in the same subsquare. So to find a 2-bit count and seek another can be faster if the counts are already computed. And a trio is found by finding 3-count then checking that ANDing the trio of bits to all other possibility groups in the house and checking the result is the same three bits, thrice, and twice exactly three, is also far quicker that an involved 3-level search and so on.
From: Terence on 23 Dec 2007 18:16
I have located the reason for the difference of opinions. Herbert's algorithm tests for valid solutions. It keeps going if a trial (valid possibility) works. But if there is another solution (one where a higher-number bit of the possibilities for a square being considered, is not chosen because the lower bit choice works, even though the higher bit can lead to another valid soultion) then this or other solutions are not found. The algorithm I am working on detects when there are no automatic decisions left, and there is no logical reason to choose one further possible route over another, and pauses to display the partial solution, full alternatives and a map of possibilities (which tend to show the partterns os sets of solutions). It stops if there is no valid solution (i.e a blank square with no possibilities remaining). So if it pauses and asks for suggestions, the puzzle is not yet found to be invalid (even if there is only one solution). This can also happen if I inhibit some complex solving rules mentioned, which helps teaching, and leads onto the higher-order (3rd and 4th order) rules. |