Sudoku
in [ASM]
|
From: Spam Killer on 5 Dec 2007 14:05 On Wed, 05 Dec 2007 18:55:21 +0100, Herbert Kleebauer wrote: > >> but there is an additional requirement for solving it. The colors do >> matter. The numbers 1-9 must appear in every color only once, and >> this variation seems to be relatively new. I've only seen this one so >> far. > >Which colors? color 1 color 2 color 3 ... color 4 color 5 color 6 ... color 7 color 8 color 9 ... color 1 color 2 color 3 ... .... in each of the squares. -- wfz
From: Terence on 5 Dec 2007 17:33 On Dec 6, 6:05 am, nos...(a)spamtrap.com (Spam Killer) wrote: > On Wed, 05 Dec 2007 18:55:21 +0100, Herbert Kleebauer wrote: > > >> but there is an additional requirement for solving it. The colors do > >> matter. The numbers 1-9 must appear in every color only once, and > >> this variation seems to be relatively new. I've only seen this one so > >> far. > > >Which colors? > > color 1 color 2 color 3 ... > color 4 color 5 color 6 ... > color 7 color 8 color 9 ... > > color 1 color 2 color 3 ... > ... > > in each of the squares. > -- > wfz The 3x3 subsquares and the rows and the columns are what the oriental fans call "houses". Other names are SQUARE, ROW, COLUMN and the 81 items are BOXES. I uses alternate colours myself, like a chess board, when displaying sets of possible digits per box in partial solutions. The preferred oriental way of solving is to use a 3 by 3 dot array in each BOX to represent possible digits, and crossing a dot (or filling a tiny circle) if a possibility is eliminated 123 456 789 I still trying to understand Herbert's strange code. It does seem to be pure X86; possibly 32 bit asm. I'm really more interested in the algorithm he mentioned (which does involve guessing when stuck; I'm trying to find rules to get past that part). My "HARD" examples all need a guess except for one.
From: Herbert Kleebauer on 5 Dec 2007 20:59 Terence wrote: > I still trying to understand Herbert's strange code. It does seem to > be pure X86; possibly 32 bit asm. You again disassembled the decoder and not the program. The following batch will generate the real (not ascii encoded) binary which you can disassemble: @echo off echo hD1X-s0P_kUHP0UxGWX4ax1y1ieimnfeinklddmemkjanmndnadmndnpbbn>bat.com echo hhpbbnpljhoxolnhaigidpllnbkdnhlkfhlflefblffahfUebdfahhfkokh>>bat.com echo wvPp0w(a)L4k9C5/R/pN0d0uDL47bwo1YiQJEWtbGov5//B6mkuMEo0IL0l/w>>bat.com echo ef2iC57R/pNEA/jeefHhC5AR/pNEA/juefXgC5ER/phCfDM(a)m042knfuur9>>bat.com echo l3LYV5wPajYHk3aZPILM5uqAk3g/XQqHL3wYkRkPKAGPq2f9wNaZc4fXkNa>>bat.com echo Rg0Hsz/aBcl3QasIP5uD9k3aVCK0AVND7sPLM5uqS0RTNajYHk3aZPILQaN>>bat.com echo @OEV/L6Da4AuEMai1QVNxak4aJ7ooVVNcXp4bNKWKM5uvR0RoM5uKRVNF@i>>bat.com echo NBJ6ra4AsEQaN8OUN2OA0b8ShaV(a)j3AluQM5iCGk3fvUNsu60HgC2aV@c3A>>bat.com echo VNczT/HM5uQ8k3aVib1AVNUNajYHk3ax(a)95AluCM5Mat@95AVNzGC0HMKiF>>bat.com echo RlwbNKda45YaBgNUNajYHk3aZPILMKAzTaN(a)OEV/LrKaBsn0MKkc2VNu9k4>>bat.com echo a4nqapP1LMKVEHr7bNKWKM5uKRlQ8MqUDzjNl/xuCMKVPLL0aZsofHUN2iw>>bat.com echo za4hsapIRFPKVPHr8sNkNaZc6fXUN02C3bNKW5MqU5HkNWPdN4yjNDUMTzz>>bat.com echo zza45YsPqkaB7m0MKMEajN2P5Mat(a)t3AVNtak4ah@1LQaN(a)OUN89wNaB/0S>>bat.com echo SaN(a)EVbahIRmbXkaxEVtTVN0fC3aZ/oxsz/axEVcTVN2OA8b8Clat(a)t3AVN>>bat.com echo tak4ah(a)1LQaN@OUN89wNap7(a)PRaNBmKP/QaN2EUfbNq1IseN(a)Jrtt7gNDIc>>bat.com echo dLMKke2VN8/RDyDUNDIMZLMqU5HkNWbfNyGC0HMKi2QVNvCk4bNqW5MKW1T>>bat.com echo aN2M30bNq1KFkNaBUF7QaN(a)M41bNq/5FmNahUJYQaN2M39bNq1KVmNaBUFg>>bat.com echo QaN(a)M4@bNq/5VoNahUJ7RaN2M3HbNq1KloNaBUFERaN(a)M4It7QRVMKke2VN>>bat.com echo 8/RDyDERJMqU5nUN(a)JLYaBcl7Ras3OKMEWjN2PKMEajN2P5MkqUNcfs4keU>>bat.com echo Nc(a)s4at@t3AVNvak4apP1LQaN(a)OVN2OA0aZf1L/@Aa4humRUN/Rasq2f(a)aV>>bat.com echo iHLMKHpdBgBM5u1R0g9M5uuQVN(a)J6ka45YaBgNUNKW5T5f31AR7M5uUQlum>>bat.com echo PKMEOqka05hzc(a)s3YP//3nqB6WNV0dNDMf0UHUN2P5MW1C0o1YiUHEi0/ki>>bat.com echo 0/EnVMKMEOqks1/HB6G29Y5PgJqNVl57dt5QpF6/Bc/Nd8LNXF6Pt0mQjla>>bat.com echo RZF5/BckQjlaRZF57rZ5Rc0mPiJ57mJqMp8rQdxaP/oU1ix5RUArPgNLNV8>>bat.com echo 5PZ0mRdF6OUwaPZ0WQZBKRmBLOjtq3.>>bat.com bat.com >sudo.com del bat.com > I'm really more interested in the algorithm he mentioned (which does > involve guessing when stuck; I'm trying to find rules to get past that > part). My "HARD" examples all need a guess except for one. For each row, column and square you have to check that in this 9 position each digit occurs only once and that it is possible to insert each 1-9 digit. I use two 9 bit variables for each position stored in a 32 bit variable. It doesn't matter where in the 32 bit variable you put this two 9 bit values, I used bit 25-17 and bit 9-1: bit 332222 222222111 1 111111 000000000 0 position 109876 543210987 6 543210 987654321 0 000000 xxxxxxxxx 0 000000 yyyyyyyyy 0 If for a position the correct digit is already found (e.g. 2), then x = 000000000 and y = 000000010 If the digit is not found but can only be 1,2,3 or 7, then x = 001000111 and y = 000000000 For example, if we have the following values for the 9 postions: 000000 xxxxxxxxx 0 000000 yyyyyyyyy 0 1: 000000 000000000 0 000000 000000001 0 2: 000000 001100110 0 000000 000000000 0 3: 000000 001100110 0 000000 000000000 0 4: 000000 000000000 0 000000 000010000 0 5: 000000 001100110 0 000000 000000000 0 6: 000000 001001101 0 000000 000000000 0 7: 000000 001100110 0 000000 000000000 0 8: 000000 001100110 0 000000 000000000 0 9: 000000 101100110 0 000000 000000000 0 then we calculate the "add" and "or" of these 9 variables. Then we compare the yyyyyyyyy postion of the "add" and "or" results: if they are not the same, then in at least two varibales the same bit in yyyyyyyyy was set which is illegal. The yyyyyyyyy position of the "or" result give us all digits which are already found and the xxxxxxxxx position of the "or" result give us all digits which can be generated by the not already solved positions. If we or together this both values we must get 111111111 or not all digits can be generated which also would be an error.
From: Terence on 6 Dec 2007 16:57 First, Thanks again Herbert for your explantions. To be fair, I DID realise Herbert's batch file produced a sudo.com file which ITSELF started by converting itself from ascii characters to the real 0-256 binary characters of the machine code. Then this executed the result in memory and read stdin. I wrote him to say so, but these crossed I think. I will try to follow Herbert's algorithm. I think it has to be same as the human method because it also reaches a guessing point. An exhaustive reiteration on oll possibilities would at some point, have to use a cut and reduce technique on intermediate situations, which could theoreticaly use a lot of memory to store later more- complete situations which may or may not be on the route to a solution. I have at least one puzzle with more than one solution. Another case was posted here.
First
|
Prev
|
Pages: 1 2 3 4 5 6 Prev: Links to useful NASM macro's Next: Why is my nasm program killing itself? |