Skip to content

Instantly share code, notes, and snippets.

@vivekannan
Last active August 29, 2015 14:11
Show Gist options
  • Save vivekannan/979a3335f2a2394dcd8c to your computer and use it in GitHub Desktop.
Save vivekannan/979a3335f2a2394dcd8c to your computer and use it in GitHub Desktop.
Solver solves 0hh1 levels.
10
...rr..brb
..b...r.bb
.r....b...
.b.r...b..
r.........
r.....r..r
.rb..r..rr
b..b...r..
.....r...r
.bb..bb...
/**
* A single file name/path should be given as a commmand line argument.
* The first line in the file should represent the size, N, of the board.
* The next N lines should contain N character representation of each row in the
* board. Use the letters 'R' & 'B' to represent tiles and any other character
* to represent empty tiles.
*/
import java.io.FileReader;
import java.io.IOException;
import java.io.BufferedReader;
import java.io.FileNotFoundException;
class Solver {
static int size;
static char[][] board;
/**
* read() reads the board from the given filename and stores it in a character
* array. Exceptions are thrown for various issues.
*
* @param String fileName - name/path of the file to be read from.
* @return void
* @throws FileNotFoundException - given file not found.
* @throws IOException - given file cannot b opened.
* @throws NumberFormatException - given size is not a number.
* @throws Exception - given size is not proper.
* @throws Exception - board dimension is incomplete.
*/
static void read(String fileName) {
try {
String line;
BufferedReader source = new BufferedReader(new FileReader(fileName));
//Parse the first line is file as the size of the board.
Solver.size = Integer.parseInt(source.readLine());
//Ensure that the size is 4, 6, 8, or 10. If not, throw exception.
if(size % 2 != 0 || (size / 2) < 2 || (size / 2) > 5)
throw new Exception(String.format("Board size should be 4, 6, 8 or 10. Given size is %d.", Solver.size));
Solver.board = new char[Solver.size][Solver.size];
for(int i = 0; i < size; i++) {
line = source.readLine();
//Throw exception if EOF or improper row length.
if(line == null || line.length() != Solver.size)
throw new Exception("Incomplete board.");
//Replace all characters other than 'B', 'R', and '.' with '.'.
line = line.toUpperCase().replaceAll("[^BR.]", ".");
Solver.board[i] = line.toCharArray();
}
}
catch(FileNotFoundException e) {
System.out.println("Given file cannot be found.");
System.exit(-1);
}
catch(IOException e) {
System.out.println("Given file cannot be opened.");
System.exit(-2);
}
catch(NumberFormatException e) {
System.out.println("Invalid size.");
System.exit(-3);
}
catch(Exception e) {
System.out.println(e.getMessage());
System.exit(-4);
}
}
/**
* Checks to see if the board if completely filled or not.
*
* @param None
* @return boolean - true if board is NOT filles else false.
*/
static boolean notSolved() {
for(int i = 0; i < Solver.size; i++)
for(int j = 0; j < Solver.size; j++)
if(Solver.board[i][j] == '.')
return true;
return false;
}
/**
* checkRuleOne() solves the board using the first rule.
*
* "Three adjacent tiles of the same color cannot exist horizontally or vertically."
*
* @param None
* @return boolean - true if some solution found else false.
*/
static boolean checkRuleOne() {
int hBlueRed, vBlueRed;
boolean changed = false;
for(int i = 0; i < Solver.size; i++) {
for(int j = 0; j < Solver.size - 2; j++) {
hBlueRed = vBlueRed = 0;
for(int k = j; k < j + 3; k++) {
if(Solver.board[i][k] == 'B')
hBlueRed++;
else if(Solver.board[i][k] == 'R')
hBlueRed--;
if(Solver.board[k][i] == 'B')
vBlueRed++;
else if(Solver.board[k][i] == 'R')
vBlueRed--;
}
for(int k = j; k < j + 3; k++) {
if(hBlueRed == 2 || hBlueRed == -2) {
if(Solver.board[i][k] == '.')
Solver.board[i][k] = (hBlueRed == 2) ? 'R' : 'B';
changed = true;
}
if(vBlueRed == 2 || vBlueRed == -2) {
if(Solver.board[k][i] == '.')
Solver.board[k][i] = (vBlueRed == 2) ? 'R' : 'B';
changed = true;
}
}
}
}
return changed;
}
/**
* tries to apply the second rule by counting the number of red and blue tiles
* in each row and column and fills the row/column accordingly.
*
* "Each row and column should have equal number of red and blue tiles."
*
* @param None
* @return boolean - true if productive else false.
*/
static boolean checkRuleTwo() {
int i;
boolean changed = false;
int hBlue, hRed, vBlue, vRed;
for(i = 0; i < Solver.size; i++) {
hBlue = hRed = vBlue = vRed = 0;
for(int j = 0; j < Solver.size; j++) {
if(Solver.board[i][j] == 'B')
hBlue++;
else if(Solver.board[i][j] == 'R')
hRed++;
if(Solver.board[j][i] == 'B')
vBlue++;
else if(Solver.board[j][i] == 'R')
vRed++;
}
for(int j = 0; j < Solver.size; j++) {
if(Solver.board[i][j] == '.' && (hBlue == Solver.size / 2 || hRed == Solver.size / 2)) {
changed = true;
Solver.board[i][j] = (hBlue == Solver.size / 2) ? 'R' : 'B';
}
if(Solver.board[j][i] == '.' && (vBlue == Solver.size / 2 || vRed == Solver.size / 2)) {
changed = true;
Solver.board[j][i] = (vBlue == Solver.size / 2) ? 'R' : 'B';
}
}
}
return changed;
}
/**
* This methods is used to find rows or columns with specified number of empty
* tiles. This method is a part of the third rule.
*
* @param int start - start looking from row/column
* @param boolean row - look for row if true else column
* @param int count - return if unfilled tiles is equal to count.
* @return int - index of the row or column with the specified conditions,
* or -1 if none,
*/
static int find(int start, boolean row, int count) {
int hCount, vCount;
for(int i = start; i < Solver.size; i++) {
hCount = vCount = 0;
for(int j = 0; j < Solver.size; j++) {
if(row && Solver.board[i][j] == '.')
hCount++;
else if(!row && Solver.board[j][i] == '.')
vCount++;
}
if((row && hCount == count) || (!row && vCount == count))
return i;
}
return -1;
}
/**
* compare() compares the given two rows/columns and tries to apply the
* third rule if they are similar.
*
* @param int filledIndex - index of the filled row/column.
* @param int unfilledIndex - index of the unfilled row/column.
* @param boolean row - rows are compared if true else column.
* @return boolean - true if similar else false.
*/
static boolean compare(int filledIndex, int unfilledIndex, boolean row) {
if(row) {
for(int j = 0; j < Solver.size; j++)
if(Solver.board[unfilledIndex][j] != '.')
if(Solver.board[filledIndex][j] != Solver.board[unfilledIndex][j])
return false;
for(int j = 0; j < Solver.size; j++)
if(Solver.board[unfilledIndex][j] == '.')
Solver.board[unfilledIndex][j] = (Solver.board[filledIndex][j] == 'B' ? 'R' : 'B');
return true;
}
for(int j = 0; j < Solver.size; j++)
if(Solver.board[j][unfilledIndex] != '.')
if(Solver.board[j][filledIndex] != Solver.board[j][unfilledIndex])
return false;
for(int j = 0; j < Solver.size; j++)
if(Solver.board[j][unfilledIndex] == '.')
Solver.board[j][unfilledIndex] = (Solver.board[j][filledIndex] == 'B' ? 'R' : 'B');
return true;
}
/**
* calls the find() and compare() methods for different row/column filled/unfilled
* pairs and tries to apply the third rule.
*
* "No two rows or columns can be similar."
*
* @paran None
* @return boolean - true if productive else false.
*/
static boolean checkRuleThree() {
int filledIndex, unfilledIndex = -1;
while((unfilledIndex = Solver.find(unfilledIndex + 1, true, 2)) != -1) {
filledIndex = -1;
while((filledIndex = Solver.find(filledIndex + 1, true, 0)) != -1)
if(Solver.compare(filledIndex, unfilledIndex, true))
return true;
}
unfilledIndex = -1;
while((unfilledIndex = Solver.find(unfilledIndex + 1, false, 2)) != -1) {
filledIndex = -1;
while((filledIndex = Solver.find(filledIndex + 1, false, 0)) != -1)
if(Solver.compare(filledIndex, unfilledIndex, false))
return true;
}
return false;
}
/**
* solve() repeatedly calls the three rule methods as long as one of them is
* productive. (returns true)
*
* @param None
* @return None
*/
static void solve() {
//Continously applies the three rules as long as one of them is productive.
while(Solver.checkRuleOne() || Solver.checkRuleTwo() || Solver.checkRuleThree());
//If the board is not filled after the loop, it cannot be solved.
if(Solver.notSolved()) {
System.out.println("Board does not have a solution. Bye, Bye....");
System.exit(-5);
}
}
/**
* print() prints the board with proper UNIX terminal color standards.
*
* @paran None
* @returns None
*/
static void print() {
for(int i = 0; i < Solver.size; i++) {
for(int j = 0; j < Solver.size; j++) {
if(Solver.board[i][j] == '.') {
System.out.print(Solver.board[i][j]);
continue;
}
System.out.print("\033[1;" + (Solver.board[i][j] == 'B' ? "34m" : "31m") + Solver.board[i][j] + "\033[0m");
}
System.out.println();
}
}
public static void main(String[] args) {
if(args.length == 0) {
System.out.println("Program expects a file containing the board to be solved.");
System.exit(0);
}
Solver.read(args[0]);
Solver.solve();
Solver.print();
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment