|
Hi folks, I've written a program which solves lights off game for every position when I got frustrated not being able to solve some simple positions. here's the code, feel free to use, change, share, etc: /* * Copyright (C) Perham 2011 <perham x gmail com> * * LightsOffSolver is free software: you can redistribute it and/or modify it * under the terms of the GNU General Public License as published by the * Free Software Foundation, either version 3 of the License, or * (at your option) any later version. * * LightsOffSolver is distributed in the hope that it will be useful, but * WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. * See the GNU General Public License for more details. * * You should have received a copy of the GNU General Public License along * with this program. If not, see <http://www.gnu.org/licenses/>. */ #include <vector> #include <iostream> #include <fstream> using namespace std; int negative (int input_board, int square) { return input_board ^ (1 << square); } int setbit (int input_board, int square, int bit) { if ((input_board >> square) % 2 == bit) return input_board; else return negative (input_board, square); } int copybit (int input_board, int in_pos, int output_board, int out_pos) { return setbit (output_board, out_pos, (input_board >> in_pos) % 2); } int rotate_move (int move, int degree) { if (degree == 90) return 20 - ((move % 5) * 5) + (move / 5); else if (degree == 180) return (24 - move); else if (degree == 270) return 4 + ((move % 5) * 5) - (move / 5); return -1; } int rotate_board (int input_board, int degree) { int output_board = 0, i; for (i = 0; i < 25; i++) output_board = copybit (input_board, i, output_board, rotate_move (i, degree)); return output_board; } int generate (int input_board, int move) { if (move > 5 && move < 19 && move % 5 != 0 && move % 5 != 4) return negative (negative (negative (negative (negative (input_board, move), move + 5), move - 5), move + 1), move - 1); if (move > 0 && move < 4) return negative (negative (negative (negative (input_board, move), move + 5), move - 1), move + 1); if (move > 20 && move < 24) return negative (negative (negative (negative (input_board, move), move - 5), move - 1), move + 1); if (move == 5 || move == 10 || move == 15) return negative (negative (negative (negative (input_board, move), move + 5), move + 1), move - 5); if (move == 9 || move == 14 || move == 19) return negative (negative (negative (negative (input_board, move), move + 5), move - 1), move - 5); if (move == 0) return negative (negative (negative (input_board, 0), 1), 6); if (move == 4) return negative (negative (negative (input_board, 4), 3), 9); if (move == 20) return negative (negative (negative (input_board, 20), 21), 15); if (move == 24) return negative (negative (negative (input_board, 24), 19), 23); } void print (int input_board) { int tmp, i; for (i = 0; i < 5; i++) { tmp = (input_board >> (5 * i)) % 32; cout << "\n" << (int) tmp % 2 << (int) (tmp % 4) / 2 << (int) (tmp % 8) / 4 << (int) (tmp % 16) / 8 << (int) tmp / 16; } cout << "\n"; } class queue { public: vector < int >q; void add (int n) { q.push_back (n); } int remove (void) { int tmp; tmp = q.at (0); q.erase (q.begin ()); return tmp; } int check (int n) { int i; for (i = 0; i < q.size (); i++) if (q.at (i) == n) return 1; return 0; } int size (void) { return q.size (); } queue () { q.reserve (3000000); q.assign (1, 0); } }; int main () { cout << "\ninitializing..."; cout.flush (); int i, j, s, flag = 0, tmp1, tmp2, tmp1r1, tmp1r2, tmp1r3, tmp2r1, tmp2r2, tmp2r3; vector < char >mark (33554432, 0); fstream filestr; vector < vector < char > >tree; tree.resize (33554432); j = 0; mark[0] = 1; queue Q; cout << " done.\n"; cout.flush (); while (s) { tmp2 = Q.remove (); cout << "\rqueue: " << s <<" "; tmp2r1 = rotate_board (tmp2, 90); tmp2r2 = rotate_board (tmp2, 180); tmp2r3 = rotate_board (tmp2r2, 90); for (i = 0; i < 25; i++) { tmp1 = generate (tmp2, i); tmp1r1 = rotate_board (tmp1, 90); tmp1r2 = rotate_board (tmp1, 180); tmp1r3 = rotate_board (tmp1r2, 90); if (mark.at (tmp1) == 0) { Q.add (tmp1); mark[tmp1] = 1; tree[tmp1].assign (tree[tmp2].begin (), tree[tmp2].end ()); tree[tmp1].push_back (i); if (!(tmp1r1 == tmp1 || tmp1r2 == tmp1 || tmp1r3 == tmp1)) { mark[tmp1r1] = 1; mark[tmp1r2] = 1; mark[tmp1r3] = 1; tree[tmp1r1].assign (tree[tmp2r1].begin (), tree[tmp2r1].end ()); tree[tmp1r1].push_back (rotate_move (i, 90)); tree[tmp1r2].assign (tree[tmp2r2].begin (), tree[tmp2r2].end ()); tree[tmp1r2].push_back (rotate_move (i, 180)); tree[tmp1r3].assign (tree[tmp2r3].begin (), tree[tmp2r3].end ()); tree[tmp1r3].push_back (rotate_move (i, 270)); } } } s = Q.size (); } cout << "\nwriting to output...\n"; cout.flush (); filestr.open ("output.txt", fstream::out); for (i = 0; i < 33554432; i++) { cout << "\r " << i; filestr << "\n" << i << ": "; for (j = 0; j < tree[i].size (); j++) filestr << " " << (int) tree[i].at (j) << " ;"; filestr << "*"; } filestr.close (); return 0; } |